Well, after all, I solved this problem, but it took a long time for me to find all mistakes in my calculations.

My idea was to generate F[N,K] in a O(log(N)*log(N)) time, which means an amount of numbers with N or less digits (in a certain base) with K one-digits. Then I wrote a function C(N, K), which finds an amount of numbers with K one-digits in [1, N] using F and deleting its first digit every time. Actually it's all about dynamic programming.

But I think there must be more clear and efficient solutions, than mine (O(log(N)*log(N)) for time and memory). If it does, please, would you be so kind to share it?

The text is incorrect:

"...to present it by the set of pairs of adjacent edges..." means not to transform the graph into a form in which it will be unequivocally presented by the set of pairs of its adjacent edges (it is rather difficult problem), but only to share (divide, separate) it into pairs of adjacent edges (it is easy).

i.g. you can divide graph [1-2-3-4-1] into [1-2] and [3-4]

i'm so glad that i can do the problem on myself!!!i come up with the right way to solve the probmlem,but i forgot about the time.so i time time limit exceeded.then i did some work and——i got ac!!!here's the for example to the problem,hope to help you:4?3=12,and 2?3=6.

In the text, what does the word SURFACE mean?

Consider the following case:
3 6 2 2 3
#.#
#.#
#.#
#.#
...
###

Can he rescued by himself??????

Is there any possibility to make Authors Ranklist also viewable per country? I mean every country to has a separate ranklist for just its coders. Shouldn't be more than few lines of code and one WHERE clause more in the database query :)

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