fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. int main() {
  4. 	using namespace std;
  5. 	ios_base::sync_with_stdio(false), cin.tie(nullptr);
  6.  
  7. 	int T; cin >> T;
  8. 	for (int case_num = 1; case_num <= T; case_num ++) {
  9.  
  10. 		int N; cin >> N;
  11. 		vector<string> A(N); for (auto& a : A) cin >> a;
  12.  
  13. 		int ans = 0;
  14.  
  15. 		string cur = A[0];
  16. 		cout << " cur = " << cur << endl;
  17. 		for (int i = 1; i < N; i++) {
  18. 			// increment cur, because strictly increasing
  19. 			for (int x = int(cur.size())-1; true; x--) {
  20. 				if (x < 0) {
  21. 					cur.insert(cur.begin(), '1');
  22. 					break;
  23. 				} else if (cur[x] == '9') {
  24. 					cur[x] = '0';
  25. 					continue;
  26. 				} else {
  27. 					cur[x]++;
  28. 					break;
  29. 				}
  30. 			}
  31.  
  32. 			string cnd = A[i];
  33. 			if (cnd.size() > cur.size()) {
  34. 				// do nothing
  35. 				cur = cnd;
  36. 				continue;
  37. 			} else {
  38. 				// try to match it in size
  39. 				assert(cur.size() >= cnd.size());
  40. 				for (int a = 0; true; a++) {
  41. 					if (a == int(cnd.size())) {
  42. 						// the prefixes match
  43. 						ans += int(cur.size() - cnd.size());
  44. 						cnd = cur;
  45. 						break;
  46. 					} else if (cnd[a] < cur[a]) {
  47. 						// it's bad
  48. 						ans += int(cur.size() - cnd.size() + 1);
  49. 						cnd.insert(cnd.end(), cur.size() - cnd.size() + 1, '0');
  50. 						break;
  51. 					} else if (cnd[a] > cur[a]) {
  52. 						// it's fine, we can just insert 0's
  53. 						ans += int(cur.size() - cnd.size());
  54. 						cnd.insert(cnd.end(), cur.size() - cnd.size(), '0');
  55. 						break;
  56. 					} else {
  57. 						continue;
  58. 					}
  59. 				}
  60. 				cur = cnd;
  61. 			}
  62. 		}
  63.  
  64. 		cout << "Case #" << case_num << ": " << ans << '\n';
  65. 	}
  66.  
  67. 	return 0;
  68. }
  69.  
Success #stdin #stdout 0s 5524KB
comments (?)
stdin
copy 
1
3
100 7 10
stdout
copy 
 cur = 100
Case #1: 4
https://ideone.com/x8QSXX
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!