Cerinta completa
Daniel loves graphs. He thinks a graph is special if it has the following properties:
- It is undirected.
- The length of each edge is .
- It includes exactly different lovely triplets.
A triplet is a set of different nodes. A triplet is lovely if the minimum distance between each pair of nodes in the triplet is exactly . Two triplets are different if or more of their component nodes are different.
Given and , help Daniel draw a special graph.
Input Format
A single line containing space-separated integers, (the number of different lovely triplets you must have in your graph) and (the required distance between each pair of nodes in a lovely triplet), respectively.
Constraints
Output Format
For the first line, print space-separated integers, (the number of nodes in the graph) and (the number of edges in the graph), respectively.
On each line of the subsequent lines, print two space-separated integers, and , describing an edge between nodes and .
Your output must satisfy the following conditions:
If there is more than one correct answer, print any one of them.
Sample Input
3 2
Sample Output
7 7
1 2
2 3
3 4
4 5
5 6
6 1
1 7
Explanation
There are exactly lovely triplets in this graph: , , and .
Observe that each node in a lovely triplet is edges away from the other nodes composing the lovely triplet.
Limbajul de programare folosit: cpp14
Cod:
/* nice editorial !! */
#include <bits/stdc++.h>
//#define debug
#define fie(i,start,stop) for ( int i = start ; i < stop ; i ++ )
#define f first
#define s second
#define pii pair < int , int >
#define vpii vector < pii >
#define vi vector < int >
#define pb push_back
#define mp make_pair
using namespace std ;
vpii nc3 ;
vi x ( 5001 , INT_MAX ) ;
vi y ( 5001 , INT_MAX ) ;
vi z ( 5001 , INT_MAX ) ;
vpii dp ( 5001 , mp ( INT_MAX , INT_MAX ) ) ;
int nc3_size = 0 ;
int p , d , n = 0 , m = 0 ;
vpii edges ( 100 ) ;
int l , mid , r ;
void build_even ()
{
#ifdef debug
cout << "building even" << endl ;
#endif
int root = n + 1 ;
int nodes = ( d - 2 ) / 2 ;
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + 2 ;
fie ( i , 0 , nodes - 1 )
{
edges [ m ].f = n + i + 2 ;
edges [ m ++ ].s = n + i + 3 ;
}
n += nodes + 1 ;
l = n ;
edges [ m ].f = root ;
edges [ m ++ ].s = n + 1 ;
fie ( i , 0 , nodes - 1 )
{
edges [ m ].f = n + i + 1 ;
edges [ m ++ ].s = n + i + 2 ;
}
n += nodes ;
mid = n ;
edges [ m ].f = root ;
edges [ m ++ ].s = n + 1 ;
fie ( i , 0 , nodes - 1 )
{
edges [ m ].f = n + i + 1 ;
edges [ m ++ ].s = n + i + 2 ;
}
n += nodes ;
r = n ;
}
void build_odd ()
{
#ifdef debug
cout << "building odd" << endl ;
#endif
if ( d == 3 )
{
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + 2 ;
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + 3 ;
edges [ m ].f = n + 2 ;
edges [ m ++ ].s = n + 3 ;
l = n + 1 ;
mid = n + 2 ;
r = n + 3 ;
n += 3 ;
return ;
}
int nodes = ( d - 3 ) / 2 ;
int root1 = n + 1 ;
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + 2 ;
fie ( i , 0 , nodes - 1 )
{
edges [ m ].f = n + i + 2 ;
edges [ m ++ ].s = n + i + 3 ;
}
n += nodes + 1 ;
l = n ;
int root2 = n + 1 ;
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + 2 ;
fie ( i , 0 , nodes - 1 )
{
edges [ m ].f = n + i + 2 ;
edges [ m ++ ].s = n + i + 3 ;
}
n += nodes + 1 ;
mid = n ;
int root3 = n + 1 ;
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + 2 ;
fie ( i , 0 , nodes - 1 )
{
edges [ m ].f = n + i + 2 ;
edges [ m ++ ].s = n + i + 3 ;
}
n += nodes + 1 ;
r = n ;
edges [ m ].f = root1 ;
edges [ m ++ ].s = root2 ;
edges [ m ].f = root1 ;
edges [ m ++ ].s = root3 ;
edges [ m ].f = root2 ;
edges [ m ++ ].s = root3 ;
}
void add_edge ( int no_l , int no_mid , int no_r )
{
#ifdef debug
cout << "adding edge " << no_l << " " << no_mid << " " << no_r << endl ;
#endif
if ( d % 2 )
{
build_odd () ;
}
else
{
build_even () ;
}
fie ( i , 0 , no_l )
{
edges [ m ].f = l ;
edges [ m ++ ].s = n + i + 1 ;
}
n += no_l ;
fie ( i , 0 , no_mid )
{
edges [ m ].f = mid ;
edges [ m ++ ].s = n + i + 1 ;
}
n += no_mid ;
fie ( i , 0 , no_r )
{
edges [ m ].f = r ;
edges [ m ++ ].s = n + i + 1 ;
}
n += no_r ;
}
void solve ()
{
while ( p )
{
#ifdef debug
cout << "component of size " << dp [ p ].f << endl ;
#endif
add_edge ( x [ dp [ p ].f ] , y [ dp [ p ].f ] , z [ dp [ p ].f ] ) ;
p -= dp [ p ].f ;
}
}
void add_edge2 ( int no_of_nodes )
{
#ifdef debug
cout << "adding edge for dist 2 " << no_of_nodes << endl ;
#endif
fie ( i , 0 , no_of_nodes )
{
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + i + 2 ;
}
n += no_of_nodes + 1 ;
}
void solve2 ()
{
int idx = nc3_size - 1 ;
while ( p )
{
if ( nc3 [ idx ].f <= p )
{
add_edge2 ( nc3 [ idx ].s ) ;
p -= nc3 [ idx ].f ;
}
else
{
idx -- ;
}
}
}
void precal ()
{
fie ( i , 1 , 100 )
{
fie ( j , i , 100 )
{
if ( i * j > 5000 || i + j > 93 )
{
break ;
}
fie ( k , j , 100 )
{
if ( i * j * k > 5000 || i + j + k > 94 )
{
break ;
}
int mul = i * j * k ;
if ( x [ mul ] == INT_MAX || ( ( x [ mul ] + y [ mul ] + z [ mul ] ) > ( i + j + k ) ) )
{
x [ mul ] = i ;
y [ mul ] = j ;
z [ mul ] = k ;
}
}
}
}
fie ( i , 0 , 5001 )
{
fie ( j , 1 , 5001 )
{
if ( i + j <= 5000 && x [ j ] != INT_MAX && ( dp [ i + j ].s > dp [ i ].s + x [ j ] + y [ j ] + z [ j ] ) )
{
dp [ i + j ].f = j ;
dp [ i + j ].s = dp [ i ].s + x [ j ] + y [ j ] + z [ j ] ;
}
}
}
int no = 3 ;
while ( true )
{
int prod = no * ( no - 1 ) * ( no - 2 ) ;
prod /= 6 ;
if ( prod <= 5000 )
{
nc3.pb ( mp ( prod , no ++ ) ) ;
#ifdef debug
//cout << "nc3 " << no - 1 << " " << prod << endl ;
#endif
}
else
{
break ;
}
}
nc3_size = nc3.size () ;
}
int main ()
{
precal () ;
cin >> p >> d ;
if ( d == 2 )
{
solve2 () ;
}
else
{
solve () ;
}
cout << n << " " << m << endl ;
fie ( i , 0 , m )
{
cout << edges [ i ].f << " " << edges [ i ].s << endl ;
}
return 0 ;
}
Scor obtinut: 1.0
Submission ID: 464650213
Link challenge: https://www.hackerrank.com/challenges/lovely-triplets/problem