1526-B, *1400

Problem - 1526B - Codeforces

문제

• $x(1\leq x \leq 10^{9})$가 주어질 때 $11,\ 111,\ 1111,\ 11111,\ ...\ $꼴 수의 합으로 표현될 수 있는지 결정하라

 

$O(1)$

Claim
어떤 수가 $11,\ 111,\ 1111,\ 11111,\ ...\ $꼴 수의 합으로 표현되면 $11$과 $111$의 합 만으로도 표현된다

$\because$
$$\begin{align*}
1111&=11 \times 100+11\\
11111&=111 \times 100+11\\
111111&=1111 \times 100+11\ \square
\end{align*}$$

 

Claim
$x$가 $11$과 $111$의 합으로 표현될 수 있을 때, $x=11A+111B,(0\leq B < 11)$
$\because$
$$\begin{align*}
\ &x = 11C+111D\\
&D = 11q+B, \ B\in [0,11)\ \square
\end{align*}$$

c++

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    int x;
    while(t--){
        cin >> x;
        bool flag = false;
        for(int i = 0; i < 11; i++){
            if(x >= 0 && x % 11 == 0) flag = true;
            x -= 111;
        }
 
        cout << (flag? "YES": "NO") << endl;
 
    }
 
    return 0;
}cs

 

python3

[(lambda n : print("YES" if (n >= 111*(n%11)) else "NO"))(int(input())) for _ in range(int(input()))]cs

※코드 출처: https://codeforces.com/blog/entry/91195, errorgorn

 

$O(1)$

$\mathrm{gcd(11,\ 111)=1}$이므로 $\mathrm{Chicken\ McNugget\ Theorem}$으로부터
$1099$ 보다 큰 수는 $11$과 $111$의 합으로 표현된다

따라서 $1099$이하의 수만 $\mathrm{dp}$ 로 되는지 확인해보면 되겠다

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int n = 1099;
bool arr[1100] {};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    arr[11] = true;
    arr[111] = true;
 
    loop(i, n){
        if(i > 11 && arr[i-11]) arr[i] = true;
        if(i > 111 && arr[i-111]) arr[i] = true;
    }
 
    int t;
    cin >> t;
    int tmp;
    while(t--){
        cin >> tmp;
        if(tmp <= 1099) cout << (arr[tmp]? "YES": "NO") << endl;
        else cout << "YES" << endl;
    }
 
    return 0;
}cs