CT51147

The Bright Frugal Pairs

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Emeric the reckoner watches over the poppy fields of Scarlet Plain's stores of ribbons. A careful computation stands between order and chaos. 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 <= 1950; 1 <= a[i],k <= 1000000.

Example 1:

Input: 684 1799147 420776 316475 81750 639507 453533 135760 315299 949594 31582 585118 160725 503405 26392 889329 406215 655258 444160 196135 573108 609982 695604 944710 777596 174796 858214 315779 907350 68922 389105 297859 308336 894782 344822 501759 871047 877885 558034 108477 657511 843571 389067 725470 522668 918768 211862 235520 46392 13341 547386 525578 64434 962440 192229 203656 260361 400531 720858 220861 488926 468597 596722 23385 234432 814333 190434 724136 183403 675290 380547 795489 976784 597223 674108 165348 748051 954682 690180 855830 825854 798780 257626 857313 862704 26810 255566 998374 359538 286828 596709 769807 158742 424233 319412 823990 409345 5734 337864 501826 592221 962615 645345 270408 263076 730146 88719 936095 909021 473640 833562 703427 866481 479227 371477 718847 75…
Output: 228110

Example 2:

Input: 1763 1646074 558464 484556 826298 447579 168100 263719 588371 981346 699207 418114 262453 196011 642036 140678 376088 721816 5933 104144 876516 651490 307299 958545 811033 727954 726556 28296 619768 948361 554815 308406 547719 565177 47473 979763 654006 241270 738116 390784 104998 4001 531272 244886 633352 928561 532450 703484 81391 946274 886460 33675 170605 446573 856803 937739 814259 28288 533898 790725 977706 841255 996690 104357 269413 835336 248403 716538 39419 159585 423421 71938 575331 520185 457034 789734 528017 706040 862464 391446 982368 894845 24562 811719 713870 220233 232366 846618 269926 454904 591437 437153 804132 347386 875811 539061 165694 947402 141896 379262 287666 667136 220544 274683 611577 680704 446652 59042 661954 336107 798 363149 550533 594935 464110 422253 83306…
Output: 1454845

Example 3:

Input: 796 577899 136563 903031 130903 248916 647636 539928 973599 980955 345687 309275 746868 618714 754311 990241 411174 784114 415809 82129 72778 893316 304787 228296 130552 209762 178310 558995 309506 595234 573504 502565 595590 291344 23895 70454 571652 443744 674129 904384 764372 619015 649081 950780 343269 436638 32512 781515 722323 976378 366876 960596 198849 500311 905617 852418 571976 722284 354846 357576 58986 695998 826158 995148 460424 986026 786741 860131 596589 497986 658303 596462 666942 970434 631478 324459 380484 681939 4038 569155 484297 581123 850574 100583 347076 390161 960166 616034 63491 812419 529202 878656 38132 764345 763225 971585 699099 183308 527932 294922 753278 691405 955385 641169 333939 971804 28887 268232 593441 202635 232592 567531 83607 558490 672698 215618 708…
Output: 50584

Constraints:

2 <= n <= 1950; 1 <= a[i],k <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
The Bright Frugal Pairs - MEDIUM Coding Problem | CodeTikki