10013 - Super long sums
Moderator: Board moderators
-
- Experienced poster
- Posts: 106
- Joined: Sun Feb 17, 2002 2:00 am
- Location: Seoul, South Korea
- Contact:
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. ^^
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. ^^
10013 WA
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]
[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]
destiny conditioned by past
Why WA?
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
After computation, only line1[num] might be leading zero, so test only for it, not whole line1.
Maxim
10013 WA >< ||
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 ~
[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 ~
10013 Super Long Sum - Java Submission TLE /_\
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]
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]
-
- New poster
- Posts: 8
- Joined: Sun Sep 14, 2003 11:38 pm
- Location: Dhaka
- Contact:
10013
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 ?
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 ?
There is Nothing, Nothing At All !
-
- Experienced poster
- Posts: 136
- Joined: Tue Apr 01, 2003 6:59 am
- Location: Jakarta, Indonesia
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??
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??
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.
10013 help me
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]
[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]
[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]
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]
10013
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
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
10013 Runtime error :(
@___@ 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]
[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]
Thanks for your help ! 

-
- Learning poster
- Posts: 53
- Joined: Sat Jan 24, 2004 9:22 pm
- Location: Tomsk, Siberia, RUSSIA
- Contact:
10013 Pascal O(N) TLE!!! How Come?!
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]

=-=-=-=-=-=-=-=-=-=-=-=-=
[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]
Last edited by alex[LSD] on Mon Feb 09, 2004 10:53 am, edited 1 time in total.
The more contests are held, the happier I am.
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
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
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Born from ashes - restarting counter of problems (800+ solved problems)