CT37470

The Polished Frugal Pairs

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Baker inherited the greenhouse at the mining town of Ironvein along with its curious bookkeeping system for ribbons. Time to make sense of it. 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 <= 2938; 1 <= a[i],k <= 1000000.

Example 1:

Input: 1301 1942535 3735 494199 289332 996897 889657 812081 643683 189380 531414 496072 303854 882756 31715 995131 453771 274916 772432 759431 446385 43379 737804 673051 121029 471434 110240 893789 409277 77110 345346 686548 610132 319613 370865 388889 449144 402677 226056 326330 429037 146057 558459 598232 490201 777705 444718 245079 232140 179668 612728 412131 407917 364366 775979 140089 666299 667339 647534 101721 311966 830039 214034 281735 621064 836485 224378 428199 733827 613415 848813 711850 564744 933269 939709 693135 283761 965867 528894 272093 897189 793914 871702 900987 377480 167331 852930 764100 163398 216963 963635 165685 308381 157587 168065 563985 718438 518168 666970 942143 619343 482917 734633 917731 551672 552514 746386 253228 852000 377664 348798 33719 772026 900480 27886 221…
Output: 844150

Example 2:

Input: 2596 1866570 630404 28616 90649 910444 946589 830989 864194 62921 565982 710074 331703 338786 906945 262193 819130 930696 434555 623541 471275 861970 974995 327439 918615 809901 897069 472611 856813 99304 787057 799592 517892 43118 23818 18310 468183 636299 373202 529680 299144 760084 58165 278489 491566 383135 103395 571184 343879 34523 324908 148675 337458 769053 335248 436250 203299 159085 119134 379745 365167 652240 241824 230143 900024 304925 799819 276920 114540 349111 616185 998733 48812 213461 387015 412626 105735 124943 991706 945826 33105 332256 757547 192026 377914 116281 359020 589194 806281 84673 648904 192250 10846 707222 76598 995256 560610 247170 854275 956993 908942 634945 615850 44005 524336 880703 36731 894540 112286 504665 844284 61261 428750 314626 91833 280517 167581 …
Output: 3338579

Example 3:

Input: 2262 1735024 263917 613468 844658 730234 428572 986087 626291 899021 377429 505050 605816 58731 536941 720912 20541 138476 314074 883335 557418 502777 457443 406304 546214 863518 425002 841485 309113 778365 200273 520815 355167 831530 931662 110673 238501 410054 975807 446296 470291 266078 393950 997464 726738 995282 840591 999308 87097 597365 124944 18594 410504 184354 389932 769097 261447 276207 586597 91313 554095 993006 379394 163736 147581 456331 422429 490805 636727 536037 984009 47404 662524 263948 272167 388654 98656 211676 805281 594327 685498 207437 865186 437995 820101 801554 795523 912619 897662 337050 720415 607368 899598 996610 547007 385459 212068 797446 425085 968948 854605 46680 341143 252285 224658 488147 487719 357979 314772 17680 727833 315769 325681 201273 112210 15924…
Output: 2459967

Constraints:

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

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