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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
First I think you wanted to write a mod instead of last div 10.
And then here is a counterexample:
4
4 4
4 5
4 5
5 5
I think your algorithm will calculate the sum as 8900.

But what you can do is to store a+b, that means you need only one array. Then you go from back to front and calculate carry.

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

your test case proof my algorithm failed, I've fixed it and got AC.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

10013 it gets rte but..

i can't find any alg..
i can't find how to get rid from rte..

#include<stdio.h>
#define N 1000000
main()
{
freopen("c:\\in.txt","r",stdin);
long long cases,z,i,m,a[N],b[N],c[N+10],d;
scanf("%lld",&cases);
for(z=0;z<cases;z++)
{
if(z) printf("\n");
scanf("%lld",&m);
for(i=0;i<m;i++)
scanf("%lld%lld",&a,&b);
for(i=0;i<m+3;i++) c=0;
for(i=(m-1);i>=0;i--)
{
d=a+b;
c[i+1]+=d%10;
c+=d/10;
}
for(i=0;i<m;i++) if(c) break;
for(;i<m+1;i++) printf("%lld",c);
printf("\n");
}
return 0;
}
"Everything should be made simple, but not always simpler"

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Sorry,
you are right hazz...
The answer is : 59822
__nOi.m....

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

10013 RTE.

Can any one tell me why this program gets a runtime error.
I have not considered any negetive index and the array size is
also large enough.

here is my code:
[cpp]

#include<stdio.h>

#define max 1000001

int main()
{
int a[max],b[max];
int n,carry=0,final=0,sum;
char ans[max]="";
char t;
unsigned long test,i,j,k=0;
scanf("%d",&n);
for(;n>0;n--)
{
scanf("%lu",&test);
for(i=0;i<test;i++)
scanf("%d %d",&a[i],&b[i]);
for(j=i-1;;j--)
{ if(j==0) final=1;
sum=a[j]+b[j]+carry;
if(sum<=9) {ans[k]=sum+'0';carry=0;}
else{
sum=sum%10;
ans[k]=sum+'0';
carry=1;
}
k++;
if(final==1) break;

}
if(carry==1) {ans[k]=1+'0';k++;}

carry=0;
for(i=0;i<k/2;i++)
{t=ans[i];
ans[i]=ans[k-i-1];
ans[k-i-1]=t;
}
ans[k]=0;
k=0;
final=0;
printf("%s\n",ans);
if(n!=1) printf("\n");
}
return 0;
}

// Thanx[/cpp]

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Ah, this is the same mistake again ... You tried to allocate a[] and b[] whose size can be 4,000,000 each in the stack. That is most likely what your problem is ... try to declare a[] and b[] as static and see what happens.

You can also try to move a[] and b[] out of your main() function.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Thanx

I have changed my code according to your suggestions and got AC.

Thanks.
Last edited by sohel on Tue Jul 27, 2004 3:00 pm, edited 1 time in total.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
i have tried many times nd got mle(memory..)..
i can't understand what your sugg is?
would u please explain in a easier mode..
--anupam
"Everything should be made simple, but not always simpler"

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

10013

Hi, i need some help here. My code generates the right output, but the judge gives WA...can anyone tell me why?
[c]
#include <stdio.h>
#include <string.h>

long int res[200000],fres[200000];

void main(void)
{
long int i,j,N,M;
int a,b,c;

#ifndef ONLINE_JUDGE
freopen("10013.in","r",stdin);
freopen("10013.out","w",stdout);
#endif

scanf("%ld",&N);
for (;N;N--)
{
scanf("%ld",&M);
memset(res,0,sizeof(res)); /*initialize both array to 0 */
memset(fres,0,sizeof(fres));
for (i=0,j=-1;i<M;i++)
{
if (i%7==0) j++; /* only 7 digits'll be stored in an element of array*/
scanf("%d %d",&a,&b);
c=a+b;
res[j]=(res[j]*10)+c;
if (i%7==0 && res[j]>10 &&i) {res[j-1]+=1; res[j]%=10;}
/* carry is added every first digit */
}
for (i=0 ; j>=0;j--,i++)
{
if (res[j]>9999999) { fres[i+1]+=res[j]/10000000; }
fres+=res[j]%10000000;
}
while(fres==0) i--;
printf("%ld",fres);
for (i--;i>=0;i--)
{
printf("%ld",fres); /*there are no leading zeros in any element*/
}
printf("\n\n");

}
}

[/c]
Here's what my code does....
1. add two integers and store 7 digits in each element of long int array.
if theres a carry...it'll normalize and sum the carry to the previous one
2. after that... check the whole array for carry again....
3. print the result in reverse order (since the array was reversed in 2nd phase)

Sample input&output

6

18
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9

3
3 0
7 9
2 8

5
5 0
8 1
8 0
1 1
1 1

4
8 0
6 3
6 3
2 8

3
1 5
1 5
3 6
2 0

4
0 9
0 9
0 9
1 9

OUTPUT :
1999999999999999998
470
59822
9000
692
10000

Thanks for any help,
Nick

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
I think Try to bigger your array size.

The first line of a input file is an integer N, then a blank line followed by N input blocks. The first line of an each input block contains a single number M (1<=M<=1000000)

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am
Thx Red Scorpion,
but larger array wouldn't change anything....unless your problem is SIGSEGV.
I've change my code and got P.E. , i don't know whats the problem...i've tried to change the output format a few times and still haven't changed

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
Finally solved.
It is similar to 729

rumel_new
New poster
Posts: 3
Joined: Tue Feb 25, 2003 5:44 pm
Location: Dhaka

10013 no problem shows me P.E. why???

here is my code:
[cpp]#include<stdio.h>
#include<stdlib.h>
void main ()
{
long int loop,m,i,n,carry,k,ff;
char *x,*y,*z;
scanf("%ld",&loop);
for(m=0;m<loop;m++)
{
scanf("%ld",&n);
x=( char*)malloc(n*sizeof(char));
y=( char *)malloc(n*sizeof(char));
z=( char*)malloc((n+1)*sizeof(char));
for(i=0;i<n;i++){
scanf("%s %s",x+i,y+i);
}
carry=0;
k=1;
for(i=n-1;i>=0;i--)
{
ff=(carry + (*(x+i)-48) + (*(y+i)-48));
*(z+k)= ((carry + (*(x+i)-48) + (*(y+i)-48))%10)+48;
carry=ff/10;
k++;
}
i=0;
*(z+i)=carry +48;
if(*(z+0)>48)
printf("%c",*(z+0));
for(k=n;k>0;k--)
printf("%c",*(z+k));
printf("\n\n");
}
}
[/cpp]

Why it show PE??
We are SKARBAN.
We will make another world.

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
Actually, I don't know much about C++
But I think you have put an extra blank line after the last test case.
You shouldn't put it and will soon get accepted without presentation error.
Other mutiple input questions will have this similar problem of P.E.

25487AH
New poster
Posts: 2
Joined: Fri Apr 11, 2003 4:58 pm
Location: Venezuela
Contact:

WA to, and i dont know why

Hi, im having troubles whit my code to, can some one help me please?

PD: if i have:
2
9 9
9 9

the output is:
98
(because its M digits, isnt?)

thats my code:

[java]
/* @BEGIN_OF_SOURCE_CODE */
// @JUDGE_ID: 25487AH 10013 Java

import java.io.*;
import java.util.StringTokenizer;
import java.lang.StringBuffer;

class Main{

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

try{
while (lg < maxLg){
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));
}

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

try{
}
catch (IOException e){
return (null);
}
return (new String (lin, 0, maxLg));
}

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(){
StringTokenizer idata;
int s,l=0;
int m,i,n;//,k=0;
StringBuffer tmp;
while (--n>=0){
idata = new StringTokenizer((new StringBuffer(Main.ReadLn2(m*4)).reverse().toString()));
tmp=new StringBuffer(m+1);

l=0;
for(i=0; i<m; i++){
if((s=(Integer.parseInt((idata.nextToken()).trim()))+(Integer.parseInt((idata.nextToken()).trim()))+l)>9){
s-=10;
l=1;
}else
l=0;
tmp.append(s);
}

System.out.println(tmp.reverse().toString());

if(n!=0)
System.out.println();
}
}
}

/* @END_OF_SOURCE_CODE */
[/java]