...the(n) Masha...

I don't understand what dp has to do with this problem. I solved it using string hashing.

#include <stdio.h>
int main(void) {
    int a, b, c, max, min, med;
    scanf("%d %d %d", &a, &b, &c);
    max = a >= b && a >= c? a: b >= a && b >= c? b: c;
    min = a <= b && a <= c? a: b <= a && b <= c? b: c;
    med = a + b + c - min - max;
    if (med == 0)
        printf("%d", - max);
    else
        printf("%d", min - max * med);
    return 0;
}

I solved the problem the way I understood it but then when staring at the discussion page I discovered that buying the same tap twice is allowed.

Binary search the optimal value when only latin and spaces. You don't have to iterate through all m. Calculate transition for n in O(1) time. Overall complexity should be something like O(|s|log(m)).

If your code needs to calculate 10^i, then don't use BINPOW. Just precalculate. It wasted my time a little bit.

The solution is actually really easy when not dp. It is just the count of numbers that are divisible by (1ll<<i) and only by (1ll<<i) times 2(i-1). If you just draw 1-15 tree and try to solve for 1 15 you'll observe it. You just have to make these checks (i'm too lazy to explain it, but if you want just comment):

    for (int i = 30; i >= 1; i--) {
        int powerOf2 = 1ll << i;
        int ci = countMultiples(n, m, powerOf2);
        ci -= al;
        int r = m / powerOf2;
        int l = n / powerOf2;
        an += 2 * (i - 1) * ci;

        if (m % powerOf2 == 0 && (r % 2 != 0 || r == 0) && ci > 0) {// <-- These are the checks
            an -= (i - 1);
        }
        if (n % powerOf2 == 0 && (l % 2 != 0 || l == 0) && ci > 0) {
            an -= (i - 1);
        }
        al += ci;
    }

thx~

Hello, could you check if my test is correct?
4
10
1234
Answer: 222 (??)
~Thanks

Maybe someone will need it.
You can read more about it here: https://en.wikipedia.org/wiki/Arithmetic_progression


#include <iostream>

using namespace std;
int main()
{
    int a;
    cin >> a;
    int result = a > 0 ? a * (a + 1) / 2 : - a * (a - 1) / 2 + 1;
    cout << result;
}

Edited by author 03.07.2024 16:31

Edited by author 03.07.2024 16:31

I had WA#7 and it was passed (and problem become accepted) when I fixed the case where the Y-cord of one of points was equal to B + C. So test 7 is something like that:

A B C
X1 B + C
X2 Y2

Good luck!

"covers segment [0, M] completely" means:

0 1
2 3
does not cover [0,3] completely

0 1
1 3
covers [0,3] completely

Hello! I found test, that crash some AC solutions (solution of my friend with self-created GCD func), please, add it to the system. Here it is:
995
805 447 327 900 484 349 760 548 525 419 613 338 81 374 242 744 813 906 965 120 983 420 720 459 477 218 444 527 209 598 758 929 635 740 312 128 318 162 390 244 297 424 283 931 794 239 211 480 880 768 245 554 276 615 543 549 202 203 98 380 681 57 648 119 646 134 691 551 727 777 452 745 164 345 989 680 261 20 132 404 44 850 624 360 288 970 708 847 396 837 405 31 756 243 90 762 686 793 236 284 496 144 634 889 476 293 887 589 914 301 145 427 359 819 246 810 967 12 885 913 351 657 339 95 875 882 715 709 352 280 214 5 309 884 463 988 521 552 733 271 385 40 667 35 905 198 451 607 46 479 636 232 18 911 488 121 147 651 146 112 544 343 36 873 279 684 233 166 771 815 212 537 639 158 953 577 649 513 719 556 443 174 832 199 425 937 623 743 725 248 21 422 796 858 1 603 326 39 303 313 559 415 241 55 516 892 854 933 465 498 391 663 482 378 511 948 193 362 647 186 275 481 738 703 487 578 226 739 41 958 564 759 331 611 175 806 23 987 438 347 807 9 210 896 510 76 800 776 532 786 764 573 85 747 653 750 859 876 138 723 462 32 161 389 219 658 625 93 266 60 928 220 507 529 118 512 171 311 446 868 306 904 106 133 985 435 774 377 116 114 583 601 560 332 322 329 871 493 500 877 614 637 204 140 61 401 666 470 961 376 898 817 626 72 24 910 42 59 328 113 205 978 80 70 491 612 670 272 888 256 73 787 917 492 254 748 943 28 384 361 671 433 981 172 710 818 992 620 66 178 821 952 802 382 659 167 94 565 769 440 53 822 675 669 641 475 947 909 643 829 49 872 763 503 672 782 976 553 935 461 991 92 130 449 631 428 124 599 897 531 597 761 489 594 687 661 587 835 182 705 250 772 56 927 129 346 17 54 185 356 984 951 883 627 955 157 103 702 191 110 580 78 299 370 292 969 963 335 924 765 47 595 545 785 200 386 907 893 62 464 505 381 184 542 668 579 920 698 962 409 442 348 833 25 936 137 844 395 437 825 799 387 795 456 714 295 530 34 305 954 315 16 277 515 366 371 838 188 860 173 519 262 867 426 941 125 732 270 101 617 593 432 843 973 269 363 14 851 524 45 827 533 13 534 690 136 673 811 735 187 797 798 441 754 731 729 344 539 726 454 694 581 664 294 895 692 135 652 986 674 592 890 308 107 317 809 849 142 159 605 632 207 571 995 610 320 773 660 170 206 495 939 310 916 642 208 190 238 304 716 153 111 990 300 86 736 728 604 957 325 375 741 752 253 455 925 156 65 96 154 434 10 88 69 676 421 730 570 410 563 469 679 431 790 879 406 82 228 259 394 894 921 801 285 816 268 485 650 820 473 354 117 602 804 38 257 258 403 591 466 251 630 724 629 538 908 169 429 337 923 408 148 350 213 37 430 557 956 575 852 766 67 857 566 87 711 502 585 574 919 751 355 367 89 814 74 222 853 7 792 413 183 379 982 706 152 215 689 506 783 388 940 975 402 249 194 163 216 445 368 959 201 721 775 781 383 942 417 974 478 586 572 753 139 831 29 812 321 468 682 993 15 160 697 866 127 217 50 784 520 704 104 141 460 296 179 622 109 934 234 874 535 972 177 75 195 63 621 83 8 665 523 393 105 886 192 494 71 265 541 274 26 414 6 365 224 555 342 590 229 688 472 683 373 915 562 526 576 901 865 416 903 264 79 830 712 102 742 755 749 713 358 247 608 846 252 791 932 227 701 43 504 314 938 960 596 100 618 779 778 324 902 471 662 971 600 411 678 341 467 397 568 645 696 307 330 457 699 518 436 22 528 968 319 789 746 638 273 77 718 569 155 281 286 289 770 695 509 30 864 353 340 400 845 52 27 91 717 115 823 99 980 260 196 862 230 508 223 964 423 486 302 788 656 945 584 946 176 540 977 950 97 757 926 399 826 150 606 298 392 357 458 930 808 550 19 840 448 824 722 235 499 255 64 836 734 644 567 189 856 561 677 197 912 842 685 267 439 522 398 372 278 944 878 333 588 3 168 891 33 151 181 737 994 616 48 231 558 828 949 640 237 453 707 143 514 474 582 282 240 418 336 654 149 58 693 628 483 780 863 369 655 848 546 497 131 180 123 841 700 490 126 287 323 547 839 412 68 855 108 861 221 803 51 619 450 517 767 2 899 979 263 922 122 290 84 918 316 11 165 4 407 334 633 881 869 225 364 501 870 609 536 291 834 966

Edited by author 20.06.2024 13:49

1 1 1 1

Dear administrators, could you please fix one little typo?
"of his big family", not "if his big family"

Same program getting WA1 with G++ and AC with MVC++. Idk why. I use linear DP, i print answer with cstdio.

i kinda changed the variables
a = the first sum suggested by petr
b = the ---------------------- taxi driver
c = amount added by petr everytime
d = ---------------- taxi driver
we can say that at step n of bargaining:
petr -> a + n*c
taxi -> b - n*d

where looking for a time when petr's suggestion is less than the drivers
which means a + nc <= c - n*d
but there sometime when petr suggest more than what the driver suggest the previous time.
that's why i am comparing between the last petr's suggestion and the previous one of the driver a+c*n > b-d*(n-1). in this case petr says ok to the taxi driver and do not suggest more than that.


void solve() {
    int a, c, b, d;
    cin >> a >> c >> b >> d;
    if (a >= b) {
        cout << a;
        return;
    }
    int n = (b-a)/(c+d);
    if ((b-1)%(c+d)!=0) n++;
    if (a+c*n > b-d*(n-1)) {
        cout << b - d*(n-1) << ln;
    }
    else {
        cout << a + n*c << ln;
    }
}


Edited by author 10.09.2022 21:11

We need version 2 of this problem, where cart can be used in more than one tunnel

string s = "";
int c;
while ((c = getchar()) != EOF)
    s.push_back((char)c);

Correct read input C++

я выбрал корнем вершину 1 и запускал в int main() дфс от этой вершины. Прошло 24 теста и упало на 25, но затем я запустился от всех вершин с условием if(!used[i]) dfs(i) и прошло. я не понял почему..