I naively applied suffix arrays with lcp and got AC in ~2.7s. (complexity N*K*log^2(K))

But I see that there are submissions with times <0.1s. What are the more efficient algorithms?

Someone mentioned suffix-function - any referece for that?
Also it was said that KMP can be used - can anyone explain how exactly it is applicable here?

Thanks in advance.

can you explain the sample for me
Thx

program ural;
uses math;
var s:array['X'..'Z']of integer;
    c:char;
    d,n,i:integer;
begin
  readln(n);
  for i:=1 to n do
    begin
      read(c);
      readln(d);
      s[c]:=s[c]+d;
    end;
  if(s['X']>0)and(s['Z']>0)then
    begin
      d:=min(s['X'],s['Z']);
      inc(s['Y'],d);
      dec(s['X'],d);
      dec(s['Z'],d);
    end
  else
    if(s['X']<0)and(s['Z']<0)then
      begin
        d:=max(s['X'],s['Z']);
        inc(s['Y'],d);
        dec(s['X'],d);
        dec(s['Z'],d);
      end;
  if(s['X']>0)and(s['Y']<0)then
    begin
      d:=max(-s['X'],s['Y']);
      inc(s['Z'],d);
      inc(s['X'],d);
      dec(s['Y'],d);
    end
  else
    if(s['X']<0)and(s['Y']>0)then
      begin
        d:=min(-s['X'],s['Y']);
        inc(s['Z'],d);
        inc(s['X'],d);
        dec(s['Y'],d);
      end;
  if(s['Z']>0)and(s['Y']<0)then
    begin
      d:=max(-s['Z'],s['Y']);
      inc(s['X'],d);
      inc(s['Z'],d);
      dec(s['Y'],d);
    end
  else
    if(s['Z']<0)and(s['Y']>0)then
      begin
        d:=min(-s['Z'],s['Y']);
        inc(s['X'],d);
        inc(s['Z'],d);
        dec(s['Y'],d);
      end;
  writeln(abs(s['X'])+abs(s['Y'])+abs(s['Z']));
  if s['X']<>0 then
    writeln('X ',-s['X']);
  if s['Y']<>0 then
    writeln('Y ',-s['Y']);
  if s['Z']<>0 then
    writeln('Z ',-s['Z']);
end.

If you have CRASH, may be, will help for you to make columns of a global variable and to clean from definitions of procedures. I got AC...

If you get WA2 try this one:
Input:
3
3 2
2 1
1 -1
3
1 2
3 2
1 3
Output:
1
2
1

Also if you get WA12 pay attention for: "All identifiers lie between 0 and 40000."

#include <iostream>
#include <iomanip>
#include<math.h>
#include<vector>
using namespace std;
int  main()
{
    cout<<setiosflags(ios::fixed)<<setprecision(4);
    vector<double>v;
    double a;
    for(int i=0;!cin.eof();i++ )
    {
        cin>>a;
        v.push_back(sqrt(a));
    }
    for(int j=v.size()-2;j>=0;j--)
    {cout<<v[j]<<"\n";}
    return 0;
}

How to control the output precision?What does "to the acuracy of 10-6?

 var
  i,j,k,n,m,tot:longint;
  ans,x1,y1,x2,y2,d1,d2,d3,x,y,angle1,angle2,t,p1,p2:double;

 function min(xx,yy:double):double;
  begin
   if xx>yy then exit(yy);
   exit(xx);
  end;

 begin
  {assign(input,'1215.in');reset(input);}
  read(x,y,n);
  read(x1,y1);
  p1:=x1;
  p2:=y1;
  d1:=sqrt(sqr(x-x1)+sqr(y-y1));
  ans:=999999999;
  tot:=0;
  for i:=2 to n do
   begin
    read(x2,y2);
    if (x1<x)and(x2>=x)and((y1<y)or(y2<y))
     then
      inc(tot);
    d2:=sqrt(sqr(x-x2)+sqr(y-y2));
    d3:=sqrt(sqr(x1-x2)+sqr(y1-y2));
    angle1:=(d2*d2+d3*d3-d1*d1)/(2*d2*d3);
    angle2:=(d1*d1+d3*d3-d2*d2)/(2*d1*d3);
    if (angle1>=0)and(angle2>=0)
     then
      begin
       if x1=x2
        then
         t:=abs(x1-x)
        else
         t:=((y1-y2)/(x1-x2)*x-y+y1+(y2-y1)/(x1-x2)*x1)/(sqrt(sqr((y1-y2)/(x1-x2))+1));
       t:=abs(t);
       ans:=min(ans,t);
      end
     else
      begin
       t:=min(d1,d2);
       ans:=min(ans,t);
      end;
    d1:=d2;
    x1:=x2;
    y1:=y2;
   end;
  x2:=p1;
  y2:=p2;
  if (x1<x)and(x2>=x)and((y1<y)or(y2<y))
     then
      inc(tot);
    d2:=sqrt(sqr(x-x2)+sqr(y-y2));
    d3:=sqrt(sqr(x1-x2)+sqr(y1-y2));
    angle1:=(d2*d2+d3*d3-d1*d1)/(2*d2*d3);
    angle2:=(d1*d1+d3*d3-d2*d2)/(2*d1*d3);
    if (angle1>=0)and(angle2>=0)
     then
      begin
       if x1=x2
        then
         t:=abs(x1-x)
        else
         t:=((y1-y2)/(x1-x2)*x-y+y1+(y2-y1)/(x1-x2)*x1)/(sqrt(sqr((y1-y2)/(x1-x2))+1));
       t:=abs(t);
       ans:=min(ans,t);
      end
     else
      begin
       t:=min(d1,d2);
       ans:=min(ans,t);
      end;
  if odd(tot)
   then
    ans:=0;
  writeln(ans*2:0:3);
 end.

just check your program on these tests
----------
4 3
1 5 8 10
answer:
1 8
5 10
wrong answer:
1 5
8
10
----------
4 2
3 5 7 10
answer:
5 10
3 7
wrong answer:
7 10
5
3

I know AC solution that answers 5 on this test instead of 3:
/////////////start of test
6






////////////end of test

6
[1 space]
[1 space]
[2 spaces]
[2 spaces]
[3 spaces]
[3 spaces]
[EOF]

Also this test should be answered 0 instead of 1.
2
 MEXX
MEXX

I gues this tests suit the condition "The brands are the strings of Latin letters and blanks." and may be added.

Thank you.

It works like this:
f1=1*f1+0*f2;
f2=0*f1+1*f2;
f3=1*f1+1*f2;
f4=1*f1+2*f2;
f5=2*f1+3*f2;
f6=3*f1+5*f2;
...^....^
...|....These coefficients are in the array c2
...These coefficients are in the array c1

----PROG BELOW----
program ural1133;
const
  maxn=2001;
var
  c1,c2:array[1..maxn]of extended;
  x,y,n,i:integer;
  fx,fy,f1,f2:longint;
function min(a,b:integer):integer;
  begin
    if a<b then min:=a else min:=b;
  end;
function max(a,b:integer):integer;
  begin
    if a>b then max:=a else max:=b;
  end;
begin
  readln(x,fx,y,fy,n);
  i:=min(min(x,y),n);
  if i<=0 then begin
    i:=1-i;
    inc(x,i);inc(y,i);inc(n,i);
  end;

  c1[1]:=1;c2[1]:=0;
  c1[2]:=0;c2[2]:=1;
  for i:=3 to max(max(x,y),n) do begin
    c1[i]:=c1[i-2]+c1[i-1];
    c2[i]:=c2[i-2]+c2[i-1];
  end;

  f1:=round((fx*c2[y]-fy*c2[x])/(c1[x]*c2[y]-c1[y]*c2[x]));
  f2:=round((fx*c1[y]-fy*c1[x])/(c2[x]*c1[y]-c2[y]*c1[x]));
  writeln(round(c1[n]*f1+c2[n]*f2));
end.

Test
1 -2000000000 2 2000000000 3

is correct?

Answer: 0

My first code:

#include <stdio.h>
int n;
long long f[501][501], g[501][501], res;
void xxx(void)
{
     for (int i=0; i<=n; i++) f[0][i] = 1;
     for (int i=1; i<35 && i<=n; i++) {
         for (int j=0; j<=n; j++)
             for (int k=0; k<=n; k++) {
                 g[j][k] = f[j][k]; f[j][k] = 0;
             }
         for (int j=1; j<=n; j++) {
             for (int k=1; k<=j; k++) f[j][k] = f[j][k - 1] + g[j - k][k - 1];
             for (int k=j+1; k<=n; k++) f[j][k] = f[j][j];
         }
         res += f[n][n];
     }
}
int main(void)
{
    scanf("%d", &n);
    xxx();
    printf("%lld\n", --res);
    return 0;
}
WA for #6.

My second code:

#include <stdio.h>
int n;
__int64 f[501][501], g[501][501], res;
void xxx(void)
{
     for (int i=0; i<=n; i++) f[0][i] = 1;
     for (int i=1; i<35 && i<=n; i++) {
         for (int j=0; j<=n; j++)
             for (int k=0; k<=n; k++) {
                 g[j][k] = f[j][k]; f[j][k] = 0;
             }
         for (int j=1; j<=n; j++) {
             for (int k=1; k<=j; k++) f[j][k] = f[j][k - 1] + g[j - k][k - 1];
             for (int k=j+1; k<=n; k++) f[j][k] = f[j][j];
         }
         res += f[n][n];
     }
}
int main(void)
{
    scanf("%d", &n);
    xxx();
    printf("%I64d\n", --res);
    return 0;
}
AC.

20 7
D 9
D 7
D 6
D 1
D 2
D 3
L 2
The answer should be 4.

During 3 days I couldn’t find appropriate way
to work with big binomials having lost of order
or overflow. Simple and clever routine was found and
gave satisfaction.