CT45017

The Frugal Pairs of Verdigris

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the copper works of Verdigris with crates of panels, and Morgana the measurer must account for every last one. 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 <= 3861; 0 <= a[i],k <= 1000000.

Example 1:

Input: 3504 778206 930678 930312 323441 915930 114769 244274 707044 16251 149329 402464 409125 866416 557468 698007 141649 795862 776512 381479 727401 120088 638916 215959 857480 553896 885965 425570 554943 643920 267482 54858 626743 78439 618374 647255 789307 614871 27884 80117 477076 860887 428115 328467 334312 915310 799117 257461 348476 780882 152934 966335 202115 781103 964141 486813 757618 287220 71630 206482 212221 30068 917913 441809 5150 136222 841650 138341 956464 914315 842229 927658 615298 769366 567874 909965 384626 398672 72089 248923 465098 616213 781685 240426 380864 292350 198887 732542 34180 783927 69726 126250 747885 847231 243617 501329 712614 636419 713990 416020 271852 901331 721427 627242 347764 588036 362893 655667 212613 629482 463256 846523 874589 232178 145556 983257 83…
Output: 1822136

Example 2:

Input: 2787 1369028 581478 57766 595844 81969 516990 658912 856368 98308 390685 613453 262529 463991 465560 168299 612953 705269 915577 793414 284385 97273 317621 45157 597202 610120 417561 700416 666247 35662 160114 30847 149749 316946 24063 242802 145401 281696 535644 107151 949004 563651 799253 240669 908892 95770 816533 183455 645884 377129 831327 414573 810933 112256 902578 857199 600081 71051 459539 228832 935784 933598 866521 249108 681880 20635 427579 714930 425419 192106 143380 507691 421899 888774 797533 881853 94131 409381 27850 59507 279196 29209 348005 987973 834683 789557 392614 758938 472276 191799 658198 11355 342600 197516 670103 819290 40506 454260 632742 103074 591986 533468 187935 192578 684537 834234 689889 909516 355116 698099 975488 183118 150653 999648 482195 700063 298510…
Output: 3078902

Example 3:

Input: 3528 1663169 314958 652418 81496 127240 989663 257609 106214 905506 387750 436788 975985 946867 581741 319341 120472 368302 845177 897210 829785 443760 250911 289089 687107 406566 485907 945421 124386 375970 187012 849186 518335 228417 181430 788070 839365 480683 994745 37808 289426 138439 401080 594731 281559 888009 596388 397646 707589 12742 862370 423074 133029 105268 25544 910806 984190 863108 750896 604846 32989 175441 675076 90756 923647 254444 445603 761169 534335 461829 251860 247042 300582 119879 222195 71075 426913 601694 640713 79712 276918 657899 132502 462725 705928 308771 362601 924161 455844 346297 719775 402991 404868 13335 410012 330958 249911 446936 930106 176836 272170 700808 687962 910056 568413 579809 42729 50425 982162 469087 160056 613189 502440 59744 381424 162953 2…
Output: 5864005

Constraints:

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

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