首页 > 试题广场 >

饥饿的小易

[编程题]饥饿的小易

热度指数：20627 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小易总是感觉饥饿，所以作为章鱼的小易经常出去寻找贝壳吃。最开始小易在一个初始位置x_0。对于小易所处的当前位置x，他只能通过神秘的力量移动到 4 * x + 3或者8 * x + 7。因为使用神秘力量要耗费太多体力，所以它只能使用神秘力量最多100,000次。贝壳总生长在能被1,000,000,007整除的位置(比如：位置0，位置1,000,000,007，位置2,000,000,014等)。小易需要你帮忙计算最少需要使用多少次神秘力量就能吃到贝壳。

输入描述:

输入一个初始位置x_0,范围在1到1,000,000,006

输出描述:

输出小易最少需要使用神秘力量的次数，如果使用次数使用完还没找到贝壳，则输出-1

示例1

输入

125000000

输出

算法知识视频讲解

Java

力喜

java实现，已通过。参考了评论的做法。

思路：对于一个数 x ，4x+3可以看作是数的二进制 ### 后加 2 个“1”： ###11，

8x+7可以看作是数的二进制 ### 后加 3 个“1”： ###111，

（因为二进制每一位是2的n次方，比如低4位是这样的： 8 4 2 1，

数字2： 0 0 1 0，然后要求4*2+3:

=数字11：0 1 1 1

加的“3”需要后两位 “2 1” 实现，然后原来的数乘以2的2次方，通过左移2位实现。

因此可知：对于一个数x 。2的n次方*x+(2的n次方)=数的二进制 ### 后再加 n 个“1”。

对于饥饿的小易，只需要知道，如果她可以吃到贝壳，那么从初始位置到贝壳位置，其二进制形式是给末尾加了几个 "1" ？假设可以吃到，加了 i 个 “1” ，其中 m 个 “1”是通过 4x+3 的方式，该方式每步可加 2 个“1”；其中 n 个 “1”是通过 8x+7 的方式，该方式每步可加 3 个“1” ，那么 i =2m+3n ，要求 m+n 的最小值。我们应该使每步 3 个 “1” 的方式尽可能多，因此，从初始位置开始，给初始位置二进制形式后面依次加1个、2个、3个... ..“1”，（用 i 控制循环个数，每次给数字 *2 +1 就可以实现末尾+1,为了避免溢出，需要对 1 0000 0000 7 取余！！！易错！因为 i 只是控制循环次数，即给末尾加了多少个 “1”，取余不影响结果。）直到遇到可以整除1 0000 0000 7的情况，也就是可以吃贝壳了，这时看 i，也就是加的 “1” 的个数，用 i 依次减去0个、1个、2个 ......“2”，（用 j 控制循环次数）遇到能被3整除的情况，这个 j 就是m，需要求（m+n）,也就是

（2m+3n+ m ）/3 = ( i+j ) /3,

如果步数达到上限3* 10万（假设用完最大次数 10万，每次加最多的“1”：3个）都没有遇到贝壳，返回 -1 即可。

代码如下：

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
long x=in.nextLong();
if(x==0) System.out.println("1");
else
System.out.println(gettimes(x));
        }
public static long gettimes(long x)
{
long temp=x;
    for(int i=1;i<=300000;i++)
    {
temp=(temp*2+1)%1000000007;
        if(temp==0)
        {
            for(int j=0;j<=(i/2);j++)
            {
                if((i-j*2)%3==0)
                {
                    return (i+j)/3;
                }
            }
        }
    }
return -1L;
}
    }

发表于 2020-02-12 13:09:50 回复(0)

Java

secondriver

import java.util.Scanner;

public clas***ain {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long x0 = scanner.nextLong();
        long m = 1000000007;//取模的值
        long s = 100000; //神秘力量使用的次数
        
        long[] begin = new long[3]; //f(x) = 4x+3 执行3次
        
        //3次的取值
        begin[0] = x0;
        begin[1] = (4 * begin[0] + 3) % m;
        begin[2] = (4 * begin[1] + 3) % m;
        
        long minStep = s;
        long cur = 0;
        int step = 0; //执行的步数
        for (int i = 0; i < 3; i++) {
            cur = begin[i];
            step = i;
            while (cur != 0 && step < minStep) {
                cur = (8 * cur + 7) % m; //g(x) = 8x+7 执行
                step++;
            }
            minStep = minStep < step ? minStep : step;
        }
        if (minStep < s) { //如果执行步长没有超过s输出最小步长
            System.out.println(minStep);
        } else {//超过返回-1
            System.out.println(-1);
        }
    }
}

发表于 2019-05-15 14:59:04 回复(0)

Java

石榴树下

参考@Leori 的思路，4x+3和8x+7执行顺序可以交换，做三次4x+3等于做两次8x+7

所以最小次数是当4*x+3取0,1,2的时候不同情况下的最小值

public class Main {

    public static final int VALUE = 1000000007;
    public static final int TEMP = 100000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            long x = sc.nextLong();
            boolean isfound = false;
            int min = Integer.MAX_VALUE;
            for(int i=0,j;i<=2;i++){
                int count = i;
                long num = x;
                for(j=0;j+i<=TEMP;j++){
                    if(num%VALUE==0){
                        isfound = true;
                        break;
                    }else {
                        num = (8 * num + 7)%VALUE;
                        count++;
                    }
                }
                if(min>count)
                    min = count;
                x = (4 * x + 3)%VALUE;
            }
            if(!isfound)
                min = -1;
            System.out.println(min);
        }
    }

}

编辑于 2018-08-03 23:41:49 回复(0)

Java

黄小斜

参考一个老哥的答案
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        long x = Long.parseLong(line);

        System.out.println(min(x));
    }

    public static long min(long x) {
        //4x + 3和8x + 7可以拆成2x + 1;
        long count = 0;
        long goal = 1000000007;
        while (count <= 300000) {
            //防止溢出，每次都取余数
            x = ((x << 1) + 1) % goal;
            count ++;
            if (count == 1)continue;
            if (x == 0)break;
        }
        if (count > 300000) {
            return -1;
        }
        //这个式子的意思是,count = 2时，res = 1，count = 3时，res = 1.
        //以此类推是正确的可以把一个数拆成最小的2和3的组合个数。
        //虽然我也不知道为什么。count = 1时是不行的。
        long res = (count + 2)/3;
        if (res > 100000) {
            return -1;
        }else {
            return res;
        }
        //
    }
}

发表于 2018-05-21 15:24:36 回复(0)

Java

绕远的偶人

速度不快但是思路简单。

4x + 3等于做了两次2x + 1， 8x + 7做了三次。

从起点开始令x0 = 2*x0 + 1，统计做了多少次2x + 1后模1000000007等于0

再把次数分解成若干个3与2的和，3的个数加上2的个数最小，不超过100000

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x0 = in.nextInt();
        in.close();
        int count = 0;
        while (x0 != 0 && count <= 300000) {
            x0 = ((x0 << 1) + 1) % 1000000007;
            count++;
        }
        int res = (count + 2) / 3;
        System.out.println(res > 100000 ? -1 : res);
    }
}

编辑于 2018-03-28 23:22:33 回复(21)

Java

longwangtang

基于陈丽丰的思路实现：

//基于 陈丽丰 的思路实现：
import java.util.*;
public class Main {
    private static long molecole = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count=0;
        long x_0=sc.nextInt();
        long x_1=x_0*4+3;
        long x_2=x_1*4+3;
        if(g(x_0,++count)||g(x_1,++count)||g(x_2,++count)){

        }else{
            System.out.println(-1);
        }
    }
    public static boolean g(long x,int count) {
        boolean result=false;
        while (count <= 100_000){
            long temp=8*x+7;
            if(temp%molecole==0){
                result=true;
                System.out.println(count);
                break;
            }else {
                x=temp%molecole;
                count++;
            }
        }
        return result;
    }

}

发表于 2017-09-12 09:54:03 回复(0)

Java

苏果飞

///////完全参考@ toraoh的思想写的java版本的代码。

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.println(fun(n));
		sc.close();		
	}
	
	public static int fun(int n){
		int mod = 1000000007;
		int times = 4;
		int ans = 100001;
		for(int i = 0; i < 300000; i++){
			int x = (int)(((long)n*times + times -1)%mod);
			if(x==0){
				ans = (i+2)/3+((i+2)%3!=0?1:0);
				break;
			}
			
			times = (times << 1) % mod;
		}
		
		return ans > 100000 ? -1 : ans;
	}
}

编辑于 2016-08-15 10:20:03 回复(1)