codeforces-scrape

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

2261B.md (2224B)


      1 Source: https://codeforces.com/problemset/problem/2261/B
      2 
      3 B. What's the Capital of France?
      4 
      5 time limit per test
      6 
      7 1.5 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 Obesity might not know the capital of France, but he does know that France has lots of restaurants.
     22 
     23 There are $n$ restaurants in a line. The $i$-th restaurant has rating $a_i$.
     24 
     25 Obesity can alter the ratings of the restaurants with his special power. In one operation, Obesity chooses two adjacent restaurants. If they have the same rating, nothing happens. Otherwise, the rating of the lower side is increased by $1$.
     26 
     27 Formally, in one operation, he does the following:
     28 
     29 * Choose an index $i$ ($1 \le i \lt n$).
     30 * If $a_i \lt a_{i+1}$, increase $a_i$ by $1$.
     31 * If $a_i = a_{i+1}$, do nothing.
     32 * If $a_i \gt a_{i+1}$, increase $a_{i+1}$ by $1$.
     33 
     34 The delicacy of the restaurants is the value of the [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR) of the ratings of all restaurants.
     35 
     36 What is the maximum delicacy Obesity can achieve after performing zero or more operations?
     37 
     38 Input
     39 
     40 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.
     41 
     42 The description of the test cases follows. The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).
     43 
     44 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$).
     45 
     46 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     47 
     48 Output
     49 
     50 For each test case, print one integer — the maximum delicacy of all restaurants.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 4
     58 
     59 1
     60 
     61 0
     62 
     63 2
     64 
     65 1 2
     66 
     67 2
     68 
     69 4 6
     70 
     71 3
     72 
     73 8 8 8
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 0
     80 
     81 3
     82 
     83 7
     84 
     85 8
     86 ```
     87 
     88 Note
     89 
     90 In the first test case, Obesity cannot perform any operations.
     91 
     92 In the second test case, it is optimal for Obesity to perform no operations: $1\, |\, 2 = 3$.
     93 
     94 In the third test case, Obesity can choose $i=1$. Since $4 \le 6$, he increases the rating of the first restaurant by $1$. The ratings are now $[5,6]$, which gives a delicacy of $7$. It can be shown that $7$ is the maximum delicacy no matter how many operations are performed.