fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6.  
  7. double getCost(const string &s) {
  8.     ll num = 0, digitSum = 0;
  9.     for (char c : s) {
  10.         num = num * 10 + (c - '0');
  11.         digitSum += (c - '0');
  12.     }
  13.     if (digitSum == 0) return 1e18;
  14.     return (double)num / digitSum;
  15. }
  16.  
  17. int main() {
  18.     ios::sync_with_stdio(false);
  19.     cin.tie(nullptr);
  20.  
  21.     int t;
  22.     cin >> t;
  23.     while (t--) {
  24.         string s;
  25.         cin >> s;
  26.         int n = s.size();
  27.  
  28.         double minCost = 1e18;
  29.         int minRemove = n - 1; 
  30.  
  31.  
  32.         for (int mask = 1; mask < (1 << n); ++mask) {
  33.             if (__builtin_popcount(mask) > 10) continue;
  34.  
  35.             string temp = "";
  36.             for (int i = 0; i < n; ++i) {
  37.                 if (mask & (1 << i)) temp += s[i];
  38.             }
  39.  
  40.             double cost = getCost(temp);
  41.             int removeCount = n - temp.size();
  42.  
  43.             if (cost < minCost || (abs(cost - minCost) < 1e-9 && removeCount < minRemove)) {
  44.                 minCost = cost;
  45.                 minRemove = removeCount;
  46.             }
  47.         }
  48.  
  49.         cout << minRemove << '\n';
  50.     }
  51.  
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
4
666
13700
102030
7
stdout 
2
4
3
0
https://ideone.com/UgQgqm
language:
C++ (gcc 8.3)
created:
4 days 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!