SHARE
TWEET

Untitled

a guest Sep 21st, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define all(v)              ((v).begin()), ((v).end())
  6. #define allr(v)             ((v).rbegin()), ((v).rend())
  7. #define sz(v)               ((int)((v).size()))
  8. #define rep(i, v)       for(int i=0;i<sz(v);++i)
  9. #define lp(i, n)        for(int i=0;i<(int)(n);++i)
  10. #define lpi(i, j, n)    for(int i=(j);i<(int)(n);++i)
  11. #define lpd(i, j, n)    for(int i=(j);i>=(int)(n);--i)
  12. #define ll long long
  13. #define pb                  push_back
  14. #define fIO ios_base::sync_with_stdio(0);cin.tie(0);
  15.  
  16. const ll inf = 1e8;
  17. const double pi = 3.1415926535897;
  18.  
  19.  
  20. const double EPS = (1e-7);
  21. int dcmp(double x, double y) {  return fabs(x-y) <= EPS ? 0 : x < y ? -1 : 1;   }
  22.  
  23.  
  24. typedef vector<int>                vi;
  25. typedef vector<pair<int,int>>      vii;
  26. typedef vector<ll>                 vll;
  27. typedef vector<double>             vd;
  28. typedef vector< vi >               vvi;
  29. typedef vector< vd >               vvd;
  30. typedef vector<string>             vs;
  31.  
  32. /**
  33.     * PLEASEEE READDD PROBLEEEM CARFULLY ****
  34.     * Always check for OVERFLOW ll vs int
  35.     * Always check for array bounds
  36.     * Check for function return
  37.     * READ OUTPUT SECTION AGAIN!!!
  38. **/
  39.  
  40. struct edge{
  41.     int from,to,w;
  42.     edge(int u,int v,int w) : from(u),to(v),w(w){}
  43.  
  44.     bool operator < (const edge &e) const{
  45.         return w > e.w;
  46.     }
  47. };
  48.  
  49. const int N = 200005;
  50.  
  51. ll seq(ll n){
  52.     double d = 1 + 8.0 * n;
  53.     double x = (-1 + sqrt(d)) / 2;
  54.  
  55.     long long k = floor(x);
  56.     long long m = k*(k+1) / 2;
  57.     if (m == n) {
  58.         return k;
  59.     } else {
  60.         return n - m;
  61.     }
  62. }
  63.  
  64. int sol(int n){
  65.     int curr = 10;
  66.     int inc = 0;
  67.     int part = 1;
  68.     int digits = 0;
  69.     for(int i = 1; i <= n; i++){
  70.         if(i == curr){
  71.             curr *= 10;
  72.             part++;
  73.         }
  74.         inc += part;
  75.         digits += inc;
  76.     }
  77.     cout << "digits: " << digits << endl;
  78.     return digits;
  79. }
  80.  
  81. int main() {
  82.     fIO
  83.  
  84.    // cout << sol(12) << endl;
  85.     int q;
  86.     int k;
  87.     cin >> q;
  88.  
  89.     while(q--){
  90.         cin >> k;
  91.  
  92.         int l = 0, r = 30000;
  93.  
  94.         while(l <= r){
  95.             int mid = (l + r) / 2;
  96.             int ret = sol(mid);
  97.  
  98.      //       cout << l << " " << r << " " << ret <<  endl;
  99.  
  100.             if(ret == k){
  101.                 cout << mid % 10 << endl;
  102.                 break;
  103.             }else if(ret > k){
  104.                 r = mid;
  105.             }else{
  106.                 l = mid + 1;
  107.             }
  108.  
  109.             if(l == r){
  110.                 int f = 0;
  111.                 int temp = sol(r - 1);
  112.                 //cout << l << " " << r << endl;
  113.                 for(int i = 1;i <= r; i++){
  114.                     //cout << temp << endl;
  115.                     int t = i;
  116.                     int f2 = 0;
  117.                     while(t){
  118.                         temp++;
  119.                         if(temp == k){
  120.                             cout << t % 10 << endl;
  121.                             f2= 1;
  122.                             break;
  123.                         }
  124.                         t /= 10;
  125.                     }
  126.                     if(f2) break;
  127.                 }
  128.                 break;
  129.             }
  130.         }
  131.     }
  132.  
  133.  
  134.  
  135. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top