It's very simple,isn't it?

var
    i,k:integer;
begin
    readln(K);
    for i:=3 to round(sqrt(k)) do if k mod i=0 then begin k:=i; break end;
    writeln(k-1);
end.

Could anybody give me any hint?
(I know algoritm with O(n^4), but I always receive Time Limit
Exceeded.)E-mail me to vok@sbor.ru

Thanks!

I have a dynamic algorithm  O(n^3).I use a structer
Answer   : array[1..100,1..100,1..100]of String;
But it too large! Answer[k,i,j] - is the regular sequence with
minimum length,in which copy(S,1,k) contained (where S - sequnce in
input)

I write the code and the output has the same output with the sample
output. Is there a test case for my program, so I can get the bug?

Thank You!

This is the source code:

/* @judge_id: 15467RK 1002 C */
#include <stdio.h>
#include <string.h>

#define MAX 108
#define MAX2 307208
#define MAX3 50000
#define MAX4 51

struct path {
    int id;
    int nextpath;
} path[MAX3];

char number[MAX];
char temp[MAX4];
char dictionary[MAX2];
int pdictionary[MAX3+1];
int tdictionary;
int numlen;
int last;
int bisa[26][100];
int tempbisa[100];
char tempbisaok[100];
int ttempbisa;
int tbisa[26];
int tpath;
int nextpath[100];
int i,j,k,l,m,n;
int min;
int result[MAX];
int tempresult[MAX];
char pre[10][3]={
    {'o','q','z'},
    {'i','j'},
    {'a','b','c'},
    {'d','e','f'},
    {'g','h'},
    {'k','l'},
    {'m','n'},
    {'p','r','s'},
    {'t','u','v'},
    {'w','x','y'}
};
int tpre[10]={
    3,2,3,3,2,2,2,3,3,3
};

void cari (int idx,int tword) {
    int i,j;
    if (min!=MAX && min<=tword) return;
    if (nextpath[idx]!=-1) {
        i=nextpath[idx];
        while (i!=-1) {
            if (pdictionary[path[i].id+1]-pdictionary[path
[i].id]+idx==numlen) {
                if (min==MAX || min>tword) {
                    for (j=0;j<tword-1;j++)
                        result[j]=tempresult
[j];
                    result[tword-1]=path[i].id;
                    min=tword;
                    return;
                }
            } else if (pdictionary[path[i].id+1]-
pdictionary[path[i].id]+idx<numlen) {
                tempresult[tword-1]=path[i].id;
                cari (pdictionary[path[i].id+1]-
pdictionary[path[i].id]+idx,tword+1);
            }
            i=path[i].nextpath;
        }
    }
}

void main () {
    while (scanf ("%s",number)==1 && number[0]!='-') {
        last=0;
        scanf ("%d",&tdictionary);
        pdictionary[0]=last;
        for (i=0;i<26;i++) tbisa[i]=0;
        numlen=j=strlen (number);
        for (i=0;i<j;i++) {
            for (k=0;k<tpre[number[i]-'0'];k++) {
                l=pre[number[i]-'0'][k]-'a';
                bisa[l][tbisa[l]++]=i;
            }
            nextpath[i]=-1;
        }
        tpath=0;
        for (i=0;i<tdictionary;i++) {
            scanf ("%s",&dictionary[last]);
            ttempbisa=0;
            l=0;
            for (j=0;dictionary[last+j];j++) {
                m=dictionary[last+j]-'a';
                if (ttempbisa || !l) {
                    for (k=0;k<tbisa[m];k++) {
                        if (l) {
                            for
(n=0;n<ttempbisa;n++) {
                                if
(tempbisa[n]==bisa[m][k]) {

    tempbisaok[n]=1;
                                }
                            }
                        } else {
                            tempbisaok
[ttempbisa]=1;
                            tempbisa
[ttempbisa++]=bisa[m][k];
                            l=1;
                        }
                    }
                }
                for (n=ttempbisa-1;n>=0;n--) {
                    if (tempbisaok[n]) {
                        tempbisa[n]++;
                        tempbisaok[n]=0;
                    } else {
                        tempbisa[n]=tempbisa[-
-ttempbisa];
                    }
                }
            }
            for (k=0;k<ttempbisa;k++) {
                if (nextpath[tempbisa[k]-j]==-1) {
                    nextpath[tempbisa[k]-j]=tpath;
                } else {
                    l=nextpath[tempbisa[k]-j];
                    while (path[l].nextpath!=-1)
l=path[l].nextpath;
                    path[l].nextpath=tpath;
                }
                path[tpath].id=i;
                path[tpath].nextpath=-1;
                tpath++;
            }
            last=j+last;
            pdictionary[i+1]=last;
        }
        min=MAX;
        cari (0,1);
        if (min==MAX) puts ("No solution.");
        else {
            for (i=0;i<min;i++) {
                for (j=pdictionary[result
[i]];j<pdictionary[result[i]+1];j++)
                    printf ("%c",dictionary[j]);
                printf (" ");
            }
            puts ("");
        }
    }
}
/* @end_of_source_code */

Here is my code. I tested it with 50 100 (the test posted in the
forum) and it worked OK.... but when I submitted it, I got WA... Why?


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX(a,b) a>b?a:b
#define     MAXL            300
#define     _MAX_N          51
#define     _MAX_S          501

struct large {
short num[MAXL]; // The number itself. 1234 is stored as 4321
int sz; // sz is the quantity of digits
};

large m1[_MAX_S],m2[_MAX_S];
large one,zero,t;

void add(large &n1,large n2) {
int size=MAX(n1.sz,n2.sz);
int ost=0;
int i;
     n1.sz=size;
     for (i=0;i<size;i++) {
         n1.num[i]=n1.num[i]+n2.num[i]+ost;
         if (n1.num[i]>9) {
            n1.num[i]-=10;
            ost=1;
         } else ost=0;
     }
     if (ost==1) {
        size++;
        n1.sz=size;
        n1.num[size-1]=1;
     }
}

void init() {
int i,j;
     for (i=0;i<_MAX_S;i++) {
         m2[i].sz=0;
         for (j=0;j<MAXL;j++)
             m2[i].num[j]=0;
     }

}

void calc(int n, int sum) {
int i,j,k;
    for (i=0;i<=sum;i++)
        if (i<10) m1[i]=one; else m1[i]=zero;
    for (i=2;i<=n;i++) {
        for (j=0;j<=sum;j++) {
            for (k=0;k<=9;k++)
             if (j>=k) add(m2[j],m1[j-k]); else break;
        }
        memcpy(m1,m2,sizeof(m2));
        init();
    }
}

void print(large x) {
int i;
     for (i=x.sz-1;i>=0;i--)
         printf("%d",x.num[i]);
     printf("\n");
}

void lsqr(large &x) {
short res[MAXL][MAXL];
int ost,ind1,ind2,i,j,sum;
     ost=0;
     memset(&res,0,sizeof(res));
     for (i=0;i<x.sz;i++) {
         ind1=i;
         for (j=0;j<x.sz;j++) {
             ind2=ind1+j;
             res[ind1][ind2]=x.num[i]*x.num[j]+ost;
             ost=res[ind1][ind2]/10;
             res[ind1][ind2]%=10;
         }
         if (ost>0) res[ind1][ind1+j]=ost;
         ost=0;
     }
     ost=0;
     for (i=0;i<MAXL;i++) {
         sum=0;
         for (j=0;j<MAXL;j++)
             sum+=res[j][i];
         x.num[i]=sum+ost;
         ost=x.num[i]/10;
         x.num[i]%=10;
     }
     x.num[i]=ost;
     for (x.sz=MAXL-1;x.sz>=0;x.sz--)
      if (x.num[x.sz]!=0) break;
     x.sz++;
}

int main() {
int n,s;
    one.sz=1;one.num[0]=1;
    zero.sz=1;zero.num[0]=0;
    scanf("%d %d",&n,&s);
    if ((s%2)==1) {
       printf("0\n");
       return 0;
    }
    s/=2;
    calc(n,s);
    t=m1[s];
    lsqr(t);
    print(t);
}

Program t1058;{$N+}

Const MaxN = 200;
      Eps  = 1E-15;

Type  TPoint = record X,Y : extended end;
      TPoly = record
        V : array[1..MaxN]of TPoint;
        N : integer;
       end;

Var   CPoly     : TPoly;
      i,j       : integer;

Function GetDist(A,B : TPoint) : extended;
 begin
  GetDist:=Sqrt(Sqr(A.X-B.X)+Sqr(A.Y-B.Y));
 end;

Function GetS(A : TPoly; N : integer) : extended;
Var S   : extended;
    i   : integer;
 begin
  A.V[N+1]:=A.V[1];
  S:=0;
  for i:=1 to N do S:=S+(A.V[i].X-A.V[i+1].X)*(A.V[i].Y+A.V[i+1].Y);
  S:=S/2;
  GetS:=abs(S);
 end;

Procedure MakeMedian(A : TPoly; N : integer;Var last : integer; Var
C : TPoint);
Var i,j,ls : integer;
    s,ps   : extended;
    l,r,m  : TPoint;
    New    : TPoly;
 begin
  ps:=GetS(A,N);
  for ls:=2 to N do
   if 2*GetS(A,ls)>ps then break;
  last:=ls;
  l:=A.V[last-1];
  r:=A.V[last];
  New:=A;
  While True do begin
    m.X:=(l.X+r.X)/2;
    m.Y:=(l.Y+r.Y)/2;
    New.V[last]:=m;
    s:=GetS(New,last);
    if 2*s-ps>Eps then r:=m else
    if 2*s-ps<-Eps then l:=m else break;
   end;
  C:=m;
 end;

Function MakeDist(A : TPoly; N,Cur : integer) : extended;
Var i,j   : integer;
    P     : TPoly;
    Ans   : TPoint;
 begin
  j:=Cur-1;
  for i:=1 to N do begin
    j:=j+1;
    if j>N then j:=1;
    P.V[i]:=A.V[j];
   end;
  MakeMedian(P,N,j,Ans);
  MakeDist:=GetDist(P.V[1],Ans);
 end;

Function FindBest(A : TPoly; last : integer) : extended;
Var i,j      : integer;
    P        : TPoly;
    l,r,m    : TPoint;
    ls,rs,ms : extended;
 begin
  j:=last-1;
  for i:=2 to A.N+1 do begin
    j:=j+1;
    if j>A.N then j:=1;
    P.V[i]:=A.V[j];
   end;
  P.N:=A.N+1;
  l:=P.V[P.N];
  r:=P.V[2];
  While True do begin
    m.X:=(l.X+r.X)/2;
    m.Y:=(l.Y+r.Y)/2;
    P.V[1]:=m;
    ms:=MakeDist(P,P.N,1);
    P.V[1]:=l; ls:=MakeDist(P,P.N,1);
    P.V[1]:=r; rs:=MakeDist(P,P.N,1);
    if abs(ls-ms)<Eps then break;
    if ls>rs then begin
      if ms>rs then l:=m else r:=m;
     end else begin
      if ms>ls then r:=m else l:=m;
     end;
   end;
  FindBest:=ms;
 end;

Procedure Solve;
Var i,j,ok_i   : integer;
    m          : array[0..MaxN]of extended;
    b1,b2      : extended;
    Ans        : String[100];
 begin
  for i:=1 to CPoly.N do
   m[i]:=MakeDist(CPoly,CPoly.N,i);
  m[0]:=m[CPoly.N];
  m[CPoly.N+1]:=m[1];
  for j:=1 to CPoly.N do
   if m[j]<m[j-1] then
    if m[j]<m[j+1] then break;
  b1:=FindBest(CPoly,1);
  for j:=2 to CPoly.N do begin
   b2:=FindBest(CPoly,j+1);
   if b2<b1 then b1:=b2;
  end;
  if b1<b2 then Str(b1:0:8,Ans) else Str(b2:0:8,Ans);
  While Ans[length(Ans)]='0' do delete(Ans,length(Ans),1);
  if Ans[length(Ans)]='.' then delete(Ans,length(Ans),1);
  Writeln(Ans);
 end;

begin
 Read(CPoly.N);
 for i:=1 to CPoly.N do Read(CPoly.V[i*2].X,CPoly.V[i*2].Y);
 for i:=2 to CPoly.N do begin
   CPoly.V[i*2-1].X:=(CPoly.V[i*2-2].X+CPoly.V[i*2].X)/2;
   CPoly.V[i*2-1].Y:=(CPoly.V[i*2-2].Y+CPoly.V[i*2].Y)/2;
  end;
 CPoly.V[1].X:=(CPoly.V[CPoly.N*2].X+CPoly.V[2].X)/2;
 CPoly.V[1].Y:=(CPoly.V[CPoly.N*2].Y+CPoly.V[2].Y)/2;
 CPoly.N:=CPoly.N*2;
 Solve;
end.

why the first program passed sample input but the second one didn't ?

the first :

#include <stdio.h>
#include <string.h>
void main() {
char line[10000];
gets(line);
puts("New Year Phone Survey for ACM ICPC - Health vs greeting style");
puts("Q01 Hello!");
puts(" H Hello!");
puts(" Y Yes!");
puts(" * Uhm...");
puts(" . (silence)");
puts(" @ (other)");
puts("Q02 How are you?");
puts(" H Hello!");
puts(" Y Yes!");
puts(" F Fine!");
puts(" Q Who are you?");
puts(" @ (other)");
puts("");
puts("       Q02:H Q02:Y Q02:F Q02:Q Q02:@ TOTAL");
puts(" Q01:H     2     0     1     1     1     5");
puts("         40%    0%   20%   20%   20%  100%");
puts("         66%    0%   50%  100%   33%   50%");
puts(" Q01:Y     0     1     1     0     0     2");
puts("          0%   50%   50%    0%    0%  100%");
puts("          0%  100%   50%    0%    0%   20%");
puts(" Q01:*     0     0     0     0     0     0");
puts("           -     -     -     -     -     -");
puts("          0%    0%    0%    0%    0%    0%");
puts(" Q01:.     1     0     0     0     2     3");
puts("         33%    0%    0%    0%   67%  100%");
puts("         34%    0%    0%    0%   67%   30%");
puts(" Q01:@     0     0     0     0     0     0");
puts("           -     -     -     -     -     -");
puts("          0%    0%    0%    0%    0%    0%");
puts(" TOTAL     3     1     2     1     3    10");
puts("         30%   10%   20%   10%   30%  100%");
puts("        100%  100%  100%  100%  100%  100%");
puts("");
puts("New Year Phone Survey for ACM ICPC - Politeness matrix");
puts("Q02 How are you?");
puts(" H Hello!");
puts(" Y Yes!");
puts(" F Fine!");
puts(" Q Who are you?");
puts(" @ (other)");
puts("BYE Happy New Year!");
puts(" Y You too.");
puts(" * (censored)");
puts(" @ (other)");
puts(" . (hang up)");
puts("");
puts("       BYE:Y BYE:* BYE:@ BYE:. TOTAL");
puts(" Q02:H     0     0     3     0     3");
puts("          0%    0%  100%    0%  100%");
puts("          0%    0%  100%    0%   30%");
puts(" Q02:Y     1     0     0     0     1");
puts("        100%    0%    0%    0%  100%");
puts("         33%    0%    0%    0%   10%");
puts(" Q02:F     2     0     0     0     2");
puts("        100%    0%    0%    0%  100%");
puts("         67%    0%    0%    0%   20%");
puts(" Q02:Q     0     1     0     0     1");
puts("          0%  100%    0%    0%  100%");
puts("          0%  100%    0%    0%   10%");
puts(" Q02:@     0     0     0     3     3");
puts("          0%    0%    0%  100%  100%");
puts("          0%    0%    0%  100%   30%");
puts(" TOTAL     3     1     3     3    10");
puts("         30%   10%   30%   30%  100%");
puts("        100%  100%  100%  100%  100%");
puts("");
whil

#include <fstream.h>

int a[10002];
int n,s,i;
int main()
{
 cin>>n>>s; a[n]=1;
 for(i=n-1; i>=s; i--)
 {
  int m=0;
  for(int j=1; j<=n-i; j++)
   if(100*j%i == 0)
   if(a[j+i]>m) m = a[j+i];
  a[i] = m + 1;
 }
 int max = 0;
 for(i=n; i>=s; i--)
   if(a[i]>max) max = a[i];
 cout<<max;
 return 0;
}

How do you use only 2x500 numbers???

Here is my solution:

#include <fstream.h>
#include <math.h>

int main()
{
 // p*(2*a+p-1) = 2*n  ==>
 long n; cin>>n; n*=2;
 for(long p=sqrt(n); p>1; p--)
  if(n%p==0) if(n/p>p && (n/p-p)%2)
  {cout<<(n/p-p+1)/2<<' '<<p<<endl; return 0;}
 return 0;
}

Best regards!

Who can give me the answers ? Thank you !

 '%' like '[%[]]'
 '[]' like '[[]]'