K-Dimensional Grids

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Neo was bored of always living in three-dimensional space. In order to cope with his boredom, he learned how to lucid dream, where he was be able to recreate his own world with K-dimensions and conveniently place himself in any corner of his world. His world can be imagined as a K-dimensional grid where each dimension is located on a unique plane with a grid size of length l_i. The drawback of Neo's dream world is that when he wakes up, he forgets most of the properties he used in order to create the world.

He is only able to remember W, the number of different shortest paths there are from his starting corner to the furthest point of his starting corner, within his K-dimensional grid, and a list of N numbers, (l_1, l_2, \dots, l_N), which are possible side lengths he chose for each dimensions' grid length. A single value of l_i may only correspond to the length of 1 dimensions' grid size.

Can you help Neo determine K, the dimension of the world he created and l_1, \dots, l_N, the length of each grid size.

Note: Neo will not create a world less than 2 dimensions.


For all subtasks, (0 \le W < 10^9 + 7), K \le N and (2 \le l_i \le 10).

Subtask 1 [10%]

K = 2

2 \le N \le 5

Subtask 2 [20%]

K = 3

2 \le N \le 10

Subtask 3 [70%]

2 \le N \le 20


First line: W, the number of different shortest paths from the corner located at the origin to its opposite corner modulo 10^9 + 7.

Second line: N, the number of possible side lengths to construct the K-dimensional grid.

Third line: N space-separated integers, l_1, l_2, \dots, l_N, the list of possible side lengths.


On the first line, print K, the dimension of the world.

On the second line, print K numbers in non-decreasing order, the lengths of each side.

If there is no solution print -1, otherwise it is guaranteed that there is only 1 solution.

Sample Input 1

2 3 2

Sample Output 1

2 2

Explanation for Sample Output 1

A 2-dimensional grid of length 2 \cdot 2 will create a grid that has 6 different paths

The 6 different paths are (where R is right and D is down) :

  • R, R, D, D
  • R, D, R, D
  • R, D, D, R
  • D, R, R, D
  • D, R, D, R
  • D, D, R, R


There are no comments at the moment.