## 100 - The 3n + 1 problem

Moderator: Board moderators

JW
New poster
Posts: 6
Joined: Sat Feb 14, 2004 4:25 pm
Thank nightdog.
Do you mean my input and output are wrong?
JW
New poster
Posts: 6
Joined: Sat Feb 14, 2004 4:25 pm
I think C++ is more powerful than C in this problem.
[cpp]#include <iostream>

using namespace std;

typedef struct cycle
{
int i, j, maxcycle;
struct cycle *next;
}LIST;

unsigned int findmaxcycle(unsigned int min, unsigned int max)
{
register unsigned int n, counter, k, maxcycle;
maxcycle = 0;
counter = 1;
k = 1;
if (min > max)
{unsigned int temp;
temp = min;
min = max;
max = temp;
}

for (k = min; k <= max; k++)
{
n = k;
while (n != 1)
{
if (n % 2 != 0)
n = 3*n + 1;
else
n = n / 2;
counter++;
}
if (counter > maxcycle)
maxcycle = counter;
counter = 1;
}
return maxcycle;
}

{
LIST* p;
while (p !=NULL)
{cout << p->i<<' '<<p->j<<' '<< p->maxcycle<<endl;
p=p->next;
}
}

int main()
{
unsigned int i, j;
while(cin >> i >> j) {
p = new LIST;
p->i = i;
p->j = j;
p->maxcycle = findmaxcycle(i,j);
q->next = p;
q = p;
}
q->next = NULL;
return 0;
}[/cpp]
nightdog
New poster
Posts: 10
Joined: Sun Jan 18, 2004 6:12 pm
you're probably right, because C++ has a cleaner way to process input/output...
nightdog
New poster
Posts: 10
Joined: Sun Jan 18, 2004 6:12 pm
JW: i mean the way you do your output is wrong...

WRONG:

1 10
1 10 X
2 20
2 20 Y

Right
1 10
2 20
[eof]
1 10 X
2 20 Y
Examiner
New poster
Posts: 28
Joined: Thu Feb 19, 2004 1:19 pm
The code works fine on my machine. Below is a short program that uses the code and prints the first line it reads. Remember to include the import statement at the top.

Code: Select all

``````Input:
Hello world!
Output:
Hello world!
``````
[java]import java.io.*;
class Main {
static String ReadLn (int maxLg) {
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try {
while (lg < maxLg) {
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));
}
public static void main(String args[]) {
System.out.println(s);
}
}
[/java]
Rakot
New poster
Posts: 1
Joined: Thu Apr 01, 2004 2:25 pm
Contact:

### What is different between your C++ and standart????(:

I wrote program(It works right on my computer and are indentical to standart) and get your error - Wrong answer WHY? (It is for all my program, but this is 100 program - i think it is enough easy to do it right:

#include <stdio.h>
int main(){
#ifndef ONLINE_JUDGE
*stdin=*fopen("100.in","rt");
freopen("1000.out","w",stdout);
#endif
int mn=0,mx=0,i=0,j=0,max=0,num=0,n=0;

for( ; ; ){
if(2!=scanf("%d %d",&mn,&mx))return 0;
for(j=mn;j<=mx;j++){
for(i=1,num=j;num!=1;i++)if(num%2)num=3*num+1; else num/=2;
if(i>max)max=i;
}
printf("%d %d %d\n",mn,mx,max);
}
}  justin
New poster
Posts: 1
Joined: Sat Apr 03, 2004 11:43 am

### Problem 100

Ok.. im not really used to this automated checking system but im having some problems.. i've made the program and it runs perfectly on my system and produces the correct answers to the test problems, however the system says it gets a 'wrong error' which is impossible considering i'm using the same program me and my team wrote at a local programming contest for this EXACT same problem, and we got it right. This is the main method of my program:

void main( void )
{
int dwBufferMin=0;
int dwBufferMax=0;
int i = 0;

for( i = 0; i < 4; i++ )
{
scanf( "%d %d", &dwBufferMin, &dwBufferMax );
printf( "%d %d %d\n", dwBufferMin, dwBufferMax, findMax( dwBufferMin, dwBufferMax ) );
}
}

where findMax is the function that does the algorithm to find the correct value to return. If the program is wanting more than 4 inputs or there is some strict strict procedure that you aren't telling people who're new to this system, i'd like to know. This program is perfect and i've submitted it 5 times and it says it's not right. It runs in under .03 seconds with a test file of 1000 questions that i made myself and produces all correct answers. Someone please help Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:
Justin, hi.
Justin wrote:If the program is wanting more than 4 inputs or there is some strict strict procedure that you aren't telling people who're new to this system, i'd like to know.
You should read until end-of-file. That's all. Good luck! CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: Problem 100

justin wrote: If the program is wanting more than 4 inputs or there is some strict strict procedure that you aren't telling people who're new to this system, i'd like to know.
The problem statement doesn't say anywhere that there'll be only 4 inputs. So continue reading couples of values until EOF.

While we're at it make sure that your findMax function will handle correctly the case when dwBufferMin>dwBufferMax...

Ciao!!!

Claudio
HerrAachen
New poster
Posts: 12
Joined: Sat Apr 03, 2004 11:01 pm

### just a short question

how long am i supposed to wait for an reply by this judge? I tried to solve problem 100 and usually got the compile error immediately. Then I changed some things and received nothin for 10 hours or something.

Herr Aachen
HerrAachen
New poster
Posts: 12
Joined: Sat Apr 03, 2004 11:01 pm
forget about my last post. I have another problem. My email providers modify the first lines of my mails, so I used the line "@begin_of_source_code" at the beginning of my code. But when I do that there is no code in the "Programm Received: 100"-mail that is returned to me. The Judge is not compiling anything it seems.

"@end_of_source_code" seems to work. Why is "@begin_of_source_code" not working???????

Herr Aachen
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Why don't you try to submit your program via the webpage http://acm.uva.es/problemset/submit.php.
It works perfectly for me.
HerrAachen
New poster
Posts: 12
Joined: Sat Apr 03, 2004 11:01 pm

### Indeedy

You're right it does. I got my first accpted now, the time sucks though.
Laurent
New poster
Posts: 2
Joined: Mon Apr 26, 2004 11:52 am
Location: Paris

### problem 100 and 102

Hello,
I have problem with 100 and 102. I have W.A. replies.
I think it may be the same type of mistake so I send my two programs :

100 :
[cpp]
#include <iostream>
using namespace std;

int calcprof2(int k)
{
int i = 0;
while (k != 1)
{
++i;
k = (k&1)?(3*k+1):(k/2);
}
return i;
}

int main()
{
int i, j, k, m;
while (!cin.eof())
{
cin >> i >> j;
cout << i << " " << j << " ";
if (i > j) {k = i; i = j; j = k;}
m = 0;
for (k = i; k <= j; ++k) m = max(m, calcprof2(k));
cout << 1+m << "\n";
}
exit(0);
}
[/cpp]

102 :
[cpp]
#include <iostream>
using namespace std;

int main()
{
unsigned int b1, g1, c1;
unsigned int b2, g2, c2;
unsigned int b3, g3, c3;
unsigned int ob1, og1, oc1;
unsigned int ob2, og2, oc2;
unsigned int ob3, og3, oc3;
unsigned int max;
unsigned int tmp;
char r[] = " ";
while (!cin.eof())
{
max = 1 << 31;
cin >> b1 >> g1 >> c1 >> b2 >> g2 >> c2 >> b3 >> g3 >> c3;
ob1 = g1 + c1;
ob2 = g2 + c2;
ob3 = g3 + c3;
og1 = b1 + c1;
og2 = b2 + c2;
og3 = b3 + c3;
oc1 = g1 + b1;
oc2 = g2 + b2;
oc3 = g3 + b3;
// BCG
if ((tmp = ob1 + oc2 + og3) < max)
{max = tmp; r = 'B'; r = 'C'; r = 'G';}
// BGC
if ((tmp = ob1 + og2 + oc3) < max)
{max = tmp; r = 'B'; r = 'G'; r = 'C';}
// CBG
if ((tmp = oc1 + ob2 + og3) < max)
{max = tmp; r = 'C'; r = 'B'; r = 'G';}
// CGB
if ((tmp = oc1 + og2 + ob3) < max)
{max = tmp; r = 'C'; r = 'G'; r = 'B';}
// GBC
if ((tmp = og1 + ob2 + oc3) < max)
{max = tmp; r = 'G'; r = 'B'; r = 'C';}
// GCB
if ((tmp = og1 + oc2 + ob3) < max)
{max = tmp; r = 'G'; r = 'C'; r = 'B';}
cout << r << max << '\n';
}
exit(0);
}
[/cpp]

Thanks,
Laurent
Laurent
New poster
Posts: 2
Joined: Mon Apr 26, 2004 11:52 am
Location: Paris

### I undersood the problem

I thought that
[cpp]
while (!cin.eof())
[/cpp]
worked. But it only worked in problem 103.
I solved 3 new problems by understanding that.