100 - The 3n + 1 problem

[Neon]

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]

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]

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]

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]

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]

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]

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]

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]

Sorry...What is the input?
159487?

[ianic]

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]

"159487 159487" if you'd like

[23756AW]

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]

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]

if (firstnum > lastnum)
{
int tmpnum ;
tmpnum = firstnum ;
firstnum = lastnum ;
lastnum = firstnum ;
}

does it really interchange the values of firstnum and lastnum?
so recode it [lastnum = tmpnum].


ashfaq

[23756AW]

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?