codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2161C.md (3721B)


      1 Source: https://codeforces.com/problemset/problem/2161/C
      2 
      3 C. Loyalty
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 No Loyalty No Royalty (c)
     22 
     23 You are a customer in a store and want to buy $n$ items. Each item $i$ has a price $a_i$ such that $1 \leq a_i \leq X$, where $X$ is a loyalty factor.
     24 
     25 Your loyalty level in the store is defined as $\lfloor {S \over X} \rfloor$, where $S$ is the total cost of items purchased so far. Initially, $S = 0$.
     26 
     27 If you buy an item with price $p$ and your loyalty level increases as a result of this purchase, you earn $p$ bonus points.
     28 
     29 Your task is to find the maximum number of bonus points you can earn by choosing an optimal order of purchase for the items.
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2 \cdot 10^4$). The description of the test cases follows.
     34 
     35 The first line of each test case contains two integers $n$ ($1 \leq n \leq 10^5$) and $X$ ($1 \leq X \leq 10^9$) — the number of items and the loyalty factor.
     36 
     37 The second line of each test case contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \leq a_i \leq X$) — the prices of the items.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     40 
     41 Output
     42 
     43 For each test case, output two lines.
     44 
     45 The first line should contain a single integer — the maximum number of bonus points that can be earned.
     46 
     47 The second line should contain $n$ integers — the prices of the items in an order of purchase that maximizes the number of bonus points.
     48 
     49 If there are several orders that maximize the number of bonus points, you can output any of them.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 7
     57 
     58 10 2
     59 
     60 1 2 1 2 1 2 1 2 1 2
     61 
     62 5 10
     63 
     64 2 2 2 2 5
     65 
     66 11 23
     67 
     68 5 5 22 1 21 2 10 3 1 1 2
     69 
     70 1 1
     71 
     72 1
     73 
     74 1 17
     75 
     76 11
     77 
     78 3 100
     79 
     80 44 32 1
     81 
     82 16 100500
     83 
     84 42801 73112 95296 68791 42217 21871 29316 84405 24273 42894 63370 53473 57156 61369 80 27290
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 12
     91 1 2 2 2 2 2 1 1 1 1
     92 5
     93 2 2 2 2 5
     94 53
     95 1 1 5 2 1 2 5 3 10 21 22
     96 1
     97 1
     98 0
     99 11
    100 0
    101 44 32 1
    102 503499
    103 53473 42894 80 57156 42801 61369 42217 63370 29316 68791 27290 73112 24273 84405 21871 95296
    104 ```
    105 
    106 Note
    107 
    108 In the first test case:
    109 
    110 1. After buying the first item $S = 1$, loyalty level is 0;
    111 2. After buying the second item $S = 3$, this increases loyalty level to $1$ and earns $2$ bonus points;
    112 3. After buying the third item $S = 5$, this increases loyalty level to $2$ and earns $2$ bonus points;
    113 4. After buying the fourth item $S = 7$, this increases loyalty level to $3$ and earns $2$ bonus points;
    114 5. After buying the fifth item $S = 9$, this increases loyalty level to $4$ and earns $2$ bonus points;
    115 6. After buying the sixth item $S = 11$, this increases loyalty level to $5$ and earns $2$ bonus points;
    116 7. After buying the seventh item $S = 12$, this increases loyalty level to $6$ and earns $1$ bonus point;
    117 8. After buying the eighth item $S = 13$;
    118 9. After buying the ninth item $S = 14$, this increases loyalty level to $7$ and earns $1$ bonus point;
    119 10. After buying the tenth item $S = 15$.
    120 
    121 Overall we got $12$ bonus points.
    122 
    123 In the second test case:
    124 
    125 1. After buying the first four items $S = 8$, loyalty level is 0;
    126 2. After buying the last item $S = 13$, this increases loyalty level to $1$ and earns $5$ bonus points.
    127 
    128 In the third test case:
    129 
    130 1. After buying the first eight items $S = 20$, loyalty level is 0;
    131 2. After buying the ninth item $S = 30$, this increases loyalty level to $1$ and earns $10$ bonus points;
    132 3. After buying the tenth item $S = 51$, this increases loyalty level to $2$ and earns $21$ bonus points;
    133 4. After buying the eleventh item $S = 73$, this increases loyalty level to $3$ and earns $22$ bonus points.