UVa100 The 3n + 1 problem

发表于 | 分类于 |
字数统计: 213 字

题目链接

题解

模拟即可
不需要RMQ也不需要记忆化…因为数据好像超出了10000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int rec(int cur){
    if(cur == 1)return 1;
    if(cur & 1)
        return rec(3 * cur + 1) + 1;
    else 
        return rec(cur >> 1) + 1;
}
void init(){
}
void solve(){
    int l, r;
    while(scanf("%d%d", &l, &r) == 2){
        int aans = 0;
        if(l < r){
            for(int i = l; i <= r; ++i)
                aans = max(aans, rec(i));
        }else {
            for(int i = r; i <= l; ++i)
                aans = max(aans, rec(i));
        }
        printf("%d %d %d\n", l, r, aans);
    }
}
int main(){
    init();
    solve();
    return 0;
}