Cerinta completa

We define the diameter of a strongly-connected oriented graph, , as the minimum integer such that for each there is a path from to of length (recall that a path’s length is its number of edges).

Given two integers, and , build a strongly-connected oriented graph with vertices where each vertex has outdegree and the graph’s diameter is as small as possible (see the Scoring section below for more detail). Then print the graph according to the Output Format specified below.

Here’s a sample strongly-connected oriented graph with nodes, whose outdegree is and diameter is .

image

Note: Cycles and multiple edges between vertices are allowed.

Input Format

Two space-separated integers describing the respective values of (the number of vertices) and (the outdegree of each vertex).

Constraints

Scoring

We denote the diameter of your graph as and the diameter of the graph in the author’s solution as . Your score for each test case (as a real number from to ) is:

  • if
  • if
  • if

Output Format

First, print an integer denoting the diameter of your graph on a new line.
Next, print lines where each line () contains space-separated integers in the inclusive range from to describing the endpoints for each of vertex ‘s outbound edges.

Sample Input 0

5 2

Sample Output 0

2
1 4
2 0
3 1
4 2
0 3

Explanation 0

The diagram below depicts a strongly-connected oriented graph with nodes where each node has an outdegree of :

The diameter of this graph is , which is minimal as the outdegree of each node must be . We cannot construct a graph with a smaller diameter of because it requires an outbound edge from each vertex to each other vertex in the graph (so the outdegree of that graph would be ).

Limbajul de programare folosit: cpp14

Cod:

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

int calcBest(int n, int m) {
    int d = 0;
    int onD = 1;
    int cn = 1;
    while (cn < n) {
        onD *= m;
        ++d;
        cn += onD;
    }
    return d;
}

const int maxn = 1005;
int g[maxn][maxn];
int n, m;

int dist[maxn];
int calcDiam(int s) {
    fill(dist, dist + n, inf);

    vector<int> q;
    dist[s] = 0;
    q.push_back(s);
    forn (ii, sz(q)) {
        int u = q[ii];
        forn (i, m) {
            int v = g[u][i];
            if (dist[v] < inf)
                continue;
            dist[v] = dist[u] + 1;
            q.push_back(v);
        }
    }

    if (sz(q) < n)
        return inf;
    return dist[q.back()];
}

int main() {
    cin >> n >> m;
    forn (i, n) {
        forn (j, m)
            g[i][j] = (i * m + j) % n;
    }
    int diam = 0;
    forn (i, n)
        diam = max(diam, calcDiam(i));
    int best = calcBest(n, m);
    //cerr << "best " << best << '\n';
    assert(diam <= best + 1);
    assert(diam >= best);

    cout << diam << '\n';
    forn (i, n) {
        forn (j, m)
            cout << g[i][j] << ' ';
        cout << '\n';
    }
}

Scor obtinut: 1.0

Submission ID: 464650161

Link challenge: https://www.hackerrank.com/challenges/diameter-minimization/problem

Diameter Minimization