My algorythm has maximum O(n^2) complexity. I have TLE 18 test.
But, when i artificially set limits for n (amount of layers) to 200 and for k (amount of bricks in a single layer) to 290, my program still gets TLE 18 test, i really have no idea how is it possible. It should get WA\AC if inputs are more than limits since i do not see any possibility of an endless cycle in my algo.

Edited by author 27.02.2020 21:19

Edited by author 27.02.2020 21:36

* The minimal height of the wall is set to 1 (previously 0).
* The total number of bricks is set to be between 1 and 100 000 (previously, not more than 1 000 000, but there were no such tests).
* New tests have been added.
* All accepted solution have been rejudged, 98 authors have lost their AC.

What does 'system of bricks' (or 'система кирпичей' in russian statement) mean?

There were two problem "Bricks" (1234 and 1311). New name of problem 1311 is "Stable Construction".

I think the test data is very weak. I guess there is no big amount of bricks at all.

hello,

i try to solve this problem, but i did a mistake..i got WA#3...i think my ideea it's not good.

can anyone give me a hint?

thx a lot

Edited by author 20.02.2007 04:29

Edited by author 20.02.2007 04:29

Just test your program with test:
2
1
1 2
0

answer: No

This can help you with WA4

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



No

I keep getting wa on test 3.
I think my program is quite easy to understand and it's very short. Many thanks if you would love to help me.
Or you can send your solution to me: fujieyun@163.com

Const MaxN = 1000;
      Zero = 1e-8;

Var B1, B2         : Array [1..MaxN,1..2] of LongInt;
    G1, G2         : Array [1..MaxN] of Record
                                          W, Loc : Double;
                                        End;
    N, H, N1, N2, I, J, P   : Integer;

Begin
  ReadLn( H );
  if H = 0
    then Begin
         WriteLn( 'Yes' ); Halt;
         End;
  ReadLn( N1 );
  For I := 1 to N1 do
    Begin
    ReadLn( B1[I,1],B1[I,2] );
    G1[I].W := B1[I,2]-B1[I,1];
    G1[I].Loc := (B1[I,1]+B1[I,2])/2;
    End;

  For I := 2 to H do
    Begin
    ReadLn( N2 ); P := 1;
    FillChar( G2, Sizeof(G2), 0 );
    FillChar( B2, Sizeof(B2), 0 );
    For J := 1 to N2 do
      Begin
      ReadLn(B2[J,1], B2[J,2] );
      G2[J].W := B2[J,2] - B2[J,1];
      G2[J].Loc := (B2[J,1] + B2[J,2])/2;
      if (P<=N1)and(G1[P].Loc < B2[J,1]+Zero)
        then Begin
             WriteLn( 'No' ); Halt;
             End;
      While (P<=N1)and(G1[P].Loc+Zero < B2[J,2]) do
        Begin
        G2[J].Loc := G2[J].Loc + (G1[P].Loc-G2[J].Loc)*G2[J].W/(G1[P].W+G2[J].W);
        G2[J].W := G2[J].W + G1[P].W;
        Inc( P );
        End;
      End;
    if P<=N1
      then Begin
           WriteLn( 'No' ); Halt;
           End;
    B1 := B2; G1 := G2; N1 := N2;
    End;
  WriteLn( 'Yes' );
End.

We have a test.
1
1
12 20

Of course it is stable. But where is the center of gravity. It is (16; 0.5), isn't it?

Check this:
4
1
0 3
1
1 4
1
2 5
1
0 3

In real world this contsruction is stable (i think) ... but is it stable in task description?

i have try many times,but i don't know why i got WA at test #3,can anyone give some test data?Thanks!

3
1
49 52
2
1 50
51 100
1
49 52

I think it is unstable. But how to explain it using the theorem given by this problem?

What is the anwer for such construction:
2
2
10 20
50 60
2
10 20
50 60

is it stable?
But system of 2 bricks from second floor [10, 20] and [50, 60] have their center of mass in 35 which is not on brick.

Another example is sort of ladder:
4-ht level: [3, 6]
3-rd level: [2, 5]
2-nd level: [1, 4]
1-fs level: [0, 3]
in real word it is unstable, but what should I output?

for each brick, is only its center of gravity considered or the center of gravity of this brick and all the bricks this brick supports ( and the bricks they support and so on...)