100 - The 3n + 1 problem

[gsingh93]

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]

what if i == j ?

[brianfry713]

What happens if i>j?

[pecijackson]

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

[white_snake]

The two numbers can appear like:
Input:

Code: Select all

10 1

Expected Output:

Code: Select all

10 1 20

[chogg]

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]

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]

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]

So, iam a new self learning programmer and though i know my submissioned codes are not the fastest.
Would you please look over
3n + 1 problem{C++} http://codepad.org/UiOoSncX

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!
thx in advance

[brianfry713]

What if i>j?

[brianfry713]

What if i>j?

[mic122]

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

[gsingh93]

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]

I forgot the return 0 :/

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

[rgracia]

I submit this code in C.

But my answer is WA.

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;
}