100 - The 3n + 1 problem

[Stefan Pochmann]

Plus, it would've been nice if you told us the result you got from the judge. Shall we guess that or what?

For the admins of this board: Could we perhaps have an introductory tutorial that everybody is forced to read before he/she is allowed to post on the board? Some ideas:

- If you have a question about a problem, look into old threads about that problem. Maybe your question is already answered there.

- Don't just ask what's wrong with your solution. Give us a hint on what the judge says.

- Format code using the formatting the board offers.

- Maybe the reason why your program is never accepted is that your mail program destroys your code. Look at the automatic reply from the judge that shows how the judge got your program. Does it differ from the one you sent? Are characters missing? Are lines cut off? (And please, could somebody finally tell me if this method works? I asked for this several times now but nobody I helped with was kind enough to answer it.)

- If you want to complain about something, don't just write that "feature X doesn't work". That doesn't help, because we don't know what you mean is wrong.

- Use existing threads for a problem if appropriate (see Adrian's post above). By appropriate I mean that I would perhaps start a new thread if my subject differs enough from the subject of the old thread.

[Davidacm]

But how do i check whether i have reached the end of the file and do i have to use cin.ignore at the end of each line as indicated in the smaple input file?

[Stefan Pochmann]

No, no, you're making this way too complicated. Just do this:

[cpp]
int i, j;
while( cin >> i >> j ){
/--- Work with i and j.
}
[/cpp]

That's it. Whitespace is ignored automatically and the ">>" returns some value that is evaluated as "false" if it can't read the two ints, so at the end of the file the while loop will stop.

[Zheng]

try this:

[cpp]
#include <fstream>
using namespace std;

void main()
{
int i, j;
int maxlength;
istream& fin = cin; //stdin

while (!fin.eof())
{
fin>>i>>j;
fin.ignore(1,'\n');

maxlength=0;
for(int y=i; y<=j; y++)
{
int count=1;
int z=y;
while(z!=1)
{
if (z%2==0)
z=z/2;
else
z=z*3+1;
count++;
}
if (count>maxlength)
maxlength=count;
}
ostream& fout = cout; //stdout
fout<<i<<" "<<j<<" "<<maxlength<<endl;
}
} [/cpp]

[Zheng]

this is my program:
[cpp]
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

#ifndef ONLINE_JUDGE
ifstream FIN("3N.in"); //debug
#else
istream& FIN = cin;
#endif

ostream& OUT = cout;

void main()
{
int count[10002];

for(int i=1;i<=10000;i++)
{
int t = i;
int j;
for(j=0;t>1;j++)
{
if(t%2)
t = 3*t + 1;
else
t/= 2;
if(t<i)//dynamic programming
{
j += count[t] + 1;
break;
}
}
count = j;
}

for(;;)
{
int i,j;
FIN>>i>>j;
if(!FIN)break;

OUT<<i<<' '<<j<<' ';
if(i>j)swap(i,j);//i is not always less than j
//there is a under line in the
//problem description: "i and j"
OUT<<*(max_element(count+i,count+j)) + 1<<endl;
FIN>>ws;
}
}
[/cpp]

[galgamet]

I submitted the following code but got a WA. What may be the problem?
[c]
#include <stdio.h>

int main(void)
{
int cur, c, i, j, cycle, tcyc;

while(scanf("%d %d", &i, &j) == 2) {
if (i > j) { c = i; i = j; j = c; }

tcyc = 0;
for(c=i; c<=j; ++c) {
cycle = 0;
cur = c;
while(1) {
++cycle;
if (cur == 1) break;
if (cur & 1) cur = 3*cur + 1;
else cur /= 2;
}
tcyc = (tcyc > cycle ? tcyc : cycle);
}

printf("%i %i %i\n", i, j, tcyc);
}

return 0;
}
[/c]

[10153EN]

Hello~
I can tell you your algorithm is of NO problem, but as you have handled the input with i > j with the swapping..... a (minor) problem appeared which leads you to get WA.

Hope can help~

[galgamet]

Ahh...
shame that I didn't notice it !

"10 1
1 10 20"

[Davidacm]

I write the program in C++. It worked well on my computer but got a W.A.
Can anyone tell me what the problem is?
[cpp]
#include<iostream>
using namespace std;

void main()
{
int i, j;
int maxlength;
while (cin>>i>>j)
{
maxlength=0;
for(int y=i; y<=j; y++)
{
int count=1;
int z=y;
while(z!=1)
{
if (z%2==0)
z=z/2;
else
z=z*3+1;
count++;
}
if (count>maxlength)
maxlength=count;
}
cout<<i<<" "<<j<<" "<<maxlength<<endl;
}
}
[/cpp]

[10153EN]

Have you read the thread about the problem 100 previously? I think it will answer your question.

And remember, don't make any assumption that the problem description does not mention. =P

[1_UtterBlue]

I'm new here. I saw other posts, and found no prolblems I got. My source codes appeared to be right on my own compiler. But I got WA from the Judge. I guess this should be something to do with the input and output in my source code. Could anyone be kind to help me?
[pascal]

Code: Select all

------------------------------------------------
(* @JUDGE_ID: 18364KN  100 Pascal *)
Program p100(input,output);

Var t,UpBound,LowBound:integer;

Function Cal_Circle(n:longint):integer;
 Var
  step:integer;
 Begin
  step:=1;
      While (n<>1) do
    begin
     If Odd(n) then n:=3*n+1
     Else n:=n div 2;
     Inc(step);
    end;
  Cal_Circle:=step;
 End;

Procedure Max_Circle(lowb,upb:integer);
 Var
  max,i,t:integer;
 Begin
  max:=0;
  For i:=lowb to upb do
   begin
    t:=Cal_Circle(i);
    If max<t then max:=t;
   end;
  Writeln(lowb,' ',upb,' ',max);
 End;

Begin
 Readln(LowBound,UpBound);
 While not eof(input) do
  begin
   If UpBound<LowBound then
       begin t:=LowBound;LowBound:=UpBound;UpBound:=t;end;
   Max_Circle(LowBound,UpBound);
   Readln(LowBound,UpBound);
  end;
End.

[/pascal]

[Stefan Pochmann]

You haven't read the other posts carefully enough, otherwise you'd know that i and j have to be printed in the order in which they appeared.

[1_UtterBlue]

Thanks to Stefan.
And I've read the answer published by this site, (on the bottom of the page---Intepreter Judge Answer. ) I found the variable which need to be calculated whether it's odd or not should be long int type. (Pascal).

[littledump]

i keep getting a wrong answer for 100 & from all the hints ive been given & all the attempts ive made i think it should work. Here have a look

[cpp]
#include <iostream.h>

unsigned long inp1, inp2, other=0, counter=0, isc=0, thei, thej;

void main(void){
while (cin >>thei >>thej){
if (thej > thei){
inp1 = thei;
inp2 = thej;
}
else{
inp2 = thei;
inp1 = thej;
}
isc = 0;
for (unsigned long i = inp1; i <= inp2; i++){
other = i;
counter = 0;
while(other != 1){
if(other % 2 == 0){
other = other / 2;
}
else{
other = (3 * other) + 1;
}
counter += 1;
}
if (counter > isc){
isc = counter +1;
}
}
cout <<thei <<" " <<thej <<" " <<isc <<endl;
}
}
[/cpp]

[Betovsky]

maybe im wrong i did a quick look
but shouldnt be if( counter +1 > isc) ?