QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#57987 | #3889. Balanced Breakdown | Beevo# | AC ✓ | 3ms | 3732kb | C++23 | 1.7kb | 2022-10-24 03:46:52 | 2022-10-24 03:46:55 |
Judging History
answer
#include <bits/stdc++.h>
#define el '\n'
#define ll long long
#define ld long double
#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
ll pw[20];
void pre() {
pw[0] = 1;
for (int i = 1; i < 19; i++)
pw[i] = pw[i - 1] * 10;
}
bool palindrome(string &s) {
for (int i = 0; i < s.size(); i++) {
if (s[i] != s[s.size() - i - 1])
return 0;
}
return 1;
}
string closestPalindrome(string &s) {
if (palindrome(s))
return s;
int n = s.size();
if (count(s.begin(), s.end(), '0') == n - 1 && s[0] == '1')
return max(string(n - 1, '9'), string("0"));
string t = "0";
for (int l = 0; l < n; l++) {
ll x = stoll(s) - pw[n - l - 1];
string cur = to_string(x);
for (int i = 0; i < (n + 1) / 2; i++) {
if (i > l)
cur[i] = cur[n - i - 1] = '9';
else {
if (n - i - 1 > l)
cur[n - i - 1] = cur[i];
else
cur[i] = cur[n - i - 1] = min(cur[i], cur[n - i - 1]);
}
}
if (stoll(cur) > stoll(t))
t = cur;
}
return t;
}
void testCase() {
pre();
string s;
cin >> s;
vector<string> v;
while (s != "0") {
v.push_back(closestPalindrome(s));
s = to_string(stoll(s) - stoll(v.back()));
}
cout << v.size() << el;
for (auto i: v)
cout << i << el;
}
signed main() {
Beevo
int T = 1;
// cin >> T;
while (T--)
testCase();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 3700kb
input:
1100000
output:
2 1099901 99
result:
ok
Test #2:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
1000
output:
2 999 1
result:
ok
Test #3:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
10
output:
2 9 1
result:
ok
Test #4:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
11005
output:
3 10901 101 3
result:
ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
100000000000000000
output:
2 99999999999999999 1
result:
ok
Test #6:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
21
output:
3 11 9 1
result:
ok
Test #7:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
1234567887664321
output:
3 1234567887654321 9999 1
result:
ok
Test #8:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
690231482249788720
output:
7 690231481184132096 1065555601 100001 1001 11 9 1
result:
ok
Test #9:
score: 0
Accepted
time: 2ms
memory: 3572kb
input:
319173294485481281
output:
7 319173293392371913 1093003901 104401 1001 55 9 1
result:
ok
Test #10:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
761353558778227546
output:
7 761353557755353167 1022772201 101101 1001 66 9 1
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
947179993313410328
output:
7 947179992299971749 1013333101 104401 1001 66 9 1
result:
ok
Test #12:
score: 0
Accepted
time: 2ms
memory: 3660kb
input:
171408535476134406
output:
7 171408534435804171 1040220401 108801 1001 22 9 1
result:
ok
Test #13:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
896452012199589977
output:
7 896452011110254698 1089229801 104401 1001 66 9 1
result:
ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
970894988875162603
output:
7 970894987789498079 1085555801 107701 1001 11 9 1
result:
ok
Test #15:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
200429647731477537
output:
7 200429646646924002 1084444801 107701 1001 22 9 1
result:
ok
Test #16:
score: 0
Accepted
time: 2ms
memory: 3556kb
input:
960284896260606337
output:
5 960284895598482069 662121266 2992 9 1
result:
ok
Test #17:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
999999999999999999
output:
1 999999999999999999
result:
ok
Test #18:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
1
output:
1 1
result:
ok
Test #19:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
7
output:
1 7
result:
ok
Test #20:
score: 0
Accepted
time: 2ms
memory: 3584kb
input:
487291873378192784
output:
1 487291873378192784
result:
ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
414821987097225805
output:
5 414821986689128414 408090804 6556 22 9
result:
ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
418581849637933703
output:
5 418581848848185814 789737987 9889 11 2
result:
ok
Test #23:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
607979478938276336
output:
5 607979478874979706 63288236 8338 55 1
result:
ok
Test #24:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
471913902748260172
output:
5 471913902209319174 538939835 1111 44 8
result:
ok
Test #25:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
1000003
output:
2 1000001 2
result:
ok
Test #26:
score: 0
Accepted
time: 2ms
memory: 3728kb
input:
123456788654328
output:
3 123456787654321 1000001 6
result:
ok