I had. You must add in your programm something like this:

 if(sum/9>2*n){
  printf("0");
  return 0;
 }

Thanks for this testset, helped me find the bug :)

The same, in a more reusable format:

18
1000000000
999999000
999000999
405
101
1001
10001
100001
1000001
10000001
100000001
555555555
191919191
838383838
123456789
987654321
987654319
101010101

71 999999929
19 999998981
3 5 999000991
3 5 397
101
3 7 991
3 31 9967
3 7 99991
3 19 999979
3 7 9999991
3 67 99999931
3 11 555555541
3 61 191919127
59 838383779
3 29 123456757
2 987654319
987654319
3 19 101010079

How to solve problem without long arithmetics?

The main idea of this test following in sorting relative fees instead of absolute fees.

Simple example:
2 1
10 10 1 1
999990 1
100 1

The first package has huge absolute value of fees ((999999 - 10) * 1), but it adds only 9 credits to the initial fees.

Edited by author 18.06.2022 20:06

You only need to write about 3 lines of python code to solve this.

try:
  help(str.split)
  help(reversed)
  help(str.join)

Thank you!

But how to prove that we can make such competition where k is the smallest value and we have (n - 1) values that are not less?

Edited by author 08.06.2022 21:21

you need to be in control. you are in control when you keep the first player in "loop". if you take number of buttons is 6, say, then the "loop" length is 3, i.e. if you take max number of buttons as 3 - 1 = 2, then whatever amount the first player takes you can keep them in loop. if they take first time 1, you take 2 - in sum 3, 3 - remaining, you are a winner. if they take 2 - you take 1, 3 remaining again - you are a winner.
so, idea is to find the smallest divisor of a number > 2 & answer will be that - 1. hope that makes sense.

Edited by author 18.01.2019 19:50

WLOG, let's break `k` elements of heap into block of length `d`. The numbers below are listed from 1, ..., k in their congruent modulo of `d`.
[1, 2, ...., (d - 1), d], [1, 2, ...., (d - 1), d], ......(k / d) blocks. Here [..] is a block notation. B = #blocks of length `d` = (k / d)

Basis: If B = 1, it's always true, as `first player` can pick whatever from 1, ..., (d - 1), `second player` always left with atleast 1 element by less then d to be picked. So `second player` player will greedily pick all remaining element in the block as an optimal move for his/her winning.

Hypothesis: Let say it's true upto (B - 1) blocks that `second player` has taken the last element.

Proof:
If we have B block then since it is true for (B - 1) blocks we left with 1 block of element to pick and since `first player` is the who pick first in the last 1 block by using the `basis` we know that `second player` is always the winner. Hence, if we take the divisor of number of elements in the heap (k) we always end of with `second player` being the winner.

Edited by author 07.06.2022 10:23

Edited by author 07.06.2022 10:23

ab@ab@ab
4

aa@ab.c
aa@as.a
aa@abs.l
14

Same problem here. .-."