## 10013 - Super long sums

Moderator: Board moderators

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:
No... I got AC now! It's only that TL is really tight.
What I changed was - now Im printing nines not one by one. Now I print them in groups '9999' + '9999' .... Same with zeros '0000'+... Strange but is decreased my Run Time by over 2secs. I think that If memory limit for this problem was 64K and time limit was a little greater... the problem would only gain from it. Seems like they ve taken it from timus without seeing where is the "cream".
The more contests are held, the happier I am.

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
my output is ok for this input.But i got WA (in 22 times)can any body help
me?what is my problem in my code i have use unsigned long.i have also solve 583 but in this problem i got WA.I am really tired for this problem.

Salmin Sultana
New poster
Posts: 16
Joined: Sun Mar 07, 2004 12:19 pm
Location: Dhaka

### 10013

why it's wa?i need some input& output.
is my algorithm correct?then why wa?

#include<stdio.h>

int d1,d2;
long int n,m,i,j,num;
int a;

int main()
{
int c,k;
scanf("%ld",&n);

for(i=0;i<n;i++)
{
scanf("%ld",&m);

for(j=0;j<m;j++)
{
scanf("%d %d",&d1,&d2);
a[j]=(d1+d2)%10;
c=(d1+d2)/10;

if(c>0)
{
for(k=j-1;k>=0;k--)
{
if((num=(a[k]+c)/10)==0)
{
a[k]=a[k]+c;
break;
}
a[k]=(c+a[k])%10;
c=num;
}
}
}
for(j=0;(a[j]==0);j++);
for(;j<m;j++)
printf("%d",a[j]);
printf("\n");
}
return 0;
}

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: why wa 10013 super long sums

Salmin Sultana wrote:[c]
#include<stdio.h>

int d1,d2;
long int n,m,i,j,num;
int a;

int main()
{
int c,k;
scanf("%ld",&n);

for(i=0;i<n;i++)
{
scanf("%ld",&m);

for(j=0;j<m;j++)
{
scanf("%d %d",&d1,&d2);
a[j]=(d1+d2)%10;
c=(d1+d2)/10;

if(c>0)
{
for(k=j-1;k>=0;k--)
{
if((num=(a[k]+c)/10)==0)
{
a[k]=a[k]+c;
break;
}
a[k]=(c+a[k])%10;
c=num;
}
}
}
for(j=0;(a[j]==0);j++);
for(;j<m;j++)
printf("%d",a[j]);
printf("\n");
}
return 0;
}[/c]
I think you don't treat the carry for the most significant cypher correctly.
Try to change your loop this way:
[c]
a=0;
for(j=1;j<=m;j++)
[/c]
and later on, when printf-ing:
[c]
for(;j<=m;j++)
[/c]
This leaves room for an extra digit at index 0.
Oh, don't forget to add room for another extra digit in your array...

Ciao!!!

Claudio

Salmin Sultana
New poster
Posts: 16
Joined: Sun Mar 07, 2004 12:19 pm
Location: Dhaka
yet i got wa.in problem it was told the sum will be no longer than the given integer.so why extra place.i think there is problem in taking input.
plssss will you check

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
Salmin Sultana wrote:yet i got wa.in problem it was told the sum will be no longer than the given integer.so why extra place.i think there is problem in taking input.
plssss will you check
Sorry for not checking the problem first...
anyway the prob with your prog is in the output:
There is a blank line between output blocks.
Your output for sample input is:

Code: Select all

``````4750
470``````
wich misses the blank line between the two output blocks...

Ciao!!!

Claudio

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
try this:

3

3
4 5
1 1
2 3

3
4 5
7 5
3 3

1
9 8

output:
925

1026

17
cuii e

Salmin Sultana
New poster
Posts: 16
Joined: Sun Mar 07, 2004 12:19 pm
Location: Dhaka
i tried with extra newline but still got wa.i am tired with it

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Clever!.

alex[LSD] wrote:now Im printing nines not one by one. Now I print them in groups '9999' + '9999' .... Same with zeros '0000'+...
Really clever! _.

kenneth_cwc
New poster
Posts: 9
Joined: Sat Oct 18, 2003 2:08 pm

### 10013 WA

[cpp]
#include<iostream>
using namespace std;
struct number
{
int digit;
number *prev;
number *next;
};

void main()
{
int n;
int m;
number* ans;
number* cur;
int t1, t2;
int i;
bool zero;

ans=new number;
ans->prev=NULL;
cur=ans;
for(m=0;m<1000001;m++)
{
cur->next=new number;
cur->next->prev=cur;
cur=cur->next;
}
cur->next=NULL;

cin>>n;
while(n>0)
{
ans->digit=0;
cin>>m;
cur=ans->next;
for(i=0;i<m;i++)
{
cin>>t1>>t2;
cur->digit=t1+t2;
cur=cur->next;
}
cur=cur->prev;
for(i=0;i<m;i++)
{
if(cur->digit/10!=0)
{
cur->prev->digit+=cur->digit/10;
cur->digit%=10;
}
cur=cur->prev;
}
zero=1; //output
cur=ans;
for(i=0;i<m+1;i++)
{
if(!zero || cur->digit!=0)
{
cout<<cur->digit;
zero=0;
}
cur=cur->next;
}
if(n!=1)
cout<<"\n\n";
else
cout<<"\n";
n--;
}
while(ans->next!=NULL)
{
ans=ans->next;
delete ans->prev;
}
delete ans;
}
[/cpp]
i tried many inputs, why got WA?

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
i don't know if such input exits in the judge data set but if may try with

Input:
2

2
0 0
0 0

1
0 0

for these kinds of input your prgram doen't give a blank line output kenneth_cwc
New poster
Posts: 9
Joined: Sat Oct 18, 2003 2:08 pm
in 10013
Each of the two given integers is not less than 1

kenneth_cwc
New poster
Posts: 9
Joined: Sat Oct 18, 2003 2:08 pm
o i found the error....

schang
New poster
Posts: 2
Joined: Sat Apr 24, 2004 11:25 pm
well, i get WA as well... and i really don't know why... i'd be grateful for any kind of suggestion!

[cpp]
#include<iostream>
#include<math.h>
using namespace std;

int resultat ;

void uebertrag(int d, int e)
{
int ink, f, blub;
f = pow(10, 9);
ink = resultat[d];

if(ink + 1 < f)
{
blub = ink + 1;
resultat[d] = blub;

return;
}
else if(ink + 1 >= f)
{
resultat[d] = ink + 1 - f;
uebertrag(d-1, 9);
}
}

void addition(int *a, int *b, int d, int e)
{
int f, g, h, m, z, y, x;
f = 0;
g = 0;
x = e;

for(int i = 0; i < e; i++)
{

h = a;
m = b;
y = pow(10, ((e-i)-1));
f += h*y;
g += m*y;
}

z = pow(10, e);
if(f + g < z)
resultat[d] = f + g;
else
{
resultat[d] = f + g - z;
uebertrag(d-1, x);
}
return;
}

int main()
{
int N;
float M;
int a ;
int b ;
int d;
float e;

cin >> N;

for(int i = 0; i < N; i++)
{
cout << endl;
cin >> M;
if(M > 9)
d = (M / 9) + 1;
else if(M < 9 || M == 9)
d = 1;

for(int j = 0; j < d; j++)
{
if(j < d-1 && M > 9)
e = 9;
else if(M < 9)
e = M;
else if(j == d-1 && M > 9)
e = ((M/9)-(d-1))*9;
else if(M == 9)
e = 9;

for(int k = 0; k < e; k++)
{
cin >> a[k];
cin >> b[k];
}
}
cout << endl;

for(int l = 0; l < d; l++)
cout << resultat[l];

cout << endl;
}
system("PAUSE");
return 0;
}[/cpp]

crisphean
New poster
Posts: 2
Joined: Thu May 27, 2004 5:04 am
Location: HK SAR
Contact:

### 10013 Super long sums WA...need help

store 8 digits in one cell... thank you very much for attentions
[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 135001
#define CARRY 100000000

long a[MAX_LEN], b[MAX_LEN];
long len;
long m;
int casen, casei;

int main()
{
long sum1, sum2;
long x1, x2;
long i, j, p;

scanf("%d", &casen);

for (casei = 0; casei < casen; casei++){
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
len = 0;

scanf("%ld", &m);
p = m%8;
len = m/8;

sum1 = sum2 = 0;
while (p > 0){
scanf("%ld %ld", &x1, &x2);
sum1 = sum1*10+x1;
sum2 = sum2*10+x2;
p--;
}
a[len+1] = sum1;
b[len+1] = sum2;

for (i = len; i > 0; i--){
sum1 = sum2 = 0;
for (j = 0; j < 8; j++){
scanf("%ld%ld", &x1, &x2);
sum1 = sum1*10+x1;
sum2 = sum2*10+x2;
}
a = sum1;
b = sum2;
}

if (m%8 != 0){
++len;
}
for (i = 1; i <= len; i++){
a += b;
}
for (i = 1; i <= len; i++){
if (a >= CARRY){
a[i+1] += a/CARRY;
a %= CARRY;
}
}
if (a[len+1]!=0){
++len;
}
printf("%ld", a[len]);
for (i = len-1; i > 0; i--){
printf("%08ld", a);
}
printf("\n");
if (casei < casen-1){
printf("\n");
}
}

return(0);
}

[/c][/code]