Ok I understand now...It means in blue-red land you can either grab mana from blue or red.

Edited by author 11.09.2020 20:18

Edited by author 12.09.2020 17:07

Edited by author 12.09.2020 17:08

Hm. Seems there are no tests with small number of linear independent rows.
I have two solutions with different answers to such tests, but both got OK.

Admins, please, add some.

30 30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
...
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2

30 30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
x20

30 30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0
x10

1. Stations may not all be connected. You may have to walk on foot between stations.
2. A and B may be one of the stations or may even be the same point. Maybe the best route is from A to B is on foot without using any stations. Consider all cases.
3. Coordinates are floating points, not integer.
4. Simple dijsktra will work.
5. Use a map to store the node number of the points. If A or B are not one of the stations then give them n and n+1 or n+1 and n+2 (depending on indexing).

It is said "Tags: dynamic programming"

But also there is math approach. In this case solution is simple math formula kind of \sum\sum C(x,y)*C(t,m). Complexity is O(n^2).

Good luck.

Test 1:
3
1 2 3

Answer 1:
1
3 1 2 3

Test 2:
3
1 3 3

Answer 2:
2
1 1
3 1 2 3

P.S. Statement is not understandable :(

Edited by author 28.12.2012 14:24

This question can be solved using the same logic in 1167(Bicolored horses), but it will give tle.

There can be multiple edges. For instance:
1 2
2 1

Using a set will give WA. Try multi-set or some other data structure in c++.

Edited by author 07.09.2020 15:22

Edited by author 07.09.2020 15:22

WA8
Please, explain, what is the reason? Is this just a problem of input/output or this is just such test case?

Let c[i][0] = a[i], i = 1..n
    c[i][1] = c[i+1][0] - c[i][0], i = 1..n-1
    c[i][2] = c[i+1][1] - c[i][1], i = 1..n-2
     ....
    c[i][d] = c[i+1][d-1] - c[i][d-1], i = 1..n-d.

   if hardness of a[i]  is d.  so all c[i][d] = const.

    1. Find minimum d, that  all c[i][d] - is const.  (example:  binary search).
    2. build b[n+i] from c[i][d].


There can calculate c[i][j] through a[i] sequences:

    c[i][1] = a[i+1] - a[i]
    c[i][2] = c[i+1][1] - c[i][1] = (a[i+2] - a[i+1]) - (a[i+1] - a[i]) = a[i+2] - a[i+1] - a[i+1] + a[i] = a[i+2] - 2*a[i+1] + a[i].

   c[i][3] = c[i+1][2] - c[i][2] = (a[i+3] - 2*a[i+2] + a[i+1]) - (a[i+2] - 2*a[i+1] + a[i]) = a[i+3] - 3* a[i+2] + 3*a[i+1] - a[i].

   ..
   c[i][d] = SUM( c[i + d - j ] * Binom(d, j) * (-1)^j, j = 0..d)

    where Binom(d, j) - Binominal coefficients , or  coefficients of (x+y)^d .

  if d - is known,

   c[1][d] = c[2][d] = ... = c[n-d][d] = W - constanta.

  b[n+1] = x

   c[n-d+1] = b[n+1] + SUM(a[n + 1- j] * binom(d,j)*(-1)^j, j = 1..d)  = W

   b[n+1] = W - SUM(a[n+1-j] * binom(d,j)*(-1)^j, j = 1..d)

   and so on.


  Only one problem,  how fastest calculate SUM(a[i + d - j] * binom(d,j)(-1)^j, j = 1..d)   ?

You might want to study this article: https://www.elcamino.edu/faculty/gfry/210/DistributeDifBallsDifBoxes.pdf

Please, give me test 18

Pigeonhole principle: It will always be possible and the answer will always be a continuous sequence.
How to solve:
Consider N = 7:
1 2 50 3 4 0 0
The sum of the segment 1, 2, 50 is 53 and that of 1,2,50,3,4 is 60
53 % 7 = 4
60 % 7 = 4
if a % x = 1
and b % x =1
then (a-b)%x is always 0
So the segment between those two prefix sums will give 0 as modulo which is (3,4) = 7

this

3 1
1000 90
1000 90
1000 90
2 5

helps me

I've noticed that the solution is always the number of walls we encounter*9 (excluding the first and last boxes). Why is this working?

If you pick n-1 as l then the second player will always win, so answer can never be 0
0 means  picked up the first player and 1 means picked up the second;
Case 1: 3 buttons
for i = 1 //doesn't make sense to solve for 1 since its asked to choose >=2
1 2 3
0 1 0 //first player won
for i = 2
1 2 3
0 0 1
0 1 1 // first play wins in each case
Case 2: 4 buttons
for i = 2
1 2 3 4
0 1 1 0
0 1 0 0 //first player wins in both these cases
for i = 3:
1 2 3 4
0 0 0 1
0 1 1 1
0 0 1 1 //second player wins in each case
case 3: 6 buttons (5 and 6 are similar)
1 2 3 4 5 6
for i = 2
0 1 1 0 0 1
0 0 1 0 0 1
0 1 1 0 1 1 //second player is  winning

It's clearly seen that the minimal choice to win is k such that n %(k+1) == 0
since n%((n-1)+1) is always 0, n-1 is always an answer in case no smaller answer exists.

import itertools
surprize =[]
x = int(input())
while x > 1:
    x -= 1
    surprize.append(x)
print (len(list(itertools.permutations (surprize))))

It's very easy to calculate this integral. But if you don't know what's integral, there are solution

In-first, i calculated a k
k = (a^2 * b * pi / 8) (or a*a*b*0.39269908169872415480783042290994 :) )
In-second, you should calculate y (or other symbol) from 1 to -1 with division (if n = 5: 1, 3/5, 1/5, -1/5, -3/5, -1)
In-third, calculate F(y) = y*(1 - y^2 / 3). (F(1) = 2/3)
in-fourth, print k*(F(yi) - F(y(i-1))) in loop
example:
if n = 2: first calculate should be k*(F(1) - F(0)), second k*(F(0) - F(-1))
if n = 3: 1) k*(F(1) - F(1/3)); 2) k*(F(1/3) - F(-1/3)); 3) k*(F(-1/3) - F(1))
etc.

[code deleted]

Edited by moderator 02.09.2020 19:58

If you want to get AC for a Kotlin solution, you should probably use java.util.Scanner instead of readLine() and try multiple times. I was able to get AC only on the second try with the same code, got TLE first time.