Sizə verilmiş x ədədini 11,111,1111,11111.... kimi ədədlərin cəmi şəklind göstərmək…
- User
Sizə verilmiş x ədədini 11,111,1111,11111.... kimi ədədlərin cəmi şəklind göstərmək mümkündürmü? Bu tip ədədlərdən hər birini bir neçə dəfə götürə bilərsiz.
məsələn,
22=11+11 144=111+11+11+11 Input İlk sətirdə testlərin sayı t (1≤t≤10000) .
Növbəti t sətirdə bir ədəd x (1≤x≤109) — cəmləməli olduğunuz ədəd.
Output Hər bir x üçün çıxışa uyğun olaraq "YES" və ya "NO" verin.
Example InputCopy 4 1 33 144 69 OutputCopy NO YES YES NO #include <bits/stdc++.h>
using namespace std;
#define ll long long #define ld long double #define endl '\n' #define pb push_back #define speedyboy ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define all(x) x.begin() , x.end() #define F first #define S second #define pll pair<ll , ll> #define YES cout << "YES" << endl; #define NO cout << "NO" << endl;
ll i , j , k , ans; const ll sz = 5e5 + 5 , INF = 1e18 , MOD = 1e9 + 7; vector v; bool dp[sz];
void solve(){ ll n; cin >> n; if(n < 11){ NO; return; } v.clear(); dp[sz] = {false}; for(i = 11 ; i <= n ; i = i * 10 + 1){ v.pb(i); } for(i = 0 ; i < v.size() ; i++){ dp[v[i]] = true; } for(i = 11 ; i <= n ; i++){ for(j = 0 ; j < v.size() ; j++){ if(i - v[j] >= 0){ if(dp[i - v[j]]){ dp[i] = true; } } } } cout << (dp[n] ? "YES" : "NO") << endl; }
signed main(){ speedyboy; ll t = 1; cin >> t; while(t--){ solve(); } } Can you fix my code?
- Assistant
Your current approach using Dynamic Programming (DP) has a couple of issues, especially given the problem constraints. Specifically:
-
DP Array Size: The DP array size is set to
5e5 + 5, but the input numberxcan be as large as1e9. This discrepancy will cause out-of-bounds errors for larger values ofx. -
DP Reset: The line
dp[sz] = {false};doesn't correctly reset the entire DP array. Instead, it only attempts to set thesz-th element, which is out of bounds.
Given these constraints, a DP approach isn't feasible for this problem due to the high range of
x(up to1e9) and the number of test cases (up to10,000). Instead, a mathematical approach can be used to determine whether a given numberxcan be expressed as a sum of numbers consisting solely of the digit1(like 11, 111, 1111, etc.).Mathematical Insight
-
Numbers to Consider: The numbers you can use for the sum are
11, 111, 1111, ...,up to the largest such number less than or equal to1e9. -
Modulo Relation: Notice that:
- Numbers with an even number of
1s (like11, 1111, ...) are divisible by11. - Numbers with an odd number of
1s (like111, 11111, ...) leave a remainder of1when divided by11.
- Numbers with an even number of
-
Condition for Representation:
- For any
x, calculates = x % 11. - If
s == 0, thenxis directly divisible by11and hence can be expressed as a sum of11s. - If
s != 0, check ifxis at leasts * 111. If it is, then you can usesnumbers of111(or larger) to make up the remainders, and the rest can be filled with11s.
- For any
Optimized Solution
Implement the above logic in your code. Here's how you can do it:
#include <bits/stdc++.h> using namespace std; #define ll long long #define YES "YES\n" #define NO "NO\n" int main(){ ios::sync_with_stdio(false); cin.tie(0); ll t; cin >> t; while(t--){ ll x; cin >> x; if(x < 11){ cout << NO; continue; } ll s = x % 11; if(s == 0){ cout << YES; } else{ if(x >= s * 111){ cout << YES; } else{ cout << NO; } } } }Explanation of the Code:
-
Input Handling:
- Read the number of test cases
t. - For each test case, read the number
x.
- Read the number of test cases
-
Condition Checks:
- Case 1: If
xis less than11, it's impossible to formxusing the allowed numbers. OutputNO. - Case 2: Calculate
s = x % 11.- If
s == 0,xis a multiple of11. OutputYES. - Otherwise, check if
xis at leasts * 111. If it is, you can usesinstances of111and the rest can be filled with11s. OutputYES. - If not, output
NO.
- If
- Case 1: If
Why This Works
This approach ensures that:
- When
s == 0, the number can be entirely composed of11s. - When
s != 0, usingsinstances of111(which addresses the remainder) alongside multiples of11covers all possible valid combinations efficiently.
This method avoids the pitfalls of the DP approach for large inputs and runs in constant time per test case, making it highly efficient for the given constraints.
-