Блог пользователя weily

Автор weily, история, 6 месяцев назад, По-английски

In last night's contest, I didn't come up with the correct solution to problem C. I used many large integers, instead of the least common multiple. But it really worked!

264483249

Can anyone hack it?

English is not my native language; please excuse typing errors.

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by weily (previous revision, new revision, compare).

»
6 месяцев назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Your solution is correct. Clearly your solution never prints a solution when there is none, so the only interesting question is whether your solution ever prints $$$-1$$$ when a solution exists.

As mentioned in the editorial, there is a solution if and only if $$$\sum_{i = 1}^n \frac{1}{k_i} < 1$$$. There are only 24269653 such arrays under the constraints of the problem ($$$k_i \le 20$$$). I simply ran your program on all those arrays and found no countertest. So it seems that trying 200 values is sufficient under the constraints of this problem.