10013 - Super long sums
Moderator: Board moderators
10013 - Super long sums
Hello !
What's wrong in this source ?
My program Accepted on acm.timus.ru but on uva.es not ?
This my source code:
[c]
#include <stdio.h>
int main() {
long l9;
int mem;
long N, M;
long i,j, k;
int S;
int l1, l2;
scanf("%ld", &M);
for(k=0; k<M; k++) {
scanf("%ld", &N);
for(i=0, l9=0, mem=-1, S=0; i<N; i++) {
scanf("%d%d", &l1, &l2);
if ((S = l1 + l2) == 9) {
if(mem == -1) printf("9");
else l9++;
}
else {
if (mem != -1) {
printf("%d", mem + S/10);
mem = S%10;
}
else mem = S;
for (j=0; j<l9; j++) printf("0");
l9 = 0;
}
}
if (mem != -1)
printf("%d", mem);
for(j=0; j<l9; j++) printf("9");
printf("\n\n");
}
return 0;
}
[/c]
What's wrong in this source ?
My program Accepted on acm.timus.ru but on uva.es not ?
This my source code:
[c]
#include <stdio.h>
int main() {
long l9;
int mem;
long N, M;
long i,j, k;
int S;
int l1, l2;
scanf("%ld", &M);
for(k=0; k<M; k++) {
scanf("%ld", &N);
for(i=0, l9=0, mem=-1, S=0; i<N; i++) {
scanf("%d%d", &l1, &l2);
if ((S = l1 + l2) == 9) {
if(mem == -1) printf("9");
else l9++;
}
else {
if (mem != -1) {
printf("%d", mem + S/10);
mem = S%10;
}
else mem = S;
for (j=0; j<l9; j++) printf("0");
l9 = 0;
}
}
if (mem != -1)
printf("%d", mem);
for(j=0; j<l9; j++) printf("9");
printf("\n\n");
}
return 0;
}
[/c]
|Q|
10013 why runtime error?
the code:
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
void add(int x[],int y[],int m)
{
int dig,tag,z[10000],i;
tag=0;
for(i=0;i<m;i++)
{
dig=(x+y+tag)%10;
tag=(x+y+tag)/10;
z=dig;
}
for(i=m-1;i>=0;i--)
{if((tag>0)&&(i==m-1)) cout<<tag;
cout<<z;
}
cout<<endl;
cout<<endl;
}
void main()
{
int x[10000,y[10000];
int n,m,i,j;
char ch;
cin>>n;
for(i=1;i<=n;i++)
{
cin.get(ch);
cin>>m;
for(j=m-1;j>=0;j--)
cin>>x[j]>>y[j];
add(x,y,m);
}
}
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
void add(int x[],int y[],int m)
{
int dig,tag,z[10000],i;
tag=0;
for(i=0;i<m;i++)
{
dig=(x+y+tag)%10;
tag=(x+y+tag)/10;
z=dig;
}
for(i=m-1;i>=0;i--)
{if((tag>0)&&(i==m-1)) cout<<tag;
cout<<z;
}
cout<<endl;
cout<<endl;
}
void main()
{
int x[10000,y[10000];
int n,m,i,j;
char ch;
cin>>n;
for(i=1;i<=n;i++)
{
cin.get(ch);
cin>>m;
for(j=m-1;j>=0;j--)
cin>>x[j]>>y[j];
add(x,y,m);
}
}
10013
Please. help me.
I solved this problem. but I recive Memory Limit Exceeded
the source:
[cpp]
#include <iostream.h>
int a[1000001];
int b[1000001];
int c[10][1000001];
unsigned long mc[10];
unsigned long n;
unsigned long m;
int temp=0;
void main()
{
cin>>n;
unsigned long i,j;
for(i=0;i<n;i=i+1)
{
cin>>m;
for(j=0;j<m;j=j+1)
{
cin>>b[j+1];
cin>>a[j+1];
}
int flag=0;
for(j=m;flag==0;j--)
{
if(j==0)flag=1;
c[j] = a[j]+b[j]+temp;
temp=0;
if(c[j]>=10)
{
c[j]=c[j]-10;
temp=1;
}
}
mc=m;
}
for(i=0;i<n;i++)
{
int flag=0;
for(j=0;j<=mc;j=j+1)
{
if((c[j]==0 && flag ==0)!=1)
{
cout<<c[j];
flag=1;
}
}
cout<<endl<<endl;
}
}
[/cpp]
How can I solve this problem ?
Pls tell me the answer .
I solved this problem. but I recive Memory Limit Exceeded
the source:
[cpp]
#include <iostream.h>
int a[1000001];
int b[1000001];
int c[10][1000001];
unsigned long mc[10];
unsigned long n;
unsigned long m;
int temp=0;
void main()
{
cin>>n;
unsigned long i,j;
for(i=0;i<n;i=i+1)
{
cin>>m;
for(j=0;j<m;j=j+1)
{
cin>>b[j+1];
cin>>a[j+1];
}
int flag=0;
for(j=m;flag==0;j--)
{
if(j==0)flag=1;
c[j] = a[j]+b[j]+temp;
temp=0;
if(c[j]>=10)
{
c[j]=c[j]-10;
temp=1;
}
}
mc=m;
}
for(i=0;i<n;i++)
{
int flag=0;
for(j=0;j<=mc;j=j+1)
{
if((c[j]==0 && flag ==0)!=1)
{
cout<<c[j];
flag=1;
}
}
cout<<endl<<endl;
}
}
[/cpp]
How can I solve this problem ?
Pls tell me the answer .
10013 time limit exceeded!
I think this should be fast enough.
However, this still exceeds time limit!!
How can I improve this?
However, this still exceeds time limit!!
How can I improve this?
Last edited by Eric on Thu Mar 27, 2003 2:53 pm, edited 1 time in total.
I am getting WA.
how is the formmating?
[cpp]#include <iostream.h>
#include <iomanip.h>
int main() {
int total,length,a,b,sum[111113],i,k,temp; // sum base 1000000000
cin >> total;
for (int count=0; count<total; count++) {
if (count != 0)
cout << "\n\n";
cin >> length; // no of digits
sum[0] = 0;
// input digits
k = length%9;
if (k==0)
k=9;
// 9 digits group
for (i=1; i<=((length-1)/9)+1; ++i) { // sum[0] is reserved in case of carry, start form sum[1]
temp=0;
while (k--) {
cin >> a >> b;
temp = temp*10 + a+b;
}
sum = temp;
if (sum > 1000000000) {
sum -= 1000000000;
++sum[i-1];
}
k=9;
}
// calculate carry
for (--i;i>=0; --i)
if (sum > 1000000000) {
sum -= 1000000000;
++sum[i-1];
}
// output
for (k=0;k<=((length-1)/9)+1;++k) {
if (sum[k]) {
cout << sum[k];
break;
}
if (k==((length-1)/9)+1) // in case the answer is zero
cout << 0;
}
for(++k; k<=((length-1)/9)+1; ++k)
cout << setw(9) << setfill('0') << sum[k];
}
return 0;
}[/cpp]
how is the formmating?
[cpp]#include <iostream.h>
#include <iomanip.h>
int main() {
int total,length,a,b,sum[111113],i,k,temp; // sum base 1000000000
cin >> total;
for (int count=0; count<total; count++) {
if (count != 0)
cout << "\n\n";
cin >> length; // no of digits
sum[0] = 0;
// input digits
k = length%9;
if (k==0)
k=9;
// 9 digits group
for (i=1; i<=((length-1)/9)+1; ++i) { // sum[0] is reserved in case of carry, start form sum[1]
temp=0;
while (k--) {
cin >> a >> b;
temp = temp*10 + a+b;
}
sum = temp;
if (sum > 1000000000) {
sum -= 1000000000;
++sum[i-1];
}
k=9;
}
// calculate carry
for (--i;i>=0; --i)
if (sum > 1000000000) {
sum -= 1000000000;
++sum[i-1];
}
// output
for (k=0;k<=((length-1)/9)+1;++k) {
if (sum[k]) {
cout << sum[k];
break;
}
if (k==((length-1)/9)+1) // in case the answer is zero
cout << 0;
}
for(++k; k<=((length-1)/9)+1; ++k)
cout << setw(9) << setfill('0') << sum[k];
}
return 0;
}[/cpp]
10013 (super long sums) TLE
I got TLE after rejuging (I got AC before).
I did not use large arrays.
Do I need to use large arrays to store the number?
[pascal]
var i, n, p, q : longint;
a, b, aa, bb, last, oldest : byte;
cases : integer;
begin
readln(cases);
readln;
repeat
readln(n);
readln(a, b);
if a + b >= 10 then write(1);
last := (a + b) mod 10;
oldest := last;
if a + b = 9 then p := 1; q := p;
for i := 2 to n + 1 do
begin
if i < n + 1 then read(a, b) else begin a := 0; b := 0; end;
if (a + b < 9) and (last < 9) then
begin
write(last);
last := a + b;
end
else
if (a + b >= 10) and (last < 9) then
begin
write(last + 1);
last := a + b - 10;
end
else
if (a + b = 9) and (last = 9) then
begin
end
else
if (a + b = 9) and (last <> 9) then
begin
oldest := last;
last := 9;
p := i; {q := p; }
end
else
if (a + b < 9) and (last = 9) then
begin
if oldest <> 9 then write(oldest);
for q := p to i - 1 do write(9);
last := a + b;
end
else
if (a + b >= 10) and (last = 9) then
begin
if oldest + 1 >= 10 then write(1);
write((oldest + 1) mod 10);
for q := p to i - 1 do write(0);
last := a + b - 10;
end;
end;
writeln; writeln;
dec(cases);
until cases = 0;
end.
[/pascal]
I did not use large arrays.
Do I need to use large arrays to store the number?
[pascal]
var i, n, p, q : longint;
a, b, aa, bb, last, oldest : byte;
cases : integer;
begin
readln(cases);
readln;
repeat
readln(n);
readln(a, b);
if a + b >= 10 then write(1);
last := (a + b) mod 10;
oldest := last;
if a + b = 9 then p := 1; q := p;
for i := 2 to n + 1 do
begin
if i < n + 1 then read(a, b) else begin a := 0; b := 0; end;
if (a + b < 9) and (last < 9) then
begin
write(last);
last := a + b;
end
else
if (a + b >= 10) and (last < 9) then
begin
write(last + 1);
last := a + b - 10;
end
else
if (a + b = 9) and (last = 9) then
begin
end
else
if (a + b = 9) and (last <> 9) then
begin
oldest := last;
last := 9;
p := i; {q := p; }
end
else
if (a + b < 9) and (last = 9) then
begin
if oldest <> 9 then write(oldest);
for q := p to i - 1 do write(9);
last := a + b;
end
else
if (a + b >= 10) and (last = 9) then
begin
if oldest + 1 >= 10 then write(1);
write((oldest + 1) mod 10);
for q := p to i - 1 do write(0);
last := a + b - 10;
end;
end;
writeln; writeln;
dec(cases);
until cases = 0;
end.
[/pascal]
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore