CT52009

The Brass shelves of Petr

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Petr inherited the chandlery at the monsoon port of Rainhaven along with its curious bookkeeping system for shelves. Time to make sense of it. Task: Print the number of inversions: index pairs (i,j) with i<j but a[i] > a[j]. Input format: First line: n. Second line: n integers. Output format: Print the inversion count (fits 64-bit). Constraints: 1 <= n <= 3197; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 3105 955533723 281605212 919194407 79735735 130435221 229250287 553554688 203610596 55956799 217309656 675676833 13657729 351134860 943151240 758629647 964941845 185856031 217291327 851493670 744002846 743702540 480568090 236539779 818963309 58424359 683045626 954203687 546459449 238537111 307944918 50643242 461265371 58311602 459975144 274332433 220592362 244162366 677632442 476935875 363803838 390356390 81787356 746773139 524188217 231943585 370483063 946836495 681903280 784123076 362295159 466527441 811274391 46942258 607429447 896708234 316159808 994282792 198102280 515579612 672647157 35286962 316965641 632118500 494782742 354283258 630078773 358414539 795088053 846209185 230140646 280685550 33536545 387858443 58734698 457264423 79390187 653149749 271183116 880084680 895096241 7149827…
Output: 2389507

Example 2:

Input: 176 100 155 95 30 82 115 142 81 93 80 79 74 84 35 112 63 45 156 22 144 113 17 24 40 71 56 167 123 170 147 51 166 39 172 154 159 68 32 134 85 114 105 16 169 148 26 60 173 129 52 9 66 143 165 160 133 108 110 99 163 149 111 10 13 126 137 57 124 128 94 90 49 2 107 168 42 33 131 41 43 117 135 138 76 37 141 136 23 36 14 6 38 109 162 161 50 103 73 65 164 31 34 1 20 92 19 58 67 62 175 152 89 145 171 27 3 21 116 83 69 101 5 130 97 125 77 122 120 104 8 28 121 48 29 0 91 70 119 7 72 139 146 53 153 15 47 78 59 174 106 61 86 88 140 150 4 75 54 46 118 132 18 151 157 64 96 12 102 44 127 158 55 11 87 98 25
Output: 8298

Example 3:

Input: 2045 849098275 500755147 516047999 422372395 562125453 121916323 269932241 562298596 915676561 143252648 695670893 535906463 595740777 937048607 953541231 95499501 144514387 588026041 404102242 973929106 38843010 749012685 184276426 342961624 537791533 543721030 269591576 643811154 846268458 301361750 732626801 349434239 165836811 635019536 675133642 992629924 910695375 578126785 893869571 50556660 828422167 383771626 515933832 341835114 928570498 511762418 239488488 285569390 712983359 902020568 320254017 100407978 687848389 334747901 966840396 319978334 863947644 895896064 844692821 807417183 125770716 67260599 702382515 579621459 735017089 858601937 852865379 737447996 46956414 892592931 779020548 310031882 893953761 637110936 179627847 184536437 117114757 908319012 393815498 257476500 …
Output: 1057129

Constraints:

1 <= n <= 3197; -1000000 <= a[i],x <= 1000000000.

Loading...
Test Cases:No test cases
No test cases available.
The Brass shelves of Petr - MEDIUM Coding Problem | CodeTikki