100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

nightdog
New poster
Posts: 10
Joined: Sun Jan 18, 2004 6:12 pm

output problem

Post by 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
New poster
Posts: 10
Joined: Thu Jan 22, 2004 3:32 am

Post by 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]
"God does not care about our mathematical difficulties. He integrates empirically."
-Albert Einstein
scruff
New poster
Posts: 29
Joined: Wed Dec 24, 2003 5:22 am

Post by 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
New poster
Posts: 10
Joined: Thu Jan 22, 2004 3:32 am

Post by fangs404 »

scruff wrote: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?
"God does not care about our mathematical difficulties. He integrates empirically."
-Albert Einstein
nightdog
New poster
Posts: 10
Joined: Sun Jan 18, 2004 6:12 pm

Access denied

Post by 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
New poster
Posts: 1
Joined: Fri Jan 23, 2004 7:31 pm

Post by 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
New poster
Posts: 10
Joined: Thu Jan 22, 2004 3:32 am

Re: Access denied

Post by fangs404 »

nightdog wrote: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.
"God does not care about our mathematical difficulties. He integrates empirically."
-Albert Einstein
scruff
New poster
Posts: 29
Joined: Wed Dec 24, 2003 5:22 am

Post by 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
New poster
Posts: 10
Joined: Thu Jan 22, 2004 3:32 am

Post by fangs404 »

scruff wrote: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]
"God does not care about our mathematical difficulties. He integrates empirically."
-Albert Einstein
minus273
New poster
Posts: 6
Joined: Mon Jan 26, 2004 3:09 pm

Post by 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?
Il fait beau aujourd'hui.
minus273
New poster
Posts: 6
Joined: Mon Jan 26, 2004 3:09 pm

Post by minus273 »

Well I found my mistake:
[pascal]
for i:=b downto a
[/pascal]
just 's/downto/to/'
Il fait beau aujourd'hui.
fibonacci
New poster
Posts: 2
Joined: Thu Jun 12, 2003 2:30 pm

#100 Memorization

Post by 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
New poster
Posts: 10
Joined: Thu Jan 22, 2004 3:32 am

Post by 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!
"God does not care about our mathematical difficulties. He integrates empirically."
-Albert Einstein
nightdog
New poster
Posts: 10
Joined: Sun Jan 18, 2004 6:12 pm

congratz dude!

Post by nightdog »

good luck with the next problem :)
fangs404
New poster
Posts: 10
Joined: Thu Jan 22, 2004 3:32 am

Re: congratz dude!

Post by fangs404 »

nightdog wrote: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.
"God does not care about our mathematical difficulties. He integrates empirically."
-Albert Einstein
Post Reply

Return to “Volume 1 (100-199)”