QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#556636#2835. Number Theoryucup-team1198#WA 1054ms5068kbC++202.7kb2024-09-10 19:50:492024-09-10 19:50:49

Judging History

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

  • [2024-09-10 19:50:49]
  • 评测
  • 测评结果:WA
  • 用时:1054ms
  • 内存:5068kb
  • [2024-09-10 19:50:49]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int INF = 1e9;

const int MAXN = 5e3 + 100;
int dp[2][2 * 6 * MAXN][3];

int lst(int x) {
  int res = x % 10;
  if (res < 0) res += 10;
  return res;
}

int rest(int x) {
  return (x - lst(x)) / 10;
}

int rest9(int x) {
  int r = x % 9;
  if (r < 0) r += 9;
  return (x - r) / 9;
}

void solve(string ns) {
  reverse(ns.begin(), ns.end());
  ns.push_back('0');
  ns.push_back('0');  
  vector<int> n;
  for (char ch : ns) {
    n.push_back(ch - '0');
  }
  int l = n.size();
  int maxc = 5 * l + 100;
  /// cerr << "start done" << endl;
  for (int i = 0; i <= 1; ++i) {
    for (int j = -maxc; j <= maxc; ++j) {
      dp[i][j + maxc][0] = dp[i][j + maxc][1] = dp[i][j + maxc][2] = INF;
    }
  }
  /// cerr << "start done" << endl;
  for (int start = -maxc; start <= maxc; ++start) {
    if (lst(start) == n[0]) {
      dp[1][start + maxc][1] = 0;
    }
  }
  /// cerr << "start done" << endl;
  for (int i = 1; i < l; ++i) {
    for (int c = -maxc; c <= maxc; ++c) {
      for (int d = -1; d <= 1; ++d) {
        dp[(i + 1) % 2][c + maxc][d + 1] = INF;
      }
    }
    for (int c = -(l - i) * 5 - 10; c <= (l - i) * 5 + 10; ++c) {
      for (int delta = -1; delta <= 1; ++delta) {
        int val = dp[i % 2][c + maxc][delta + 1];
        if (val == INF) continue;
        int carry = rest9(c) + delta;
        int rem = lst(n[i] - carry);
        int start = rest(c - rem) * 10 + rem;
        for (int c1 = start; c1 <= start + 10; c1 += 10) {
          int val1 = val + i * abs(c - c1);
          int carry1 = rest(carry + c1);
          int delta1 = carry1 - rest9(c1);
          assert(abs(delta1) < 2);
          /// cerr << delta1 << endl;
          dp[(i + 1) % 2][maxc + c1][1 + delta1] = min(dp[(i + 1) % 2][maxc + c1][1 + delta1], val1);
        } 
      }
    }
  }
  int ans = INF;
  for (int i = -maxc; i <= maxc; ++i) {
    for (int delta = -1; delta <= 1; ++delta) {
      int carry = rest9(i) + delta;
      if (carry == 0) {
        ans = min(ans, dp[l % 2][i + maxc][1 + delta]);
      }
    }
  }
  cout << ans << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  string n;
  for (int i = 0; i < 5000; ++i) {
    n.push_back('0' + (rand() % 10));
  }
  solve(n);



  /// string n;
  while (cin >> n) {
    solve(n);
  }

  
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1054ms
memory: 5068kb

input:

12
100
998244353

output:

30950846
3
5
76

result:

wrong answer 1st lines differ - expected: '3', found: '30950846'