题解：UVA371 Ackermann Functions

zhoujunchen · 2024-12-21 10:22:49 · 题解

感觉像冰雹猜想。

做题思路

求出 l\le i\le r 的 X_i，然后取最大值，并记录 i。

好像没有数据范围，那就把 X 数组开 10^6。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int x[(int)1e6+5];
int akm(int n){
    if(x[n])return x[n];
    if(n==1)return 0;
    if(n%2==0)return x[n]=akm(n/2)+1;
    return x[n]=akm(3*n+1)+1;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int l,r;
    while(cin>>l>>r){
        if(!l&&!r)break;
        if(r<l)swap(l,r);
        int ans=-1e9,idx;
        for(int i=l;i<=r;i++){
            if(!x[i])x[i]=akm(i);
            if(ans<x[i])ans=x[i],idx=i;
        }
        printf("Between %d and %d, %d generates the longest sequence of %d values.\n",l,r,idx,ans);
    }
    return 0;
}