3926 - Counting Paths

Created by Marcelo Fornet Fornés
Added by MarX (2017-07-06)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

In the city outskirts, Charlie is building a new theme park, which he plans to open next summer. The greatest attractions in the park will be a roller coaster and a maze. Construction of the roller coaster is almost complete, so it will be ready on time by summer. However, the maze is still in the design stage and Charlie asks for your help to complete it. He knows that many children will attend the new park once it opens, so he wants to create the most impressive maze ever seen.

The maze consists of junctions and corridors connecting the junctions. There are two special junctions designated as the start and end of the maze. Each child will traverse the maze from the start to the end, using the minimal number of corridors. Charlie wishes that each child that goes through the maze experience it differently than any other child (so each child has a different story to tell to others after completing the maze). To do so, he will have each child go through a different path, but he figured he would need many paths in his maze.

Since Charlie has predicted that exactly K children will attend the theme park in the first day, you need to design a new maze that has exactly K minimal paths from the start junction to the end junction. Charlie is not as rich as you may believe, so you can only use at most 500 junctions and 500 corridors connecting the junctions. Since different corridors will have different interesting items in their interior, Charlie does not mind having two or more corridors connecting the same pair of junctions.

More formally:
  • A path is a sequence of junctions such that two consecutive junctions are connected with a corridor.
  • A path is minimal if among all the paths that go from one junction to another, it goes through the minimum number of junctions.
  • A minimal path P1 is different from another minimal path P2 if there exists a corridor in P1 that does not exist in P2 or vice versa.
  • Corridors are undirected: if a corridor connects junction A with junction B, it can be traversed in both directions.
En las afueras de la ciudad, Charlie está construyendo un nuevo parque temático, cuya apertura está planificada para el próximo verano. Las dos grandes atracciones en el parque serán una montaña rusa y un laberinto. La construcción de la montaña rusa está casi terminada, de manera que estará lista para el próximo verano.  Por otro lado, el laberinto aún está en la fase de diseño, por lo que Charlie te pide que le ayude a completarlo. Él sabe que muchos niños asistirán al parque una vez que se inaugure y, por tal razón, él desea crear el laberinto más impresionante jamás visto.

El laberinto consiste de intersecciones y pasadizos conectando las intersecciones. Dos intersecciones especiales son designadas como el inicio y fin del laberinto. Cada niño recorre el laberinto desde la intersección inicial hasta la final, usando la mínima cantidad de pasadizos posibles. Charlie desea que cada niño se lleve un recuerdo distinto al de cualquier otro niño que complete el recorrido del laberinto (para que tenga una historia distinta que contar a los demás).  Para lograr este objetivo, Charlie asignará una ruta distinta a cada niño, pero se dio cuenta que su laberinto necesita contener muchas rutas posibles.

Como Charlie predice que exactamente K niños asistirán al parque en el día de apertura, él te pide que diseñes un laberinto que contenga exactamente K rutas de longitud mínima que van de la intersección inicial hasta la intersección final. Charlie no es tan rico como creías, por lo cual solo se te permite tener a lo sumo 500 intersecciones y 500 pasadizos conectando las intersecciones. Como distintos pasadizos contiene diferentes artículos de interés, en su interior, Charlie no le importa si dos o más pasadizos conectan la misma pareja de intersecciones.

Mas formalmente:
  • Una ruta es una secuencia de intersecciones donde dos intersecciones consecutivas en la secuencia están conectadas por un pasadizo.
  • Una ruta se considera mínima si, entre todas las rutas que van desde una intersección a otra, esta atraviesa la mínima cantidad de intersecciones.
  • Una ruta mínima P1 se considera distinta a otra ruta mínima P2 si existe un pasadizo en P1 que no existe en P2 o viceversa.
  • Los pasadizos no tienen orientación: si un pasadizo conecta las intersecciones A y B, este puede ser cruzado en cualquiera de las dos direcciones.
;jsessionid=8FE4B52705FB3D04735DDD874CA032D0
In the city outskirts, Charlie is building a new theme park, which he plans to open next summer. The greatest attractions in the park will be a roller coaster and a maze. Construction of the roller coaster is almost complete, so it will be ready on time by summer. However, the maze is still in the design stage and Charlie asks for your help to complete it. He knows that many children will attend the new park once it opens, so he wants to create the most impressive maze ever seen.

The maze consists of junctions and corridors connecting the junctions. There are two special junctions designated as the start and end of the maze. Each child will traverse the maze from the start to the end, using the minimal number of corridors. Charlie wishes that each child that goes through the maze experience it differently than any other child (so each child has a different story to tell to others after completing the maze). To do so, he will have each child go through a different path, but he figured he would need many paths in his maze.

Since Charlie has predicted that exactly K children will attend the theme park in the first day, you need to design a new maze that has exactly K minimal paths from the start junction to the end junction. Charlie is not as rich as you may believe, so you can only use at most 500 junctions and 500 corridors connecting the junctions. Since different corridors will have different interesting items in their interior, Charlie does not mind having two or more corridors connecting the same pair of junctions.

More formally:
  • A path is a sequence of junctions such that two consecutive junctions are connected with a corridor.
  • A path is minimal if among all the paths that go from one junction to another, it goes through the minimum number of junctions.
  • A minimal path P1 is different from another minimal path P2 if there exists a corridor in P1 that does not exist in P2 or vice versa.
  • Corridors are undirected: if a corridor connects junction A with junction B, it can be traversed in both directions.

Input specification

A single line with an integer K (1 ≤ K ≤ 1018) is given. It represents the number of children attending the park in the first day and, thus, the exact number of minimal paths the maze must contain from the start junction to the end junction.
La entrada contiene una sola línea con el número entero K (1 ≤ K ≤ 1018). Este número representa la cantidad de niños que Charlie predice asistirán al parque en el día inaugural y, en consecuencia, también representa la cantidad exacta de rutas mínimas desde inicio a fin que el laberinto debe contener.
A single line with an integer K (1 ≤ K ≤ 1018) is given. It represents the number of children attending the park in the first day and, thus, the exact number of minimal paths the maze must contain from the start junction to the end junction.

Output specification

In the first line, print two integers N and M (2 ≤ N ≤ 500, 1 ≤ M ≤ 500), which represent the number of junctions and corridors in the maze respectively.

In the second line, print two different integers S and T (1 ≤ S, T ≤ N, ST) such that S represents the junction where the maze starts and T is where it ends.

In each of the next M lines, print two integers U and V (1 ≤ U, VN) representing one corridor connecting junctions U and V.

The final maze must have exactly K paths of minimal lengths from S to T. Of course, this implicitly means that T must be reachable from S.

It is guaranteed that a solution exists given the constraints.
En la primera línea, imprime dos números enteros  N y M (2 ≤ N ≤ 500, 1 ≤ M ≤ 500), los cuales representan la cantidad de intersecciones y pasadizos en el laberinto a construir.

En la segunda línea, imprime dos números enteros S y T (1 ≤ S, T ≤ N, ST) donde S representa la intersección inicial donde el laberinto empieza y T es la intersección donde termina.

En cada una de las siguientes M líneas, imprime dos números enteros U y V (1 ≤ U, VN) representando un pasadizo conectando las intersecciones U y V.

El laberinto final debe contener exactamente K rutas mínimas que empieza en S y termina en T. Obviamente, esto implica que T debe ser alcanzable desde S.

Se garantiza de que existe una solución bajo las restricciones presentadas.
A single line with an integer K (1 ≤ K ≤ 1018) is given. It represents the number of children attending the park in the first day and, thus, the exact number of minimal paths the maze must contain from the start junction to the end junction.

Sample input

10

Sample output

4 9
1 3
1 2
1 2
1 4
2 3
2 3
2 3
2 3
3 4
3 4

Hint(s)