codeforces-scrape

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

817B.md (1590B)


      1 Source: https://codeforces.com/problemset/problem/817/B
      2 
      3 B. Makes And The Product
      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 After returning from the army Makes received a gift — an array *a* consisting of *n* positive integer numbers. He hadn't been solving problems for a long time, so he became interested to answer a particular question: how many triples of indices (*i*,  *j*,  *k*) (*i* < *j* < *k*), such that *a**i*·*a**j*·*a**k* is minimum possible, are there in the array? Help him with it!
     22 
     23 Input
     24 
     25 The first line of input contains a positive integer number *n* (3 ≤ *n* ≤ 105) — the number of elements in array *a*. The second line contains *n* positive integer numbers *a**i* (1 ≤ *a**i* ≤ 109) — the elements of a given array.
     26 
     27 Output
     28 
     29 Print one number — the quantity of triples (*i*,  *j*,  *k*) such that *i*,  *j* and *k* are pairwise distinct and *a**i*·*a**j*·*a**k* is minimum possible.
     30 
     31 Examples
     32 
     33 Input
     34 
     35 ```
     36 4  
     37 1 1 1 1
     38 ```
     39 
     40 Output
     41 
     42 ```
     43 4
     44 ```
     45 
     46 Input
     47 
     48 ```
     49 5  
     50 1 3 2 3 4
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 2
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 6  
     63 1 3 3 1 3 2
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 1
     70 ```
     71 
     72 Note
     73 
     74 In the first example Makes always chooses three ones out of four, and the number of ways to choose them is 4.
     75 
     76 In the second example a triple of numbers (1, 2, 3) is chosen (numbers, not indices). Since there are two ways to choose an element 3, then the answer is 2.
     77 
     78 In the third example a triple of numbers (1, 1, 2) is chosen, and there's only one way to choose indices.