10013 - Super long sums

[alex[LSD]]

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

[mohiul alam prince]

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]

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[1000001];

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]

[c]
#include<stdio.h>

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

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]=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]

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]

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]

try this:

3

3
4 5
1 1
2 3

3
4 5
7 5
3 3

1
9 8

output:
925

1026

17

[Salmin Sultana]

i tried with extra newline but still got wa.i am tired with it

[_.B._]

now Im printing nines not one by one. Now I print them in groups '9999' + '9999' .... Same with zeros '0000'+...

Really clever!

[kenneth_cwc]

[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?
thanks for your help~

[prince56k]

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]

in 10013
Each of the two given integers is not less than 1

[kenneth_cwc]

o i found the error....
thanks for reading~

[schang]

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 [111112];

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 [9];
int b [9];
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];
}
addition(a, b, j, e);
}
cout << endl;

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

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

[crisphean]

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]