QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#556634 | #2835. Number Theory | ucup-team1198# | WA | 40ms | 3576kb | C++20 | 2.7kb | 2024-09-10 19:49:53 | 2024-09-10 19:49:56 |
Judging History
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: 100
Accepted
time: 0ms
memory: 3572kb
input:
12 100 998244353
output:
3 5 76
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 40ms
memory: 3576kb
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:
29 36 28 27 35 36 22 30 32 22 33 15 20 30 28 32 19 29 40 22 34 34 30 26 30 35 24 23 42 18 26 28 31 14 22 22 33 22 43 30 21 23 42 19 30 33 43 30 21 18 34 36 21 18 19 34 6 30 35 42 14 27 36 32 23 24 30 35 28 22 32 27 41 39 26 37 30 28 39 35 22 24 32 44 34 36 35 42 22 22 31 35 25 32 32 15 17 33 38 31 2...
result:
wrong answer 42nd lines differ - expected: '24', found: '23'