QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#556636 | #2835. Number Theory | ucup-team1198# | WA | 1054ms | 5068kb | C++20 | 2.7kb | 2024-09-10 19:50:49 | 2024-09-10 19:50:49 |
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: 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'