20123: 7-友好数

brute force, math, dfs similar, http://cs101.openjudge.cn/practice/20123/

黑板上写了一个正整数N，其首位不为0，位数不超过10^5。

N被称为7-友好数，如果可以擦掉若干位，使得剩下的数字构成的数为7的倍数。

要求不能擦掉所有数字，但允许只剩下一个数字0。

请你编写程序，判断N是不是7-友好数。

输入

一个正整数N，其位数 ≤ 10^5。

输出

如果N是7-友好数，那么输出YES ；否则输出 NO

样例输入

输入样例1：
123364315

输出样例1：
YES

解释：可以使得剩下的数为35，因此满足要求。

样例输出

输入样例2：
31116

输出样例2：
NO

来源：cs101-2019 金及凯

python

#20123:7-友好数，http://cs101.openjudge.cn/practice/20123/
#
# 陈威宇：>=7位就一定YES了，因为所有后缀%7有两个相等的（抽屉原理），
# 取这两个后缀里长的那个去掉短的那个即可？
'''
通过递归地尝试不同的子串来寻找符合条件的解.
`dfs(n, i)` 函数是进行深度优先搜索的核心部分。它接受两个参数：`n`代表当前搜索到的子串，
`i`代表当前处理到的位置索引。在函数内部，通过不断拼接字符来生成不同的子串，
然后检查是否满足能够被7整除的条件。

'''
def dfs(n, i):
    global bo
    if len(n) > 0 and int(n) % 7 == 0:
        bo = True
    if bo:
        return
    if i >= l:
        return
    dfs(n, i+1)
    dfs(n+s[i], i+1)


s = input()
l = len(s)
if l >= 7:
    print('YES')
    exit()
bo = False
dfs('', 0)
if bo:
    print('YES')
else:
    print('NO')

20123: 7-友好数 ​

20123: 7-友好数