Just drawing different patterns on paper for several hours and the solution will come!

My solutions in the two languages produce the same output on my tests. However, the Go version gets WA1. Please fix this.

Give me this test

Edited by author 25.10.2017 18:58

Edited by author 25.10.2017 07:16

...

Edited by author 25.10.2017 12:47

n > k in 2nd test

The following code:

cin>>n;
for(i=1;i<=n;i++) {
  cin>>x[i]>>y[i];
  assert(x[i]>=1 && x[i]<=10 && y[i]>=1 && y[i]<=10);
  here[x[i]][y[i]]=true;
}

gives RTE, so test 2 is wrong. After, removing the assert, it gives WA :)

Hello. Task number is 2023.
Timus flatly refuses to accept. He had a lot of tests, but he did not find any flaws. Maybe someone will tell me, otherwise I'll kill myself tomorrow.

n = int(input())
zn = [1]
k=0
y = 0
sh1 = ('Alice', 'Ariel', 'Aurora', 'Phil', 'Peter', 'Olaf', 'Phoebus', 'Ralf', 'Robin')
sh2 = ('Bambi', 'Belle', 'Bolt', 'Mulan', 'Mowgli', 'Mickey', 'Silver', 'Simba', 'Stitch')
for j in range (n):
    i = input()
    if i in sh1:
        zn.append (1)
    elif i in sh2:
        zn.append (2)
    else:
        zn.append (3)
    n-=1
for k in range (len(zn)):
    y+= abs ((int(zn [k-1]))-int(zn [k]))
lop = y-zn[-1]+1
print (lop)

Finally ACed by changing to a direct approch.
But I still don't understand what's wrong with my previous algo(which results to WA5)
It's something like this:

For example, for such a input:
4  6
1  1  2  3  3  7
4  5  2  6  6  7
4  5  8  9  12  11
10 10 8  9  12  11

1.Construct a n*m graph G, every vertices connected with all it's neighbors(up, down, left, right)
(for layout reasons here I use hex to number the vertices)

(the graph left is only a illustration to explain the things happening to the former graph.
the graph right shows the result we get in every stage.)
1-1-2-3-3-7        o-o-o-o-o-o
| | | | | |        | | | | | |
4-5-2-6-6-7        o-o-o-o-o-o
| | | | | |        | | | | | |
4-5-8-9-C-B        o-o-o-o-o-o
| | | | | |        | | | | | |
A-A-8-9-C-B        o-o-o-o-o-o

2.Remove an edge whose endpoints have the same number.
Repeat this operation until no such pairs connected.
finally we get something like this
1 1-2-3 3-7        o o-o-o o-o
| |   | |          | |   | |
4-5-2-6 6-7        o-o-o-o o-o
    | | | |            | | | |
4-5-8-9-C-B        o-o-o-o-o-o
| |                | |
A A-8-9-C-B        o o-o-o-o-o

3.Pick a vertex v, which has a minimum degree(non-zero), and w, an arbitrary neighbor of v.
Assign a incremental number to both v and w, and remove all the edges who cover v or w.
Repeat this operation until Δ(G) == 0.
For the input the process will be:

            (STEP1)
1 1-2-3 3-7        1 o-o-o o-o
| |   | |            |   | |
4-5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4-5-8-9-C-B        o-o-o-o-o-o
| |                | |
A A-8-9-C-B        o o-o-o-o-o

            (STEP2)
1 1-2-3 3 7        1 o-o-o 2 2
  |   |              |   |
4 5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4-5-8-9-C-B        o-o-o-o-o-o
| |                | |
A A-8-9-C-B        o o-o-o-o-o

            (STEP3)
1 1-2-3 3 7        1 o-o-o 2 2
  |   |              |   |
4 5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4 5-8-9-C-B        3 o-o-o-o-o
  |                  |
A A-8-9-C-B        3 o-o-o-o-o

            (STEP4)
1 1-2-3 3 7        1 o-o-o 2 2
  |   |              |   |
4 5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4 5-8-9-C-B        3 o-o-o-o-o
  |                  |
A A-8-9 C B        3 o-o-o 4 4

            (STEP5)
1 1-2-3 3 7        1 o-o-o 2 2
  |   |            | |   |
4 5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4 5-8-9-C-B        3 o-o-o-o-o
  |                  |
A A 8 9 C B        3 o 5 5 4 4

            (STEP6)
1 1-2-3 3 7        1 o-o-o 2 2
  |   |            | |   |
4 5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4 5 8-9-C-B        3 6 o-o-o-o

A A 8 9 C B        3 6 5 5 4 4

            (STEP7)
1 1 2 3 3 7        1 7 7 o 2 2
      |                  |
4 5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4 5 8-9-C-B        3 6 o-o-o-o

A A 8 9 C B        3 6 5 5 4 4

            (STEP8)
1 1 2 3 3 7        1 7 7 o 2 2
      |                  |
4 5 2 6 6-7        1 8 8 o o-o
      | | |              | | |
4 5 8-9-C-B        3 6 o-o-o-o

A A 8 9 C B        3 6 5 5 4 4

            (STEP9)
1 1 2 3 3 7        1 7 7 9 2 2

4 5 2 6 6-7        1 8 8 9 o-o
        | |                | |
4 5 8-9-C-B        3 6 o-o-o-o

A A 8 9 C B        3 6 5 5 4 4

            (STEP10)
1 1 2 3 3 7        1 7 7 9 2 2

4 5 2 6 6-7        1 8 8 9 o-o
        | |                | |
4 5 8 9 C-B        3 6 A A o-o

A A 8 9 C B        3 6 5 5 4 4

            (STEP11)
1 1 2 3 3 7        1 7 7 9 2 2

4 5 2 6 6 7        1 8 8 9 B B

4 5 8 9 C-B        3 6 A A o-o

A A 8 9 C B        3 6 5 5 4 4

            (STEP12)
1 1 2 3 3 7        1 7 7 9 2 2

4 5 2 6 6 7        1 8 8 9 B B

4 5 8 9 C B        3 6 A A C C

A A 8 9 C B        3 6 5 5 4 4

4.Finally we got a valid output:
1 7 7 9 2 2
1 8 8 9 B B
3 6 A A C C
3 6 5 5 4 4

I know I must mistaked something, but I can't find the mistake.
Please tell me where is wrong, or give me some tests to beat this algo.
Thanks in advance.

Edited by author 31.05.2009 00:28

()(
Answer: 0.

By my mind, my solution is right.
It builds a shedule of transporting with maximal money values superseding least values before that time.

But my solution falls on ninth test. I think that something wrong with that test.

The nine has two representation according to to these rules, am I wrong?

random_shuffle and check prefix sums for division.

If you have WA #14 you need to know that the 14th test contains both numbers 29 and 30 in the row. Check range of numbers: [1, 30].

You must deal with e-9 precision
such test like
999999 100099 1000000 0 1

the solution is 3.1423994906657376×10−6

Good Luck :)

I don't know what is wrong!

Can someone give me more testcases to figure out what's wrong with my solution?

Если у вас задача уже зашла (Accepted), а потом пишется что на ней (Wrong Answer) например, то задача считается, как решённая (Accepted). Вдруг кому-то поможет.