UVa : 100 (The 3n + 1 problem)
December 9, 2008 6 Comments
Title : The 3n + 1 problem
Link : http://uva.onlinejudge.org/external/1/100.html
Tricky Lines :
- For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.
- You can assume that no operation overflows a 32-bit integer.
- The integers i and j must appear in the output in the same order in which they appeared in the input
Analysis :
- Integer data type is enough for this problem
- first number i can be greater than j
in that case swap these two values [35] - cycle length must be counted including value 1 [42]
- output the values of i and j as was in input.
In case if you swapped them it could create problem
Critical Input:
10 1
210 201
999999 1
Critical Output:
10 1 20
210 201 89
999999 1 525
Runtime : 0.980s
Faster solution :
use bitwise operation [46]
whenever u do the the operation 3n + 1, u have to do the operation n / 2 in the next step to get the result. Do these two operation in if statement [45] and make cycle_length += 2
Solution :
// @BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define long long LL
using namespace std;
int main ()
{
int i, j;
while ( scanf ("%d %d", &i, &j) != EOF ) {
int temp_i = i;
int temp_j = j;
if ( i > j ) swap (i, j);
int max_cycle_length = 0;
int cycle_length;
while ( i <= j ) {
int n = i;
cycle_length = 1;
while ( n != 1 ) {
if ( n % 2 == 1 ) n = 3 * n + 1;
else n /= 2;
cycle_length++;
}
if ( cycle_length > max_cycle_length )
max_cycle_length = cycle_length;
i++;
}
printf ("%d %d %d\n", temp_i, temp_j, max_cycle_length);
}
return 0;
}
// @END_OF_SOURCE_CODE
/* @JUDGE_ID:kimda 100 C "sample loop" */ /* @BEGIN_OF_CODE */ #include <stdio.h> void main() { long num,n,i,j,count,max_cycle; long tmp,itmp,jtmp; while(scanf("%ld %ld",&i,&j)!=EOF) { if(i==0 && j==0) break; max_cycle=0; itmp=i; jtmp=j; if(i>j) { tmp=itmp; itmp=jtmp; jtmp=tmp; } for(n=itmp;n<=jtmp;n++) { num=n; count=1; while(num!=1) { if(!(num%2)) { num/=2; count++; } else { num=(num*3)+1; count++; } printf("%d\n",n); } if(max_cycle < count) max_cycle=count; } printf("%ld %ld %ld\n",i,j,max_cycle); } } /* @END_OF_CODE */#include
long int count=0;
void f(long int n)
{
if(n==1)
count++;
else if(n%2!=0)
{
count++;
f(3*n+1);
}
else
{
count++;
f(n/2);
}
}
int main()
{
long int a,b,max,i,atemp,btemp,temp;
while(scanf(“%lld%lld”,&a,&b)==2)
{
if(a==0||b==0)
break;
atemp=a;
btemp=b;
if(a>b)
{
temp=atemp;
atemp=btemp;
btemp=temp;
}
max=0;
for(i=atemp;imax)
max=count;
}
printf(“%ld %ld %ld\n”,a,b,max);
}
return 0;
}
// Run time .664s
#include
#include
#include
#define foq(i,start,end) for(long long i=start;i<=end;i++)
#define fo(i,start,end) for(long long i=start;i<end;i++)
using namespace std;
int main()
{
long long i,j,count;
while((scanf("%lld%lld",&i,&j)==2))
{
long long max=0;
long long d=i;
long long b=j;
if(j1)
{
if((n/2)*2==n)
{
n=n/2;
count++;
}
else
{
n=3*n+1;
count++;
}
}
if(count>max)
{
max=count;
}
}
}
cout<<d<<" "<<b<<" "<<max<<endl;
}
return 0;
}
//Run time: .656s
Use ‘n’ as long long int n , otherwise the posted solution fails for input
1 999999
Solution:
100 : 3n+1
#include
int main()
{
long int i,j,n1,n2,max=0,l,temp;
while(scanf(“%ld %ld”,&n1,&n2)==2){
printf(“%ld”,n1);
printf(” %ld”,n2);
max=0;
if(n2<n1){
temp=n2;
n2=n1;
n1=temp;
}
for(j=n1;jmax) max=l;
}
printf(” %ld\n”,max);
}
return 0;
}
for solution of this problem and other more problem visit http://uvasolve.co.cc
#include
#include
#include
using namespace std;
unsigned long calc(unsigned long n);
int main()
{
int i, j, a, b, m;
vector temp;
while while (cin >> i >> j)
{
if (i < j)
{
a = i;
b = j;
}
else
{
a = j;
b = i;
}
temp.clear();
for (unsigned int k = a; k <= b; ++k)
{
temp.push_back(calc(k));
}
m = *max_element(temp.begin(), temp.end());
cout << i << ' ' << j << ' ' << m << endl;
}
}
unsigned long calc(unsigned long n)
{
unsigned long ret = 1;
while (n != 1)
{
if (n % 2 == 0)
n = n/2;
else
n = 3*n + 1;
ret++;
}
return ret;
}