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
branka
New poster
Posts: 4
Joined: Fri Sep 10, 2004 2:21 pm

10013 stil got WA!!!!Please!!!!

Post by branka »

I change my code, but i stil get WA and i don't know why???
My new code is:

JAVA:

Code: Select all

[java]
/* @JUDGE_ID: 50020MM 10035 java */
import java.io.*;
import java.util.*;

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

        try
        {
            while (lg < maxLg)
            {
                car = System.in.read();
                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));
    }

    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()
    {
        String input;
        StringTokenizer idata;
        int N;
        int stevec = 0;
        int M = 0;
        int prenesi = 0;
        int vsota = 0;
        int stevilo = 0;
        input = Main.ReadLn (255);
        N = Integer.parseInt(input.trim());
        input = Main.ReadLn (255);

        while (stevec < N)
        {
			prenesi = 0;
        	input = Main.ReadLn (255);
            M = Integer.parseInt(input.trim());
            if((N == 0) &&(M == 0))break;
            	int tab1 [] = new int[M];
                int tab2 [] = new int[M];
                int rezultat [] = new int[M];
                for (int i=0; i < M; i++)
                {
                	input = Main.ReadLn (255);
                	idata = new StringTokenizer (input.trim());
                	int a = Integer.parseInt(idata.nextToken());
                	int b = Integer.parseInt(idata.nextToken());
                	vsota = a + b;
                	rezultat[i] = vsota;
				}//for
				for(int i = M-1; i >= 0; i--){
			    	rezultat[i] = rezultat[i]+prenesi;
              		if((rezultat[i]) >= 10){
						prenesi = 1;
                		rezultat[i] = rezultat[i]%10;
					}//if
					else{
						rezultat[i] = rezultat[i];
						prenesi = 0;
					}//else
				}//for
				stevec++;
				System.out.println();
				for(int k = 0; k < M; k++){ 
					System.out.print(rezultat[k]);
				}
				System.out.println("\n");
		} //while
	} //Begin()
} //class
/* @END_OF_SOURCE_CODE  */
[/java]


Do you have to read all the blocks and then you print the answer, or you read one block at the time. Can you do like this???



input
2

4
1 2
3 4
5 5
4 1

output
3805

input
3
9 8
6 2
1 1

output
782


Thank you for you help!!!!
 :D  :D  :D

Isilio
New poster
Posts: 4
Joined: Sun Nov 16, 2003 8:53 am

come on try!!!

Post by Isilio »

man u need to read all the input n print the output!!

Bye bye!!!

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

10013

Post by emotional blind »

i dont know why get wrong answer
is there any critical input..
help me plz

[/c]
#include<stdio.h>


#define MAX 1000000

int main(void)
{
unsigned long int block,i;
long int m,j;
short p[MAX],a,b,carry;

scanf("%lu",&block);

for(i=1;i<=block;i++){
scanf("%ld",&m);
j=0;
for(j=0;j<m;j++){
scanf("%hd%hd",&a,&b);
p[j]=a+b;
}
carry=0;
for(j=m;j>=0;j--){
p[j]=p[j]+carry;
carry=p[j]/10;
p[j]=p[j]%10;
}

if(i>1)printf("\n");
for(j=0;j<m;j++)printf("%hd",p[j]);
printf("\n");
}
return 0;
}
[c][/c]

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

carry....... oh yeah

Post by sohel »

Consider this input

Code: Select all

1

2
9 9
9 9
Your program outputs 98, but the correct output should be 198.

And try to make your array size a little larger... I mean change it to something like 1000010.

Hope it helps. :wink:

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

thanks

Post by emotional blind »

thanks sohel i got accepted.
thanks a lot
but problem description says
"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)

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

you are right

Post by sohel »

Hmm.. I think you are right..
- I overlooked this statement and coded without noticing it and got AC.

Well, it looks like your code is correct with respect to the problemstatement but not with the judge data.

I will inform the concerned people about this error.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

No, the problem statement and the inputset are correct. My AC program wouldn't work if that was not so.
Sohel, your testcase is illegal. Your program got AC because the input doesn't contain cases like that.
The problem in "emotional blind"'s program is the statement[c] for(j=m;j>=0;j--){
p[j]=p[j]+carry;
carry=p[j]/10;
p[j]=p[j]%10;
}
[/c]which will access p[1000000] for m==1000000, and that is out of bounds and leads to eratic behaviour.

Change it to[c]for(j=m-1;j>=0;j--){
...[/c]
and the above program gets accepted.

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

oops

Post by sohel »

Once again you are right...
.. I actually sent emotional blind's code by modifying the part I have mentioned and increasing the array size to 1000100 and got AC and so I thought it was because of amending the former part that caused the code to to get ACed.

I later just increased the array size and that got AC too and it infers that my suggestions/ideas were a little of the track.

Sorry for any confusion that I might have created and thanks to LJ for correcting the wrong information that are posted in this forum.

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

10013 Super Long Sums Why WA?

Post by Morning »

I've read all topics concerning 10013,but still don't know why i got WA.
can anyone help me?

Code: Select all

#include <cstdio>
#include <cmath>
using namespace std;
#define	MAXDIGITS	1000101		/* maximum length bignum */ 

typedef struct {
        char digits[MAXDIGITS];         /* represent the number */
        long lastdigit;			/* index of high-order digit */
} bignum;

void print_bignum(bignum *n)
{
	long i;
	for (i=n->lastdigit; i>=0; i--)
		printf("%c",'0'+ n->digits[i]);
	printf("\n");
}

void long_to_bignum(long s, bignum *n)
{
	long i;				/* counter */
	long t;				/* long to work with */

	for (i=0; i<MAXDIGITS; i++) n->digits[i] = (char) 0;

	n->lastdigit = -1;

	t = s;

	while (t > 0) {
		n->lastdigit ++;
		n->digits[ n->lastdigit ] = (t % 10);
		t = t / 10;
	}

	if (s == 0) n->lastdigit = 0;
}

void initialize_bignum(bignum *n)
{
	long_to_bignum(0,n);
}


long max(long a, long b)
{
	if (a > b) return(a); else return(b);
}

void zero_justify(bignum *n)
{
	while ((n->lastdigit > 0) && (n->digits[ n->lastdigit ] == 0))
		n->lastdigit --;
}

void add_bignum(bignum *a, bignum *b, bignum *c)
{
	long carry;			/* carry digit */
	long i;				/* counter */

	initialize_bignum(c);

	c->lastdigit = max(a->lastdigit,b->lastdigit)+1;
	carry = 0;

	for (i=0; i<=(c->lastdigit); i++) {
		c->digits[i] = (char) (carry+a->digits[i]+b->digits[i]) % 10;
		carry = (carry + a->digits[i] + b->digits[i]) / 10;
	}
	zero_justify(c);
}
int main()
{
	long N,digi,temp,first1,first2;
	bignum n1,n2,n3;
	scanf("%d",&N);
	while(N--)
	{
		first1 = first2 = 1;
		initialize_bignum(&n1);
		initialize_bignum(&n2);
		scanf("%d",&digi);
		n1.lastdigit = n2.lastdigit = digi - 1;
		for(long i = 0;i < digi;i++)
		{
			scanf("%d",&temp);
			if(temp == 0 && first1) {n1.lastdigit--;first1 = 0;}//delete the pre 0s
			else n1.digits[digi - 1 - i] = temp;
			scanf("%d",&temp);
			if(temp == 0 && first2) {n2.lastdigit--;first2 = 0;}
			else n2.digits[digi - 1 - i] = temp;
		}
		add_bignum(&n1,&n2,&n3);
		print_bignum(&n3);
		printf("\n");
	}
	return 0;
}
thanks
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui »

Hi, Morning.
Your code was not able to be executed in my environment.
Maybe total number of array elements are too many.

Try compile and execute the code once on another machine.

Best regards.

User avatar
dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

10013

Post by dovier_antonio »

This is my source code for the problem 10013, now I got WA, but I don't know where is my bug... ;)

Please Help me....

Code: Select all


Thanks in advance!
Last edited by dovier_antonio on Fri Feb 03, 2012 9:37 am, edited 1 time in total.

User avatar
dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

Hi !!!!

Post by dovier_antonio »

I make my array in 100010 and I got WA !!!!

I casting any character (digits):

char c;

int t = c - 48;

I think that my problem is in the range

Thanx in advances!!!

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

Your array's still too small, try with 1000001.

User avatar
dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

Hi !!! In the problem 10013 I have WA...

Post by dovier_antonio »

I'm trying with all tests in his forum and I got WA again...

thanks in advance!
Last edited by dovier_antonio on Fri Feb 03, 2012 9:38 am, edited 1 time in total.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

Did you try

Code: Select all

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

4
1 5
1 5
3 6
2 0

5
0 0
0 9
0 9
0 9
1 9
?

I tested your program and its results differ from my results (well, one line anyway).

And please be careful with those ... smileys.

Post Reply

Return to “Volume 100 (10000-10099)”