10013 - Super long sums

Moderator: Board moderators

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

Hi WA !!!!!

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

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

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

Code: Select all

``````1999999999999999998

470

59822

9000

6692                 < ---- ????

10000``````
?

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

Hi !!!

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

Last edited by dovier_antonio on Fri Feb 03, 2012 9:41 am, edited 1 time in total.

dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba
Finally I got accepted!!

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

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

J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Contact:
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
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:
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 =]
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

boyeric
New poster
Posts: 6
Joined: Sun Jun 20, 2004 5:08 pm

10013 by a desperate JAVA user.... MLE + TLE

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{

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++){
digit = Integer.parseInt(line.trim());
for(int j=0 ; j<digit ; j++){
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;
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{
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());
}

}

/* read token from stdIn with standard delims */

/* 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 )
while( delim.indexOf( (int) c ) == -1 && c != 65535 ){
s.append( (char) c );
}
}catch( Exception e ){ return (null); }
if( s.toString().equals("") ) return null;
return s.toString();
}

}``````
Last edited by boyeric on Thu Jun 09, 2005 4:42 am, edited 1 time in total.

boyeric
New poster
Posts: 6
Joined: Sun Jun 20, 2004 5:08 pm
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;
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];
digit = Integer.parseInt(line.trim());
for(int j=0 ; j<digit ; j++){
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");
}
}
}

/* read token from stdIn with standard delims */

/* 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 )
while( delim.indexOf( (int) c ) == -1 && c != 65535 ){
s.append( (char) c );
}
}catch( Exception e ){ return (null); }
if( s.toString().equals("") ) return null;
return s.toString();
}

}``````

boyeric
New poster
Posts: 6
Joined: Sun Jun 20, 2004 5:08 pm

10013

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
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
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
keep it real!

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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){
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));
}
``````
Last edited by Sedefcho on Sat Jun 25, 2005 9:56 pm, edited 1 time in total.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:
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.
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

Andisheh
New poster
Posts: 5
Joined: Fri Aug 26, 2005 11:29 pm

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
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

``````1