CodeForces 550C Divisibility by Eight(열거)

1928 단어 codeforces
[제목 링크] 클릭 here~~
[제목 대의]
100자리를 넘지 않는 숫자를 주고, 몇 자리 숫자를 삭제할 수 있는지를 요구하면, 나머지 숫자는 8로 나누어질 수 있다.
[문제풀이 사고방식]: 여기에 성질이 있다. 만약에 한 수를 세면 세 자리가 8로 나누어진다면 이 수는 8로 나누어질 수 있다.
증명: 5자리 예를 들어 _____  __              __  __                __  ___ abcde=ab000+cde=1000×ab+cde=8×125×ab+cde가 뚜렷하다×125×ab는 반드시 8 또는 125의 배수이기 때문에 cde가 8 또는 125로 정제될 때 다섯 자리 abcde는 8 또는 125로 정제될 수 있다.자릿수가 아무리 많아도 마찬가지입니다. 주로 1000=125*8입니다.
그러면 다음 세 분만 다 들어주시면 돼요.
코드:
#include <bits/stdc++.h>
using namespace std;
int main()
{
    char str[110];
    while(cin>>str)
    {
        bool ok=false;
        int len=strlen(str);
        for(int i=0; i<len; ++i)
        {
            if((str[i]-'0')%8==0)
            {
                puts("YES");
                cout<<(str[i]-'0')<<endl;
                return 0;
            }
        }
        for(int i=0; i<len; ++i)
        {
            for(int j=i+1; j<len; ++j)
            {
                if(((str[i]-'0')*10+(str[j]-'0'))%8==0)
                {
                    puts("YES");
                    cout<<((str[i]-'0')*10+(str[j]-'0'))<<endl;
                    return 0;
                }
            }
        }
        for(int i=0; i<len; ++i)
        {
            for(int j=i+1; j<len; ++j)
            {
                for(int k=j+1; k<len; ++k)
                {
                    if(((str[i]-'0')*100+(str[j]-'0')*10+str[k]-'0')%8==0)
                    {
                        puts("YES");
                        cout<<((str[i]-'0')*100+(str[j]-'0')*10+str[k]-'0')<<endl;
                        return 0;
                    }
                }
            }
        }
        puts("NO");
    }
}

공식 문제풀이는 dp를 사용합니다. 좀 번거롭습니다.

좋은 웹페이지 즐겨찾기