fork(6) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. const int MaxN = 1e5;
  6. const ll mod = 1e9 + 7;
  7.  
  8. ll fun(ll x, ll size) {
  9. 	ll count = 0;
  10. 	for(int i = 1; i < size; i++) {
  11. 		ll num = (9ll * pow(10, i-1));
  12. 		count += (num * i);
  13. 	}
  14. 	ll mi = pow(10ll, size - 1);
  15. 	count += ((x - mi) * size) + 1;
  16. 	return count;
  17. 	// returns starting index of x.
  18. }
  19.  
  20. int main() {
  21.  
  22. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  23.  
  24. 	int t;
  25. 	cin >> t;
  26.  
  27. 	while(t--) {
  28.  
  29. 		ll N;
  30. 		cin >> N;
  31.  
  32. 		ll sum = 0, which_size;
  33.  
  34. 		for(int i = 1; i <= 18; i++) {
  35. 			ll num = (9ll * pow(10, i-1));
  36. 			sum += (num * i);
  37. 			if(N <= sum) {
  38. 				which_size = i;
  39. 				break;
  40. 			}
  41. 		}
  42.  
  43. 		ll lo = pow(10ll, which_size - 1);
  44. 		ll hi = pow(10ll, which_size) - 1;
  45.  
  46. 		// cout << "lo : " << lo << " hi : " << hi << endl;
  47. 		ll mid, ans = 0, index = 0;
  48.  
  49. 		while(lo <= hi) {
  50. 			mid = (lo + hi)/2;
  51. 			ll value = fun(mid, which_size);
  52. 			if(value <= N) {
  53. 				index = max(index, value);
  54. 				ans = max(ans, mid);
  55. 				lo = mid + 1;
  56. 			}
  57. 			else {
  58. 				hi = mid - 1;
  59. 			}
  60. 		}
  61.  
  62. 		// cout << ans << " " << index << "\n";
  63.  
  64. 		string str = to_string(ans);
  65.  
  66. 		for(auto ch : str) {
  67. 			if(N == index) {
  68. 				cout << (ch - '0')  << "\n";
  69. 				break;
  70. 			}
  71. 			index++;
  72. 		}
  73.  
  74. 	}
  75.  
  76. }
Success #stdin #stdout 0s 4696KB
comments (?)
stdin
copy 
1
10
stdout
copy 
1
https://ideone.com/KdmBMC
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!