饥饿的小易(枚举 广度优先遍历(BFS卡塔 尔(英

作者:编程技术

 

n = int(raw_input().strip())
mod = int(1e9 7)
ans = -1
time = 4
for i in range(1,300001):
    x = (n*time time-1)%mod
    if x == 0:
        ans = (i 1)/3
        if (i 1)%3:
            ans  = 1
        break
    time = (time*2)%mod
print(ans)

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

——问:如果我发现a==2^5或a==2^4的时候满足要求,但是5和4才不能表示成3的倍数,怎么办?

输出:

125000000

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

输入

 

如果你多枚举一些,就会发现,能变换出的数的形式都是:

本周早些时候,学弟给我发了一道网易的笔试题,饥饿的小易,感觉有点意思~分享给大家

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

题目描述:

示例1

 

y=4x 3

现在解题思路就很清晰了,以0,f,ff为起始位置,每次都移动g,看什么时候能移动到能被1000000007整除的位置。代码如下:

观察变换形式,并做变形:

希望对大家有所帮助~

第二种方法要比第一种方法高效一点

乍一看这道题,是有点懵逼的,如果用暴力法来做100%超时。以我的经验来看估计这是一道数学问题,我们就分析一下题目描述中的关键信息吧,看看有没有什么玄机。小章鱼只能移动到4 * x 3或者8 * x 7,那我们认为f(x)=4 * x 3, g(x)=8 * x 7。关键部分到了,我瞪俩眼睛观察了好久,终于发现

4x 3=4(x 1)-1

1. f(g(x)) = g(f(x))  我们可以认为最终小章鱼的移动路线是可以用fg表示的字符串,而且fg可以随意调换位置~所以说腻,ffggffgf=fffffggg

分析:

2. f(f(f(x)))=g(g(x)) 也就是说,每做3次f移动等于2次g移动,那么我们可以将结果的fg串中每3个f换成2个g,那么结果的fg串是一个最多包含2个f的fg串~所以说腻,fffffggg=ffggggg

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

 

——问:那最小要执行几次变换?

 

8x 7=8(x 1)-1

#!/usr/bin/python
# -*- coding: utf-8 -*-


def get_result(n):
    l_ = [n, n * 4   3, 16 * n   15]
    for j, m in enumerate(l_):
        for i in range(100000):
            m = (8 * m   7) % 1000000007
            if m == 0:
                return i j 1
    return -1

if __name__ == '__main__':
    n = input()
    print get_result(n)

8y 7=8((4(x 1)-1) 1)-1=8(4(x 1))-1=32(x 1)-1

好啦,这道题到此已经完美解决啦~

输出描述:

 

对5这种情况,除以3余2,那刚好,用一次乘4的变换就行了

输入:

答:我们直接贪心,尽量让a乘8(乘2次8和乘3次4一样大,当然是乘8越多,变换次数越少)

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

答:直接考虑最大情况,每次变换都选择8x 7那种,也就是,每次a乘上8,也就是说,最坏是(2^3)^100000=2^300000次

题目描述

  这道题我们只能把每步都分为两种情况,使用神秘力量1(4 * x 3)和使用神秘力量2(8 * x 7)。从出发点开始枚举,使用广度优先遍历算法(BFS)。由于贝壳出现在能被1,000,000,007整除的位置,所以我们只需要考虑00000007后的结果。我们要记录初次到达某个位置时使用了几次神秘力量。

如果多层嵌套呢?

考虑直接枚举那个a,从2^2一直到……等等,最大是2的多少次?

所以,枚举a,从2^2次,一直到2^300000次

a(x 1)-1,其中a是2的>=2的幂次数(4、8、16、32、64、……)

 1

我们可以利用这个特点

 

from collections import deque
mod = 1e9 7
n = int(raw_input().strip())
currentPos = n%mod
power = {}
power[currentPos] = 0
d = deque()
d.append(currentPos)
flag = False
while len(d):
    currentPos = d.popleft()
    if power[currentPos] > 100000:
        break
    if currentPos == 0:
        flag = True
        break
    nextPos = (4*currentPos 3)%mod
    if nextPos not in power:
        power[nextPos] = power[currentPos] 1
        d.append(nextPos)
    nextPos = (8*currentPos 7)%mod
    if nextPos not in power:
        power[nextPos] = power[currentPos] 1
        d.append(nextPos)
if flag:
    print(power[currentPos])
else:
    print(-1)

答:别忘了你手上还有4x 3的变换(就是a乘4的变换)

第一种方法:

对4这种情况,除以3余1,我们考虑,消去一个乘8的变换,用2个乘4的变换代替并补足。

 

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

 

然后,对每个a检查一下,乘起来结果9 7是不是0,如果是0,说明100000次之内有解

第二种方法:

输出

参考博客:

输入描述:

本文由分分快三计划发布,转载请注明来源

关键词: 分分快三计划 编程