CT47893

The Frugal Pairs of Goldmeadow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Darian found an old ledger of scrolls in the depot attic at the trading post of Goldmeadow. 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 <= 1742; 0 <= a[i],k <= 1000000.

Example 1:

Input: 1715 1864784 478237 320737 935252 71623 946591 696176 767234 272071 302699 840816 46739 589736 811204 844232 316630 706316 854946 824254 740115 221557 370819 482418 570948 569244 106414 62119 656742 358775 732906 190032 104898 1707 571378 504167 16760 591188 533792 842722 986886 359438 633805 664498 699541 803216 116690 344252 761347 358907 69857 246601 287937 18714 134925 745470 646752 438126 964987 961255 882646 111707 33679 176071 277120 56480 28828 129507 69463 845171 554561 271449 903224 867004 904592 338240 209445 279437 434944 109597 188493 721979 423973 494689 414233 546851 362468 101411 581131 607690 682183 178100 164045 868819 986047 227827 977774 517859 690735 988416 485328 137789 545946 696081 52256 299155 209615 691163 504663 898470 558043 993516 481730 158220 915573 432219 75…
Output: 1457778

Example 2:

Input: 219 1554644 710506 49998 397788 944789 323360 238132 966720 954672 754904 623724 92089 661043 622697 904367 905323 152650 557344 428551 22055 164839 234580 514712 313467 739076 22909 187804 119891 912612 834788 302332 75231 343608 601059 548653 237478 255130 467131 510869 559734 192031 706584 239805 71067 128686 275226 90768 56910 332611 53995 903284 62399 381215 92140 91814 996968 428537 373881 530265 622780 238471 631526 179928 892660 505995 153556 516431 503584 337761 695162 375560 393523 446324 88423 55722 153305 209817 446399 542619 780867 389914 295332 145450 917467 517981 72664 866432 716991 548841 863745 618323 614369 426571 425945 110682 273372 731018 382595 657111 525666 168926 898585 101256 485869 44544 504460 288994 76792 232028 742928 958164 244124 302510 446938 259824 559550 …
Output: 22154

Example 3:

Input: 1329 654553 671046 76403 417059 742518 262957 713997 138397 87602 754590 577423 188929 53184 559204 979004 381496 186209 824144 347623 695520 14200 468771 50136 858216 518389 134567 918854 93745 83144 337803 999898 489689 922927 200716 541942 2126 965125 894659 653075 856472 292752 674271 848994 935943 37679 639328 18605 642592 872512 843296 918480 893399 364471 582579 442890 400952 386184 425637 62997 75960 663216 531536 464568 782396 981676 178918 167034 752368 976538 748933 521902 718830 571799 205029 174452 759393 664829 521833 626507 308661 769692 975994 98893 96868 357134 62878 791220 979367 973333 596942 851151 982171 473012 559767 293573 997180 254952 551340 165609 403990 512639 9122 41787 688429 533810 63953 36742 401028 902651 370454 73291 608468 874325 917608 399083 228278 76726…
Output: 173002

Constraints:

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

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