?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
99688938 |
Practice: lazy_learner |
1409D - 23 | GNU C++11 | Time limit exceeded on test 2 | 2000 ms | 0 KB | 2020-11-27 09:08:59 | 2020-11-27 09:08:59 |
#include<bits/stdc++.h> using namespace std; ////////// Template structure for debugging #define tr(...) trace(#__VA_ARGS__, __VA_ARGS__) template <typename Arg1> void trace(const char* name, Arg1&& arg1){ cout << name << " : " << arg1 << endl; } template <typename Arg1, typename... Args> void trace(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ','); cout.write(names, comma-names) << " : " << arg1 << " | " ; trace(comma+1, args...); } #define print(...) pr(#__VA_ARGS__, __VA_ARGS__) template <typename Arg1> void pr(const char* name, Arg1&& arg1){ cout << arg1 << endl; } template <typename Arg1, typename... Args> void pr(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ','); cout << arg1 << " "; pr(comma+1, args...); } void printV(vector<int> &arr) { cout << "Vector : "; for(int i=0;i<arr.size();i++) cout << arr[i] << " \n"[ i == arr.size()-1 ]; } void printA(int arr[], int n) { cout << "Array : "; for(int i=0;i<n;i++) cout << arr[i] << " \n"[ i == n-1 ]; } //-----------Prime factorization of a number N //vector<int> factorize(int N){ //for(ll i=2; i*i <=N; i++){ //if(N % i)continue; //factors.push_back(i); //while(N % i == 0)N /= i; //} //if(N > 1)factors.push_back(q1); //return factors //} //-----------Power for a ^ b //int power(int a, int b){ //int ans = 1; //while(b){ //if(b&a)ans *= a; //a *= a; //b >>= 1; //} //return ans //} //-----------factorial of a number n //int fact(int n){ //int ans = 1; //for(int i=1; i<=n; i++)ans = 1ll * ans * i % MOD; //return ans; //} //-----------N C r //int ncr(int n, int r){ //if(r > n)return 0; //if(r==0 || n==0)return 1; //if(r==1)return n; //int a = fact(n), b = 1ll * fact(n-r) % MOD, c = 1ll * fact(r) % MOD; //int ans = 1ll * a * power(b, MOD-2) % MOD; //ans = 1ll * ans * power(c, MOD-2) % MOD; //return ans; //} //------------------sieve of Eratosthenes // //arr[0] = 1; //arr[1] = 1; //for(int i=2; i*i <= N; i++){ //if(!arr[i]){ //for(int j=i*i; j<=N; j++) //arr[j] = 1; //} //} typedef long long ll; bool possible(ll num, ll s, ll moves){ string s1 = to_string(num), s2 = to_string(num + moves); if(s2.length() > s1.length())return true; int sum1 = 0, sum2 = 0; for(int i=0; i<s1.length(); i++)sum1 += s1[i] - '0'; for(int i=0; i<s1.length(); i++){ if(s1[i] == s2[i]){ sum2 += s1[i] - '0'; } else { sum2 += s1[i] - '0' + 1; break; } } return min(sum1, sum2) <= s; } vector<int> arr; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--){ ll num, s; cin >> num >> s; ll l = 0, r = 1e18+1, m; while(l<r){ m = l + (r-l)/2; if(possible(num, s, m))r=m; else l = m+1; } cout << l << endl; } }
?
?
?
?