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.

Could anyone provide me with an O(n) solution? My works O(n log(n))

Just used STL contaners such as std::map<std::string,T>, std::vector<T>. :)
33 lines of code.

plz help me, i got WA on this test , if someone knows this one help me!.

Use heavy-light decomposition: after O(N) preprocessing, every tree path becomes O(log N) contiguous ranges in the HLD order. Because cave radiation only increases, maintain range maximums with a monotone Fenwick tree, giving O(log N) per update and O(log^2 N) per path query with O(N) memory.

Current #1 AC

Edited by author 06.06.2026 21:24

Edited by author 06.06.2026 21:24