Program ISBN;
const
n=10;
F=11;
var
s:string;
i,p,ans:longint;
begin
ans:=0;
readln(s);
if s[n]='X' then s[n]:=char(58);
p:=pos('?',s);
for i:=1 to n do
if i<>p then inc(ans,(ord(s[i])-48)*(10-i+1));
// ans +p*? mod 11 =0
ans:=ans mod F;
ans:=(F-ans) mod F;
for i:=0 to n do
begin
if ((11-p)*i) mod F=ans then
begin
if (p=n) and (i=10) then begin writeln('X'); halt; end;
if (i<10) then begin writeln(i); halt; end;
end;
end;
writeln('-1');
end.
Program P1226;
const
maxn=100;
maxt=10;
var
tt,n,m,i,j,k,ans:longint;
flag:boolean;
a:array[1..maxn] of string;
p:string;
next:array[1..maxn] of longint;
function kmp(a,b:string):boolean;
var
i,j,n,m:longint;
begin
i:=1;j:=0;next[1]:=0;
n:=length(a); m:=length(b);
while (i<m) do
begin
if (j=0) or (b[i]=b[j]) then
begin
inc(i);inc(j);
if (b[i]<>b[j]) then next[i]:=j else next[i]:=next[j];
end else j:=next[j];
end;
i:=0;j:=0;
while (i<=n) and (j<=m) do
begin
if (j=0) or (a[i]=b[j]) then
begin
inc(i);inc(j);
end else j:=next[j];
end;
if (j>m) then exit(true);
exit(false);
end;
function ob_s(a:string):string;
var
i,j,n:longint;
begin
ob_s:=''; n:=length(a);
for i:=n downto 1 do ob_s:=ob_s+a[i];
end;
function compare(a,b:string):boolean;
var
n,m:longint;
begin
n:=length(a);m:=length(b);
if (n<>m) then exit(n<m);
for i:=1 to n do
if a[i]<>b[i] then exit(a[i]<b[i]);
exit(false);
end;
begin
readln(tt);
while (tt>0) do
begin
ans:=0;
readln(n);
for i:=1 to n do readln(a[i]);
for i:=1 to length(a[1]) do
for j:=i to length(a[1]) do
begin
p:=copy(a[1],i,j-i+1);
flag:=true;
for k:=2 to n do
begin
if not((kmp(a[k],p) or kmp(a[k],ob_s(p)))) then
begin
flag:=false; break;
end;
end;
if flag and (length(p)>ans) then ans:=length(p);
end;
writeln(ans);
dec(tt);
end;
end.
Program grid;
const
maxn=10000;
maxm=75;
var
n,m,i,j,k:longint;
a:array[1..maxn] of string;
f:array[1..maxm] of longint;
flag:boolean;
p:array[1..maxn] of longint;
begin
fillchar(f,sizeof(f),0);
readln(n,m);
for i:=1 to n do
begin
readln(a[i]);
for j:=1 to m do
begin
flag:=true;
for k:=j+1 to m do
if a[i][k]<>a[i][k-j] then begin flag:=false; break; end;
if flag then inc(f[j]);
end;
end;
for i:=1 to m do if f[i]=n then break;
m:=i;
for i:=1 to n do delete(a[i],m+1,maxlongint);
j:=0;p[1]:=0;
for i:=2 to n do
begin
while (j>0) and (a[i]<>a[j+1]) do j:=p[j];
if (a[i]=a[j+1]) then inc(j);
p[i]:=j;
end;
n:=n-p[n];
writeln(m*n);
end.
Program Poj3461;
const
maxm=10000;
maxn=1000000;
var
tt,n,m,i,j:longint;
a,b:ansistring;
P:array[1..maxn] of longint;
function kmp:longint;
var
n,m,i,j:longint;
begin
kmp:=0;
n:=length(a);m:=length(b);
P[1]:=0;j:=0;
for i:=2 to m do
begin
while (j>0) and (b[j+1]<>b[i]) do j:=p[j];
if (b[j+1]=b[i]) then inc(j);
p[i]:=j;
end;
j:=0;
for i:=1 to n do
begin
while (j>0) and (b[j+1]<>a[i]) do j:=p[j];
if (b[j+1]=a[i]) then inc(j);
if j=m then
begin
inc(kmp);
j:=p[j];
end;
end;
end;
begin
readln(tt);
while (tt>0) do
begin
readln(b);
readln(a);
writeln(kmp);
dec(tt);
end;
end.
Program Poj1961;
const
maxn=10000000;
var
i,j,tt,n,duan_luo:longint;
next:array[1..maxn] of longint;
a:ansistring;
begin
tt:=1;
while (true) do
begin
readln(n);
if n=0 then break;
readln(a); inc(n); a:=a+'.';
i:=1;j:=0;next[1]:=0;
while (i<=n-1) do
begin
if (j=0) or (a[i]=a[j]) then
begin
inc(i);inc(j);
// if (a[i]<>a[j]) then next[i]:=j else next[i]:=next[j];
next[i]:=j;
end
else j:=next[j];
end;
writeln('Test case #',tt);
for i:=2 to n do
begin
duan_luo:=i-next[i];
if (duan_luo>0) and ((i-1) mod duan_luo=0) and ((i-1) div duan_luo>1) then
writeln(i-1,' ',(i-1) div duan_luo);
end;
// readln;
writeln;
inc(tt);
end;
end.
Program BlueJeans;
const
maxn=60;
maxm=10;
var
tt,i,j,k,n,m:longint;
a:array[1..maxm] of string;
next:array[1..maxn] of longint;
p,ans:string;
flag:boolean;
function kmp(a,s:string):boolean;
var
i,j,n:longint;
begin
n:=length(a);
j:=0; next[1]:=0; i:=1;
while i<n do
begin
if (j=0) or (a[i]=a[j]) then
begin
inc(i); inc(j);
if (a[i]<>a[j]) then next[i]:=j else next[i]:=next[j];
end else j:=next[j];
end;
j:=0; i:=0;
while (i<=maxn) and (j<=n) do
begin
if (j=0) or (a[j]=s[i]) then
begin
inc(i); inc(j);
// if (j=n) then exit(true);
end else j:=next[j];
end;
if j>n then exit(true);
exit(false);
end;
function compare(a,b:string):boolean;
var
i,n,m:longint;
begin
n:=length(a); m:=length(b);
if (n<>m) then exit(n<m);
for i:=1 to n do if (a[i]<>b[i]) then exit(ord(a[i])>ord(b[i]));
exit(false);
end;
begin
readln(tt);
while (tt>0) do
begin
ans:='';
readln(m);
for i:=1 to m do readln(a[i]);
for i:=1 to maxn do
for j:=i to maxn do
begin
p:=copy(a[1],i,j-i+1);
flag:=false;
for k:=2 to m do
begin
if not(kmp(p,a[k])) then begin flag:=true; break; end;
end;
if not(flag) and (compare(ans,p)) then ans:=p;
end;
if length(ans)<3 then writeln('no significant commonalities')
else writeln(ans);
dec(tt);
end;
end.
Program SeekName;
const
maxn=400000;
var
n,i,j,size:longint;
a:ansistring;
ans,next:array[1..maxn] of longint;
begin
while not seekeof do
begin
readln(a); a:=a+'.';
n:=length(a);
j:=0;next[1]:=0;i:=1;
while (i<n) do
begin
if (j=0) or (a[i]=a[j]) then
begin
inc(i);
inc(j);
// if (a[i]<>a[j]) then next[i]:=j else next[i]:=next[j];
next[i]:=j;
end else j:=next[j];
end;
size:=0; j:=n;
repeat
inc(size);
ans[size]:=j-1;
j:=next[j];
until j<=1;
write(ans[size]);
for i:=size-1 downto 1 do write(' ',ans[i]);
writeln;
end;
end.
Program poj3468;
const
maxn=100000;
maxq=100000;
var
n,m,i,j,k:longint;
lazy,t:array[1..maxn*8] of int64;
c:char;
Procedure pushup(root:longint);
begin
t[root]:=t[root*2]+t[root*2+1];
end;
Procedure build(l,r,root:longint);
var
m:longint;
begin
if (l=r) then
begin
read(t[root]);
exit;
end;
m:=(l+r) shr 1;
build(l,m,root*2);
build(m+1,r,root*2+1);
pushup(root);
end;
Procedure Pushdown(l,r,root:longint);
var
m:longint;
begin
m:=(l+r) shr 1;
if (lazy[root]=0) then exit;
inc(lazy[root shl 1],lazy[root]);
inc(lazy[root shl 1+1],lazy[root]);
inc(t[root shl 1],lazy[root]*(m-l+1));
inc(t[root shl 1+1],lazy[root]*(r-(m+1)+1));
lazy[root]:=0;
end;
Procedure update(l,r,nowl,nowr,root,cost:longint);
var
m:longint;
begin
if (l<=nowl) and (nowr<=r) then
begin
inc(lazy[root],cost);
inc(t[root],(nowr-nowl+1)*cost);
exit;
end;
pushdown(nowl,nowr,root);
m:=(nowl+nowr) shr 1;
if (l<=m) then update(l,r,nowl,m,root*2,cost);
if (m+1<=r) then update(l,r,m+1,nowr,root*2+1,cost);
pushup(root);
end;
function query(l,r,nowl,nowr,root:longint):int64;
var
m:longint;
res:int64;
begin
if (l<=nowl) and (nowr<=r) then
begin
exit(t[root]);
end;
pushdown(nowl,nowr,root);
m:=(nowl+nowr) shr 1;
res:=0;
if (l<=m) then res:=res+query(l,r,nowl,m,root*2);
if (m+1<=r) then res:=res+query(l,r,m+1,nowr,root*2+1);
exit(res);
end;
begin
readln(n,m);
fillchar(lazy,sizeof(lazy),0);
build(1,n,1);
readln;
while (m>0) do
begin
read(c);
if c='Q' then
begin
readln(i,j);
writeln(query(i,j,1,n,1));
end
else
begin
readln(i,j,k);
update(i,j,1,n,1,k);
end;
dec(m);
end;
end.
