2015
07-16

# Hailstone HOTPO

The hailstone sequence is formed in the following way:

(1) If n is even, divide it by 2 to get n’
(2) If n is odd, multiply it by 3 and add 1 to get n’

It is conjectured that for any positive integer number n, the sequence will always end in the repeating cycle: 4, 2, 1, 4, 2, 1,… Suffice to say , when n == 1, we will say the sequence has ended.

Write a program to determine the largest value in the sequence for a given n.

The first line of input contains a single integer P, (1<= P <= 100000), which is the number of data set s that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input consisting of two space separated decimal integers. The first integer is the data set number. The second integer is n, (1 <= n <= 100,000), which is the starting value.

The first line of input contains a single integer P, (1<= P <= 100000), which is the number of data set s that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input consisting of two space separated decimal integers. The first integer is the data set number. The second integer is n, (1 <= n <= 100,000), which is the starting value.

4
1 1
2 3
3 9999
4 100000

1 1
2 16
3 101248
4 100000

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <map>

using namespace std;
const int N = 50000009;
int ans[N];
int find(int n)
{
if(n<N)
{
if(n==1) return 1;
if(ans[n]) return ans[n];
if(n&1) ans[n] = find(n*3+1);
else
{
int t = find(n>>1);
ans[n] = max(n,t);
return ans[n];
}
return ans[n];
}else
{
if(n&1) return find(n*3+1);
else return max(n,find(n>>1));
}
return n;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
ans[1] = 1;
int cas,n,a;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&a,&n);
printf("%d %d\n",a,find(n));
}
return 0;
}