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 c++da yaz kodunu
- Assistant
Certainly! The problem requires determining whether a given number ( x ) can be expressed as a sum of numbers composed solely of the digit
1with at least two digits (i.e.,11,111,1111, etc.). This problem can be approached using a greedy algorithm, where we attempt to subtract the largest possible "special" number from ( x ) iteratively until ( x ) becomes zero. If at any point ( x ) cannot be reduced to zero using the available special numbers, the answer is "NO."Here's the step-by-step reasoning:
-
List of Special Numbers: The special numbers (composed solely of the digit
1with at least two digits) up to ( 10^9 ) are: [ \text{coins} = [111111111, 11111111, 1111111, 111111, 11111, 1111, 111, 11] ] -
Greedy Approach: For each value of ( x ):
- Start by subtracting the largest possible special number from ( x ).
- Repeat this process with the remainder until ( x ) becomes zero.
- If ( x ) can be reduced to zero by this method, output "YES"; otherwise, output "NO".
This method works efficiently because the list of special numbers is limited and the largest possible "coin" is significantly big, allowing for quick reductions in ( x ).
-
Implementation Considerations:
- Use fast input and output methods to handle up to ( 10^4 ) test cases efficiently.
- Iterate through the special numbers in descending order to maximize the reduction of ( x ) in each step.
Here is the C++ implementation based on the above reasoning:
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); // List of special numbers in descending order vector<long long> coins = {111111111, 11111111, 1111111, 111111, 11111, 1111, 111, 11}; int t; cin >> t; while(t--){ long long x; cin >> x; long long original_x = x; for(auto coin: coins){ if(coin <= x){ long long k = x / coin; x -= k * coin; } } if(x ==0){ cout << "YES\n"; } else{ cout << "NO\n"; } } }Explanation of the Code:
-
Input Handling:
- The first input line reads the number of test cases ( t ).
- For each test case, it reads the number ( x ).
-
Processing Each Test Case:
- For each ( x ), iterate through the
coinslist starting from the largest special number. - Subtract as many instances of the current
coinfrom ( x ) as possible. - After iterating through all coins, check if ( x ) has been reduced to zero.
- For each ( x ), iterate through the
-
Output:
- If ( x ) is zero after the subtraction process, output "YES".
- Otherwise, output "NO".
This approach ensures that each test case is processed efficiently, even for the upper limits of the input constraints.
-