## 100 - The 3n + 1 problem

Moderator: Board moderators

gsingh93
New poster
Posts: 5
Joined: Sat Jan 07, 2012 8:29 am

### WA on Problem 100

I'm getting a wrong answer on Problem 100. Before you ask, yes, I did consider that j < i. I've tested it and it works fine. It works with all of the given samples. Here is my code.

Code: Select all

``````#include <iostream>

using namespace std;

int main ()
{
int i, j, maxLength = 0, temp, count, swap;

while(cin >> i >> j)
{
int min = i;
int max = j;

if(j < i)
{
min = j;
max = i;
}

for (int k = min+1; k < max; k++)
{
temp = k;
count = 1;
while(temp != 1)
{
if(temp%2==0)
temp /= 2;
else
temp = temp*3+1;
count++;
}

if (count > maxLength)
{
maxLength = count;
}
}

cout << i << " " << j << " " << maxLength << endl;
}

return 0;
}
``````

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: WA on Problem 100

what if i == j ?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 3n + 1

What happens if i>j?
Check input and AC output for thousands of problems on uDebug!

pecijackson
New poster
Posts: 3
Joined: Tue Jan 31, 2012 7:05 am

### Re: 3+1 problem - runtime error

i tried to figure out the problem up there but still unable to solve the problem. anybody can help to solve it?

white_snake
New poster
Posts: 3
Joined: Sun Feb 12, 2012 12:57 pm

### Re: 3n + 1

The two numbers can appear like:
Input:

Code: Select all

``10 1``
Expected Output:

Code: Select all

``10 1 20``

chogg
New poster
Posts: 2
Joined: Mon Apr 02, 2012 2:48 am

### Re: WA on Problem 100

To the OP: your program hangs on input line
1 1000000
Mine returns in a fraction of a second. Although, I'm still getting WA and I have no idea why.

chogg
New poster
Posts: 2
Joined: Mon Apr 02, 2012 2:48 am

### Re: WA on Problem 100

chogg wrote:Although, I'm still getting WA and I have no idea why.
Oh good lord, it was fumbling on the i > j case. I had explicitly taken that case into account, but I was looping over the original variables rather than the properly-ordered ones. Fixed that; problem accepted!

mic122
New poster
Posts: 6
Joined: Mon Apr 09, 2012 1:01 pm

### 100 - Runtime error

Hi !

I also don't know why i get runtime error in this task. I checked this with the biggest possible tests. Could you look at, please ?

Code: Select all

``````#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#define rep(x,n) for (int x = 0; x < n; x++)
#define pb push_back
#define straznik 100000000
using namespace std;
struct typ
{
int war, ind, kt;
};
struct cmp
{
bool operator() (typ a, typ b)
{
return (a.war < b.war);
}
};
vector <bool> enabled;
vector < vector <int> > seq;
vector <int> maxy;
set <typ, cmp> drzewo;
int l,p;
int rob (int pe)
{
int n = pe;
typ typek; typek.war = n;
typek.ind = 0;
typek.kt = pe-l;
drzewo.insert(typek);
seq[pe-l].pb(n);
enabled[pe-l] = false;
//cout << n << "\n";
while(n!=1)
{
if (n % 2 == 1) n = 3*n + 1;
else n /= 2;
//cout << " n " << n << "\n";
typ typek; typek.war = n;
set<typ,cmp>::iterator it = drzewo.find(typek);
typ found; found = *(it);
if ( (found.war != n || drzewo.end() == it) && n != 1 )
{
//cout << "mam koniec\n";
typek.ind = seq[pe-l].size();
typek.kt = pe-l;
drzewo.insert(typek);
seq[pe-l].pb(n);
if (n >= l && n <= p) enabled[n-l] = false;
} else
{
if (n!=1) {
//cout << "znalazlem " << found.war << " " << found.ind << " " << found.kt << "\n";
//cout << "pe " << pe << " "<< seq[pe-l].size() + maxy[found.kt]-found.ind << "\n";
return (seq[pe-l].size() + maxy[found.kt] - found.ind); }
else {
typek.ind = seq[pe-l].size();
typek.kt = pe-l;
typek.war = 1;
drzewo.insert(typek);
seq[pe-l].pb(1);
return seq[pe-l].size();}
}
}
return seq[pe-l].size();
}
int main()
{
int mx = 0;
while (cin >> l >> p)
{
enabled.clear(); enabled.resize(p-l+1,true);
seq.clear(); seq.resize(p-l+1); drzewo.clear();
maxy.clear(); maxy.resize(p-l+1); mx = 0;
typ t; t.war = straznik;
drzewo.insert(t);
for (int x = l; x <= p; x++)
{
//cout << "x " << x << "\n";
if (enabled[x-l]) {int r = rob(x); maxy[x-l] = r;  mx = max(r, mx);  }
}
cout << l << " "<< p  << " "<< mx << "\n";
}
return 0;
}
``````

phillinux
New poster
Posts: 1
Joined: Mon Apr 09, 2012 6:55 pm

### General Submission Q + Wrong Answer->100 The 3n + 1 problem

So, iam a new self learning programmer and though i know my submissioned codes are not the fastest.

and give me a hint on what topic i should definitely check out.

They say my submissioned Code is Wrong (Wrong Answer) though the time cap is 3 seconds and according to the submission page mine takes 0.264s and as far as i tested my code does exactly what is asked for.

Iam Using CodeBlocks IDE(nightly build debugger branch) on Windows7x64

I realy like to play around with problems but it gets me a bit discouraged when i cant find appropiate information, learning material and when i submit sth it always says wrong answer, despite that i only now the internet to ask :/ help me out!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 100 - Runtime error

What if i>j?
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: General Submission Q + Wrong Answer->100 The 3n + 1 prob

What if i>j?
Check input and AC output for thousands of problems on uDebug!

mic122
New poster
Posts: 6
Joined: Mon Apr 09, 2012 1:01 pm

### Re: 100 - Runtime error

Maybe it's the reason (application has died). I thought the given interval will suit to i <= j

gsingh93
New poster
Posts: 5
Joined: Sat Jan 07, 2012 8:29 am

### WA for problem 100

I've searched the forums, but can't find anything wrong with this code:

Code: Select all

``````#include <iostream>

using namespace std;

int countCycles(int, int);

int main() {
int i, j, cycles;

while (cin >> i >> j) {
if (i > j)
cycles = countCycles(i, j);
else
cycles = countCycles(j, i);

cout << i << " " << j << " " << cycles << "\n";
}
}

int countCycles(int i, int j) {
int count = 0;
int max = 0;
int n;

for (int k = j; k <= i; k++) {
n = k;
count++;

while (n != 1) {
if (n % 2) {
n = 3*n + 1;
} else {
n /= 2;
}

count++;
}
if (count > max)
max = count;
count = 0;
}

return max;
}
``````
It works when i > j, i < j, and when i == j, but I still get a WA

gsingh93
New poster
Posts: 5
Joined: Sat Jan 07, 2012 8:29 am

### Re: WA for problem 100

I forgot the return 0 :/

Compiler didn't even give me a warning...

rgracia
New poster
Posts: 1
Joined: Sun May 27, 2012 12:57 am

### Re: If you get WA in problem 100, read me before post!

I submit this code in C.

I don't know why...

Please tell me why. I'm nervous because I can't wait.

The outputs in my PC are correct.
----
Hablo español mejor que inglés xD.

Code: Select all

``````#include <stdio.h>

long maxCicles(long num);

int main() {

long num1;
long num2;
long lowNum, bigNum;
long maxNum = 0;
int i;
long currNum = 0;

while (scanf("%ld", &num1) != EOF)
{
scanf("%ld", &num2);

if (num1 > num2)
{
bigNum = num1;
lowNum = num2;
}
else
{
bigNum = num2;
lowNum = num1;
}

for (i = lowNum; i<=bigNum; i++)
{
currNum = maxCicles(i);
if (currNum > maxNum)
{
maxNum = currNum;
}
}

printf("%ld ",num1);
printf("%ld ",num2);
printf("%ld", maxNum);
printf("\n");

}

return 0;
}

long maxCicles(long num)
{
long count = 1;
long n = num;

while (n != 1)
{
if (n % 2 != 0)
{
n = (3*n)+1;
}
else
{
n = n / 2;
}
count++;
}

return count;
}``````