QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#556629#2835. Number Theoryucup-team1198#RE 0ms3660kbC++202.7kb2024-09-10 19:47:162024-09-10 19:47:17

Judging History

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

  • [2024-09-10 19:47:17]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3660kb
  • [2024-09-10 19:47:16]
  • 提交

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 = 6 * l + 10;
  /// 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 = -maxc; c <= maxc; ++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);
          /// cerr << delta1 << endl;
          if (abs(delta1) < 2) {
            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: 100
Accepted
time: 0ms
memory: 3660kb

input:

12
100
998244353

output:

3
5
76

result:

ok 3 lines

Test #2:

score: -100
Runtime Error

input:

4296
5370
8014
9532
6311
4070
2541
4782
5630
1487
2916
454
2020
5650
1851
5885
3556
6533
5044
1780
5746
5605
7860
4416
4495
8081
2416
3534
6045
3348
4536
8725
3505
1074
1531
937
7954
4451
7052
9586
3468
2679
6085
9908
3630
8046
6282
2883
9021
1436
5201
8166
8986
2167
7780
4156
101
3753
5732
5173
118...

output:


result: