10013 - Super long sums

[dovier_antonio]

I'm trying with yours tests and all seems to be ok! I don't know where is my problem.

Thanks!

[WR]

Your result is really

Code: Select all

1999999999999999998

470

59822

9000

6692                 < ---- ????

10000

?

[dovier_antonio]

nothing... i'm WA again... :/

thanks by your help...

[dovier_antonio]

Finally I got accepted!!

My mistake was that I delete the leading zeros from the output...

Thanks!

[J&Jewel]

HI morning if not solved this problem yet then
just think it normally..this is a very easy problem!
1. do loop to m.
2.scan p & q and add them put in an array.
3.call norm function.
the norm function
int norm()
{
long i,len,coff;
len=count;
for(i=0;i<len-1;i++)
{
if(array[count-1]>=10)
{
coff=array[count-1]/10;
array[count-2]=array[count-2]+coff;
array[count-1]=array[count-1]%10;
}
else
coff=0;
--count;

}
return len;
}
i think this might help.....

[Jemerson]

Hi, Ive got the same problem, my code looks like yours and ive also tryied many different approaches. In fact i guess the problem is in the input reader, maybe work with String slow down the program. I'll try to find one readInt code to try again and post the result =]

[boyeric]

hi dudes, i am extremely desperate.... i implemented problem 10013 by JAVA using 2 different algorithms and submitted over 25 times, one got Memory Limit Exceeded, and the other Time Limit excceeded.... could any java experts please give me a hand?

the first version got MTE:

Code: Select all

import java.util.StringTokenizer;
import java.util.Vector;

/**@author Eric
 * Created on 2005-6-8
 */
class Main {

	public static void main(String[] args) {
		try{
			
			String line = Main.readLine();
			int c = Integer.parseInt(line.trim());
			int digit;
			short a, b, d;
			StringTokenizer st;
			Vector v = new Vector();
			for(int i=0 ; i<c ; i++){
				line = Main.readLine();
				digit = Integer.parseInt(line.trim());
				for(int j=0 ; j<digit ; j++){
					line = Main.readLine();
					st = new StringTokenizer(line.trim());
					a = Short.parseShort(st.nextToken().trim());
					b = Short.parseShort(st.nextToken().trim());
					while(b>0){
						a++;
						b--;
					}
					if (a > 9){
						a -= 10;
						v.addElement(""+a);
						int k = v.size()-2;
						while(Integer.parseInt((String)v.elementAt(k))+1>9){							v.removeElementAt(k);
							v.insertElementAt(""+0,k);
							k--;
						}
						d = Short.parseShort((String)v.elementAt(k));
						v.removeElementAt(k);
						v.insertElementAt(""+(d+1),k);
						for (k=0 ; k<v.size()-1 ; k++){
							System.out.print((String)v.elementAt(0));
							v.removeElementAt(0);
						}
					}else{
						v.addElement(""+a);
						if(a<9){
							for (int k=0 ; k<v.size()-1 ; k++){
								System.out.print((String)v.elementAt(0));
								v.removeElementAt(0);
							}
						}
					}
				}
				for (int j=0 ; j<v.size() ; j++){
					System.out.print((String)v.elementAt(0));
					v.removeElementAt(0);
				}
				if(i!=c-1){
					System.out.println("\n");
				}
							}
		}catch(Exception e){
			System.err.println(e.getMessage());
		}
		
	}
	
	static String readLine(){return token( "\n\r" );}    
	    
	    
	/* read token from stdIn with standard delims */ 
	static String token( ){return token( " \n\r\t" );} 
	    
	    
	/* read token from stdIn with custom delims */ 
	/* returns null for end of file or any exceptions */ 
	static String token( String delim ){ 
		char c = delim.charAt(0); 
		StringBuffer s = new StringBuffer(""); 
		try{ 
		  while( delim.indexOf( (int) c ) != -1 && c != 65535 ) 
			  c = (char) System.in.read(); 
		  while( delim.indexOf( (int) c ) == -1 && c != 65535 ){ 
			  s.append( (char) c ); 
			  c = (char) System.in.read(); 
		  } 
		}catch( Exception e ){ return (null); } 
		if( s.toString().equals("") ) return null; 
		return s.toString(); 
	}

}

[boyeric]

the second version with TLE. in fact i've seen people with exactly the same algorithm got accepted in C, just dont know why it doesn't work for JAVA.....

Code: Select all

import java.util.StringTokenizer;

/**@author Eric
 * Created on 2005-6-9
 */
class Main {

	public static void main(String[] args) {
		short [] res;
		String line = Main.readLine();
		int c = Integer.parseInt(line.trim());
		short a, b, base, over, d;
		int digit;
		StringTokenizer st;
		for(int i=0 ; i<c ; i++){
			res = new short [1000000];
			line = Main.readLine();
			digit = Integer.parseInt(line.trim());
			for(int j=0 ; j<digit ; j++){
				line = Main.readLine();
				st = new StringTokenizer(line.trim());
				a = Short.parseShort(st.nextToken().trim());
				b = Short.parseShort(st.nextToken().trim());
				while(b>0){
					a++;
					b--;
				}
				res[j] = a;
			}
			for(int j=digit-1 ; j>=0 ; j--){
				if (res[j]>=10){
					res[j]-=10;
					res[j-1]+=1;
				}
			}
			for (int j=0 ; j<digit ; j++){
				System.out.print(res[j]);
			}
			if (i != c-1){
				System.out.println("\n");
			}
		}
	}
	
	static String readLine(){return token( "\n\r" );}    
	    
	    
	/* read token from stdIn with standard delims */ 
	static String token( ){return token( " \n\r\t" );} 
	    
	    
	/* read token from stdIn with custom delims */ 
	/* returns null for end of file or any exceptions */ 
	static String token( String delim ){ 
		char c = delim.charAt(0); 
		StringBuffer s = new StringBuffer(""); 
		try{ 
		  while( delim.indexOf( (int) c ) != -1 && c != 65535 ) 
			  c = (char) System.in.read(); 
		  while( delim.indexOf( (int) c ) == -1 && c != 65535 ){ 
			  s.append( (char) c ); 
			  c = (char) System.in.read(); 
		  } 
		}catch( Exception e ){ return (null); } 
		if( s.toString().equals("") ) return null; 
		return s.toString(); 
	}

}

[boyeric]

I've tried really hard and enormous different approaches but still cannot get it work..... i even copy-pasted exactly the same code from C to JAVA except for difference from input/output, but it still gave a TLE error while the same code in C got AC, depresssssed....

Could any JAVA experts who has solved #10013 please share your source code or experience with us?

Expecting.....

[jaracz]

system("Pause"); <--- will lead you always to WA (if not compile error)
I didn't read your code enough to state what is wrong, but try erasing this unlucky"system("Pause")";

maybe it helps, regards

[Sedefcho]

I've solved it in C++ but I have solved many problems in Java.
Can you send me your code via a private message? I will try it
when I have some time. I hope I will notice something wrong
which would explain the TLE of your Java program.
You said you've even copy-pasted from C to Java and
you have just changed the I/O processing. Then maybe
the problem is in your I/O processing ?!
As I don't know how experienced you are in Java - do you know
that you should use a special function for reading input in Java
( btw, its source code is here somewhere on that site ) ?!

I give it below:

Code: Select all

public static String readLn (int maxLg){
            byte lin[] = new byte [maxLg];
            int lg = 0, car = -1;

            try{
                while (lg < maxLg){
                    car = System.in.read();
                    if ((car < 0) || (car == '\n')) break;
                    lin [lg++] += car;
                }
            }catch (java.io.IOException e){
                return (null);
            }

            if ((car < 0) && (lg == 0)) return (null);  // eof
            return (new String (lin, 0, lg));
    }

[Sedefcho]

Well, I remember that problem. No other problems
( or at least very few of them ) have such large input
lines ( up to 1 000 000 chars ). If you use
the function I mentioned above then I may be able to give
you a hint of why
just calling it once with a maxLg = 1000 000 is so slow.
And I'm sure the Judge's test input data has many lines and many
of them are with a length of about 100 000 - 1 000 000.

We could try to optimize the code of readLn(int).
Or we can even use a specific function for reading the input
in this problem 10013. By "specific", I mean a function different
than the normal one ( different than the one given in my previous
post ).

[Jemerson]

I suggest you to use a StringBuffer object and put all your answers together and just print it all in the end. Printing in Java is too slow.

[Andisheh]

my code give the correct answer for any input I have tried,
I dont know whats wrong with that,
would you help me!


#include <iostream.h>
//#include <fstream.h>
#include <string.h>
//#include <math.h>
#include <stdlib.h>
int a[1000001],b[1000001],r[1000001];
void main()
{
int i,j,k,n,m,l,sum;

//ifstream f("10013.in");
cin>>n;
for(k=0 ; k<n ; k++)
{
cin>>m;
for(i=0 ; i<m ; i++)
{
cin>>a;
cin>>b;
}
a=b=0;
sum=0;
r[m+1]=0;
j=0;
for(i=m-1 ,l=0; i>=0 ; i--,l++)
{
sum=(a+b+j);
if(sum>9)
j=1;
else
j=0;
r[i+1]=sum%10;
}
if(j==1)
r[0]=1;
else
r[0]=0;
// cout<<sum<<endl;
for(i=0 ; r==0 ; i++);
for(j=i ; j<=m ; j++)
cout<<r[j];
cout<<endl;
if(k<n-1)
cout<<endl;
// cout<<r<<endl;
}
// cin>>i;
}

[tan_Yui]

Hi, 58225CY, Andisheh.

Your code outputs blank line in the case of the following :

Code: Select all

1

1
0 0

Best regards.