cứu e:[ *xin tip hok tin cho giỏi vs ặ:(

Thuật toán

Nhận xét: Tất cả các số có nhiều hơn 3 chữ số 1 được sử dụng đều "vô dụng", tức việc sử dụng nó tương đương với việc sử dụng một số số $11$ và $111$.

Thật vậy, giả sử ta sử dụng một số $x = \underbrace{111\ldots11}_{n \text{ chữ số } 1}$ ($n > 3$)

Nếu $n$ chẵn $\Rightarrow x \vdots 11$. Do đó, $x$ sẽ có thể được biểu diễn bằng tổng của một số số $11$.

Nếu $n$ lẻ. Ta có $x = \underbrace{111\ldots11}_{n-3 \text{ chữ số } 1} \times 1000 + 111$. Do $n$ lẻ nên $n-3$ chẵn. Vì vậy số $x$ có thể được viết bằng tổng của một số số $11$ và một số $111$.

Với nhận xét trên, ta rút ra được rằng việc viết lại số $x$ bằng các số có dạng đã cho chỉ có thể làm được khi và chỉ khi $x$ có thể viết được dưới dạng $111a + 11b$ ($a, b \in N$).

Giả sử $x$ có thể biểu diễn được với dạng trên, khi đó $x = 111a + 11b$. Do $111 \equiv 1$ (mod $11$) nên $111a \equiv a$ (mod $11$). Mà $11b \vdots 11$ nên ta suy ra $x \equiv a$ (mod $11$).

Để tránh giá trị $111a$ trở nên quá lớn, ta sẽ chọn $a$ nhỏ nhất, tức $a = x \% 11$ với $%$ là phép chia lấy dư. 

Tóm lại, số $x$ viết được dưới dạng $111a + 11b$ khi và chỉ khi $111a \leq x$ với $a = x \% 11$.

Phiên bản tiếng anh của bài này là 1536B - I hate 1111 (Codeforces Round 723 Div. 2)

Code (C++)

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

int t,n,mod;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> t;
    while(t--){
        cin >> n;
        mod = n % 11;
        if(111 * mod <= n){
            cout << "YES";
        }else{
            cout << "NO";
        }
        cout << '\n';
    }
    return 0;
}