Any hint for solving this problem?

Try this test:

2
abc
b
1
abc

Correct answer: 1 1

3 5
1 4 5
7 3 8
2 4 4
7 5 3
7 7 0

3 5
2 5 1
5 3 4
3 8 8
8 6 0
6 6 1
I got tle on these tests.But I got AC.

O(N) for RAM and CPU, don't know why memory limit is that high. Based on classics for tree diameter.

What is the maximum number of divisions needed to get the full period?
I got TLE this O(n^2) algo there n is the number of divisions.

You can solve that with algo Djikstra.
We have 6!*8*8 vertex (hash of cube and point) .
And all vertexs have <=4 edges.
P.s. sry for English )

Edited by author 09.08.2014 16:51

just use DSU to check teams, and then build answer

The first day has no delay flight from the day before.

2
1 60 100
23:00

He can departure from 24:00 , not 00:00

O(W*H) solution passes

Edited by author 22.08.2021 13:50

Edited by author 22.08.2021 13:50

In my programme, I use 1000 000 random locations to check if the points are in the circle.
At first, I wrote something like this: "double tx = ( double )( rand() % 101 ) / 100.0 ";(because: 0 ≤ x ≤ 1, -> rand() % 101 ∈[ 0, 100 ] );and just got WA......
Finally I changed the 101 into 100 and got AC;
Can anyone tell me why 101 is incorrect? or it is actually right?

WA8:
6
aabcaa
ans: 6
RE9:
7
aaaaaaa
ans: 7

why I get wa on test 23?

I've tried many test data.But I always got wa on test data 8.

Here is my code.
And I'm sorry for my bad English- -!
Waiting for your data! Thanks very much!


program ural1019_3;
var
  fill:array [1..5000,1..3] of longint;
  point:array [1..10003] of longint;
  col:array [1..10002] of byte;
  a,i,d,n,la,nn,x,y,u,yy:longint;
  c:char;

procedure qsort(l,r:integer);
var i,j,x,y:longint;
begin
     i:=l;j:=r;x:=point[(l+r) div 2];
     repeat
           while point[i]<x do inc(i);
           while point[j]>x do dec(j);
           if i<=j then begin
              y:=point[i];point[i]:=point[j];point[j]:=y;
              inc(i);dec(j);
           end;
     until i>j;
     if l<j then qsort(l,j);
     if i<r then qsort(i,r);
end;

procedure work;
var
  a,i,b,ll,max,lr,ml,mr:longint;

  function x2find(p:longint):integer;
  var a,l,r,x:longint;
  begin
    l:=1;r:=nn;
    while l<r do begin
          x:=point[(l+r) div 2];
          if p=x then break;
          if p<x then r:=(l+r) div 2-1;
          if p>x then l:=(l+r) div 2+1;
    end;
    x2find:=(l+r) div 2;
  end;

begin
  for a:=1 to nn-1 do col[a]:=1;
  for a:=1 to n do begin
      i:=x2find(fill[a,1]);
      for b:=i to nn-1 do if point[b]<>fill[a,2] then col[b]:=fill[a,3] else break;
  end;
  max:=0;a:=1;
  while a<nn do begin
        while (col[a]=2) and (a<=nn-1) do inc(a);
        if a=nn then break;
        ll:=point[a];
        while (col[a]=1) and (a<=nn-1) do inc(a);
        lr:=point[a];
        if lr-ll>max then begin max:=lr-ll; ml:=ll; mr:=lr; end;
  end;
  if n<=0 then writeln('0 1000000000') else writeln(ml,' ',mr);
end;

begin
  readln(n);u:=n;
  for a:=1 to u do begin
      read(x,y,c);
      while (c<>'w') and (c<>'b') do read(c);
      readln;
      if x>y then begin yy:=x; x:=y; y:=yy; end;
      if x=y then begin dec(n); continue; end;
      fill[a,1]:=x; fill[a,2]:=y;
      point[a*2-1]:=fill[a,1];point[a*2]:=fill[a,2];
      if c='w' then fill[a,3]:=1 else fill[a,3]:=2;
  end;
  point[n*2+1]:=0;point[n*2+2]:=1000000000;
  qsort(1,n*2+2);
  la:=1;i:=2;
  while i<n*2+2 do begin
        while (point[i]=point[la]) and (i<=n*2+2) do inc(i);
        if i>n*2+2 then break;
        inc(la);
        point[la]:=point[i];
  end;
  nn:=la;
  work;
end.

Edited by author 27.07.2007 20:54

The problem looks trivial at first glance. But I had never experienced such many corner cases.

My solution should use 2 * M * K indexations of linear array in the worst case (100 000 000 for max M and K) but works about 0.5s, twice less than time limit, and it is Java!

Does it mean that so simple algorithm is enough or that tests are weak?

Edited by author 15.05.2007 02:27

My programme is:

const nnn=100;
var n,k,b,c,d,f:integer;
    a:array[1..nnn,0..(nnn-1)*nnn div 2] of shortint;
    e:array[1..100] of integer;
begin
  readln(n,k);
  k:=n*(n-1) div 2-k;
  for b:=1 to n do e[b]:=(b-1)*b div 2;
  for b:=1 to n do begin
    for c:=0 to e[n] do a[b,c]:=-1;
    a[b,e[b]]:=0;
  end;
  for b:=1 to n do
    for c:=0 to e[b]-1 do
      for f:=b-1 downto 1 do begin
        d:=f;
        if c<e[b-d] then break;
        if a[d,c-e[b-d]]>=0 then begin
          a[b,c]:=d; break;
        end;
      end;
  if a[n,k]<0 then writeln(-1) else
    while n>0 do begin
      for b:=a[n,k]+1 to n-1 do writeln(b,' ',b+1);
      if a[n,k]+1<>n then writeln(n,' ',a[n,k]+1);
      if a[n,k]<>0 then writeln(a[n,k],' ',a[n,k]+1);
      b:=k; dec(k,e[n-a[n,k]]); n:=a[n,b];
    end;
end.

Definition: "inside the island"

Let's define the definition recursively:
1)If an island/sea touches the edge of the map, then it does not lie inside the sea/island

2)If an island/sea does not have internal seas/islands, then all the seas/islands it touches (it should be one if it does not touch the edge of the map) contain this island/sea inside themselves.

3)If an island/sea has internal seas/islands, then all these seas/islands in this island/sea, and all the seas of which these island/sea touch, which are not internal, contain this island/sea.

this all means that if the island lies inside the sea, which is inside the island, which is inside the sea, which is inside the island that touches the end of the map, and the illuminated sea is selected, the sea that is inside the island touching the map, then all the islands inside the sea are not part of the island touching the end of the map, and if the outer sea is selected, then since it is not exactly contains an island touching the map, then it should not contain islands inside this island

Добрый день!
Я сдал эту задачу, и у меня возникли трудности с условием. Во-первых, нигде не написано, что такое "внутри моря". Во-вторых, когда я догадался до значения вышеупомянутого термина, я не уловил смысла в следующем предложении: "Острова, касающиеся границы карты, не могут быть использованы для захоронений шаманов – шаманы этого очень не любят". Острова, находящиеся на границе, точно не лежат внутри никакого моря. В связи с этим, у меня возникло предположение, что ответ на следующий тест - 1 (что вроде неверно):
5 7 1 1
.....
.####
.#...
.#.#.
.#...
.####
.....
(в ответ входит маленький островок справа). Поправьте условие, пожалуйста!