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

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

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

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

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Sun Feb 29, 2004 5:15 pm

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

Post by Salmin Sultana » Mon Mar 08, 2004 4:12 pm

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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: why wa 10013 super long sums

Post by CDiMa » Tue Mar 09, 2004 11:00 am

Salmin Sultana wrote:[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
New poster
Posts: 16
Joined: Sun Mar 07, 2004 12:19 pm
Location: Dhaka

Post by Salmin Sultana » Tue Mar 09, 2004 11:39 am

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

Post by CDiMa » Tue Mar 09, 2004 1:40 pm

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

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

Post by alu_mathics » Tue Mar 09, 2004 3:04 pm

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

Post by Salmin Sultana » Tue Mar 09, 2004 3:49 pm

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

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

Clever!.

Post by _.B._ » Thu Apr 01, 2004 6:08 am

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! :D
_.

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

10013 WA

Post by kenneth_cwc » Wed Apr 07, 2004 9:48 pm

[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
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
Location: BANGLADESH

Post by prince56k » Mon Apr 12, 2004 3:41 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

Post by kenneth_cwc » Tue Apr 13, 2004 9:35 am

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

Post by kenneth_cwc » Tue Apr 13, 2004 10:01 am

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

schang
New poster
Posts: 2
Joined: Sat Apr 24, 2004 11:25 pm

Post by schang » Sat Apr 24, 2004 11:31 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 [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
New poster
Posts: 2
Joined: Thu May 27, 2004 5:04 am
Location: HK SAR
Contact:

10013 Super long sums WA...need help

Post by crisphean » Mon May 31, 2004 5:30 am

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]

Post Reply

Return to “Volume 100 (10000-10099)”