codeforces-scrape

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

1990C.md (2183B)


      1 Source: https://codeforces.com/problemset/problem/1990/C
      2 
      3 C. Mad MAD Sum
      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 We define the $\operatorname{MAD}$ (Maximum Appearing Duplicate) in an array as the largest number that appears at least twice in the array. Specifically, if there is no number that appears at least twice, the $\operatorname{MAD}$ value is $0$.
     22 
     23 For example, $\operatorname{MAD}([1, 2, 1]) = 1$, $\operatorname{MAD}([2, 2, 3, 3]) = 3$, $\operatorname{MAD}([1, 2, 3, 4]) = 0$.
     24 
     25 You are given an array $a$ of size $n$. Initially, a variable $sum$ is set to $0$.
     26 
     27 The following process will be executed in a sequential loop until all numbers in $a$ become $0$:
     28 
     29 1. Set $sum := sum + \sum_{i=1}^{n} a_i$;
     30 2. Let $b$ be an array of size $n$. Set $b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i])$ for all $1 \le i \le n$, and then set $a_i := b_i$ for all $1 \le i \le n$.
     31 
     32 Find the value of $sum$ after the process.
     33 
     34 Input
     35 
     36 The first line contains an integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases.
     37 
     38 For each test case:
     39 
     40 * The first line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the size of the array $a$;
     41 * The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$) — the elements of the array.
     42 
     43 It is guaranteed that the sum of $n$ over all test cases will not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, output the value of $sum$ in a new line.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 4
     55 
     56 1
     57 
     58 1
     59 
     60 3
     61 
     62 2 2 3
     63 
     64 4
     65 
     66 2 1 1 2
     67 
     68 4
     69 
     70 4 4 4 4
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 1
     77 13
     78 9
     79 40
     80 ```
     81 
     82 Note
     83 
     84 In the first test case, $a=[1]$ initially.
     85 
     86 In the first loop:
     87 
     88 1. Set $sum := sum + a_1 = 0+1=1$;
     89 2. Set $b_1 :=\ \operatorname{MAD}([a_1])=\ \operatorname{MAD}([1])=0$, and then set $a_1 := b_1$.
     90 
     91 After the first loop, $a=[0]$ and the process ends. The value of $sum$ after the process is $1$.
     92 
     93 In the second test case, $a=[2,2,3]$ initially.
     94 
     95 After the first loop, $a=[0,2,2]$ and $sum=7$.
     96 
     97 After the second loop, $a=[0,0,2]$ and $sum=11$.
     98 
     99 After the third loop, $a=[0,0,0]$ and $sum=13$. Then the process ends.
    100 
    101 The value of $sum$ after the process is $13$.