CT53456

The Leatherwick Frugal Pairs

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the tannery row of Leatherwick, someone must schedule the next expedition. This year the task falls to Tanya, armed only with the ribbons register. 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 <= 3378; 0 <= a[i],k <= 1000000.

Example 1:

Input: 2392 1220564 735836 994042 679928 44530 209305 239705 22278 950730 172918 992289 766121 450956 405406 406226 451363 738831 124245 14614 854592 495472 530244 169288 314440 274119 546864 634776 4272 340737 960793 816008 191485 203606 312344 624481 579383 402674 652208 635271 310904 306660 77916 353748 240101 757513 482 645974 917590 275216 474492 756484 414119 228396 448622 884791 298162 797850 486440 373602 928381 179656 853686 219578 732684 102493 773526 602256 897167 169798 109358 865603 386622 48229 99433 28066 335906 833248 379255 391111 661110 700725 421488 54345 372916 243762 111833 390513 630622 273517 946412 4416 69959 281288 441855 370424 567578 769275 181517 472214 26751 537094 974015 512515 558328 196680 712478 314463 441392 193272 489845 650428 118458 551926 779917 641477 240426…
Output: 1965763

Example 2:

Input: 8 244660 65483 536582 964491 308358 352013 70915 82544 563908
Output: 3

Example 3:

Input: 2552 1038162 226061 587538 573097 438813 273199 195517 868936 55299 989573 602437 96941 269482 297121 644936 604306 182980 874575 811650 647009 519596 905359 648530 16206 10172 402543 581799 107138 91792 506367 798381 316854 50058 199281 855436 456002 205826 43978 750633 28070 761292 647331 113913 649827 396920 560351 255520 184417 147805 892008 109768 257962 872459 212209 136006 972435 106531 187729 982577 489273 771822 5609 8000 167250 572461 316357 18814 27298 856569 254748 139327 784085 582994 29027 3656 385172 19344 592956 637804 698697 386890 215395 906398 104632 689244 113744 515939 608868 911261 460185 889173 790859 688124 146193 732120 868085 237301 332107 969121 861048 363205 715917 36334 264232 934085 666186 540413 200138 823678 375633 308023 485650 770655 926331 552038 639437 2…
Output: 1736254

Constraints:

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

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