Форум Всеукраїнської інтернет-олімпіади NetOI

program Army;

//{$DEFINE test}

const
  MaxCm = 100000;

type
  TArrayOfCmn = array[0..MaxCm] of Int64;

var
  C_val: TArrayOfCmn;
  Cu   : array[0..MaxCm] of Boolean;

procedure Int2String(a: Int64; var S: string);

  function Str100(i: Integer): string;
  begin
    Str100 := Chr(i div 10 + Ord('0')) + Chr(i mod 10 + Ord('0'));
  end;

var
  R:      Integer;
  Is_Neg: Boolean;
begin
  S := '';
  Is_Neg := a<0;
  if Is_Neg then a:=-a;
  repeat
    R:=a mod 100;
    a:=a div 100;
    Insert(Str100(R), S, 1);
  until (a=0) or (Length(S) = 254);
  while (Length(S) > 1) and (S[1] = '0') do Delete(S, 1, 1);
  if Is_Neg then Insert('-', S, 1);
end;

procedure C(const M, N: LongInt; var Res: Int64);
var
  NC: Int64;
  I: LongInt;
begin
  if N>M then
    Res:=0
  else if Cu[M]{(C_val[M]<>nil)and(C_val[M]^[N]<>nil)} then
    Res:=C_val[M]
  else if N=1 then
    Res:=M
  else if N=0 then
    Res:=0
  else if N=M then
    Res:=1
  else begin
    I:=M;
    while (I>N)and(not Cu[i]) do
      Dec(I);
    if I=N then
      NC:=1
    else
      NC:=C_val[i];
    while I<M do begin
      NC:=(NC*(I+1)) div (I+1-N);
      Inc(I);
      C_val[i]:=NC;
      Cu[i]:=True;
    end;
    Res:=NC;
  end;
  Cu[M]:=True;
  C_val[M]:=Res;
end;

procedure ReadData;
var
  min, v, op, I, N, K: LongInt;
  Count, cnt_i: Int64;
  Res: String;
begin
  Read(N, K);
  if K=0 then begin
    WriteLn(N);
    Exit;
  end;
  FillChar(Cu, SizeOf(Cu), 0);
  Read(v);
  op:=v-1;
  min:=v;
  C(N-1-op, K, Count);
  for I:=2 to N do begin
    Read(v);
    if v>min then begin
      op:=op+(v-min)-1;
      min:=v;
    end else
      op:=op-1;
    C(N-I-op, K, cnt_i);
    Count:=Count+cnt_i;
  end;
  Int2String(Count, Res);
  Writeln(Res);
end;

begin
{$IFDEF test}
  Assign(Input, 'Input.dat');
  Assign(Output, 'Output.dat');
  Reset(Input);
  Rewrite(Output);
{$ENDIF}
  ReadData;
{$IFDEF test}
  Close(Output);
  Close(Input);
{$ENDIF}
end.

#define NetOI
#include<stdio.h>
#define AddEdge(a,b,n)\
    if(A[a][b]==0){\
        Adj[a][++*Adj[a]]=b;\
        Adj[b][++*Adj[b]]=a;\
    }\
    A[a][b]+=n;\
    A[b][a]+=n;\
    C[a]=!C[a];\
    C[b]=!C[b]

#define AddVertex(v)\
    if(HVI[v]==-1){\
        HV[VN]=v;\
        HVI[v]=VN++;\
    }\
    v=HVI[v]

char HVI[51];
char HV[50],VN;

bool C[50];

short A[50][50],N;
char R[1002];
short RN=0;
char Adj[50][51];

void Search(char v){
    static char vi;
    char i=1;
    for(;i<=*Adj[v];i++){
        vi=Adj[v][i];
        while(A[v][vi]){
            A[v][vi]--;
            A[vi][v]--;
            N--;
            Search(vi);
            vi=Adj[v][i];
        }
    }
    R[RN++]=v;
}

int main(){
#ifndef NetOI
    *stdin=*fopen("NewDomino.in","r");
#endif
    scanf("%d",&N);
    short i=0,a,b;
    for(;i<=50;i++)
        HVI[i]=-1;
    for(i=0;i<N;i++){
        scanf("%d%d",&a,&b);
        AddVertex(a);
        AddVertex(b);
        AddEdge(a,b,1);
    }
    for(i=0;i<VN;i++)
        if(C[i])
            goto NA;    
    Search(0);
    if(N||R[0]!=R[RN-1]){
NA:
        printf("-1");
    }else
        for(RN-=2;RN>=0;RN--)
            printf("%d %d ",int(HV[R[RN+1]]),int(HV[R[RN]]));
#ifndef NetOI
    fclose(stdin);
#endif
    return 0;
}

#define    NetOI
#include<stdio.h>

#define swap(a,b)    a=(a^=b)^(b^=a)

short N,x[53];
unsigned long R[52][52];

int main(){
#ifndef NetOI
    *stdin=*fopen("DSP2.in","r");
#endif
    scanf("%d%d",x+52,&N);
    short i=1;
    for(N++;i<N;i++)
        scanf("%d",&x[i]);
    x[N]=x[52];
    short j;
    short in,n=N-1,k;
    unsigned long m;
    for(i=1;i<n;i++){
        k=i+1;
        for(j=k+1;j<=n;j++)
            if(x[j]<x[k])
                k=j;
        if(x[k]<x[i])
            swap(x[k],x[i]);
    }
    for(i=1,j=1;i<=N;i++)
        if(x[i]!=x[i-1])
            x[j++]=x[i];
    n=(N=j-1)-1;
    switch(N) {
    case 0:
        printf("%d","0");
        break;
    case 1:
        printf("%d",x[n]);
        break;
    default:
        for(i=N-2;i>=0;i--)
            R[i][i+2]=x[i+2]-x[i];
        for(j=3;j<=N;j++)
            for(i=0;i<=N-j;i++){
                R[i][n=(in=i+j)]=-1;in-=1;
                for(k=i+1;k<=in;k++){
                    m=R[i][k]+R[k][n];
                    if(m<R[i][n])R[i][n]=m;
                }R[i][n]+=x[n]-x[i];
            }
        printf("%lu",R[0][N]);
    }
#ifndef NetOI
    fclose(stdin);
#endif
    return 0;
}

#define NetOI
#include<stdio.h>

long a[100000],b[100000],n,m;
long long f[2][100000];
char c[100000];

#define f(i)    f[J][i]
#define g(i)    f[K][i]
#define SwapLayers    K=J,J^=1
#define swap(a,b)    a=(a^=b)^(b^=a)
#define sgn(a)    (a<0?-1:1)
#define min(a,b)    (a<b?a:b)
#define rN        13
#define abs(a)    (a<0?-a:a)

short J=1,K=0,y=1;
long long r[rN];

long long F(int x){
    short i=0;
    long x0=x-1;
    long d,min,max;
    if((d=a[x]-a[x0])>0)
        r[0]=g(x0);
    else r[0]=0;
    max=abs(d);
    if(max==1)
        return f(x0)+r[0];
    min=0;
    for(i=1;i<rN;i++){
        if((d=a[x]-a[x0-i])>0)    r[i]=r[i-1]+g(x0-i);
        else {    
            r[i]=r[i-1];d=-d;
        }
        if(d==1)return f(x0-i)+r[i];
        if(d<max){
            max=d;
            min=i;
        }
    }
    i=min;
    x0-=i;
    min=a[x0];
    max=a[x];
    if(min>max)
        swap(min,max);
    long long R=0;
    long j=min+1;
    for(min=y-1;j<max;j++)
        if(b[j]<x0&&b[j]>=min)
            R+=g(b[j]);
    if(a[x0]>a[x])
        R=-R;
    R+=f(x0);
    return r[i]+R;
}

bool CalcC(){
    long l,r,k,i,R=1,p[12];
    c[0]=1;
    for(p[1]=0,i=1;i<n;i++){
        l=1;r=R;
        while(l<=r)
            if(a[p[k=(l+r)/2]]>a[i])r=k-1;
            else l=k+1;
        if(r<11)
            r++;
        if(r>R)
            p[R=r]=i;
        else if(a[i]<a[p[r]])
            p[r]=i;
        c[i]=r;
    }
    if(R<=m)
        return false;
    return true;
}

int main(){
#ifndef NetOI
    *stdin=*fopen("Army.in","r");
#endif
    scanf("%ld%ld",&n,&m);
    long i=0,t;
    for(;i<n;i++){
        scanf("%ld",a+i);
        b[--a[i]]=i;
        f[0][i]=1;
    }
    if(CalcC()){
        long long R;
        for(;y<=m;y++,SwapLayers){
            for(i=min(y+rN,n)-1;i>=y;i--){
                if(c[i]>y){
                    for(R=0,t=y-1;t<i;t++)
                        if(a[t]<a[i])
                            R+=g(t);
                    f(i)=R;
                }else f(i)=0;
            }
            for(i=y+rN;i<n;i++)
                if(c[i]>y)
                    f(i)=F(i);
                else f(i)=0;
        }
        if(c[m]>m)
            R=g(m);
        else R=0;
        for(i=m+1;i<n;i++)
            if(c[i]>m)
                R+=g(i);
        printf("%I64d",R);
    }else printf("0");
#ifndef NetOI
    fclose(stdin);
    return 0;
#endif
}

#define NetOI
#include<stdio.h>
#include<math.h>

#define sqr(a)    (a)*(a)
#define S(x0,y0,x1,y1)    sqrt(sqr((x1)-(x0))+sqr((y1)-(y0)))
#define S2(x0,y0,x1,y1)    (sqr((x1)-(x0))+sqr((y1)-(y0)))
#define Eps        1E-16
#define Eps2    1E-8
#define MaxPath    1E9
const long double PI=3.1415926535897932384626433832795;

struct Point{
    double x,y;
};

inline bool CrossLine(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3){
    double    a0=y1-y0,b0=x0-x1,c0=-(x0*a0+y0*b0),
            a2=y3-y2,b2=x2-x3,c2=-(x2*a2+y2*b2);
#define f0(x,y)    (a0*x+b0*y+c0)
#define f2(x,y)    (a2*x+b2*y+c2)
    return (f0(x2,y2)*f0(x3,y3)<=-Eps && f2(x0,y0)*f2(x1,y1)<=-Eps);
#undef f0
#undef f2
}

class Polygon{
private:
    template<class T>
    static T Abs(T a){
        return (a<0?-a:a);
    }
public:
    double x,y;
    Point p[20];
    double r,R;
    short n;
    void Read(){
        scanf("%d%lf%lf%lf%lf",&n,&x,&y,&p[0].x,&p[0].y);
        short i=1;
        R=S(x,y,p[0].x,p[0].y);
        double A=atan2(p[0].x-x,p[0].y-y),dA=2*PI/n;
        for(;i<n;i++){
            p[i].x=x+cos(A+dA*i)*R;
            p[i].y=y+sin(A+dA*i)*R;
        }
        double tX=(p[1].x+p[0].x)/2-x,tY=(p[1].y+p[0].y)/2-y;
        r=sqrt(tX*tX+tY*tY);
    }
    bool Cross(double x0,double y0,double x1,double y1){
        double a=y1-y0,b=x0-x1,c=-(x0*a+y0*b);
        double C2=a*a+b*b;
        double H=(a*x+b*y+c)/sqrt(C2);
        if(H<0)H=-H;
        double L0=S2(x,y,x0,y0);
        double L1=S2(x,y,x1,y1);
        if(C2<Abs(L1-L0)+Eps2 && L0+Eps2>=R*R && L1+Eps2>=R*R)
            return false;
        if(H+Eps>R)
            return false;
        if(H<r-Eps)
            return true;
        short i=0;
        for(i=1;i<n;i++)
            if(::CrossLine(x0,y0,x1,y1,p[i].x,p[i].y,p[i-1].x,p[i-1].y))
                return true;
        return false;
    }
}P[10];

short N,VN=2;
unsigned char *Adj[202];
unsigned char C[202];
#define AddEdge(v,e)    Adj[v][C[v]++]=e
Point* p[202],CP[2];
double S[202];

bool VerifyLine(double x0,double y0,double x1,double y1){
    short i=0;
    for(;i<N;i++)
        if(P[i].Cross(x0,y0,x1,y1))
            return false;
    return true;
}

inline void Relax(unsigned char i,unsigned char j){
    double L=S[i]+S(p[i]->x,p[i]->y,p[j]->x,p[j]->y);
    if(S[j]>L)S[j]=L;
}

int main(){
#ifndef NetOI
    *stdin=*fopen("Lake.in","r");
#endif
    scanf("%lf%lf%lf%lf%d",&CP[0].x,&CP[0].y,&CP[1].x,&CP[1].y,&N);
    short i,j,k,LN;
    for(i=0;i<N;){
        P[i].Read();
        if(P[i].R>=Eps)
            i++;
        else N--;
    }
    for(i=0;i<202;Adj[i++]=new unsigned char[202])
    p[0]=&CP[0];
    p[1]=&CP[1];
    if(VerifyLine(p[0]->x,p[0]->y,p[1]->x,p[1]->y))
        printf("%.16lf",double(S(p[0]->x,p[0]->y,p[1]->x,p[1]->y)));
    else{
        for(i=0;i<N;i++)
            for(j=0,LN=VN;j<P[i].n;j++,VN++){
                p[VN]=&P[i].p[j];
                k=LN+(j+1)%P[i].n;
                AddEdge(VN,k);
                AddEdge(k,VN);
                for(k=0;k<LN;k++)
                    if(VerifyLine(p[VN]->x,p[VN]->y,p[k]->x,p[k]->y)){
                        AddEdge(VN,k);
                        AddEdge(k,VN);
                    }
            }
        VN--;
        for(S[0]=0,i=1;i<=VN;S[i++]=MaxPath);
        unsigned char Q[202],T;
        for(T=0;T<VN;T++)
            Q[T]=T+1;
        for(i=0;i<C[0];i++)
            Relax(0,Adj[0][i]);
        unsigned char MinI;
        for(;T;Q[MinI]=Q[--T]){
            MinI=0;
            for(i=1;i<T;i++){
                if(S[Q[i]]<S[Q[MinI]])
                    MinI=i;
            }
            i=Q[MinI];
            for(j=0;j<C[i];j++)
                Relax(i,Adj[i][j]);
        }
        if(S[1]<MaxPath)
            printf("%.lf",S[1]);
        else printf("-1");
    }
#ifndef NetOI
    fclose(stdin);
#endif
    for(i=0;i<VN;i++)
        delete Adj[i];
    return 0;
}

#define NetOI
#include<stdio.h>

short aN=0,bN=0;
unsigned char *a=new unsigned char[10001],*b=new unsigned char[10001];
short SSS=0;
#define q    32768
#define fq(v)    ((v)%q)
#define p    53
short    *L=new short[q],
        *Ta=new short[10000],
        *Tb=new short[10000];
long P;
#define T0(T0,Ai)    fq(fq(long(T0)*p)+Ai)
#define Ti(Ti1,Ai1,Aid1)    fq(fq(p*long(Ti1))+fq(q-fq(long(Ai1)*P))+Aid1)

inline bool F(short d){
    short i,Na=aN-d+1,Nb=bN-d+1;
    for(i=0,P=1;i<d;i++)
        P=fq(P*p);
    Ta[0]=0;
    for(i=0;i<d;i++)
        Ta[0]=T0(Ta[0],a[i]);
    L[Ta[0]]=-1;
    for(Na--,i=0;i<Na;i++)
        L[Ta[i+1]=Ti(Ta[i],a[i],a[i+d])]=-1;
    Tb[0]=0;
    for(i=0;i<d;i++)
        Tb[0]=T0(Tb[0],b[i]);
    L[Tb[0]]=-1;
    for(Nb--,i=0;i<Nb;i++)
        L[Tb[i+1]=Ti(Tb[i],b[i],b[i+d])]=-1;
    short t;
    for(i=0;i<=Na;i++){
        t=Ta[i];
        Ta[i]=L[t];
        L[t]=i;
    }
    short j,k;
    for(j=0;j<=Nb;j++)
        for(i=L[Tb[j]];i>=0;i=Ta[i]){
            for(k=0;a[i+k]==b[j+k]&&k+i<aN&&k+j<bN;k++);
            if(k>=d){
                SSS=k;
                return true;
            }
        }
    return false;
}

int main(){
#ifndef NetOI
    *stdin=*fopen("Message.in","r");
#endif
    gets((char*)a);
    gets((char*)b);
    for(;a[aN];aN++);
    for(;b[bN];bN++);
    short L=1,R=(aN<bN?aN:bN),D;
    do {
        if(F(D=(L+R)/2))
            L=SSS+1;
        else
            R=D-1;
    } while(L<=R);
    printf("%d",SSS);
#ifndef NetOI
    fclose(stdin);
#endif
    delete[] a,b,L,Ta,Tb;
    return 0;
}

{$APPTYPE CONSOLE}
{$B-,R-}
const
 maxn=50;
 maxk=1000;
var
 a:array[1..maxn,1..maxn] of smallint;
 num:array[1..maxn] of smallint;
 st:array[1..maxk+2] of byte;
 numst,numpath:smallint;
 n,k,i,aa,bb,tek:smallint;
 path:array[1..maxk+2] of byte;
procedure Search(ver:byte);
var
 i:byte;
begin
 i:=1;
 while (i<=n)and(a[ver,i]=0)do inc(i);
 if i<=n then
  begin
   dec(a[ver,i]);
   dec(a[i,ver]);
   inc(numst);
   st[numst]:=i;
   Search(i);
  end;
end;
begin
 fillchar(a,sizeof(a),0);
 fillchar(num,sizeof(num),0);
 n:=0;
 read(k);
 for i:=1 to k do
  begin
   read(aa,bb);
   if aa>n then n:=aa;
   if bb>n then n:=bb;
   inc(num[aa]);
   inc(num[bb]);
   inc(a[aa,bb]);
   inc(a[bb,aa]);
  end;
 for i:=1 to n do if odd(num[i]) then
  begin
   writeln(-1);
   halt;
  end;
 tek:=1;
 while num[tek]=0 do inc(tek);
 numst:=0;
 numpath:=0;
 inc(numst);
 st[numst]:=tek;
 while numst>0 do
  begin
   tek:=st[numst];
   Search(tek);
   inc(numpath);
   path[numpath]:=tek;
   dec(numst);
  end;
 write(path[1]);
 for i:=2 to numpath-1 do write(' ',path[i],' ',path[i]);
 writeln(' ',path[numpath]);
end.

{$APPTYPE CONSOLE}
{$B-,R-}
const
 maxn=50;
 nv=1000000;
var
 a:array[1..maxn+2] of smallint;
 f:array[1..maxn+2,1..maxn+2] of longint;
 l,n,i,j:smallint;
procedure calc(i,j:byte);
var
 k:byte;
 tek:longint;
begin
 if f[i,j]<>nv then exit;
 for k:=i+1 to j-1 do
  begin
   if f[i,k]=nv then calc(i,k);
   if f[k,j]=nv then calc(k,j);
   tek:=f[i,k]+f[k,j]+a[j]-a[i];
   if tek<f[i,j] then f[i,j]:=tek;
  end;
end;
begin
 a[1]:=0;
 read(l,n);
 for i:=1 to n do read(a[i+1]);
 inc(n);
 a[n+1]:=l;
 inc(n);
 for i:=1 to n do
  for j:=1 to n do
   f[i,j]:=nv;
 for i:=1 to n do f[i,i]:=0;
 for i:=1 to n-1 do f[i,i+1]:=0;
 calc(1,n);
 writeln(f[1,n]);
end.

{$APPTYPE CONSOLE}
{$B-,R-}
{$MAXSTACKSIZE $01000000}
const
 maxn=100000;
 maxtree=300000;
 maxk=11;
type
 treeel=record
  a,b:longint;
  count:int64;
  left,right:longint;
 end;
var
 i,n,h:longint;
 j,k:byte;
 height:array[1..maxn] of longint;
 ans:array[1..maxn] of int64;
 res:int64;
 tree:array[1..maxtree] of treeel;
function BuildTree(a,b:longint):longint;
var
 mid,tekh:longint;
begin
 inc(h);
 tekh:=h;
 tree[tekh].a:=a;
 tree[tekh].b:=b;
 if a<b then
  begin
   mid:=(a+b)div 2;
   tree[tekh].left:=BuildTree(a,mid);
   tree[tekh].right:=BuildTree(mid+1,b);
  end;
 BuildTree:=tekh;
end;
procedure UpdateTree(tek:longint;index:longint;c:int64);
var
 mid:longint;
begin
 if c<>0 then
  while tek<>0 do
   begin
    inc(tree[tek].count,c);
    mid:=(tree[tek].a+tree[tek].b) div 2;
    if index<=mid then tek:=tree[tek].left else tek:=tree[tek].right;
   end;
end;
function Num(tek,h:longint):int64;
var
 ans:int64;
 mid:longint;
begin
 ans:=0;
 while (tek<>0)and(tree[tek].count<>0) do
  begin
   mid:=(tree[tek].a+tree[tek].b) div 2;
   if h>=mid then
    begin
     inc(ans,tree[tree[tek].left].count);
     tek:=tree[tek].right;
    end else tek:=tree[tek].left;
  end;
 Num:=ans;
end;
begin
 read(n,k);
 for i:=1 to n do read(height[i]);
 if k+1>n then
  begin
   writeln(0);
   halt;
  end;
 h:=0;
 fillchar(tree,sizeof(tree),0);
 BuildTree(1,n);
 for i:=1 to n do ans[i]:=1;
 for j:=1 to k do
  begin
   for i:=1 to h do tree[i].count:=0;
   for i:=1 to n do
    begin
     UpdateTree(1,height[i],ans[i]);
     ans[i]:=Num(1,height[i]-1);
    end;
  end;
 res:=0;
 for i:=1 to n do inc(res,ans[i]);
 writeln(res);
end.

{$APPTYPE CONSOLE}
{$B-,R-,N+}
const
 maxlake=10;
 maxver=20;
 maxn=maxlake*maxver+2;
 delta=1e-9;
 nv=1e9;
type
 point=record
  x,y:extended;
 end;
 lake=record
  n:byte;
  v:array[1..maxver+2] of point;
 end;
var
 ver:array[1..maxn] of point;
 a:array[1..maxn,1..maxn] of extended;
 f:array[0..maxn] of extended;
 stver,endver,zentr,pp,next:point;
 ang:extended;
 numlake,numver,i,j,k,l,{s,}x,y,n:byte;
 mnog:array[1..maxlake+2] of lake;
 v1,v2,v3:point;
 flag:boolean;
 sign1,sign2:shortint;
 p1,p2,zn:boolean;
 q:array[1..maxn] of byte;
 min,numzero:byte;
function sign(a:extended):shortint;
begin
 if abs(a)<delta then sign:=0 else
 if a>0 then sign:=1 else
 {if a<0 then }sign:=-1;
end;
begin
 for i:=1 to maxn do
  for j:=1 to maxn do
   a[i,j]:=nv;
 n:=0;
 read(stver.x,stver.y,endver.x,endver.y);
 read(numlake);
 for i:=1 to numlake do
  begin
   read(numver);
   mnog[i].n:=numver;
   ang:=2*Pi/numver;
   read(zentr.x,zentr.y,pp.x,pp.y);
   mnog[i].v[1]:=pp;
   inc(n);
   ver[n]:=pp;
   for j:=2 to numver do
    begin
     next.x:=(pp.x-zentr.x)*cos(ang)-(pp.y-zentr.y)*sin(ang)+zentr.x;
     next.y:=(pp.y-zentr.y)*cos(ang)+(pp.x-zentr.x)*sin(ang)+zentr.y;
     pp:=next;
     inc(n);
     ver[n]:=pp;
     mnog[i].v[j]:=pp;
    end;
   mnog[i].v[numver+1]:=mnog[i].v[1];
  end;
 inc(n);
 ver[n]:=stver;
 inc(n);
 ver[n]:=endver;
 k:=0;
 inc(numlake);
 mnog[numlake].n:=1;
 mnog[numlake].v[1]:=stver;
 mnog[numlake].v[2]:=stver;
 inc(numlake);
 mnog[numlake].n:=1;
 mnog[numlake].v[1]:=endver;
 mnog[numlake].v[2]:=endver;
 for i:=1 to numlake do
  begin
   for j:=k+1 to k+mnog[i].n-1 do
    begin
     a[j,j+1]:=sqrt(sqr(ver[j].x-ver[j+1].x)+sqr(ver[j].y-ver[j+1].y));
     a[j+1,j]:=a[j,j+1];
    end;
   a[mnog[i].n+k,1+k]:=sqrt(sqr(ver[mnog[i].n+k].x-ver[1+k].x)+sqr(ver[mnog[i].n+k].y-ver[1+k].y));
   a[1+k,mnog[i].n+k]:=a[mnog[i].n+k,1+k];
   inc(k,mnog[i].n);
  end;
 k:=0;
 for i:=1 to numlake do
  begin
   for j:=k+1 to k+mnog[i].n do
    for l:=k+mnog[i].n+1 to n do
     begin
      flag:=true;
      x:=1;
      {s:=0;}
      if (abs(ver[l].x-ver[j].x)<delta)and(abs(ver[l].y-ver[j].y)<delta) then x:=numlake+1;
      while (x<=numlake)and flag do
       begin
        y:=1;
        while (y<=mnog[x].n)and flag do {if (s+y<>j)and(s+y<>l)and(s+y mod mnog[x].n+1<>j)and(s+y mod mnog[x].n+1<>l) then}
         begin
          numzero:=0;
          v1.x:=ver[l].x-ver[j].x;
          v1.y:=ver[l].y-ver[j].y;
          v2.x:=mnog[x].v[y].x-ver[j].x;
          v2.y:=mnog[x].v[y].y-ver[j].y;
          v3.x:=mnog[x].v[y+1].x-ver[j].x;
          v3.y:=mnog[x].v[y+1].y-ver[j].y;
          sign1:=sign(v1.x*v2.y-v1.y*v2.x);
          sign2:=sign(v1.x*v3.y-v1.y*v3.x);
          inc(numzero,2-abs(sign1)-abs(sign2));
          if sign1<>sign2 then p1:=true else p1:=false;
          v1.x:=mnog[x].v[y+1].x-mnog[x].v[y].x;
          v1.y:=mnog[x].v[y+1].y-mnog[x].v[y].y;
          v2.x:=ver[j].x-mnog[x].v[y].x;
          v2.y:=ver[j].y-mnog[x].v[y].y;
          v3.x:=ver[l].x-mnog[x].v[y].x;
          v3.y:=ver[l].y-mnog[x].v[y].y;
          sign1:=sign(v1.x*v2.y-v1.y*v2.x);
          sign2:=sign(v1.x*v3.y-v1.y*v3.x);
          inc(numzero,2-abs(sign1)-abs(sign2));
          if sign1<>sign2 then p2:=true else p2:=false;
          if (p1 and p2)and(numzero<2) then flag:=false;
          inc(y);
         end;{ else inc(y);}
        {inc(s,mnog[x].n);}
        inc(x);
       end;
      if flag then
       begin
        a[j,l]:=sqrt(sqr(ver[l].x-ver[j].x)+sqr(ver[l].y-ver[j].y));
        a[l,j]:=a[j,l];
       end;
      end;
    inc(k,mnog[i].n);
  end;
 fillchar(q,sizeof(q),0);
 for i:=1 to n do f[i]:=nv;
 q[n-1]:=1;
 f[n-1]:=0;
 flag:=true;
 while flag do
  begin
   min:=0;
   flag:=false;
   for i:=1 to n do if (q[i]=1)and((min=0)or(f[i]<f[min]))then
    begin
     flag:=true;
     min:=i;
    end;
   if min<>0 then q[min]:=2;
   if flag then
    for i:=1 to n do if a[min,i]+f[min]<f[i] then
     begin
      q[i]:=1;
      f[i]:=a[min,i]+f[min];
     end;
  end;
 writeln(f[n]);
end.

{$APPTYPE CONSOLE}
{$B-,R-,H+}
const
 maxl=10000;
 base=257;
 modul=299993;
type
 tlist=record
  pol:smallint;
  next:longint;
 end;
var
 s1,s2,s:string;
 len1,len2:smallint;
 hash:array[1..modul] of record
  first,last:smallint;
 end;
 h:smallint;
 table:array[1..maxl] of tlist;
function CheckStr(i,j,k:smallint):boolean;
var
 l:smallint;
begin
 l:=0;
 while (l<k)and(s1[i+l]=s2[j+l])do inc(l);
 if l=k then CheckStr:=true else CheckStr:=false;
end;
function CheckSeq(k:smallint):boolean;
var
 i:smallint;
 tekhash,maxdigpow:longint;
 teklist:smallint;
begin
 fillchar(hash,sizeof(hash),0);
 h:=0;
 tekhash:=0;
 maxdigpow:=1;
 for i:=1 to len1 do
  begin
   tekhash:=(base*tekhash+Ord(s1[i])) mod modul;
   if i<=k then maxdigpow:=(maxdigpow*base) mod modul else
    tekhash:=(tekhash+modul-(maxdigpow*Ord(s1[i-k]))mod modul)mod modul;
   if i>=k then
    begin
     if hash[tekhash].first<>0 then
      begin
       teklist:=hash[tekhash].last;
       inc(h);
       table[teklist].next:=h;
       teklist:=table[teklist].next;
       table[teklist].pol:=i-k+1;
       table[teklist].next:=0;
       hash[tekhash].last:=teklist;
      end else
      begin
       inc(h);
       hash[tekhash].first:=h;
       teklist:=hash[tekhash].first;
       table[teklist].pol:=i-k+1;
       table[teklist].next:=0;
       hash[tekhash].last:=teklist;
      end;
    end;
  end;
 tekhash:=0;
 maxdigpow:=1;
 for i:=1 to len2 do
  begin
   tekhash:=(base*tekhash+Ord(s2[i])) mod modul;
   if i<=k then maxdigpow:=(maxdigpow*base) mod modul else
    tekhash:=(tekhash+modul-(maxdigpow*Ord(s2[i-k]))mod modul)mod modul;
   if (i>=k)and(hash[tekhash].first<>0)then
    begin
     teklist:=hash[tekhash].first;
     repeat
      if CheckStr(table[teklist].pol,i-k+1,k) then
       begin
        CheckSeq:=true;
        exit;
       end;
      teklist:=table[teklist].next;
     until teklist=0;
    end;
  end;
 CheckSeq:=false;
end;
function GetMaxSubseqLength:smallint;
var
 l,r,tek:smallint;
begin
 l:=1;
 r:=len1;
 if not CheckSeq(l) then
  begin
   GetMaxSubseqLength:=0;
   exit;
  end;
 if CheckSeq(r) then
  begin
   GetMaxSubseqLength:=r;
   exit;
  end;
 while l<>r do
  begin
   tek:=(l+r) div 2+1;
   if CheckSeq(tek) then l:=tek else r:=tek-1;
  end;
 GetMaxSubseqLength:=l;
end;
begin
 readln(s1);
 readln(s2);
 if length(s1)>length(s2) then
  begin
   s:=s1;
   s1:=s2;
   s2:=s;
  end;
 len1:=length(s1);
 len2:=length(s2);
 writeln(GetMaxSubseqLength);
end.