WA #5:
2
-2000 0 -1000 0
0 -1000 0 -2000
> 367.0796326795

WA #7:
2
935 973 -16 438
867 30 196 463
> 1040.9330224527

WA #13:
2
0 7 0 8
6 10 6 1
> 12.7006778631

What can cause a "wrong answer" in 7-th test?

The total length of all strings (including the first one with the number N) exceeds the specified size of 4000000 bytes.

Hi,

Kindly add support for ocaml to execute timus problems.

Thanks.

1) write in the assignment that family ties and victims cannot be repeated in the input, or add such tests. this is a real problem when searching for maniacs in databases.
2) write in the assignment that a werewolf cannot kill himself.

#include <cstdio>
int main() {
    freopen("output.txt", "w", stdout);
    printf("99999\n");
    printf("0 0 10 100\n");
    for(int i =0 ; i < 99998; ++i) {
        printf("%d %d %d %d\n",  (i+1)*10,0,(i+2)*10 , 100);
    }
    return 0;
}
My early solution get AC, but must get TL.

Edited by author 19.01.2011 16:05

What is the answer for
2
0 0 3 3
3 2 5 7

Answer is -1?

http://pastebin.com/Cr6m0rw7
I think I tried everything that can limit memory but still got MLE :/

5 3 1
2
2
2
2
2
3
4
6

ans: 11

5 3 3
1
2
3
4
5
1
4
7

ans: 12

9 9 123
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

ans: 9

I have solved this problem by Fenvic tree, at first I got WA on 5 test, then I changed int-s into long long-s and now I have WA on 6 test. If you had this kind of experience please tell me what types should I use to get AC?
Thanks.

How I can do it on 0.001?

Edited by author 31.10.2008 02:29

You should find maximum matrix which is square, black and also contains white square inside rotated by 45 degrees. For instance:
1)
1 1 1 0 1 1 1
1 1 0 0 0 1 1
1 0 0 0 0 0 1
0 0 0 0 0 0 0
1 0 0 0 0 0 1
1 0 0 0 0 1 1
1 1 1 0 1 1 1
2)
1 1 1 1 0 1 1 1 1
1 1 1 0 0 0 1 1 1
1 1 0 0 0 0 0 1 1
1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1 1
1 1 1 0 0 0 1 1 1
1 1 1 1 0 1 1 1 1
are desired matrices maximum width of which you must find

My solution runs in O(N logN) and it uses heap data structure. The discussion forums hint that there may be a O(N) time solution. Is there a linear time algorithm?

What means if gear-wheel have only one cog?

Edited by author 26.09.2004 20:25

There is simple O(N+M) algo (core part is like 5 lines), and it's "online" (no preprocessing of queries required)

Edited by author 10.06.2026 04:20

Notice, that you can move duons alongside diagonal (A->F, A->H, G->E, ...)

Who know O(H*W) or, O(H*W*5) algo ???

It is much more interesting to look for good tests for this task than just to solve it.
Here is the AC program (with a small error in order not to publish solutions). I will look for where it will fail.
#include<iostream>
#include<cmath>//too lazy to write sqrt() yourself
int main() {
    unsigned l, h, o;
    std::cin>>l>>h>>o;
    unsigned phase = 0;
    if(l<h*2) phase = o*sqrt((2*h-l)/981)/15+1;
    char const*answer[]{"Butter","Bread\n"};
    std::cout<<answer[(phase>>1)&1]<<std::endl;
}

Tree for minimum is enough.

Input
0
50 10
0 0
100
200
-1
Output
-5.00

I thought at first, that an absolute value has to be printed, which gets WA 3.