10013 - Super long sums

[soyoja]

Hint ) If you use Visual C++ compiler, it supply only 250,000
local integer array size... ( or 1 million char array )
If you declare more size of array, your program corrupt.
Even though you use other compiler, wasting memory is very bad idea...
Why I refer to VC compiler? Because many of ACM Asia regional contest - especially Korean regional contest - use this compiler. ^^

[WanBa]

I am bogged with anger.great regards to the man helping me.
[cpp]
#include<iostream>
using namespace std;
int line1[1000001];
int line2[1000001];
void add ( int size )
{
int i;
int carry (0);
for ( i = 0; i < size; ++i ) {
line1 += line2 + carry;
carry = line1 / 10;
line1 %= 10;
}
line1 = carry;

}
int main()
{
int i, m;
int num, n;
bool Head;
cin >> n;
for ( m = 0; m < n; ++m ) {
if ( m > 0 )
cout << endl;
cin >> num;
line1[num] = line2[num] = 0;
for ( i = num - 1; i >= 0; --i )
cin >> line1 >> line2;
add ( num );
Head = true;
for ( i = num ; i >= 0; --i )
if ( Head && line1 == 0 )
;
else {
Head = false;
cout << line1;
}
if ( Head )
cout << 0 ;
cout << endl;

}
return 0;
}[/cpp]

[Maxim]

First of all, set not only line1[num] and line2[num] to zero, but all num + 1 elements of each line to zero.
After computation, only line1[num] might be leading zero, so test only for it, not whole line1.

Maxim

[monmobear]

I got AC this code

[cpp]

//@BEGIN_OF_SOURCE_CODE
//@JUDGE_ID: 30286PY 10013 C++

#include<iostream.h>
#include<stdio.h>
#include<fstream.h>
#include<math.h>
//#include<conio.h>
long a[1000050]={0};

void main(){
int i,j,k;
int n,m,ta,tb,c;
int wide=5;
//ifstream cin("10013.in");

cin>>n;
// cout<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<=1000050;j++)
a[j]=0;

cin>>m;
for(j=m;j>0;j--)
{
cin>>ta>>tb;
a[(j)]+=ta;
a[(j)]+=tb;
k=0;
while(1)
{
c=(a[j+k]/10);
if(c!=0)
{
a[j+k]=a[j+k]%10;
a[j+k+1]+=c;
}
else
break;
k++;
}
}
if(a[m+1]!=0)
cout<<a[m+1];//<<" ";

cout<<a[m];//<<" ";

for(j=m-1;j>0;j--)
{
cout<<a[j];//<<" ";
}
cout<<endl;
if(i!=n-1)
cout<<endl;
}
}
//@END_OF_SOURCE_CODE
//22/06/03 02:30
[/cpp]

But ... @@ this is WA ... why ??

[cpp]

#include<iostream.h>
#include<stdio.h>
#include<fstream.h>
#include<math.h>
void main(){
// for only
int i,j,k;

long a[500000]={0};
int n,m,ta,tb,c;
int wide=5;
ifstream ifile("10013.in");

ifile>>n;
for(i=0;i<n;i++)
{
for(j=0;j<=500000;j++)
a[j]=0;

ifile>>m;
for(j=m;j>0;j--)
{
ifile>>ta>>tb;
a[(j-1)/(5)]+=ta*(int)pow(10,((j-1)%5));
a[(j-1)/(5)]+=tb*(int)pow(10,((j-1)%5));

k=0;
while(1)
{
c=(a[j/wide+k]/100000);
if(c!=0)
{
a[j/wide+k]=a[j/wide+k]%100000;
a[j/wide+k+1]+=c;
}
else
break;
k++;
}
}
if(a[m/6+1]!=0)
cout<<a[m/6+1];

cout<<a[m/6];
for(j=m/6-1;j>=0;j--)
{
k=4;
while(1)
{
if(k==0)
break;
if(a[j]/(int)pow(10,k--)==0)
cout<<0;
else
break;
}

cout<<a[j];
}
cout<<endl;
if(i!=n-1)
cout<<endl;
}
cin.get();
}

[/cpp]


Help me ~ thx ~

[ThomasTse]

I have tried different codings for 10013 by using java, but all result with a TLE reply.
Can any Java expert help me ?

Here is one of my coding.

[java]
import java.io.*;
import java.util.*;

class Main
{
static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

public static void main (String args[]) // entry point from OS
{
Main myWork = new Main(); // create a dinamic instance
myWork.Begin(); // the true entry point
}

void Begin()
{
String input;
StringTokenizer temp;
int n;
int count = 0;
int m = 0;
input = Main.ReadLn (255);
n = Integer.parseInt(input.trim());
String resultString[] = new String[n];

while (count<n)
{
input = Main.ReadLn (255);

count++;
input = Main.ReadLn (255);
m = Integer.parseInt(input.trim());
int no_1 [] = new int[m];
int no_2 [] = new int[m];
int result [] = new int[m];
for (int i=0;i<m;i++)
{
input = Main.ReadLn (255);
temp = new StringTokenizer (input.trim());
no_1 = Integer.parseInt(temp.nextToken());
no_2 = Integer.parseInt(temp.nextToken());
result = no_1 + no_2;
if(i>0 && result>9){
result = result%10;
result[i-1] = result[i-1]+1;
}
} // end for loop

resultString[count-1]="";
for (int i=0;i<result.length;i++){
resultString[count-1] = resultString[count-1] + Integer.toString(result);
}

} //end while loop

// print out the results
for (int x=0;x<n;x++){
System.out.println(resultString[x]+"\n");
}
} // end Method Begin()

} // end Class Main[/java][/code][/java]

[Ashique Mahmood Rupam]

In "The Input" section of 10013 - "Each of the two given integers is not less than 1, and the length of their sum does not exceed M." <-- what does it really mean?
I could get ac long ago if I did not read this line. then this line is surely misleading one.
Problems may be misleading, but should not be with wrong specifications. So, anyone who knows what this line means ?

[Joseph Kurniawan]

For instance, if m = 5, then the result of the summation won't have more than 5 digits. i.e. there won't be such input as m=5:
5
5 5
5 5
5 5
5 5
5 5

The result would be 111110 (6 digits and 6>m).
Is that where your confusion lies??

[problem]

wa .plz check my code and give me solution.
[c]

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

void main()
{
int t[5000]={0};
int i,n,p=0,r,r1=0,j,k,l,m;
int sum,sum1=0.0;
while(scanf("%d",&i)!=EOF)
{
for(j=0;j<i;j++)
{
scanf("%d",&n);
for(k=0;k<n;k++)
{
scanf("%d%d",&l,&m);
sum=l+m;
t[k]=sum;
}
for(k=n-1;k>=0;k--)
{
r=r1+fmod(t[k],10);
sum1=sum1+(r*pow(10,p));
p++;
r1=t[k]/10;
}
printf("%d\n",sum1);
sum1=0;
p=0;
}
}
}
[\c]

[problem]

[c]

Firstly sum up all the digit of the number then sum up the factorizing
number.if sum of each digit is equal to the sum of factorizing number
then the number is called smith number.

sample input:
-------------

20
4937774
4997775
5445454
4648787
4897987
5789798
9554564
8545644
7564545
8798798
6787878
5789721
6465788
4875211
9999999
8888888
7777777
6666666
5555555
4444444

sample output:
--------------

4937775
4997801
5445463
4648799
4897993
5789857
9554569
8545651
7564550
8798813
6787889
5789722
6465791
4875214
10000019
8888927
7777786
6666679
5555567
4444469
[\c]

[osan]

i didn't check ur code.
u told about smith number on top.
smith number is a problem which's number is 10042 && u told it is 10013. make sure about the problem.

& one thing fmod is a function which use to mod a floating number.

OSAN

[Frostina]

@___@ Why... plz help me...

[cpp]
#include <iostream>
#include <string>
using namespace std;
int main() {
long n,m,i,j; int t1,t2;
string str;
cin >> n;
for (i=0;i<n;i++) {
cin >> m;
for (j=0;j<m;j++) {
cin >> t1 >> t2;
if (t1+t2<10)
str[j] = (t1+t2+48);
else {
str[j] = (t1+t2+38);
str[j-1]++;
}
}
for (j=0;j<m;j++) cout << str[j];
cout << endl << endl;
}
return 0;
}[/cpp]

[pavelph]

You have to find the sum of two numbers with maximal size of 1.000.000 digits.

I think your code can`t solve numbers that have 1000000 digits. Isn`t it?

[Frostina]

Can't string do it ??@_________@

Should I change my code to this ??

[cpp] char str[1000001] [/cpp]

[alex[LSD]]

Well MAYBE my program doesnt output correct answers (that might be true), but how come it gets TLE?!
=-=-=-=-=-=-=-=-=-=-=-=-=
[pascal]
Program uva10013; {Superlong Summs}

Var HasDig : boolean;
a,b,NT,N9,N,i,Dig : longint;
Begin
Read(NT);
While NT>0 do Begin
n9:=0;
Read(N);
read(A,B); Dig:=(a+B) mod 10;

For i:=2 to N do Begin
read(A,B);
Case A+B of
0..8: Begin
Write(Dig);
While N9>0 do Begin Write('9'); Dec(N9); End;
Dig:=A+B;
End;
9:Inc(N9);
10..18: Begin
Write(Dig+1);
While N9>0 do Begin Write('0'); Dec(N9); End;
Dig:=A+B-10;
End;
End;
End;

Write(Dig);
While N9>0 do Begin Write('9'); Dec(N9); End;
Writeln;
Writeln;

Dec(Nt);
End;
End.
[/pascal]

[Dominik Michniewski]

I don't know Pascal very well (I don't remember this behaviour) but what happend when after last case will be empty line ? read() will wait for input or not ? maybe this is cause of TLE

Best regards
DM