codeforces-scrape

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

2273A.md (2268B)


      1 Source: https://codeforces.com/problemset/problem/2273/A
      2 
      3 A. Lavencia Oranges
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 René is leaving Lavencia after two long, cold years, with $n$ Lavencia oranges and $n$ bags for the oranges (initially empty), both numbered from $1$ to $n$. René packs the oranges according to an array $a$: orange $i$ goes into bag $a_i$.
     22 
     23 Lavencia has a regulatory process for exports. Jacqueline carries it out: she chooses an integer $s$ and confiscates all bags holding exactly $s$ oranges, picking whichever $s$ takes the most oranges from René. The cost of $a$ is the number of oranges Jacqueline confiscates.
     24 
     25 More formally, for a given array $a$, let $c_i$ be the number of elements that appear exactly $i$ times in $a$. The cost of $a$ is: $$ \max_{0 \le i \le n} i \cdot c_i $$
     26 
     27 Given $n$, find an array $a$ that minimizes the cost.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     32 
     33 The only line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, output two lines.
     40 
     41 On the first line, output a single integer — the minimum possible cost.
     42 
     43 On the second line, output $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — any array that achieves this minimum.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 3
     51 
     52 4
     53 
     54 5
     55 
     56 8
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 2
     63 1 2 3 3
     64 3
     65 1 1 2 2 2
     66 3
     67 4 2 1 5 1 3 1 3
     68 ```
     69 
     70 Note
     71 
     72 In the first test case, René places $1$, $1$, $2$, and $0$ oranges into the four bags, respectively. If Jacqueline picks size $1$, she confiscates bags $1$ and $2$, and René loses $2$ oranges. If she picks size $2$, she confiscates bag $3$, and he again loses $2$. Therefore, the cost is $2$. It can be proved that this is the minimum cost for this test case.
     73 
     74 In the second test case, bag $1$ holds $2$ oranges, bag $2$ holds $3$, and the other bags are empty. Picking size $2$ costs René $2$ oranges, and picking size $3$ costs him $3$, so the cost is $3$. It can be proved that, in this case, $3$ is the minimum cost.