QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #231878 | #6440. Xingqiu's Joke | zGoofy# | AC ✓ | 1235ms | 3768kb | C++14 | 980b | 2023-10-29 17:31:22 | 2023-10-29 17:31:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void solve() {
int a, b;
cin >> a >> b;
map<pair<int, int>, int>mp;
vector<int>cnt;
if (a > b) {
swap(a, b);
}
int t = b - a;
for (int i = 2; i <= t; i++) {
if (t % i == 0) {
cnt.push_back(i);
while (t % i == 0) {
t /= i;
}
}
}
if (t != 1) {
cnt.push_back(t);
}
function<int(int, int)>dfs = [&] (int a, int t) {
if(t == 1) return a - 1;
if(a == 1) return 0;
if(mp[{a, t}]) return mp[{a, t}];
int res = a - 1;
for(auto i : cnt) {
if(t % i == 0) {
res = min({dfs(a / i, t / i) + a % i + 1, dfs(a / i + 1, t / i ) + i - (a % i) + 1, res});
}
}
mp[{a, t}] = res;
return res;
};
cout << dfs(a, b - a) << endl;
return;
}
signed main() {
ios::sync_with_stdio(false);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
5 4 7 9 8 32 84 11 35 2 1
output:
2 7 5 4 0
result:
ok 5 number(s): "2 7 5 4 0"
Test #2:
score: 0
Accepted
time: 350ms
memory: 3696kb
input:
300 223528529 446621399 755625805 978718675 257717538 480810408 277875777 54782907 963091558 739998688 282469431 505562301 38752451 261845321 474429597 697522467 67026335 290119205 874629705 651536835 301964126 78871256 316864911 93772041 545942587 322849717 640801578 417708708 683070559 906163429 9...
output:
12 19 15 17 16 17 13 19 15 17 15 15 18 17 17 19 14 18 15 16 17 18 19 15 17 17 17 12 19 16 12 19 16 15 13 18 17 18 16 15 14 17 14 16 15 14 19 18 16 14 16 17 16 18 14 16 17 14 18 17 16 19 19 18 17 16 16 14 23 14 14 18 18 20 16 16 17 17 12 18 19 17 16 18 16 15 18 12 15 18 16 12 19 18 15 18 17 14 13 16 ...
result:
ok 300 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 3612kb
input:
300 636099362 669653794 640628976 607074544 492031079 458476647 420324662 386770230 234845232 201290800 416098756 382544324 513320531 546874963 245050186 278604618 688926901 722481333 458533405 424978973 863331691 896886123 638892374 672446806 849746534 816192102 761591596 728037164 369934525 403488...
output:
51 49 48 45 35 45 50 42 53 47 61 53 59 55 43 41 53 55 44 62 48 39 36 60 40 55 49 54 50 38 59 41 39 43 47 57 54 50 52 39 54 52 39 37 32 34 56 38 53 41 51 50 55 56 35 44 35 45 59 33 53 59 56 57 43 53 54 45 34 58 33 55 56 33 46 49 33 38 38 55 54 47 56 47 52 60 36 53 56 53 44 43 34 59 55 49 52 40 35 55 ...
result:
ok 300 numbers
Test #4:
score: 0
Accepted
time: 271ms
memory: 3640kb
input:
300 867787179 877654074 403881553 407432589 201172453 192754452 822066929 815320907 516801596 518734008 278735158 276997924 39842929 46406996 229923235 222281597 958111516 962220928 514454467 511546909 66273896 56535006 603599579 602886043 99119397 89783150 606236932 603774684 948362977 945928285 92...
output:
33397 48909 859594 170 484 187 9768 1359 33428 10364 18 1664 2186 277 1043 2411 227 174111 60 367 572 540712 863 122 222 2212 1989 320715 1651 209 100 122 12752 245 213 297173 1028 1390798 858 77 6974 1773 83 197 16962 56842 310 452 70 1626 64838 160 1805 1556 1166 247 19389 6519 589 14465 157 244 2...
result:
ok 300 numbers
Test #5:
score: 0
Accepted
time: 364ms
memory: 3568kb
input:
300 444931791 453867214 642779735 650889499 768469200 759932977 134609333 127541032 543262545 533662538 588655171 585712884 757077977 751113265 161317175 158154061 892529978 885427686 795149579 788861982 241771671 251274046 302494348 311533914 889928290 899661013 920557338 930025416 203697226 200533...
output:
741 160 209219 311632 9495 197970 166 146 583369 2912482 363 749 119 7218 119212 2918 55779 545 46 377 763 37357 10528 3053 372686 5498 2710 1815 9471 1681 23722 3121 198441 179 184540 78019 62009 9912 816 162 1149 5903 723881 157 1198 17554 176 2222 245003 137138 7745 119 52478 4287 20434 3985 72 1...
result:
ok 300 numbers
Test #6:
score: 0
Accepted
time: 284ms
memory: 3616kb
input:
300 815736190 821647539 717319350 721891990 679088597 681494998 289436765 281383905 346742284 353165330 345091279 339262087 225500907 221657013 929824953 932291419 902707251 900613118 290094789 283209001 984907015 988781551 480809075 475536306 538994292 545389379 184484298 194275007 200905296 204085...
output:
447 842 385 227 7356 4687 3832 413 1863 1817 11006 6637 1807068 476 512 1410 4656 169 574810 1418 321 4623 801 292 664 2030320 2758 674376 1115 786 1413 263 229 880 2236 124680 469 739 624 34515 525 474 480 379286 349429 115 649 280 110 2454 554 164 4109 7077 4658 380 3005 26132 61563 411 126 268 20...
result:
ok 300 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
300 393 250 621 915 69 447 419 360 875 659 639 80 666 663 620 486 968 997 30 385 384 987 597 149 722 151 764 27 443 905 545 133 881 312 761 875 852 346 702 80 560 59 285 300 1 638 978 665 567 713 439 957 20 1000 917 197 790 306 890 919 149 72 380 667 696 614 437 435 268 925 768 718 289 691 40 305 82...
output:
9 8 5 12 10 8 221 22 44 6 9 9 150 7 7 31 258 11 7 40 21 20 0 41 14 7 3 7 7 40 5 15 10 218 19 19 14 8 61 6 14 8 10 10 24 5 1 28 18 13 30 22 0 7 1 3 4 2 5 3 16 22 9 39 20 3 10 9 6 6 17 7 10 8 941 43 11 9 15 92 10 5 6 4 12 24 14 6 33 16 35 9 26 6 19 200 19 106 8 3 17 25 1 116 24 42 12 7 26 5 7 11 13 3 ...
result:
ok 300 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
300 954 822 741 246 91 504 224 159 461 963 702 621 798 421 433 629 71 848 725 621 119 221 409 716 688 758 200 906 762 209 771 792 367 582 523 556 49 743 426 338 592 389 979 299 460 842 155 813 488 946 589 195 317 796 408 664 748 327 231 220 843 982 80 588 701 509 92 926 942 95 50 366 747 980 310 685...
output:
11 10 13 8 23 12 10 8 5 11 4 103 14 100 31 40 18 20 25 10 8 7 41 13 17 3 163 11 95 20 15 21 12 17 8 14 51 7 6 9 10 26 8 4 26 7 267 7 8 15 26 173 105 14 53 12 5 9 33 14 7 10 26 8 152 12 7 10 8 68 51 38 9 9 12 10 38 21 62 13 17 29 11 6 12 59 31 33 119 4 13 17 29 11 16 14 4 8 9 19 7 16 9 7 4 12 6 3 9 7...
result:
ok 300 numbers
Test #9:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
300 651 806 667 787 243 758 932 572 311 420 596 805 40 581 349 396 496 843 399 751 727 671 615 433 596 497 361 719 491 566 302 442 961 280 520 657 231 507 514 797 254 163 144 477 312 530 551 587 90 926 89 147 58 93 786 163 256 675 615 539 526 629 645 549 28 121 526 959 966 181 629 669 909 195 207 41...
output:
6 12 39 9 19 9 39 27 150 9 16 9 9 4 13 7 54 32 6 54 8 7 18 20 5 5 7 17 164 12 16 13 4 94 25 21 6 6 559 121 50 17 8 9 6 28 81 43 36 64 19 8 55 7 12 7 5 11 100 21 1 22 11 14 44 9 10 9 38 9 8 178 10 9 2 157 5 10 3 18 23 14 6 40 5 30 10 13 3 261 7 9 36 9 17 2 6 27 6 29 12 7 13 14 10 12 17 105 11 7 7 8 9...
result:
ok 300 numbers
Test #10:
score: 0
Accepted
time: 5ms
memory: 3516kb
input:
11 123 1000000000 577 1000000000 999999999 1000000000 1 1000000000 1 8 89 90 32 33 32 64 32 48 2 1 2 3
output:
122 26 999999998 0 0 88 31 5 5 0 1
result:
ok 11 numbers
Test #11:
score: 0
Accepted
time: 1235ms
memory: 3768kb
input:
300 145104214 880238614 127876087 863010487 104800898 839935298 163159502 898293902 123844183 858978583 200379134 935513534 259979849 995114249 236805749 971940149 168601371 903735771 142242124 877376524 146341274 881475674 236317497 971451897 167366468 902500868 111571114 846705514 130512743 865647...
output:
17 18 18 18 17 18 18 18 18 18 18 17 18 18 19 20 17 18 19 17 18 18 18 17 19 17 19 18 17 19 18 18 18 17 18 18 17 18 19 18 19 17 18 18 18 17 18 18 17 18 17 19 19 19 18 19 17 17 18 17 17 19 18 19 17 18 17 18 19 17 17 18 17 18 15 19 18 17 19 17 18 18 18 16 19 18 18 17 18 18 17 18 18 20 18 18 18 18 15 18 ...
result:
ok 300 numbers