10013 - Super long sums

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Post by soyoja » Fri Apr 18, 2003 1:25 am

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
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am

10013 WA

Post by WanBa » Mon May 12, 2003 7:37 am

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]
destiny conditioned by past

User avatar
Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

Why WA?

Post by Maxim » Mon May 12, 2003 1:08 pm

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
New poster
Posts: 2
Joined: Sat Jun 21, 2003 11:18 pm

10013 WA >< ||

Post by monmobear » Sat Jun 21, 2003 11:22 pm

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
New poster
Posts: 2
Joined: Wed Jul 02, 2003 5:52 am

10013 Super Long Sum - Java Submission TLE /_\

Post by ThomasTse » Wed Jul 02, 2003 6:00 am

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
New poster
Posts: 8
Joined: Sun Sep 14, 2003 11:38 pm
Location: Dhaka
Contact:

10013

Post by Ashique Mahmood Rupam » Fri Sep 26, 2003 1:04 am

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 ?
There is Nothing, Nothing At All !

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Fri Sep 26, 2003 7:38 am

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??
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.

problem
New poster
Posts: 27
Joined: Mon Nov 10, 2003 12:40 am

10013 help me

Post by problem » Tue Nov 25, 2003 11:34 am

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
New poster
Posts: 27
Joined: Mon Nov 10, 2003 12:40 am

Post by problem » Wed Dec 10, 2003 12:08 pm

[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
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

10013

Post by osan » Wed Dec 17, 2003 5:02 pm

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
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am

10013 Runtime error :(

Post by Frostina » Tue Dec 30, 2003 6:41 pm

@___@ 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]
Thanks for your help ! ;)

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Hm...

Post by pavelph » Tue Dec 30, 2003 9:53 pm

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
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am

Post by Frostina » Wed Dec 31, 2003 1:45 am

Can't string do it ??@_________@

Should I change my code to this ??

[cpp] char str[1000001] [/cpp]
Thanks for your help ! ;)

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

10013 Pascal O(N) TLE!!! How Come?!

Post by alex[LSD] » Mon Feb 09, 2004 10:42 am

Well MAYBE my program doesnt output correct answers (that might be true), but how come it gets TLE?! :o
=-=-=-=-=-=-=-=-=-=-=-=-=
[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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Feb 09, 2004 10:52 am

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
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)

Post Reply

Return to “Volume 100 (10000-10099)”