codeforces-scrape

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

651B.md (1460B)


      1 Source: https://codeforces.com/problemset/problem/651/B
      2 
      3 B. Beautiful Paintings
      4 
      5 time limit per test
      6 
      7 1 second
      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 There are *n* pictures delivered for the new exhibition. The *i*-th painting has beauty *a**i*. We know that a visitor becomes happy every time he passes from a painting to a more beautiful one.
     22 
     23 We are allowed to arranged pictures in any order. What is the maximum possible number of times the visitor may become happy while passing all pictures from first to last? In other words, we are allowed to rearrange elements of *a* in any order. What is the maximum possible number of indices *i* (1 ≤ *i* ≤ *n* - 1), such that *a**i* + 1 > *a**i*.
     24 
     25 Input
     26 
     27 The first line of the input contains integer *n* (1 ≤ *n* ≤ 1000) — the number of painting.
     28 
     29 The second line contains the sequence *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 1000), where *a**i* means the beauty of the *i*-th painting.
     30 
     31 Output
     32 
     33 Print one integer — the maximum possible number of neighbouring pairs, such that *a**i* + 1 > *a**i*, after the optimal rearrangement.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 5  
     41 20 30 10 50 40
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 4
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 4  
     54 200 100 100 200
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 2
     61 ```
     62 
     63 Note
     64 
     65 In the first sample, the optimal order is: 10, 20, 30, 40, 50.
     66 
     67 In the second sample, the optimal order is: 100, 200, 100, 200.