100 - The 3n + 1 problem

[JW]

Thank nightdog.
Do you mean my input and output are wrong?

[JW]

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;
}

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

int main()
{
unsigned int i, j;
LIST *head, *p, *q;
head = new LIST;
q = p = head;
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;
printlist(head);
return 0;
}[/cpp]

[nightdog]

you're probably right, because C++ has a cleaner way to process input/output...

[nightdog]

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]

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) {
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));
}
public static void main(String args[]) {
String s = ReadLn(1024);
System.out.println(s);
}
}
[/java]

[Rakot]

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]

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]

Justin, hi.

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]

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]

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]

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]

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]

You're right it does. I got my first accpted now, the time sucks though.

[Laurent]

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[0] = 'B'; r[1] = 'C'; r[2] = 'G';}
// BGC
if ((tmp = ob1 + og2 + oc3) < max)
{max = tmp; r[0] = 'B'; r[1] = 'G'; r[2] = 'C';}
// CBG
if ((tmp = oc1 + ob2 + og3) < max)
{max = tmp; r[0] = 'C'; r[1] = 'B'; r[2] = 'G';}
// CGB
if ((tmp = oc1 + og2 + ob3) < max)
{max = tmp; r[0] = 'C'; r[1] = 'G'; r[2] = 'B';}
// GBC
if ((tmp = og1 + ob2 + oc3) < max)
{max = tmp; r[0] = 'G'; r[1] = 'B'; r[2] = 'C';}
// GCB
if ((tmp = og1 + oc2 + ob3) < max)
{max = tmp; r[0] = 'G'; r[1] = 'C'; r[2] = 'B';}
cout << r << max << '\n';
}
exit(0);
}
[/cpp]

Thanks,
Laurent

[Laurent]

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