can anybody tell me what the #32 test is ????
i got wa on this test........thanks a lot /!!!!

I have check all of the datas in 'DISCUSS',every one is true
But I got WA on Testdata26
Any one can tell me what 26 is?
Thanks!
My email:caoyuan9642@163.com

haha
so happy

Something like 2121.

It is subnumber of 1212 1213

But! It can be either 1[212 1]213 or 121[2 121]3.

Correct answer is 3739 (first case), incorrect is 3741 (second case).

Test 1 :    101
Ans :    10
Test 2 :    123
Ans :    1
Test 3 :    7
Ans :    7
Test 4 :    91
Ans :    9
Test 5 :    9100
Ans :    189
Test 6 :    21
Ans :    15
Test 7 :    231
Ans :    260
Test 8 :    9100101
Ans :    189
Test 9 :    000612300000
Ans :    995888949
Test 10 :    78910111
Ans :    7
Test 11 :    698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110
Ans :    2850
Test 12 :    0999100
Ans :    35287
Test 13 :    1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111
Ans :    919111111111111111111111111111111111111111111111111111111111111111111111111111111111111111104
Test 14 :    566666
Ans :    1887
Test 15 :    1
Ans :    1
Test 16 :    0
Ans :    11
Test 17 :    0000000
Ans :    68888891
Test 18 :    09
Ans :    171
Test 19 :    999
Ans :    2588
Test 20 :    9919
Ans :    2863
Test 21 :    0202
Ans :    6971
Test 22 :    0202020202020202020
Ans :    2313131313131
Test 23 :    00070007000700070007
Ans :    8289728972891
Test 24 :    9999999999999939999999999
Ans :    14888888888888785
Test 25 :    1    5    len=100
Ans :
Test 26 :        4    len=100
Ans :
Test 27 :    0    len=200
Ans :
Test 28 :    0    6    len=100
Ans :
Test 29 :    9    len=200
Ans :
Test 30 :    9    9    len=100
Ans :
Test 31 :    3    len=84
Ans :
Test 32 :    7    8    len=100
Ans :
Test 33 :    5    len=100
Ans :
Test 34 :
Ans :
Test 35 :
Ans :
Test 36 :
Ans :
Test 37 :
Ans :
Test 38 :    13206252123724040484317964602881252884069781203380530661996711969    2    len=100
Ans :
Test 39 :    2226671115560004449333778222667111556000    len=100
Ans :
Test 40 :
Ans :

Here are some tests: 0202, 231, 0202020202020202020...

My program for problem 1165 got WA at test 29!
I nearly can't believe it...
I have checked my program for a million times through different test data, but there isn't an error I can get from that...
Will any one help me by giving some SPECIAL test data?
P S: All the test data on the discuss board is tested, no errors were found...

Hope for reply!

Thanks so much!

The code is here...

[no code here!]

Edited by moderator 09.05.2004 00:02

I tried to use ansistring to solve this problem.
But...
It seems that the program runs too slowly.
Who can tell me the way to make the solution faster?
Thank you very much.

I think I've passed all the tests ther user TEST sent here,
but I always get Crash(access violation).
Could you tell me why?


program p1005;
type
  number=record
    n:array[1..300]of integer;
    nk:integer;
  end;
var
  a,s,t:string;
  f:array[1..200]of number;
  ansk,i,j,st,p,long:integer;
  final,ans:number;
  d1:boolean;

  function combine(x,y:string):string;
  var
    i:integer;
  begin
    for i:=length(x) downto 1 do
      if copy(x,length(x)-i+1,i)=copy(y,1,i) then
      begin
        x:=x+copy(y,i+1,length(y)-i);
        exit(x);
      end;
    exit(x+y);
  end;


  function next(ts:string):string;
  var
    i:integer;
  begin
    i:=length(ts);
    ts[i]:=succ(ts[i]);
    while (ts[i]=':')and(i>0) do
    begin
      ts[i]:='0';
      ts[i-1]:=succ(ts[i-1]);
      dec(i);
    end;
    if i=0 then begin ts:='1'+ts;ts:=copy(ts,1,length(ts)-1);end;
    exit(ts);

  end;

  function check(st:integer;a:string):boolean;
  var
    ts:string;
    watch,k,now:integer;
    back:boolean;


  begin
    back:=false;
    if st<>1 then
    begin
      ts:=copy(s,1,st-1);

      k:=length(ts);
      if (ts[1]='0')and(abs(length(ts)-length(a))<1) then exit(false);
      ts:=next(ts);
      if copy(a,1+length(a)-k,k)<>copy(ts,length(ts)-k+1,k) then exit(false);
    end;
    now:=st;
    ts:=a;
    while now+length(ts)-1-ord(back)<=length(s) do
    begin
      if copy(s,now,length(ts))<>ts then exit(false);
      now:=now+length(ts);
      ts:=next(ts);
    end;

    if now>length(s) then exit(true);
    if copy(s,now,length(s)-now+1)<>copy(ts,1,length(s)-now+1) then
    exit(false);
    exit(true);
  end;

  function plus(a,b:number):number;
  var
    i,j,t:integer;
    c:number;
  begin
    if a.nk>b.nk then j:=a.nk else j:=b.nk;
    t:=0;fillchar(c,sizeof(c),0);
    for i:=1 to j do
    begin
      c.n[i+1]:=(a.n[i]+b.n[i]+c.n[i])div 10;
      c.n[i]:=(c.n[i]+a.n[i]+b.n[i])mod 10;
    end;
    if c.n[j+1]<>0 then inc(j);
    c.nk:=j;
    exit(c);
  end;

  procedure makef;
  var

    temp:number;
    i,j:integer;
  begin
    f[1].nk:=1;
    f[1].n[1]:=9;

    for i:=2 to length(a)-1 do
    begin
      fillchar(temp,sizeof(temp),0);
      j:=9*i;
      temp.n[i]:=j;j:=i;
      while temp.n[j]>10 do
      begin
        temp.n[j+1]:=temp.n[j] div 10;
        temp.n[j]:=temp.n[j] mod 10;
        inc(j);
      end;
      temp.nk:=j;
      f[i]:=plus(f[i-1],temp);
    end;
  end;

  procedure makeans;
  var
    k,l,i,j:integer;
    temp:number;
  begin
    fillchar(ans,sizeof(ans),0);
    ans:=plus(ans,f[length(a)-1]);
    l:=length(a);


    {i:=ord(a[1])-49;
    if i<>0 then
    begin
      fillchar(temp,sizeof(temp),0);
      temp.n[l]:=i*l;i:=l;
      while temp.n[i]>=10 do
      begin
        temp.n[i+1]:=temp.n[i] div 10;
        temp.n[i]:=temp.n[i] mod 10;
        inc(i);
      end;
      temp.nk:=i;
      ans:=plus(ans,temp);
    end;}

    for k:=1 to l do
    begin
      i:=ord(a[k])-48;if k=1 then dec(i);if k=l then inc(i);
      fillchar(temp,sizeof(temp),0);
      temp.n[l-k+1]:=i*l;i:=l-k+1;
      while temp.n[i]>10 do
      begin
        temp.n[i+1]:=temp.n[i] div 10;
        temp.n[i]:=temp.n[i] mod 10;
        inc(i);
      end;
      temp.nk:=i;
      ans:=plus(ans,temp);
    end;
  end;

  function minus(a,b:number):number;
  var
    i,j:Integer;
    c:number;
  begin
    fillchar(c,sizeof(c),0);
    for i:=1 to a.nk do
    begin
      c.n[i]:=c.n[i]+a.n[i]-b.n[i];
      if c.n[i]<0 then
      begin
        inc(c.n[i],10);
        dec(c.n[i+1]);
      end;
    end;
    if a.n[a.nk]=0 then c.nk:=a.nk-1 else c.nk:=a.nk;
    exit(c);
  end;


  procedure print;
  var
    i,j:integer;
    temp:number;
  begin
    i:=0;
    while p>0 do
    begin
      inc(i);
      temp.n[i]:=p mod 10;
      p:=p div 10;
    end;
    temp.nk:=i;
    ans:=minus(ans,temp);
    if ans.nk<final.nk then final:=ans;
    if ans.nk=final.nk then
    begin
      i:=ans.nk;
      while ans.n[i]=final.n[i] do dec(i);
      if ans.n[i]<final.n[i] then final:=ans;
    end;
  end;









begin

  final.nk:=1000;
  readln(s);

  for long:=1 to length(s) do
    for st:=1 to length(s)-long+1 do
    begin
      a:=(copy(s,st,long));
      if (check(st,a))and(a[1]<>'0') then
      begin
        makef;
        makeans;
        p:=st+long-2;
        print;
      end;
      if st<>length(s)-long+1 then continue;

      t:=next(copy(s,1,st-1));
      t:=copy(t,length(t)-st+2,st-1);
      a:=combine(a,t);
      if (check(st,a))and(a[1]<>'0') then
      begin
        makef;
        makeans;
        p:=st+length(a)-2;
        print;
      end;

  end;

  a:='1'+s;
  makef;
  makeans;
  p:=length(s)-1;
  print;

  for i:=final.nk downto 1 do write(final.n[i]);
  writeln;



end.

It's so simple in C# ...
But what's wrong ?

using System;
using System.Text;
using System.IO;

    class Program
    {
        static void Main()
        {
            StringBuilder seq = new StringBuilder();
            for (ulong i = 1; i < 100000; ++i)
            {
                seq.Append(i);
            }
            string str = seq.ToString();
            string j = Console.ReadLine();
            Console.WriteLine(str.IndexOf(j) + 1);
        }
    }

Test    input   output
1    101    10
2    123    1
3    7    7
4    91    9
5    9100    189
6    21    15
7    231    260

Strangely enough, it takes less than 1 sec to run the 'Complete number' part, whose time complexity appears to be O(n^2), but nearly 4 sec to run the 'No complete number' part, whose time complexity seems to be O(n). I doubt it's the function 'connect' that makes it slow. Can anyone help me?

program ural1165;
var
  a,k,s,t:string;
  l,i,j:byte;
function max(a,b:byte):byte;
  begin
    if a>b then max:=a else max:=b;
  end;
function min(a,b:byte):byte;
  begin
    if a<b then min:=a else min:=b;
  end;
function minstr(a,b:string):string;
  var
    i:byte;
  begin
    if length(a)<length(b) then begin
      minstr:=a;exit;
    end
    else if length(a)>length(b) then begin
      minstr:=b;exit;
    end
    else
      for i:=length(a) downto 1 do
        if a[i]<b[i] then begin
          minstr:=a;exit;
        end
        else if a[i]>b[i] then begin
          minstr:=b;exit;
        end;
    minstr:=a;
  end;
function serial(l:byte;c:char):string;
  var
    s:string;
    i:byte;
  begin
    s:='';
    for i:=1 to l do
      s:=s+c;
    serial:=s;
  end;
function reverse(a:string):string;
  var
    i:byte;
    s:string;
  begin
    s:='';
    for i:=length(a) downto 1 do
      s:=s+a[i];
    reverse:=s;
  end;
function connect(a,b:string):string;
  var
    i:byte;
  begin
    i:=min(length(a),length(b))-1;
    while i>0 do begin
      if copy(a,1,i)=copy(b,length(b)-i+1,i) then begin
        connect:=copy(b,1,length(b)-i)+a;
        exit;
      end;
      dec(i);
    end;
    connect:=b+a;
  end;
function inc1(a:string):string;
  var
    l,i:byte;
  begin
    l:=length(a);
    i:=1;
    repeat
      if a[i]<'9' then break;
      inc(i);
    until i>l;
    if i>l then
      inc1:=serial(l,'0')+'1'
    else begin
      inc(a[i]);
      while i>1 do begin
        dec(i);
        a[i]:='0';
      end;
      inc1:=a;
    end;
  end;
function dif(a,b:string):string;
  var
    l,i:byte;
  begin
    l:=length(a);
    while length(b)<l do b:=b+'0';
    for i:=1 to l do
      dec(a[i],ord(b[i])-48);
    for i:=1 to l-1 do
      if a[i]<'0' then begin
        inc(a[i],10);
        dec(a[i+1]);
      end;
    while a[length(a)]='0' do
      delete(a,length(a),1);
    dif:=a;
  end;
function product(a:string;b:byte):string;
  var
    s:string;
    i:byte;
    p:integer;
  begin
    s:='';p:=0;
    for i:=1 to length(a) do begin
      inc(p,(ord(a[i])-48)*b);
      s:=s+chr(48+p mod 10);
      p:=p div 10;
    end;
    while p>0 do begin
      s:=s+chr(48+p mod 10);
      p:=p div 10;
    end;
    product:=s;
  end;
function position(x:string):string;
  var
    s:string;
    l,i:byte;
  begin
    l:=length(x);
    s:=inc1(product(dif(x,'1'),l));
    for i:=1 to l-1 do
      s:=dif(s,product(serial(i-1,'0')+'9',l-i));
    position:=s;
  end;
function expand(x:string;p:byte):boolean;
  var
    t:string;
    q:byte;
  begin
    expand:=false;q:=p;
    {Expand front}
    t:=x;
    while p>0 do begin
      if t='1' then exit;
      t:=dif(t,'1');
      if length(t)>p then t:=copy(t,1,p);
      if t<>copy(a,l-p+1,length(t)) then exit;
      dec(p,length(t));
    end;
    {Expand rear}
    t:=x;
    p:=l-length(x)-q;
    while p>0 do begin
      t:=inc1(t);
      if length(t)>p then t:=copy(t,length(t)-p+1,p);
      if t<>copy(a,p-length(t)+1,length(t)) then exit;
      dec(p,length(t));
    end;
    expand:=true;
  end;
begin
  assign(input,'1165.in');reset(input);
  readln(a);
  l:=length(a);
  if a=serial(l,'0') then
    k:=inc1(position(a+'1'))
  else begin
    a:=reverse(a);
    k:=serial(255,'9');

    {Complete number}
    for i:=l downto 1 do
      if a[i]>'0' then
        for j:=i downto 1 do
          if expand(copy(a,j,i-j+1),l-i) then begin
            str(l-i,t);
            k:=minstr(k,dif(position(copy(a,j,i-j+1)),reverse(t)));
          end;

    {No complete number}
    for i:=l-1 downto 1 do
      if a[i]>'0' then begin
        s:=copy(a,i+1,l-i);
        s:=inc1(s);
        if length(s)>l-i then delete(s,l-i+1,1);
        str(l-i,t);
        k:=minstr(k,dif(position(connect(copy(a,1,i),s)),reverse(t)));
      end;
  end;
  writeln(reverse(k));
end.

 Don't try to understand something from my code it is .....

aduna == a + b
inmult == a * b
inc == a + 1
comp == compare

//Don't read it!

Edited by moderator 03.11.2004 17:44

Edited by moderator 03.11.2004 17:44

label Metka;
const maxn = 220;
var
  p,i,j,k,n,m,pos,num,d: integer;
  s: string;
  a,res,b: array[1..2*maxn] of integer;
  max,buf,bufer: array[1..2*maxn] of byte;
  fl: boolean;
procedure calc;
var i,j,k,n,m: integer;
begin
  for i := maxn-20 downto 1 do begin
    if max[i] <> 0 then break;
  end;
  for j := 1 to i-1 do begin
    res[j] := 9*j;
  end;
  for j := 1 to i+10 do begin
    res[j+1] := res[j+1] + res[j] div 10;
    res[j] := res[j] mod 10;
  end;
  dec(max[i]);
  fillchar(a,sizeof(a),0);
  for j := 1 to i do begin
    a[j] := max[j]*i;
  end;
  for j := 1 to i+10 do begin
    a[j+1] := a[j+1] + a[j] div 10;
    a[j] := a[j] mod 10;
  end;
  for j := 1 to i+10 do begin
    b[j+1] := b[j+1] + (a[j] + res[j]) div 10;
    b[j] := b[j] + (a[j] + res[j]) mod 10;
  end;
  res := b;
  res[1] := res[1] +2- pos;
  j := 1;
  while res[j] >= 10 do begin
    res[j+1] := res[j+1] + res[j] div 10;
    res[j] := res[j] mod 10;
    inc(j);
  end;
end;

function srav: boolean;
var i:integer;
begin
  srav := false;
  for i := maxn downto 1 do begin
    if max[i] > bufer[i] then begin
      srav := true;
      exit;
    end;
    if max[i] < bufer[i] then break;
  end;
end;

function test(st,fin: integer): boolean;
var i: integer;
begin
  if st >= 1 then begin
    if buf[fin-st+1] = 0 then begin
      test := false;
      exit;
    end;
  end;
  test := true;
  for i := st to fin do begin
    if (i<1) or (i>n) then continue;
    if buf[fin-i+1] <> a[i] then begin
      test := false;
      exit;
    end;
  end;
end;

procedure incr;
var p : integer;
begin
  p := 1;
  inc(buf[p]);
  while buf[p]>=10 do begin
    buf[p] := buf[p] mod 10;
    buf[p+1] := buf[p+1] +1;
    inc(p);
  end;
  if p > j-i+1 then inc(d);
end;

procedure decr;
var p,i : integer;
begin
  p := 1;
  while buf[p]=0 do begin
    inc(p)
  end;
  dec(buf[p]);
  for i := p-1 downto 1 do buf[i] := 9;
end;

begin
  readln(s);
  fl := true;
  fillchar(max,sizeof(max),9);
  for i := 1 to length(s) do begin
    val(s[i],a[i],k);
    if a[i] <> 0 then fl := false;
  end;
  if fl then begin
    fillchar(max,sizeof(max),0);
    max[length(s)+1] := 1;
    goto Metka;
  end;
  n := length(s);
  for i := 1 to n do begin
    for j := i to n do begin
      if a[i] = 0 then break;
      d := 0;
      fillchar(buf,sizeof(buf),0);
      fillchar(bufer,sizeof(bufer),0);
      for k := j downto i do begin
        buf[j-k+1] := a[k];
        bufer[j-k+1] := a[k];
      end;
      p := i;
      fl := true;
      repeat
        p := p-j+i-1+d;
        decr;
        if not test(p,p+j-i+d) then begin
          fl := false;
          break;
        end;
      until p < 1;
      if fl then begin
        repeat
          p := p+j-i+1+d;
          incr;
          if not test(p,p+j-i+d) then begin
            fl := false;
            break;
          end;
        until p > n;
      end;
      if fl then begin
        if srav then begin
          max := bufer;
          pos := i;
        end;
      end;
    end;
  end;
  for i := 2 to n do begin
    for j := i-1 downto 1 do begin
      if a[i]=0 then break;
      d := 0;
      fillchar(buf,sizeof(buf),0);
      fillchar(bufer,sizeof(bufer),0);
      for k := i-1 downto j do begin
        buf[i-k] := a[k];
        bufer[i-k] := a[k];
      end;
      for k := n downto i do begin
        bufer[i-j+1+n-k] := a[k];
        buf[i-j+1+n-k] := a[k];
      end;
      p := i;
      fl := true;
      num := n-j+1;
      repeat
        p := p-num;
        if not test(p,p+num-1) then begin
          fl := false;
          break;
        end;
        decr;
      until p < 1;
      if fl then begin
        repeat
          p := p+num;
          incr;
          if not t

Wrong Anser: BUT I checked with the test data on this
site....correct....

take a look at my code please.
thanks. is there any test case that does not work??

// USU Problem 1165
// Subnumber
// Done by Teh Ming Han

#include <string.h>
#include <iostream.h>
#include <stdlib.h>

int main(){
    int i,a,pos,mat=-1,ori=-1,n=0;
    char dat[201]={'\0'};
    cin.getline(dat,200,'\n');

    pos=0;
    int length = strlen(dat);
    for (i=1;true;i++){
        char ne[8]={'\0'};
        itoa(i,ne,10);
        for (a=0;a<strlen(ne);a++){
            n++;
            if (ne[a]==dat[pos]){
                if (pos==0) ori = n;
                pos++;
            }else pos=0;
            if (pos==length){
                mat = ori;
                break;
            }
        }
        if (mat!=-1) break;
    }
    cout<<mat;
    return 0;
}

00000->99999 have been accepted by my source
(using KMP to judge it)

but it is still got WR


#include<stdio.h>
#include<string.h>

#define MAX 350
/*&#1105;&#1071;&#1109;&#171;&#182;&#1048;&#1169;&#1098;&#1042;&#1083;*/

void add(int a[],int la,int b[],int lb,int c[],int *lc){
    int i;
    int flag = 0;

    /*init*/
    for(i = 0;i < MAX;i++)
        c[i] = 0;

    for(i = 0;i <(la>lb?la:lb);i++){
        c[i] = (flag + a[i] + b[i])%10;
        flag = (flag + a[i] + b[i])/10;
        }

    if(flag != 0)
        c[i++] = flag;

    (*lc) = i;
    }

void sub(int a[],int la,int b[],int lb,int c[],int *lc){
    /*make sure that a >= b
        make sure that la >= lb*/
    int i;
    int flag = 0;
    int t;

    for(i = 0;i < MAX;i++)
        c[i] = 0;

    for(i = 0;i <la;i++){
        t = a[i] - b[i] -flag;
        if(t < 0){
            t += 10;
            flag = 1;
            c[i] = t;
            }
        else{
            flag = 0;
            c[i] = t;
            }
        }

    (*lc) = 0;
    for(i = MAX-1;i >= 0;i--){
        if(c[i] != 0){
            (*lc) = i + 1;
            break;
            }
        }
    if((*lc) == 0) (*lc) = 1;
    lb -= lb;
    }
int sub1(int digit[],int *l)
{
    int flag = -1;
    int i;
    int t;
    for(i = 0;i < (*l);i++)
    {
        t = digit[i] + flag;
        if(t < 0)
        {
            flag = -1;
            t += 10;
        }
        else
        {
            digit[i] = t;
            break;
        }
        digit[i] = t;
    }
    if(digit[*l - 1] == 0)
    {
        (*l)--;
    }
    return 0;
}

int add1(int digit[],int *l)
{
    int flag = 1;
    int i;
    int t;
    for(i = 0;i <= (*l);i++)
    {
        t = digit[i] + flag;
        if(t >= 10)
        {
            flag = 1;
            t -= 10;
        }
        else
        {
            digit[i] = t;
            break;
        }
        digit[i] = t;
    }
    if(digit[*l] != 0)
    {
        (*l)++;
    }
    return 0;
}

void mul(int a[],int la,int b[],int lb,int c[],int *lc){
    int i,j;
    int flag,t;

    /*init*/
    for(i = 0;i < MAX;i++)
        c[i] = 0;

    if(la == 1 &&a[0] == 0 ||
        lb == 1&&b[0] == 0){
            (*lc) = 1;
            return;
            }
    for(i = 0;i <la;i++){
        flag = 0;
        for(j = 0;j < lb;j++){
            t = c[i + j] + a[i] * b[j] + flag;
            c[i + j] = t%10;
            flag = t/10;
            }
        while(flag > 0){
            t = c[i + j] + flag;
            c[i + j] = t%10;
            flag = t/10;
            j++;
            }
        }
    if(c[la+lb-1] != 0)
        (*lc) = la+lb;
    else
        (*lc) = la + lb -1;
    }

void let(int a[],int *la,int b[],int lb){
    int i;
    for(i = 0;i< MAX;i++)
        a[i] = b[i];
    (*la) = lb;
    }
void make(int a,int r[],int *lb){
    int i;

    /*init*/
    for(i = 0;i < MAX;i++)
        r[i] = 0;

    i = 0;
    while(a > 0){
        r[i] = a%10;
        a /= 10;
        i++;
        }
    if(i == 0)
        (*lb) = 1;
    else
        (*lb) = i;
    }

void output(int a[],int la){
    int i;
    for(i = la -1;i >= 0;i--)
        printf("%d",a[i]);
    }

int compare(int a[],int la,int b[],int lb)
{
    int i;
    if(la > lb)
    {
        return 1;
    }
    if(lb > la)
    {
        return -1;
    }
    for(i = la - 1;i >= 0;i--)
    {
        if(a[i] > b[i])
        {
            return 1;
        }
        if(a[i] < b[i])
        {
            return -1;
        }
    }
    return 0;
}

/*&#1105;&#1071;&#1109;&#171;&#182;&#1048;&#1169;&#1098;&#1042;&#1083;&#1029;&#1073;&#1050;&#1096;*/

#define MAXLEN 205
int checklist[MAXLEN][MAX];
int checklen[MAXLEN];
/*checklist[i] = the index of 10...0(i zeros)*/

int check_init(void)
{
    int i;
    int t[MAX],lt;
    int a[MAX],la;
    int b[MAX],lb;
    int c[MAX],lc;
    int nine[MAX],lnine;

    make(9,nine,&lnine);

    make(1,checklist[0],checklen + 0);
    for(i = 1;i < MAXLEN;i++)
    {
        make(0,t,&lt);
        t[i - 1] = 1;
        lt = i;/*10 ^ (i - 1) */
        mul(nine,lnine,t,lt,a,&la);/*9 * 10 ^ ( i - 1) */
        make(i,b,&lb);/* i */
        mul(b,lb,a,la,c,&lc);/*i * 9 * 10 ^ ( i - 1) */
        add(c,lc,checklist[i - 1],checklen[i - 1],
                checklist[i],checklen + i);

type tnode=array[1..500] of integer;
var a,b,c,r:tnode;
    i,j,k,v,n,tb,tc,tr:integer;
    ss:string;

procedure sub;
var i:integer;
begin
  dec(c[1]);
  i:=1;
  while c[i]=-1 do
  begin
    dec(c[i+1]);
    c[i]:=9;
    inc(i);
  end;
  if (tc>1)and(c[tc]=0) then dec(tc);
end;

procedure add;
var i:integer;
begin
  inc(c[1]);
  i:=1;
  while c[i]=10 do
  begin
    inc(c[i+1]);
    c[i]:=0;
    inc(i);
  end;
  if c[tc+1]>0 then inc(tc);
end;

function equal(x,y,k:integer):boolean;
var i:Integer;
begin
  equal:=false;
  for i:=0 to k-1 do
  if c[i+x]<>a[y+i] then exit;
  equal:=true;
end;

function check:boolean;
begin
  check:=false;
  c:=b;tc:=tb;
  k:=j+1;
  while k<=n do
  begin
    sub;
    if (tc=1)and(c[1]=0) then exit;
    if k+tc-1<=n then
    begin
      if equal(1,k,tc) then else exit;
      inc(k,tc);
    end else
    begin
      if equal(1,k,n-k+1) then else exit;
      k:=n+1;
    end;
  end;

  c:=b;tc:=tb;
  k:=j-i;
  while k>0 do
  begin
    add;
    if k-tc+1>0 then
    begin
      if equal(1,k-tc+1,tc) then else exit;
      dec(k,tc);
    end else
    begin
      if equal(tc-k+1,1,k) then else exit;
      k:=0;
    end;
  end;
  check:=true;
end;

procedure wish(k:integer);
var i:integer;
begin
  if tb>tr then exit;
  if tb<tr then
  begin
    r:=b;tr:=tb;v:=k;
    exit;
  end;
  for i:=tb downto 1 do
  begin
    if b[i]>r[i] then exit;
    if b[i]<r[i] then
    begin
      r:=b;tr:=tb;v:=k;
      exit;
    end;
  end;
  if k<v then v:=k;
end;

procedure compute;
begin
  if tr=1 then
  begin
    tc:=1;c[1]:=r[1]+v;
    exit;
  end;

  fillchar(c,sizeof(c),0);
  for i:=1 to tr-1 do
  begin
    j:=i;k:=i;
    while j>0 do
    begin
      inc(c[k],j mod 10);
      if c[k]>9 then begin inc(c[k+1]);dec(c[k],10);end;
      j:=j div 10;
      inc(k);
    end;
  end;
  if c[k]>0 then tc:=k else tc:=k-1;

  k:=0;
  for i:=1 to tc do
  begin
    c[i]:=c[i]*9+k;
    k:=0;
    while c[i]>9 do
    begin
      inc(k);
      dec(c[i],10);
    end;
  end;
  if k>0 then begin inc(tc);c[tc]:=k;end;

  j:=tr;
  dec(r[tr]);
  while (tr>0)and(r[tr]=0) do dec(tr);
  for i:=1 to tr do
  begin
    inc(c[i],r[i]*j);
    while c[i]>9 do
    begin
      inc(c[i+1]);
      dec(c[i],10);
    end;
  end;
  i:=tr+1;
  while c[i]>9 do
  begin
    while c[i]>9 do
    begin
      inc(c[i+1]);
      dec(c[i],10);
    end;
    inc(i);
  end;
  if i>tc then tc:=i;
  if c[tc]=0 then dec(tc);

  inc(c[1],v+1);
  i:=1;
  while (c[i]>9)or(c[i]<0) do
  begin
    while c[i]>9 do
    begin
      inc(c[i+1]);
      dec(c[i],10);
    end;
    while c[i]<0 do
    begin
      dec(c[i+1]);
      inc(c[i],10);
    end;
    inc(i);
  end;
  if i>tc then tc:=i;
  if c[tc]=0 then dec(tc);
end;

begin
  assign(input,'');
  reset(input);
  readln(ss);
  while ss[1]=' ' do delete(ss,1,1);
  while ss[length(ss)]=' ' do  delete(ss,length(ss),1);
  n:=length(ss);
  fillchar(a,sizeof(a),0);
  for i:=1 to n do a[i]:=ord(ss[n+1-i])-48;

  tr:=500;
  fillchar(b,sizeof(b),0);
  for i:=1 to n-1 do
  begin
    tb:=i;
    for j:=n downto n-i+1 do
    if j<i then break else
    if a[j]>0 then
    begin
      move(a[j-i+1],b[1],i*2);
      if check then wish(j-n);
    end;
    if tr<500 then break;
  end;

  if tr=500 then
  if a[n]=0 then
  begin
    tr:=n+1;
    move(a[1],r[1],n*2);
    r[tr]:=1;
    v:=1;
  end else
  begin
    tr:=n;
    move(a[1],r[1],n*2);
    v:=0;
  end;

  fillchar(c,sizeof(c),0);
  for i:=n-1 downto 1 do
  if a[i]>0 then
  begin
    tc:=n-i;
    move(a[i+1],c[1],tc*2);
    add;
    if tc>n-i then