100 - The 3n + 1 problem

[nightdog]

From what i understood from your code, you seem to be outputting the result after each input, i.e:

1 10
1 10 20
100 200
100 200 125

you should be doing this:

1 10
100 200
[EOF (^D)]
1 10 20
100 200 125

if you keep getting wrong answer, try submit-o-matic to submit your code instead of using e-mail.

[fangs404]

Well, I tried your suggestion, but it's still not accepting it. I tried sending it with the online form, but I get an e-mail saying this:

"Access Denied.

You aren't authorized to use the Online Judge from that host.

--
The Online Judge"

I don't know what that means, but whatever. Here's my revised code. Any other suggestions?

[java]
import java.io.*;

class Main
{
public static void main(String[] args)
{
Main puzzle = new Main();
int highest = 0, a = 0, b = 0, temp = 0, index = 0;
String nums, num1, num2;
boolean switched = false;
int[][] list = new int[10][3];

while((nums = puzzle.ReadLn(1024)) != null && nums.length() > 1)
{
num1 = nums.substring(0, nums.indexOf(32));
num2 = nums.substring(nums.indexOf(32) + 1, nums.length() - 1);
a = Integer.parseInt(num1);
b = Integer.parseInt(num2);

if(a > b)
{
temp = a;
a = b;
b = temp;
switched = true;
}

for(int q = a; q <= b; q++)
if(puzzle.returnCount(q) > highest)
highest = puzzle.returnCount(q);

if(index == list.length)
{
int[][] tempList = list;
list = new int[list.length * 2][3];

for(int x = 0; x < tempList.length; x++)
list[x] = tempList[x];
}

if(!switched)
{
list[index][0] = a;
list[index][1] = b;
list[index++][2] = highest;
}
else
{
list[index][0] = b;
list[index][1] = a;
list[index++][2] = highest;
}

highest = 0;
switched = false;
}

for(int x = 0; x < list.length; x++)
if(list[x][1] == 0)
{
index = x;
x = list.length;
}

for(int x = 0; x < index; x++)
System.out.println(list[x][0] + " " + list[x][1] + " " + list[x][2]);
}

public int returnCount(int num)
{
int temp = num, count = 1;

while(temp != 1)
{
if(temp % 2 == 0)
temp /= 2;
else
temp = temp * 3 + 1;

count++;
}

return count;
}

public String ReadLn(int maxLg)
{
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);

return (new String (lin, 0, lg));
}
}
[/java]

[scruff]

You don't have to read all the input and then output all the answers at once. You can solve each input one at a time, like you did in your first example.

PS... Please shorten your signature it makes the page width and all the text messed up.

[fangs404]

You don't have to read all the input and then output all the answers at once. You can solve each input one at a time, like you did in your first example.

PS... Please shorten your signature it makes the page width and all the text messed up.

that's the problem, though. it won't accept my first example. why won't it accept it? it's correct. any idea?

[nightdog]

If you got an answer from the online judge saying you're not permitted to use that host to submit, it means you have the option to only accept submissions by e-mail.
you can either submit your code using the e-mail you specified when you subscribed or change that parameter, which can be done by going to http://acm.uva.es/cgi-bin/OnlineJudge?U ... itUserMenu

[NSI]

Please, help me!
I got WA. What can I do???
This is my code:

const
maxn=1000000;

type int=integer;
real=extended;

var
n,i,a,b,max,kolvo:int;
cyc:array[1..maxn] of int;
_a,_b,_res:array[1..100000] of int;

function Rec(v:int64):int;
var
res:int;
begin
if (v<=maxn)and(cyc[v]>0) then
begin
Rec:=cyc[v]; exit;
end;
if v and 1=1 then res:=Rec(3*v+1)+1 else res:=Rec(v shr 1)+1;
Rec:=res;
if v<=maxn then cyc[v]:=res;
end;

begin
fillchar(cyc,sizeof(cyc),0);
cyc[1]:=1;
for i:=2 to maxn do if cyc=0 then
if i and 1=1 then cyc:=Rec(i) else cyc:=cyc+1;
kolvo:=0;
while not Eof do
begin
read(a,b);
if a=0 then break;
inc(kolvo);
_a[kolvo]:=a;
_b[kolvo]:=b;
if a>b then
begin
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;
max:=0;
for i:=a to b do if cyc>max then max:=cyc;
_res[kolvo]:=max;
end;
for i:=1 to kolvo do writeln(_a,' ',_b,' ',_res);
end.

Thank you.

[fangs404]

If you got an answer from the online judge saying you're not permitted to use that host to submit, it means you have the option to only accept submissions by e-mail.
you can either submit your code using the e-mail you specified when you subscribed or change that parameter, which can be done by going to http://acm.uva.es/cgi-bin/OnlineJudge?U ... itUserMenu

well, I changed my settings, sent it in, and i'm still getting a WA. now, i've tried e-mail and the online judge. here's my most recent code:

[java]
import java.io.*;

public class Main
{
public static void main(String[] args)
{
Main puzzle = new Main();
int highest = 0, a = 0, b = 0, temp = 0;
String nums, num1, num2;
boolean switched = false;

while((nums = puzzle.ReadLn(1024)) != null && nums.length() > 1)
{
num1 = nums.substring(0, nums.indexOf(32));
num2 = nums.substring(nums.indexOf(32) + 1, nums.length() - 1);
a = Integer.parseInt(num1);
b = Integer.parseInt(num2);

if(a > b)
{
temp = a;
a = b;
b = temp;
switched = true;
}

for(int q = a; q <= b; q++)
if(puzzle.returnCount(q) > highest)
highest = puzzle.returnCount(q);

if(!switched)
System.out.println(a + " " + b + " " + highest);
else
System.out.println(b + " " + a + " " + highest);

highest = 0;
switched = false;
}
}

public int returnCount(int num)
{
int temp = num, count = 1;

while(temp != 1)
{
if(temp % 2 == 0)
temp /= 2;
else
temp = temp * 3 + 1;

count++;
}

return count;
}

public String ReadLn(int maxLg)
{
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);

return (new String (lin, 0, lg));
}
}
[/java]

does anyone have any idea what i'm doing wrong? thanks.

[scruff]

NSI: It looks like you are using int64 for Rec() to calculate the cycle counts and what not, but you only read in a and b as int I believe that int will hold values -32767 to 32765 or something like that. I can't remember exactly if pascal has unsigned int then this will only hold up to 65535 this is still not high enough to hold all of the inputs. So change your program to hold int64 for your a and b variables and any other that hold values above the 65535 limit.

fangs404: I don't know java but you need to make sure that your int's do not need to be long int's or something else maybe.

[fangs404]

fangs404: I don't know java but you need to make sure that your int's do not need to be long int's or something else maybe.

nah, that's not the problem. the max value of an int in java is 2147483648, and the numbers we'll be given will be between 0 and 1000000. anything else? here's my most recent code that works but isn't accepted:

[java]
import java.io.*;

public class Main
{
public static void main(String[] args)
{
Main puzzle = new Main();
int highest = 0, a = 0, b = 0, temp = 0;
String nums, num1, num2;
boolean switched = false;

while((nums = puzzle.ReadLn(256)) != null && nums.length() > 1)
{
num1 = nums.substring(0, nums.indexOf(32));
num2 = nums.substring(nums.indexOf(32) + 1, nums.length() - 1);
a = Integer.parseInt(num1);
b = Integer.parseInt(num2);

if(a > b)
{
temp = a;
a = b;
b = temp;
switched = true;
}

for(int q = a; q <= b; q++)
if(puzzle.returnCount(q) > highest)
highest = puzzle.returnCount(q);

if(!switched)
System.out.println(a + " " + b + " " + highest);
else
System.out.println(b + " " + a + " " + highest);

highest = 0;
switched = false;
}
}

public int returnCount(int num)
{
int temp = num, count = 1;

while(temp != 1)
{
if(temp % 2 == 0)
temp /= 2;
else
temp = temp * 3 + 1;

count++;
}

return count;
}

public String ReadLn(int maxLg)
{
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);

return (new String (lin, 0, lg));
}
}
[/java]

[minus273]

[pascal]
program uva100;
{3n+1 problem}
function find(num:longword):longword;
var
fd:integer;
begin
fd:=1;
while (num<>1) do begin
inc(fd);
if num mod 2=1 then
num:=num*3+1
else
num:=num div 2;
end;
find:=fd;
end;
var
a,b,i,c,mc:longword;
begin
repeat
readln(a,b);
mc:=0;
if a<=b then
for i:=a to b do begin
c:=find(i);
if c>mc then mc:=c;
end
else
for i:=b downto a do begin
c:=find(i);
if c>mc then mc:=c;
end;
writeln(a,' ',b,' ',mc);
until eof;
end.
[/pascal]
Submitted by mail:

Code: Select all

#!/bin/sh
UVA_USERNAME=*******
if [ -e $1 ]
then
        echo 'UVA Problems Submitter(in Pascal)'
        touch /tmp/UVA_MAIL_$$
        echo 'Which problem? (number)'
        read UVA_NUMBER
        echo "{ @JUDGE_ID: ${UVA_USERNAME} ${UVA_NUMBER} Pascal}">/tmp/UVA_MAIL_$$
        cat $1>>/tmp/UVA_MAIL_$$
        cat /tmp/UVA_MAIL_$$
        mail -r foo@bar.net judge@uva.es < /tmp/UVA_MAIL_$$
        rm /tmp/UVA_MAIL_$$
fi

Who can tell me where's my mistake?

[minus273]

Well I found my mistake:
[pascal]
for i:=b downto a
[/pascal]
just 's/downto/to/'

[fibonacci]

I've tried to impliment memorization to speed up the #100, however.. it seems i'm getting times in excessive of 6+ seconds (compared with ~3 seconds without).

[java]
import java.io.*;
import java.util.*;
class Main
{

public static void main (String args[])
{
Main Puzzle = new Main();
Puzzle.Start();
}

void Start()
{
// memory
int[] mem = new int[1000001];

String stringInput;
int min, max, maxCycle = 0, counter = 1;
while ((stringInput = Main.ReadLn (255)) != null)
{
StringTokenizer input = new StringTokenizer(stringInput);
int a = Integer.parseInt(input.nextToken());
int b = Integer.parseInt(input.nextToken());
if (a < b)
{
min=a;
max=b;
}
else
{
min=b;
max=a;
}

for (int start = min; start <= max; start++)
{
boolean update = true;
int curNumber = start;
while (curNumber != 1)
{
// first check memory
if (curNumber > 100 && curNumber <= 1000000 && mem[curNumber] != 0)
{
counter+=mem[curNumber];
curNumber = 1; // done with while loop
update = false;
}

if (curNumber != 1)
{
if (curNumber % 2 == 0)
curNumber/=2;
else
curNumber = (3*curNumber)+1;
counter++;
}
}

if (update)
mem[start] = counter-1;


if (counter > maxCycle)
maxCycle = counter;

counter = 1;
}
System.out.println(a + " " + b + " " +maxCycle);
maxCycle = 0;
}
}

// input function
static String ReadLn (int maxLg)
{
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);
return (new String (lin, 0, lg));
}
}
[/java]

[fangs404]

i finally figured out my mistake. as it turns out, i can't use the substring call to parse through the string. the substring call will pick up '\n' and '\r', and to make things a whole lot easier, i just used stringtokenizer. answer accepted!

[nightdog]

good luck with the next problem

[fangs404]

good luck with the next problem

thanks. hopefully, i won't have any problems any more (other than algorithmical), now that i know the way that the judge wants us to parse and read in strings. thanks for all your help.