Discussion @ 1165. Subnumber @ Timus Online Judge

Could anyone try to find why does my program get WA?

Posted by shitty.Mishka 20 Dec 2001 15:24

Program Subnumber;
Const MaxLen=400;
Type TNum=Array[0..MaxLen] Of Integer;{0-sign of the number}
Procedure Add(A,B:TNum;Var C:TNum);   Forward;
Procedure Sub(A,B:TNum;Var C:TNum);   Forward;
Procedure Mul10(Pow:Integer;Var X:TNum); Forward;
Procedure Mulm10(Pow:Integer;Var X:TNum);Forward;
Procedure Mul(A,B:TNum;Var C:TNum);   Forward;
Procedure MulC(A:TNum;C:Integer;Var B:TNum);Forward;
Procedure InputLong(Var X:TNum);      Forward;
Procedure PrintLong(Var X:TNum);      Forward;
Function Len(X:TNum):Integer;         Forward;
Function CmpEqLns(A,B:TNum):Char;     Forward;
Function Cmp(A,B:TNum):Char;          Forward;
Procedure Dvd(A,B:TNum;Var C:TNum);   Forward;
Procedure InToTNum(K:Integer;Var R:TNum); Forward;
Procedure StToTNum(S:String;Var R:TNum); Forward;
Function Max(X,Y:Integer):Integer;
Begin
If X>Y Then Max:=X Else Max:=Y;
End;
Procedure Add;
Var I,D                     :Integer;
Begin
D:=0;
For I:=MaxLen DownTo MaxLen-Max(Len(A),Len(B)) Do Begin
   C[I]:=(A[I]+B[I]+D) Mod 10;
   D:=(A[I]+B[I]+D) Div 10;
End;
End;
Procedure Mul10;
Var I:Integer;
Begin
For I:=1 To MaxLen-Pow Do
   X[I]:=X[I+Pow];
For I:=MaxLen+1-Pow To MaxLen Do
   X[I]:=0;
End;
Procedure Mulm10;
Var I:Integer;
Begin
For I:=MaxLen DownTo Pow+1 Do
   X[I]:=X[I-Pow];
For I:=1 To Pow Do
   X[I]:=0;
End;
Procedure Mul;
Var I,J,D                  :Integer;
      T                      :TNum;
Begin
For I:=1 To MaxLen Do C[I]:=0;
For I:=MaxLen DownTo MaxLen+1-Len(B) Do Begin
   For J:=1 To MaxLen Do T[J]:=0;
   D:=0;
   For J:=MaxLen DownTo 1 Do Begin
    T[J]:=(A[J]*B[I]+D) Mod 10;
    D:=(A[J]*B[I]+D) Div 10;
   End;
   Mul10(MaxLen-I,T);
   Add(T,C,C);
End;
End;
Procedure MulC;
Var i,j,d:Integer;
      t:TNum;
Begin
For I:=1 To MaxLen Do B[I]:=0;
For J:=1 To MaxLen Do T[J]:=0;
D:=0;
For J:=MaxLen DownTo MaxLen-Len(A) Do Begin
   T[J]:=(A[J]*C+D) Mod 10;
   D:=(A[J]*C+D) Div 10;
End;
Add(T,B,B);
End;
Procedure InputLong;
Var I                      :Integer;
      S                      :String;
      Cod                    :Integer;
Begin
Readln(S);
If S[1]='-' Then Begin
   X[0]:=1;
   Delete(S,1,1);
End;
For I:=1 To Length(S) Do Val(S[I],X[MaxLen-Length(S)+I],Cod);
End;
Procedure PrintLong;
Var I                      :Integer;
Begin
If Len(X)=0 Then
   Write(0)
Else
   For I:=MaxLen+1-Len(X) To MaxLen Do
    Write(X[I]);
End;
Function Len;
Var I                      :Integer;
Begin
Len:=0;
I:=1;
While ((X[I]=0) And (I<=MaxLen)) Do Inc(I);
Len:=MaxLen+1-I;
End;
Function CmpEqLns;
Var I                      :Integer;
      R                      :Char;
Begin
R:='=';
I:=1;
While ((I<=MaxLen) And (R='=')) Do Begin
   If A[I]>B[I] Then
    R:='>'
   Else If A[I]<B[I] Then
    R:='<';
   Inc(I);
End;
CmpEqLns:=R;
End;
Function Cmp;
Begin
If A[0]=1 Then
   If B[0]=1 Then Begin
    A[0]:=0;
    B[0]:=0;
    Cmp:='=';
    If Cmp(A,B)='<' Then
     Cmp:='>'
    Else If Cmp(A,B)='>' Then
     Cmp:='<'
   End Else
    Cmp:='<'
Else
   If B[0]=1 Then
    Cmp:='>'
   Else
    If Len(A)>Len(B) Then Cmp:='>' Else
     If Len(A)<Len(B) Then Cmp:='<' Else
      Cmp:=CmpEqLns(A,B);
End;
Procedure Sub;
Var I,D                    :Integer;
Begin
If A[0]=1 Then Begin
   A[0]:=1-A[0];
   B[0]:=1-B[0];
   Sub(A,B,C);
   C[0]:=1-C[0]
End Else
   If Cmp(A,B)='<' Then Begin
    Sub(B,A,C);
    C[0]:=1-C[0];
   End Else
    If B[0]=1 Then Begin
     B[0]:=0;
     Add(A,B,C);
    End Else Begin
     D:=0;
     For I:=MaxLen DownTo MaxLen-Max(Len(A),Len(B)) Do Begin
      C[I]:=(A[I]-B[I]+10-D) Mod 10

Hope this'll help you !

Posted by I have answers to all your questions :) 20 Dec 2001 18:51

I'm sorry that i dont have time to look deeper in ur program , it's
quite complex :)
- There's a bug in function Len, "While ((X[I]=0) And (I<=MaxLen)) Do
Inc(I)" must be changed to "While ((I<=MaxLen) and (X[I]=0)) Do Inc
(I)" otherwise u'll get array bound exceeded (put $R+ in the first
line of ur program then submit it , u'll see that)
- I found a case which ur program gives WA : "09910", the correct
answer is 909,910,.. instead of 99,100,..

That's all :)
Good luck!

Thank you! But there's still something wrong. here's my new code.

Posted by shitty.Mishka 20 Dec 2001 20:29

Could you try to find a new test case please?

Program Subnumber;
Const MaxLen=205;
Var mt,dt:Array[0..100] Of Byte;
    st:Array[0..9,0..9] Of Byte;
Type TNum=Array[0..MaxLen] Of Integer;{0-sign of the number}
Procedure Add(A,B:TNum;Var C:TNum);   Forward;          {Сложение}
Procedure Sub(A,B:TNum;Var C:TNum);   Forward;
Procedure Mul10(Pow:Integer;Var X:TNum); Forward;          {Умножение
на 10 в степени}
Procedure Mulm10(Pow:Integer;Var X:TNum);Forward;
Procedure Mul(A,B:TNum;Var C:TNum);   Forward;          {Умножение}
Procedure MulC(A:TNum;C:Integer;Var B:TNum);Forward;       {Умножение
числа на цифру}
Procedure InputLong(Var X:TNum);      Forward;          {Ввод}
Procedure PrintLong(Var X:TNum);      Forward;          {Вывод}
Function Len(X:TNum):Integer;         Forward;          {Определение
длины}
Function CmpEqLns(A,B:TNum):Char;     Forward;          {Сравненме
чисел одной длины}
Function Cmp(A,B:TNum):Char;          Forward;          {Сравнение
чисел}
Procedure Dvd(A,B:TNum;Var C:TNum);   Forward;
Procedure InToTNum(K:Integer;Var R:TNum); Forward;
Procedure StToTNum(S:String;Var R:TNum); Forward;
Function Max(X,Y:Integer):Integer;
Begin
If X>Y Then Max:=X Else Max:=Y;
End;
Procedure Add;
Var I,D,v                     :Integer;
Begin
D:=0;
For I:=MaxLen DownTo 1 Do Begin
   v:=st[A[I],B[I]]+D;
   C[I]:=mt[v];
   D:=dt[v];
End;
End;
Procedure Mul10;
Var I:Integer;
Begin
For I:=1 To MaxLen-Pow Do
   X[I]:=X[I+Pow];
For I:=MaxLen+1-Pow To MaxLen Do
   X[I]:=0;
End;
Procedure Mulm10;
Var I:Integer;
Begin
For I:=MaxLen DownTo Pow+1 Do
   X[I]:=X[I-Pow];
For I:=1 To Pow Do
   X[I]:=0;
End;
Procedure Mul;
Var I,J,D                  :Integer;
      T                      :TNum;
Begin
For I:=1 To MaxLen Do C[I]:=0;
For I:=MaxLen DownTo MaxLen+1-Len(B) Do Begin
   For J:=1 To MaxLen Do T[J]:=0;
   D:=0;
   For J:=MaxLen DownTo 1 Do Begin
    T[J]:=(A[J]*B[I]+D) Mod 10;
    D:=(A[J]*B[I]+D) Div 10;
   End;
   Mul10(MaxLen-I,T);
   Add(T,C,C);
End;
End;
Procedure MulC;
Var i,j,d:Integer;
      t:TNum;
Begin
For I:=1 To MaxLen Do B[I]:=0;
For J:=1 To MaxLen Do T[J]:=0;
D:=0;
For J:=MaxLen DownTo MaxLen-Len(A) Do Begin
   T[J]:=(A[J]*C+D) Mod 10;
   D:=(A[J]*C+D) Div 10;
End;
Add(T,B,B);
End;
Procedure InputLong;
Var I                      :Integer;
      S                      :String;
      Cod                    :Integer;
Begin
Readln(S);
If S[1]='-' Then Begin
   X[0]:=1;
   Delete(S,1,1);
End;
For I:=1 To Length(S) Do Val(S[I],X[MaxLen-Length(S)+I],Cod);
End;
Procedure PrintLong;
Var I                      :Integer;
Begin
If Len(X)=0 Then
   Write(0)
El

try this input : 0909 , the correct answer is 35251

Posted by I have answers to all your questions :) 20 Dec 2001 23:12

Discussion of Problem 1165. Subnumber