20180301出题:A strange number

  • 2018-03-01
  • 361
  • 0

A strange number

Time Limit: 1s

Description

Given a positive integer with a maximum of 100 digits, ask if you can remove several bits (removing zero bit is also okay) from it, so that the modified number can be divisible by 8.

Input

The input consists of multiple test cases. Each test case contains a positive integer with a maximum of 100 digits.

Output

Print “YES” if you can complete the given question.
Print “NO” if you can’t.

Sample Input

1234
3354
6789

Sample Output

YES
NO
YES

Solution

由于并没有规定要拿掉多少个,所以我们可以随意的拿掉任意数量的数字,而我们知道一个数字能不能被8整除取决于其后三位,后三位能被8整除那么这个数就能被8整除,于是我们只需要在字符串中取出三个数字,只要这三个数组成的数能被8整除,那么就是可行的答案

#include <bits/stdc++.h>
using namespace std;

void find(char num[])
{
    for (int k = 0; k < strlen(num); ++k)
    {
        if ((num[k]-48) % 8 == 0)
        {
            printf("YES\n");
            return;
        }
    }

    for (int j = 0; j < strlen(num); ++j)
        for (int k = j + 1; k < strlen(num); ++k)
        {
            if (((num[j]-48)*10 + (num[k]-48)) % 8 == 0)
            {
                printf("YES\n");
                return;
            }
        }

    for (int i = 0; i < strlen(num); ++i)
        for (int j = i + 1; j < strlen(num); ++j)
            for (int k = j + 1; k < strlen(num); ++k)
            {
                if (((num[i]-48)*100 + (num[j]-48)*10 + (num[k]-48)) % 8 == 0)
                {
                    printf("YES\n");
                    return;
                }

            }
    printf("NO\n");
}

int main()
{
    char num[105];
    while (~scanf("%s", num))
    {
        find(num);
    }

    return 0;
}

题目改编自:Codeforces 550c

评论

还没有任何评论,你来说两句吧

发表评论

冀ICP备19026961号