难度 1500
题目 Codeforces:
You are given a non-negative integer n, its decimal representation consists of at most 100 digits and doesn‘t contain leading zeroes.
Your task is to determine if it is possible in this case to remove some of the digits (possibly not remove any digit at all) so that the result contains at least one digit, forms a non-negative integer, doesn‘t have leading zeroes and is divisible by 8. After the removing, it is forbidden to rearrange the digits.
If a solution exists, you should print it.
The single line of the input contains a non-negative integer n. The representation of number n doesn‘t contain any leading zeroes and its length doesn‘t exceed 100 digits.
Print "NO" (without quotes), if there is no such way to remove some digits from number n.
Otherwise, print "YES" in the first line and the resulting number after removing digits from number n in the second line. The printed number must be divisible by 8.
If there are multiple possible answers, you may print any of them.
Keyword
decimal representation 十进制表示
leading zeroes 前导零
remove 去除
rearrange 重新安排
quotes 引用
multiple 多个
题目解析
本题还是比较好理解的,因为大部分不熟悉的单词和题目关系也不会太大,简单来说,题目会给出一个不大于100位的十进制数字,所以只能用string或者字符数组存,这样一个100位十进制数前面没有零。
我们可以对这样一个数字中的任意一位进行去除,去除若干数字后,使得当前数字没有前导零(比如08就是有前导零的数字),且能够被8整除。
这样的题拿到以后首先就不可能说对100位的数字直接进行运算,那么通过观察可以知道,一个大于四位数的十进制数字能否被8整除取决于后三位,如果后三位能够被8整除,那么就说明成功了。
又因为题目说了,可能存在多种情况,输出任意一种情况即可,那么事实上只要确认后三位能被8整除,那么直接输出后三位即可,因为可以视为前面的所有位数都被我们去掉了。
解析完毕,以下是参考代码
1 #include<iostream> 2 #include<string> 3 using namespace std; 4 bool back(int a) 5 { 6 cout << "YES\n" << a; 7 return 1; 8 } 9 int main() 10 { 11 string a; cin >> a; 12 int length = a.length(); 13 for (int i = 0; i < length; i++)if (!((a[i] - ‘0‘) % 8) && back(a[i] - ‘0‘))return 0; 14 for (int i = 0; i < length - 1; i++) 15 for (int j = i + 1; j < length; j++) 16 if (!(((a[i] - ‘0‘) * 10 + a[j] - ‘0‘) % 8) && back((a[i] - ‘0‘) * 10 + a[j] - ‘0‘))return 0; 17 for (int i = 0; i < length - 2; i++) 18 for (int j = i + 1; j < length - 1; j++) 19 for (int k = j + 1; k < length; k++) 20 if (!(((a[i] - ‘0‘) * 100 + (a[j] - ‘0‘) * 10 + a[k] - ‘0‘) % 8) && back((a[i] - ‘0‘) * 100 + (a[j] - ‘0‘) * 10 + a[k] - ‘0‘))return 0; 21 cout << "No"; 22 return 0; 23 }