CT39946

The Frugal Pairs at Tuskmore

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the boar woods of Tuskmore with crates of scrolls, and Rowena the assayer 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 <= 3585; 0 <= a[i],k <= 1000000000.

Example 1:

Input: 3084 1281609273 584644979 416944222 20777687 79759870 632668197 141403283 326548230 496989659 713783096 2476652 723629189 163494368 291544217 243149417 739236040 822791066 460244710 400277140 958925746 111680252 58836892 508404795 413839934 499450911 616986077 762675713 870217574 250223431 727912089 681696230 710691957 745373294 898989781 150893207 688849802 630445380 690130122 301036898 810246908 269292311 979760900 188201802 506489260 12872263 294835782 649595737 257396971 243040402 929983926 461398046 620204590 516056273 883261384 219421441 607648902 526254989 166338696 331302150 142625936 819857813 548971891 895597973 582478794 448669814 227251701 624599701 875922767 930615511 52971893 973353856 388007097 956457356 839254977 625706955 7164196 514202226 262623078 787834355 934491083 189…
Output: 3524543

Example 2:

Input: 1603 1069050323 539530620 194910478 291504186 373444796 404656985 572776156 642680526 978274285 736119295 556479859 818757857 168717796 640140159 170634682 740988778 172824189 49027800 26810815 693242163 308289432 158943390 407771651 299920710 703670223 64464474 843866102 307121266 818659546 752112892 665504207 545707675 747033129 534579548 142776033 303847522 796624300 163655799 707515602 7000301 928585698 17568301 679585443 396831767 372266060 33980737 649053026 219224004 620703308 874160009 25526171 345552097 624366799 954113081 368944165 549465826 666134406 288210799 704375980 367864443 541403493 63780758 363787668 14568501 876136339 311318929 780980580 124390414 517933870 108940055 68109555 167547916 156331119 246932390 186320433 596131125 176647416 186846045 105465055 753201250 85176…
Output: 754790

Example 3:

Input: 2708 1914436141 108682915 682781343 69919659 970483225 752527270 358243529 170444739 656598046 170196348 542415171 141356059 422714493 794194451 336762256 745749205 490321896 67048565 759544165 916000902 552698379 262136497 60513867 664040184 80501934 150928796 523068288 459043726 238245329 649382956 715969789 486525932 196980694 130975978 407777717 707961689 447948206 681064553 187643734 210660479 220449709 413810688 389883493 783688360 430493447 306297088 770507315 889824002 578988150 748693217 191921767 684841751 76788743 723459779 161849129 343794777 103194230 433412132 961645342 798577884 77105805 656805792 322100151 269114532 656339331 556992033 600795833 336989667 80781992 208510210 662056909 702272955 715157195 341288068 216687498 817951636 868580979 434130871 332335819 571135653 2…
Output: 3651326

Constraints:

2 <= n <= 3585; 0 <= a[i],k <= 1000000000.

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