Page 66 of 93
Posted: Wed Nov 21, 2007 7:25 pm
by mf
You get WA because your code throws an exception (I guess there could be leading spaces or more than one space between numbers), which you catch and silently exit. You don't have to do that. If your main() throws exceptions, it's OK, you'll just get a "Runtime Error" verdict instead of WA.
Scanner class is pretty slow, and you shouldn't use it if the input could be potentially large. Use BufferedReader and StringTokenizer instead like in this code:
Code: Select all
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
while (true) {
String line = reader.readLine();
if (line == null) {
// end of file reached
break;
}
StringTokenizer tokenizer = new StringTokenizer(line);
int num1 = Integer.parseInt(tokenizer.nextToken());
int num2 = Integer.parseInt(tokenizer.nextToken());
...
}
}
}
And one more thing - apparently, % 2 and /= 2 operations are too slow in Java, I couldn't get rid of TLE with them. Use bitwise operators instead: x%2 == (x&1), x/2 == (x>>1).
Posted: Wed Nov 21, 2007 8:08 pm
by ithenewguyi
great, thank you for your tips, it REALLY helps
but when i output something like
System.out.println(line+" "+biggest);
i got a Presentation Error, not sure why that happens...
Posted: Wed Nov 21, 2007 8:11 pm
by mf
Judge probably expects you to omit any unnecessary spaces in the output even when they're present in the input.
i.e use System.out.println(num1+" "+num2+" "+biggest);
Posted: Wed Nov 21, 2007 8:16 pm
by ithenewguyi
ahh, thank you very much!
Posted: Sun Dec 09, 2007 6:56 am
by Codemonkey2000
I keep getting time limit exceeded. I don't know how to make this code any more efficient. Am I missing something? :S
Code: Select all
uses crt;
var i,j,max,x,tmp:longInt;
function foo(a:longInt):longInt;
var x,c:longInt;
begin
x:=a;
c:=1;
while (x<>1) do
begin
if ((x mod 2) =0) then
x:=x div 2
else
x:=x*3+1;
c:=c+1;
end;
foo:=c;
end;
begin
while not eof do
begin
readln(i,j);
max:=0;
write(i,' ',j);
if i>j then
begin
tmp:=i;
i:=j;
j:=tmp;
end;
for x:=i to j do
begin
tmp:=foo(x);
if tmp>max then
max:=tmp;
end;
writeLn(' ',max);
end;
end.
Posted: Mon Dec 10, 2007 10:12 pm
by scott1991
this code is giving wa as well. I'm sure it's fine...Cheers for any help. Scott
Posted: Tue Dec 11, 2007 12:41 am
by Codemonkey2000
I'm not getting WA, I'm getting Tile limit exceeded.
Posted: Tue Dec 11, 2007 2:40 am
by Leonid
Codemonkey2000 wrote:I'm not getting WA, I'm getting Tile limit exceeded.
Use more efficient implementation
Posted: Tue Dec 11, 2007 11:56 pm
by Codemonkey2000
Leonid wrote:Codemonkey2000 wrote:I'm not getting WA, I'm getting Tile limit exceeded.
Use more efficient implementation
I know, but how can I make my code any more efficient? I posted the code above.
Posted: Wed Dec 12, 2007 6:15 am
by CMG
scott1991:
Code: Select all
for(o;o<=j;o++)
{
i=o;
while(i!=1)
{
i = (i&1)==0?(i>>1):(i*3+1);
n++;
}
}
Your limit didn't include j previously, and the inside of the while statement can be simplfied as shown.
Codemonkey2000: you should do something similar.
Posted: Wed Dec 12, 2007 9:53 pm
by scott1991
Now i'm really confused
for 1 and 10, it gives max cycle length as 67!!! the code now is:
Code: Select all
// 3n+1 - 100.cpp : Defines the entry point for the console application.
#include <iostream>
int main()
{
int n=0,i,j,store=0,o,p,temp,f;
a:
scanf("%d%d",&o,&j);
if (o==-1||j==-1)
{return 0;}
else
{
if(o>j)
{temp=o;o=j;j=temp;f=1;}
p=o;
for(o;o<=j;o++)
{
i=o;
while(i!=1)
{
i = (i&1)==0?(i>>1):(i*3+1);
n++;
}
}
if(store<n)
{store=n;}
n=1;
if (f==1)
{temp=j;j=p;p=temp;f=0;}
printf("%d %d %d\n",p,j,store);
store=0;
goto a;
}
return 0;
}
please healp!!!!
Posted: Wed Dec 12, 2007 11:16 pm
by CMG
Code: Select all
for(o;o<=j;o++) {
n = 1;
i = o;
while(i!=1) {
i = (i&1)==0?(i>>1):(i*3+1);
n++;
}
if(store<n) {
store = n;
}
}
Your problem was when you changed from your previous code you took out the check if(store<n) from the for statement and forgot to reset n to 1 in the for statement as well, which was partly my fault since I closed the for loop statement in my previous post when I didn't mean to
.
Posted: Thu Dec 13, 2007 8:11 pm
by scott1991
that did help...but it is still a wrong answer...can anyone give a list of tests or something? cheers. scott
my code now stands thus:
Posted: Thu Dec 13, 2007 8:51 pm
by mf
Try the input
Your code outputs two different answers.
Posted: Thu Dec 13, 2007 9:09 pm
by scott1991
lol...well thats odd...Well, now that's cleared up...the program works!!! Cheers guys!!! Your a great help. CMG-Thanks for your help...you've taught me something new(the ? sign) and MF- thanks for your time to spot something i wouldn't have unless i had cone through tonnes of inputs. Cheers once again!