CT38047

The Whitestone Frugal Pairs

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the alabaster quarry of Whitestone, Emir records each stretches in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2935; 0 <= a[i],k <= 1000000.

Example 1:

Input: 1066 1267781 236195 675583 979457 851001 202647 666080 332933 730992 617933 457162 180831 856422 541003 493258 6158 67852 437927 753551 192445 537361 576129 140731 622225 557050 876444 265061 850046 678378 427170 148278 119651 416273 647104 103412 287745 123723 27844 716409 752873 418934 760621 625321 873572 637270 522070 208723 676907 687633 116865 112423 699889 547449 95503 514429 445975 701138 677968 973585 873722 685374 427688 623672 615218 304221 625921 587559 362462 793711 302433 912508 878573 78432 453394 444788 635706 816106 940444 460844 705117 818746 474059 518814 253112 291184 501430 575651 53430 449478 767573 845674 94299 861393 814959 495565 774095 262271 142046 218427 809281 956379 204393 361947 423903 982451 738290 71812 816427 203059 860013 268188 446217 232129 681949 79171…
Output: 414795

Example 2:

Input: 1327 1227911 761964 7196 553730 434714 654657 530364 692940 679025 338572 163472 393762 144310 673923 222081 28589 45146 584892 607824 461596 816812 111652 255054 466481 897087 89920 626401 195735 152661 909712 199385 14351 622846 210552 458034 791847 828666 885470 780515 7123 105249 999567 649666 414707 267130 384510 554160 284540 583526 28746 527180 57240 293470 16426 673626 312951 550277 907659 714787 190243 426474 352673 558725 254517 405522 75130 116094 462271 182681 313978 344886 679071 581984 700556 580607 266880 79178 342192 555097 960376 797683 461069 543021 3933 686167 888969 845253 192425 567611 870929 161550 645637 379752 632510 893197 682927 973500 112680 277837 202222 168722 37424 512357 88804 719390 249474 395473 95948 319341 242508 867048 952156 115164 108082 742455 179313 …
Output: 639207

Example 3:

Input: 792 575759 495235 719182 83553 773121 860525 364058 931231 782714 648 677194 359748 464245 33410 458235 97867 529097 319590 569086 408628 325777 798655 518233 528158 981601 876900 344947 583944 259297 347112 451360 954175 112633 625848 654804 724222 451582 375480 599624 652929 583277 691800 428632 822013 406741 224510 195259 285525 183791 948814 520396 846571 879007 884054 319138 497625 66889 54876 45358 651132 754292 956161 758951 144142 28435 775814 988584 987309 345342 809492 941196 631284 890441 179872 967786 483779 182544 19415 511056 947012 675974 779579 169846 975009 407990 824127 272445 127222 662199 20151 187529 864363 122346 976762 556684 93153 574316 1355 951830 815383 250570 13844 929107 162140 167832 355164 162350 957766 989690 606549 621524 938154 821445 155655 276271 594761 …
Output: 50466

Constraints:

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

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