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

yulka
New poster
Posts: 2
Joined: Mon Aug 02, 2004 6:15 pm
Contact:

problem with i & j limit

Post by yulka »

There is written that i & j are less then 10000 in the problem, but in your input one of them is about 995000, why? I think it's mistake...

JuaingFall
New poster
Posts: 13
Joined: Tue Aug 03, 2004 4:24 am
Location: CHINA

Thanks

Post by JuaingFall »

With your help I got AC,Thank you indeed!

ToasterStrudel
New poster
Posts: 1
Joined: Wed Sep 08, 2004 3:38 am

Problem 100 compiler error

Post by ToasterStrudel »

I am getting a compiler error but the code compiles fine on my machine.

the error codes I am getting are as follows:
02836780_24.java:1: Class or interface declaration expected.
This is a multi-part message in MIME format.
^
gcj: Internal compiler error: program jc1 got fatal signal 11


Any help would be appreciated
here is my code:


import java.io.*;
import java.util.*;
/**
/* @JUDGE_ID: 49883TY 100 */

public class Collatz
{

private int iMyStartingInt;
private int iMyEndingInt;


public Collatz()
{
}

/* Taken from the uva website
* http://online-judge.uva.es/board/cms_vi ... bd1dc61510*/
public 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));
}


int collatzIterative(int min,int max)
{
int currNumCycleLength = 0;
int hiLength = 0;
int currCycleLength = 0;

for(int i=min;i<=max;i++)
{
int j=i;
while(j != 1)
{
if(j%2 == 0)
{
j=(j/2);
currCycleLength++;
}
else
{
j=(3*j+1);
currCycleLength++;
}
}

if(currCycleLength > hiLength)
{
hiLength = currCycleLength;
}
currCycleLength = 0;
}
return hiLength+1;
}


/*This was taken from the uva website
* http://online-judge.uva.es/board/cms_vi ... bd1dc61510
* and I figured it would be ok to use since someone asked about it on the message board*/
public void main()
{
String input;
int min,max,a,b;
StringTokenizer idata;

while ((input = ReadLn (255)) != null)
{
idata = new StringTokenizer (input);
a = Integer.parseInt (idata.nextToken());
b = Integer.parseInt (idata.nextToken());
if (a < b) { min=a; max=b; } else { min=b; max=a; }
System.out.print(a + " " + b);
System.out.print(a + " " + b + collatzIterative(min,max));

}
}



}

woni
New poster
Posts: 1
Joined: Wed Sep 08, 2004 7:35 pm

100 problem I recieve fail message!!!

Post by woni »

[cpp]
fail message is 'Your program has not solved the problem. It ran during 1.570 seconds.'

my code is
/*
#include <iostream>
using namespace std;

int main()
{
int startPoint, endPoint;
int length, maxLength;
int i, j;

while(cin >> startPoint >> endPoint){
maxLength = 0;
for(i = startPoint; i <= endPoint; i++){
j = i;
length = 1;
while(j != 1){
if(j % 2 == 1){
j = j * 3 + 1;
length++;
}
else{
j >>= 1;
length++;
}
}
if(maxLength < length){
maxLength = length;
}
}
cout << startPoint << " " << endPoint << " " << maxLength << endl;
}
return 0;
}
*/

why did code fail???
please know~
^^[/cpp]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

Read specification of problem carefully. If you don't find why this program fails, try to search other topics about this problem. If in any topic you can't find solution - then start new topic :-)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland

Post by wolf »

Hi woni !

First You should change all 'int' in you code to 'unsigned long' (why? see problem specification).
And second thing, you have to exchange input integers if the first integer is greater than second one (see problem specification too :-D)

Thats all I think.

vladrac
New poster
Posts: 7
Joined: Mon Sep 20, 2004 4:09 am
Location: Brazil

I read every thing about the 100 problem, but still WA, help

Post by vladrac »

Please, somebody, whats wrong with this code?

#include "stdio.h"


int main(void)
{
unsigned long i,j,k,max=1,m2=1;

while(scanf("%lu %lu", &i,&j)!=EOF) {
if(i>j){
i ^= j;
j ^= i;
i ^= j;
printf("%lu %lu ",j,i);
}
else {
printf("%lu %lu ",i,j);
}
k=j;
while(k>=i)
{
if (k!=1){
j=k;
while (j!=1){
if (j % 2 !=0){
j=(3*j)+1;
}
else{
j/=2;
}
m2++;
}
}
else
{
m2=1;
}
if(m2>max) max=m2;
k--;
m2=1;
}
printf("%lu\n",max);
}
return 0;

Code: Select all

[c][/c]

vladrac
New poster
Posts: 7
Joined: Mon Sep 20, 2004 4:09 am
Location: Brazil

Output Limit Exceeded? what does it means?

Post by vladrac »

the code is this:
#include "iostream.h"
#include "stdio.h"
int main(void)
{
unsigned long i,j,k,max=1,m2=1;

while(scanf("%lu %lu",&i,&j)!=0) {
cout<<i<<" "<<j<<" ";
if(i>j){
i ^= j;
j ^= i;
i ^= j;
}
k=j;
while(k>=i)
{
if (k!=1){
j=k;
while (j!=1){
if (j % 2 !=0){
j=(3*j)+1;
}
else{
j/=2;
}
m2++;
}
}
else
{
m2=1;
}
if(m2>max) max=m2;
k--;
m2=1;
}
cout<<max<<"\n";

}

return 0;
}

plz help[cpp][/cpp]

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

Removed after Per's clarification...
Last edited by anupam on Wed Sep 22, 2004 12:15 am, edited 1 time in total.
"Everything should be made simple, but not always simpler"

vladrac
New poster
Posts: 7
Joined: Mon Sep 20, 2004 4:09 am
Location: Brazil

Post by vladrac »

plz, some1!

what does "OutPut Limit Exceeded" means?

Code: Select all

#include "stdio.h"
int main(void)
{
unsigned long i,j,k,max=1,m2=1;

while(scanf("%lu %lu",&i,&j)!=0) {
printf("%u %u ",i,j);
if(i>j){
i ^= j;
j ^= i;
i ^= j;
}
k=j;
while(k>=i)
{
if (k!=1){
j=k;
while (j!=1){
if (j % 2 !=0){
j=(3*j)+1;
}
else{
j/=2;
}
m2++;
}
}
else
{
m2=1;
}
if(m2>max) max=m2;
k--;
m2=1;
}
printf("%u\n",max);
max=1;
}

return 0;
}


anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

it means that your program didn't stop printing after a certain time. The cases where to break is not checked by your program. Or, memory may be overlapped so that the tracking variables have lost it's original value.
"Everything should be made simple, but not always simpler"

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

Your end condition is wrong:
while(scanf("%lu %lu",&i,&j)!=0) {

it should be: while(scanf("%lu %lu",&i,&j) == 2) {
since if end of file is reached, scanf returns EOF, which is different from 0, so it will run forever.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Read the documentation on scanf(), it will return EOF if the end of the input is reached, a value different from 0.
This is the reason why your while loop never stops and your program keeps producing output until the judge kills it.

Change your while loop to
[c]while(scanf("%lu %lu",&i,&j)==2) {[/c]
and you'll get Wrong Answer.

To get Accepted you'll also have to change the format in the printf() function to %lu in stead of %u.

[Edit:]
Adrian: our postings crossed!

Anupam: please try to make sense if you're helping someone.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

oops, sorry. Here is what I wanted to say:
1. If the break condition was not checked by a program it will get OLE. For example, in the problem statement it was told that input will end with two zeroes, but in your program you used
while(scanf("%d%d",&a,&b)!=EOF){
}
then the program may get OLE if the algorithm falls in an infinite loop outputing the same value (let 0) infinite times.
To check whether your program crashes with infinite loop the judge restricted the size of the output file for your program. For example, the output for your program may not exceed 40 KB. If your output exceeds 40 KB you will be shown Output limit exceeded.

2. For example, you have tracked the breaking case,
scanf("%d%d",&a,&b) && (a||b))
{
}
you have used array (let a[40]);
but the judges data accesses a[45] (array index out of bound), in this case, the data in a and b variable may be lost due to overlapping of memory.

Now, i think I made it clearer. If I couldn't then forgive me for the poor english. :wink:
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

Removed after Per's clarification...
Last edited by anupam on Wed Sep 22, 2004 12:10 am, edited 1 time in total.
"Everything should be made simple, but not always simpler"

Post Reply

Return to “Volume 1 (100-199)”