CT35919

The Tempest Frugal Pairs

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Smith found an old ledger of panels in the granary attic at the caldera rim of Firewatch. The margin notes pose a precise question. Task: Print the number of index pairs (i,j), i<j, with a[i]+a[j] <= k. Input format: First line: n and k. Second line: n integers. Output format: Print the pair count (fits 64-bit). Constraints: 2 <= n <= 3849; 0 <= a[i],k <= 1000000.

Example 1:

Input: 506 940693 579170 74506 597914 641679 235075 699012 475458 592304 260481 642136 377420 744790 537076 167331 95871 227988 59565 65789 640561 309528 185363 532646 59644 520633 591335 862231 416353 388204 142466 418678 524593 710933 577472 78619 539341 249271 84251 746808 495377 65285 89173 803165 191586 479657 514427 611726 252115 870682 615324 897827 192601 618253 779068 28129 639779 228458 181651 110872 755639 617974 402835 580031 834869 783923 864956 287674 616502 119636 381196 808155 377550 100436 151328 280075 227785 324722 453666 558289 69926 699511 945115 461188 413835 525139 379462 515779 437729 948708 200204 367218 197106 395087 428851 370676 34687 149283 408478 514771 957962 439746 392193 100440 685147 234106 484727 338094 551357 919245 988464 115468 317015 838072 503821 393704 679…
Output: 60124

Example 2:

Input: 2751 78186 310659 668516 957719 691802 674767 484384 483720 119750 904437 411136 799836 648893 430362 517952 703708 375395 985877 50205 103103 730870 310674 925850 87627 756065 842476 247317 615689 67693 430118 991934 885107 584620 293507 42872 207596 575015 4133 258808 322899 672754 319241 571729 880867 659745 512518 444035 808013 39558 100972 860069 92386 907222 262022 785092 422222 429857 521917 188625 21170 255244 944591 147145 973800 972408 222611 793369 500454 305803 659237 871748 359353 523994 715113 852358 784188 334550 577063 984339 891028 527110 456532 503885 92273 770710 241745 274380 381600 674439 45930 245945 757106 226023 91559 213883 980550 181509 726986 372579 403637 691306 443954 633552 463361 705365 153325 186456 148536 175156 508170 498158 845810 975748 253643 915798 581…
Output: 13797

Example 3:

Input: 1846 1292488 990290 880620 533040 754816 986229 674316 703127 209328 949239 743411 792281 623837 885159 341623 687522 784341 896665 470716 961005 189869 752996 584125 610434 488590 482055 134802 573816 880814 799198 959076 44470 613621 860252 840702 742013 530404 175120 144789 797644 873534 31367 346005 173441 174627 80769 715775 855692 132265 117167 158135 305476 895463 306556 219405 655594 102565 486114 815593 586377 545752 802060 851122 5514 776716 874098 876843 973080 713897 214118 884037 143901 651986 307038 486748 807302 914663 783310 254250 104402 790800 688079 169980 831227 967307 991338 248381 129083 17839 297088 616206 768696 403272 679767 330175 155323 875957 277531 25660 706148 916129 578739 244405 521132 323066 108490 380548 982516 892616 621485 266344 149950 801737 254582 649…
Output: 1245066

Constraints:

2 <= n <= 3849; 0 <= a[i],k <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.