fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9. int t;
  10. cin >> t;
  11. while (t--) {
  12. int n;
  13. cin >> n;
  14. string s;
  15. cin >> s;
  16.  
  17. // To store the minimum cost required to buy all figures
  18. long long min_cost = 0;
  19.  
  20. // To accumulate costs in each possible visit
  21. long long visit_cost = 0;
  22.  
  23. // Traverse the string and calculate costs
  24. for (int i = 0; i < n; ++i) {
  25. if (s[i] == '1') {
  26. visit_cost += (i + 1);
  27. min_cost += (i + 1);
  28. }
  29. }
  30.  
  31. // Deduct the cost of the highest-priced figure from each visit for discount
  32. for (int i = 0; i < n - 1; ++i) {
  33. if (s[i] == '1' && s[i + 1] == '1') {
  34. min_cost -= max(i + 1, i + 2);
  35. }
  36. }
  37.  
  38. cout << min_cost << endl;
  39. }
  40. return 0;
  41. }
  42.  
Success #stdin #stdout 0s 5272KB
stdin
4
1
1
6
101101
7
1110001
5
11111
stdout
1
10
8
1