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

JW
New poster
Posts: 6
Joined: Sat Feb 14, 2004 4:25 pm

Post by JW »

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

JW
New poster
Posts: 6
Joined: Sat Feb 14, 2004 4:25 pm

Post by 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
New poster
Posts: 10
Joined: Sun Jan 18, 2004 6:12 pm

Post by nightdog »

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

Post by 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
New poster
Posts: 28
Joined: Thu Feb 19, 2004 1:19 pm

Post by 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
New poster
Posts: 1
Joined: Thu Apr 01, 2004 2:25 pm
Contact:

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

Post by 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
New poster
Posts: 1
Joined: Sat Apr 03, 2004 11:43 am

Problem 100

Post by 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
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs »

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

Post by CDiMa »

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

Post by 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
New poster
Posts: 12
Joined: Sat Apr 03, 2004 11:01 pm

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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
New poster
Posts: 12
Joined: Sat Apr 03, 2004 11:01 pm

Indeedy

Post by HerrAachen »

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

Post by 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
New poster
Posts: 2
Joined: Mon Apr 26, 2004 11:52 am
Location: Paris

I undersood the problem

Post by 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.

Post Reply

Return to “Volume 1 (100-199)”