Well, may it's there... but I managed to get 0.14 sec AC with O(N^2*M/2).

First of all, precision of 1e-8 is ok to get AC (with double type and without trigonometry).

Now about WA16 - that's the case when one of boundary rays is parallel to OX. When some angular segments crosses OX, I perform a split at 0/2PI point. In described case it was possible that I first delete a draught at point 0 and then add it. So, sorting should be not just angular, but also additions should precede deletions. This condition is automatic for regular cases, so I omitted it. But in described case special care should be taken.

Помогите найти ошибку в задании №1263. Я использовал язык Си. Код программы:
#include <stdio.h>
void main()
{
 int N,M,i,j,a[10000];
 double p;
vv:
 scanf("%d",&N);
 scanf("%d",&M);
 if (N<=0 || N>10000 || M<=0 || M>10000) goto vv;
{
 for (i=0; i<M; i++)
  {
    scanf("%d",&a[i]);
  }

for (j=1;j<=N;j++)
 { p=0.0;
  for (i=0;i<M;i++)
  {
    if(a[i]==j)
   {
    p=p+1;
   }
  }
   p=p/M*100;
   printf("%.2f%\n",p);
  }
}
}

I used 'C'language. Following code(task№1263):
#include <stdio.h>
void main()
{
 int N,M,i,j,a[10000];
 double p;
vv:
 scanf("%d",&N);
 scanf("%d",&M);
 if (N<=0 || N>10000 || M<=0 || M>10000) goto vv;
{
 for (i=0;i<M;i++)
  {
    scanf("%d",&a[i]);
  }

for (j=1;j<=N;j++)
 { p=0.0;
  for (i=0;i<M;i++)
  {
    if(a[i]==j)
   {
    p=p+1;
   }
  }
   p=p/M*100;
   printf("%.2f%\n",p);
  }
}
}

Что за ****?)

var sum,s,n,i,j,k:longint; a:array[1..100]of longint;
begin
 read(s,n);
 for i:=1 to s do read(a[i]);
 for j:=1 to s do
   for i:=1 to j do
    begin  sum:=0;
     for k:=i to j do sum:=sum+a[k];
     if sum>j-i+n+1 then begin write('NO'); exit; end;
    end;
 write('Yes');
end.

Many people above have solved this problem, but they didn't express their thought well.

The key is this:
For ANY 3 vectors in the set with module not exceeed L,
we can ALWAYS choose 2 of them and, with choosing the direction, make the module of their sum not exceed L.
(this can be proved by geometry)

So, we choose the two and reduce them to one (simply adding them and record the direction).
Thus, we can reduce the amount of vectors by this until there are only TWO.
At last, for any two vectors which has the module not longer than L,
we can make the module of their sum not exceed L*sqrt(2).

And that's all the key.
What's left is to find a way to programme.
Use tree to store the father-son relation is a good choice.

Maybe it will help you, maybe not for my poor English.

How many structures  need quick solution.
I worked with segments [i,j] on [1,N] and used
1: short num[50000] for quicksort of segments;
2: short prev[50000] for fathes of segments. Segment I is father of segment J if I smallest segment containing J.
3: vector<short>sons[50000] for sons of segments.
Last structure very slow and I had bad Ac time 0.95.

How do this faster?
1) Adding virtual edges to pairs of vertices with odd degree
2) Building Eler circuit in new graph.
3) Cutting circuit by virtual edges.
But Graph is undirected and when we removing edges
in classic stac algorithm we should use set-class as
dynamic Adj list for each vertex instead of vector-class

my program gives the same output file as th oficial ones
but goth WA any tricks about end of line or something?

What is wrong with this test ?

Help!
Thanks.

Edited by author 09.06.2006 18:06

It seems like the limits for input values given in problem statement are incorrect - after changing data types from short int (which have max value larger than 30000) to int I got AC for test cases 2..16 - in opposite to the version before this change. So the WA was caused by numbers at input larger than 30000 - it shouldn't happen.

Am I wrong or should it be fixed?

Test 1 :    101
Ans :    10
Test 2 :    123
Ans :    1
Test 3 :    7
Ans :    7
Test 4 :    91
Ans :    9
Test 5 :    9100
Ans :    189
Test 6 :    21
Ans :    15
Test 7 :    231
Ans :    260
Test 8 :    9100101
Ans :    189
Test 9 :    000612300000
Ans :    995888949
Test 10 :    78910111
Ans :    7
Test 11 :    698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110
Ans :    2850
Test 12 :    0999100
Ans :    35287
Test 13 :    1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111
Ans :    919111111111111111111111111111111111111111111111111111111111111111111111111111111111111111104
Test 14 :    566666
Ans :    1887
Test 15 :    1
Ans :    1
Test 16 :    0
Ans :    11
Test 17 :    0000000
Ans :    68888891
Test 18 :    09
Ans :    171
Test 19 :    999
Ans :    2588
Test 20 :    9919
Ans :    2863
Test 21 :    0202
Ans :    6971
Test 22 :    0202020202020202020
Ans :    2313131313131
Test 23 :    00070007000700070007
Ans :    8289728972891
Test 24 :    9999999999999939999999999
Ans :    14888888888888785
Test 25 :    1    5    len=100
Ans :
Test 26 :        4    len=100
Ans :
Test 27 :    0    len=200
Ans :
Test 28 :    0    6    len=100
Ans :
Test 29 :    9    len=200
Ans :
Test 30 :    9    9    len=100
Ans :
Test 31 :    3    len=84
Ans :
Test 32 :    7    8    len=100
Ans :
Test 33 :    5    len=100
Ans :
Test 34 :
Ans :
Test 35 :
Ans :
Test 36 :
Ans :
Test 37 :
Ans :
Test 38 :    13206252123724040484317964602881252884069781203380530661996711969    2    len=100
Ans :
Test 39 :    2226671115560004449333778222667111556000    len=100
Ans :
Test 40 :
Ans :

K==20 at test #1

And the answer for this test is "2\n0 2", as in the sample

Is this test correct?


Edited by author 15.02.2007 00:05

there is no need to start exam earlier, because both
T1 and T3 are measured in munutes from the begining of exam,
so if the exam starts earlier nothing changes.
please, correct the statement.

Edited by author 12.08.2008 18:54