游客 注册 | 登录
中文 | En

2007 - 蹦蹦跳跳的Rabbit大神

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

关于兔子~蹦蹦跳跳的兔子~谨以此题膜拜Rabbit大神。

话说小兔兔跳得很远，如果他处于位置x，则他能跳到4x+3或8x+7的位置，但是由于环境不好，只有%1,000,000,007=0的位置才有草。

但是小兔兔很饿，他最多只能跳100,000次，问，他最少需要跳几次才能吃到草？

如果他吃不到草，输出-1。

假设小兔兔的位置是281250001，则他先跳到1125000007（4x+3），再跳到9000000063(8x+7)。9000000063=9*1000000007。所以需要跳两次。

题目输入

一个数x，表示小兔兔的位置，n<1,000,000,007

题目输出

一个数，最少跳的次数，如果在规定步数内吃不到草输出-1.

输入/输出样例

输入格式

125000000
281250001

输出格式

1
2

C语言解答

#include<stdio.h>

const int maxn=1000000007;

int main(void)
{
    long long x, m;
    int cnt;
    int temp;
    while(scanf("%lld", &m)!=EOF){
        cnt=0; temp=0;
        x=m;
    for(int i=0; i<=100000; i++)
    {
        if(x%maxn==0)
        {
            temp=1;
            break;
        }
        else
        {
            x=(8*x+7)%maxn;
            cnt++;
        }
    }
    if(temp==0)
    {
        x=m;
        cnt=0;
        x=(4*x+3)%maxn;
        cnt++;
        for(int i=1; i<=100000; i++)
        {
            if(x%maxn==0)
            {
                temp=1;
                break;
            }
            else
            {
                x=(8*x+7)%maxn;
                cnt++;
            }
        }
    }
    if(temp==0)
    {
        x=m;
        cnt=0;
        x=(4*x+3)%maxn;
        x=(4*x+3)%maxn;
        cnt+=2;
        for(int i=2; i<=100000; i++)
        {
            if(x%maxn==0)
            {
                temp=1;
                break;
            }
            else
            {
                x=(8*x+7)%maxn;
                cnt++;
            }
        }
    }
    if(temp==0)
    printf("-1\n");
    else
    printf("%d\n", cnt);
}
    return 0;
}

C++解答

#include<stdio.h>

const int maxn=1000000007;

int main(void)
{
    long long x, m;
    int cnt;
    int temp;
    while(scanf("%lld", &m)!=EOF){
        cnt=0; temp=0;
        x=m;
    for(int i=0; i<=100000; i++)
    {
        if(x%maxn==0)
        {
            temp=1;
            break;
        }
        else
        {
            x=(8*x+7)%maxn;
            cnt++;
        }
    }
    if(temp==0)
    {
        x=m;
        cnt=0;
        x=(4*x+3)%maxn;
        cnt++;
        for(int i=1; i<=100000; i++)
        {
            if(x%maxn==0)
            {
                temp=1;
                break;
            }
            else
            {
                x=(8*x+7)%maxn;
                cnt++;
            }
        }
    }
    if(temp==0)
    {
        x=m;
        cnt=0;
        x=(4*x+3)%maxn;
        x=(4*x+3)%maxn;
        cnt+=2;
        for(int i=2; i<=100000; i++)
        {
            if(x%maxn==0)
            {
                temp=1;
                break;
            }
            else
            {
                x=(8*x+7)%maxn;
                cnt++;
            }
        }
    }
    if(temp==0)
    printf("-1\n");
    else
    printf("%d\n", cnt);
}
    return 0;
}

Java解答

import java.util.*;

public class Main{
    public static long mod=1000000007;
    public static long fun(long x){
        return (2*x+1)%mod;
    }
    public static void main(String args[]){
        Scanner cin=new Scanner(System.in);
        long x,n;
        long mx=100001*3;
        while(cin.hasNext()){
            x=cin.nextInt();
            n=0;
            while(x!=0 && n<mx){
                x=fun(x);
                n++;
            }
            if(mx==n){
                System.out.println(-1);
            }
            else{
                long xx=n/3,yy;
                n%=3;
                while(n%2!=0){
                    xx--;
                    n+=3;
                }
                yy=n/2;
                xx+=yy;
                if(xx>100000)
                    System.out.println(-1);
                else
                    System.out.println(xx);
            }
       }
    }
}
请先登陆