QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#135686#6300. Best Carry Player 2Swarthmore#WA 1ms3500kbC++202.8kb2023-08-05 21:48:552023-08-05 21:48:58

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 21:48:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3500kb
  • [2023-08-05 21:48:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Template {{{
#define REP(n) for (int _=0; _<(n); _++)
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

namespace std {
  template<class Fun>
  class y_combinator_result {
    Fun fun_;
  public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
   
    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
      return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
  };
   
  template<class Fun>
  decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
  }
} // namespace std

#define DEBUG(x) cerr << #x << ": " << x << '\n'
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) { 
  return os << '(' << p.first << ", " << p.second << ')'; 
}
template<typename T_container, 
  typename T = typename enable_if<!is_same<T_container, string>::value, 
  typename T_container::value_type>::type> 
ostream& operator<<(ostream &os, const T_container &v) { 
  os << '['; string sep; 
  for (const T &x : v) 
    os << sep << x, sep = ", "; 
  return os << ']'; 
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// }}}

ll ex10[20];
vector<int> dx;
ll dp[20][2][20];

const ll INF = LLONG_MAX;

ll f(int i, int c, int k) {
  if (i == 18) {
    return k == 0 ? 0 : INF;
  }
  auto& res = dp[i][c][k];
  if (res != -1) return res;
  int d = dx[i] + c;
  if (d == 10) {
    res = f(i+1, 1, k-1);
  }
  else {
    res = f(i+1, 0, k);
    ll tr = f(i+1, 1, k-1);
    if (d > 0 && tr < INF) ckmin(res, tr + (10 - d) * ex10[i]);
  }
  return res;
}

void solve() {
  memset(dp, -1, sizeof dp);
  ll x; cin >> x;
  ll k; cin >> k;

  dx.clear();
  while (x > 0) {
    dx.push_back(x % 10);
    x /= 10;
  }
  while (sz(dx) < 19) dx.push_back(0);

  if (k == 0) {
    for (int i = 0; i <= 18; i++) {
      if (dx[i] < 9) {
        cout << ex10[i] << '\n';
        return;
      }
    }
    assert(false);
  }

  // cout << dx << endl;
  ll ans = f(0, 0, k);
  cout << (ans < INF ? ans : -1) << '\n';
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  ex10[0] = 1;
  for (int i = 1; i <= 18; i++) {
    ex10[i] = ex10[i-1] * 10;
  }
  int T; cin >> T;
  while (T--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3500kb

input:

4
12345678 0
12345678 5
12345678 18
990099 5

output:

1
54322
999999999987654322
9910

result:

ok 4 lines

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3492kb

input:

21
999990000099999 0
999990000099999 1
999990000099999 2
999990000099999 3
999990000099999 4
999990000099999 5
999990000099999 6
999990000099999 7
999990000099999 8
999990000099999 9
999990000099999 10
999990000099999 11
999990000099999 12
999990000099999 13
999990000099999 14
999990000099999 15
999...

output:

100000
10000
1000
100
10
1
900001
9900001
99900001
999900001
10000000001
9999910000
9999901000
9999900100
9999900010
9999900001
9000009999900001
99000009999900001
999000009999900001
-1
1000000000000000000

result:

wrong answer 20th lines differ - expected: '99999999999999999900000000000000000', found: '-1'