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

Neon
New poster
Posts: 3
Joined: Sun Nov 03, 2002 6:14 pm

dont understand why

Post by Neon » Sun Nov 03, 2002 6:22 pm

I am having problems with the same. I dont even know whats wrong with my code.

**********************************************************************************************************
[cpp]// @BEGIN_OF_SOURCE_CODE
/* @JUDGE_ID: xxxxxx 100 C++ */

#include <iostream>
#include <stdlib.h>
#include <stdio.h>

void main()
{
int num,first,last,count,max,temp;

while(cin>>first>>last){

temp=first;
if(first==0){
if(last==0){
printf("%d %d %d\n",first,last,0);
continue;
}
else
first++;
}

num=first;
max=0;
while (num<=last) {
count = 0;
while(true) {
count++;
if(num<=1) break;
if((num%2)==1)
num=(3*num)+1;
else
num/=2;
}
first++;
num=first;
if(max<count)
max=count;
}
printf("%d %d %d\n",temp,last,max);
}
}
// @END_OF_SOURCE_CODE[/cpp]
***********************************************************************************
I am new here, and I dont understand what the rules are very clearly.
A clue would be enough,

Thanks in advance,
Neon.

Neon
New poster
Posts: 3
Joined: Sun Nov 03, 2002 6:14 pm

Definition of 100

Post by Neon » Mon Nov 04, 2002 3:18 am

Can someone please explain how problem 100 should be constructed? Please tell me the type of inputs and type of outputs.

For instance, in my program given below, I keep accepting input until there's no input, with "while(cin>>first>>last)".

Should my program work for specific type of input? if so, what is it? Because I am getting the output all right, but I keep getting WA from the judge.

[cpp]
// @BEGIN_OF_SOURCE_CODE
/* @JUDGE_ID: xxxxx 100 C++ */

#include <iostream>
#include <stdlib.h>
#include <stdio.h>

void main()
{
int num,first,last,count,max,temp;

while(cin>>first>>last){

temp=first;
if(first==0){
if(last==0){
printf("%d %d %d\n",first,last,0);
continue;
}
else
first++;
}

num=first;
max=0;
while (num<=last) {
count = 0;
while(true) {
count++;
if(num<=1) break;
if((num%2)==1)
num=(3*num)+1;
else
num/=2;
}
first++;
num=first;
if(max<count)
max=count;
}
printf("%d %d %d\n",temp,last,max);
}
}
// @END_OF_SOURCE_CODE
[/cpp]

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

Post by Mahbub » Wed Nov 06, 2002 9:10 am

Input can be like
3 2
100 1

That is first > last...in that case u need to swap while finding the max value.
But be careful to print 'first' and 'last' (as per ur code) according to input serial (not swapped..:)).

Thats all
Light

zorbathut
New poster
Posts: 16
Joined: Tue Nov 05, 2002 6:31 am

Post by zorbathut » Wed Nov 06, 2002 9:17 am

I'd be a little worried about mixing cin and printf. Might work. I *know* that mixing scanf/cin or printf/cout is a bad idea, but if you used one for input and the other for output, it might or might not work.

In any case, your basic structure (the loop and EOF detection) is fine. Once you're calculating the right answers, it'll work. :)

darklegend
New poster
Posts: 1
Joined: Wed Nov 06, 2002 12:41 pm

100 ..time limit exceeded

Post by darklegend » Wed Nov 06, 2002 12:55 pm

Hmmm...strange..but it gives me a time limit exceeded....what my prob??

[cpp]

#include <fstream.h>

int algo(register float x){
int ctr=0;
while (x != 1){
if((int)x % 2 == 0) x=x/2;
else x=3*x+1;
ctr++;
}
return (ctr+1);
}

int main(){

register float tmp=0,num1,num2,count=0,bl=0;

ifstream in;
in.open("3n.in");

ofstream out;
out.open("3n.out");

while(in.eof() != 1){
//in.clear();


in >> num1 >> num2;
if(num1 > num2){
tmp=num2;
num2=num1;
num1=tmp;
bl=1;
}

if(in.eof() == 1) break;


for(register float y=num1;y<=num2;y++){

tmp=algo(y);

if(tmp > count) count =tmp;

}
if(bl == 1) out << num2 <<" "<< num1 <<" "<< count <<endl;

else out << num1 <<" "<< num2 <<" "<< count <<endl;
count=0;
tmp=0;
}

out.close();
in.close();

return (0);

}

[/cpp]

Thnx for ur helppp....

rhtiwari
New poster
Posts: 5
Joined: Thu Jul 11, 2002 10:59 am

Re: Test all possibilities

Post by rhtiwari » Fri Nov 08, 2002 6:59 pm

Iv@n wrote:You must to test all input possibilities like "num1 == num2", the input order must be the same of output "10 1" ...

Iv@n
Brasil
I did that (at least I think so :( ) and stiil, WA!
My code is attached.
Please help!


-------------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
int firstnum,lastnum ;
int seqlength, maxseqlength ;
int i ;
int currnum ;
int orderchanged ;

while(scanf("%d %d", &firstnum, &lastnum) != EOF)
{
orderchanged = 0 ;
if (firstnum > lastnum)
{
int tmpnum ;
tmpnum = firstnum ;
firstnum = lastnum ;
lastnum = firstnum ;

orderchanged = 1 ;
}
maxseqlength = 0 ;
for (i = firstnum ; i <= lastnum ; i++)
{
currnum = i ;
seqlength = 1 ;
while( 1 != currnum)
{
seqlength++ ;
if (currnum %2 != 0)
currnum = 3*currnum + 1 ;
else
currnum /= 2 ;
}
if (seqlength > maxseqlength)
maxseqlength = seqlength ;
}
if (orderchanged == 0)
printf("%d %d %d\n",firstnum, lastnum, maxseqlength) ;
else
printf("%d %d %d\n",lastnum, firstnum, maxseqlength) ;
}
return 0;
}

littledump
New poster
Posts: 25
Joined: Wed Jun 05, 2002 4:55 am
Location: London, ON, Canada
Contact:

Post by littledump » Sat Nov 09, 2002 7:25 am

the problem is youre reading from files

when submitting to this judge, input comes from stdio

so in c++ the way i do it is

[cpp]#include <iostream>

using namespace std;

while(cin >> someVariable){

yourProblemSolvingCodeHere

}[/cpp]

wrygiel
New poster
Posts: 4
Joined: Sun Nov 10, 2002 1:26 pm

[100] Wrong sulution was Accepted?

Post by wrygiel » Sun Nov 10, 2002 1:31 pm

Some of these numbers when computing them with cardinal/longword in pascal - are wrong. There are about 100 of them (which exceed the limit of 2^32 during computation). One of my colegues sent the wrong program (with the cardinals) and it was accepted. For example he got 159487 -> 246 (in my opinion it should be 184). I think the tests should be changed. Or am I wrong?

haaaz
New poster
Posts: 29
Joined: Sun Sep 08, 2002 8:02 am

Post by haaaz » Sun Nov 10, 2002 1:35 pm

Sorry...What is the input?
159487?

ianic
New poster
Posts: 1
Joined: Sun Nov 10, 2002 2:28 pm

Pb 100 : Time exceeded with C programs

Post by ianic » Sun Nov 10, 2002 2:37 pm

I've got problems dealing with time exceeded.
I sent a C++ progam which was accepted, then I turned this program into C language and I got a time exceeded answer.
Here is another C program I wrote which is not accepted because of time exceeded :
[c]
#include <stdio.h>

int cycle(int a) {
int cnt = 1;
while(a>1) {
cnt++;
if(a%2)
a = 3*a + 1;
else a/=2;
}
return cnt;
}

int maxcycle(int a, int b) {
int max = 0,i,c;
if(a>b) {
a-=b;
b+=a;
a=b-a;
}
for(i=a;i<=b;i++) {
c = cycle(i);
if(c>max) max=c;
}
return max;
}

int main(void) {
int n1,n2;
while(scanf("%d %d",&n1,&n2))
printf("%d %d %d\n",n1,n2,maxcycle(n1,n2));
return 0;
}
[/c]

Does anyone have an answer ?
Thanx

wrygiel
New poster
Posts: 4
Joined: Sun Nov 10, 2002 1:26 pm

Post by wrygiel » Sun Nov 10, 2002 5:53 pm

"159487 159487" if you'd like

23756AW
New poster
Posts: 5
Joined: Mon Sep 30, 2002 1:00 am

Post by 23756AW » Mon Nov 11, 2002 2:32 am

Per the above reply that is correct. Specify C++ in your header or get in the habit of using /* xxx */ comment style. I typically use the /* ...
style in both this and work so that when I work on both C and C++ programs I don't run into that problem (this has happened where I work sometimes where our newer code is in C++ and legacy code in C).

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

just a comment

Post by ec3_limz » Mon Nov 11, 2002 8:44 am

I would like to comment although BC++ is ANSI/ISO compatible (if I remember correctly), one can modify compiler options such that code written in C++ can be compiled even if the source code is intended to be written fully in C.

ashfaq_csdu
New poster
Posts: 4
Joined: Mon Mar 18, 2002 2:00 am

Re: Test all possibilities

Post by ashfaq_csdu » Mon Nov 11, 2002 8:19 pm

rhtiwari wrote: if (firstnum > lastnum)
{
int tmpnum ;
tmpnum = firstnum ;
firstnum = lastnum ;
lastnum = firstnum ; :o
}
does it really interchange the values of firstnum and lastnum? 8)
so recode it [lastnum = tmpnum].


ashfaq

23756AW
New poster
Posts: 5
Joined: Mon Sep 30, 2002 1:00 am

Post by 23756AW » Tue Nov 12, 2002 12:58 am

That C code cannot possibly represent the C++ solution that was accepted. There is not one shred of dynamic programming there which is a key component to solving this problem. That looks like the brute force method which doesn't work in C or C++. Can I see the C++ code you submitted?

Post Reply

Return to “Volume 1 (100-199)”