codeforces-scrape

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

1761B.md (2299B)


      1 Source: https://codeforces.com/problemset/problem/1761/B
      2 
      3 B. Elimination of a Ring
      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 Define a cyclic sequence of size $n$ as an array $s$ of length $n$, in which $s_n$ is adjacent to $s_1$.
     22 
     23 Muxii has a ring represented by a cyclic sequence $a$ of size $n$.
     24 
     25 However, the ring itself hates equal adjacent elements. So if two adjacent elements in the sequence are equal at any time, one of them will be erased immediately. The sequence doesn't contain equal adjacent elements initially.
     26 
     27 Muxii can perform the following operation until the sequence becomes empty:
     28 
     29 * Choose an element in $a$ and erase it.
     30 
     31 For example, if ring is $[1, 2, 4, 2, 3, 2]$, and Muxii erases element $4$, then ring would erase one of the elements equal to $2$, and the ring will become $[1, 2, 3, 2]$.
     32 
     33 Muxii wants to find the maximum number of operations he could perform.
     34 
     35 Note that in a ring of size $1$, its only element isn't considered adjacent to itself (so it's not immediately erased).
     36 
     37 Input
     38 
     39 Each test contains multiple test cases. The first line contains a single integer $t$ ($1\leq t\leq 100$) — the number of test cases. The description of test cases follows.
     40 
     41 The first line of each test case contains a single integer $n$ ($1\leq n\leq 100$) — the size of the cyclic sequence.
     42 
     43 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq a_i\leq n$) — the sequence itself.
     44 
     45 It's guaranteed that $a_i\ne a_{i+1}$ for $1\leq i \lt n$.
     46 
     47 It's guaranteed that $a_n\ne a_1$ when $n \gt 1$.
     48 
     49 Output
     50 
     51 For each test case, output a single integer — the maximum number of operations Muxii can perform.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 3
     59 
     60 4
     61 
     62 1 2 3 2
     63 
     64 4
     65 
     66 1 2 1 2
     67 
     68 1
     69 
     70 1
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 4
     77 3
     78 1
     79 ```
     80 
     81 Note
     82 
     83 In the first test case, you can erase the second element first, then erase the remaining elements one by one in any order. In total, you can perform the operation $4$ times. Note that if you erase the first element first, then the sequence will be turned into $[2,3,2]$ and then immediately become $[2,3]$.
     84 
     85 In the second test case, you can erase the first element first, then the sequence becomes $[2,1]$. Then you can erase all remaining elements one by one in any order.