codeforces-scrape

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

996B.md (2271B)


      1 Source: https://codeforces.com/problemset/problem/996/B
      2 
      3 B. World Cup
      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 Allen wants to enter a fan zone that occupies a round square and has $n$ entrances.
     22 
     23 There already is a queue of $a_i$ people in front of the $i$-th entrance. Each entrance allows one person from its queue to enter the fan zone in one minute.
     24 
     25 Allen uses the following strategy to enter the fan zone:
     26 
     27 * Initially he stands in the end of the queue in front of the first entrance.
     28 * Each minute, if he is not allowed into the fan zone during the minute (meaning he is not the first in the queue), he leaves the current queue and stands in the end of the queue of the next entrance (or the first entrance if he leaves the last entrance).
     29 
     30 Determine the entrance through which Allen will finally enter the fan zone.
     31 
     32 Input
     33 
     34 The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the number of entrances.
     35 
     36 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the number of people in queues. These numbers do not include Allen.
     37 
     38 Output
     39 
     40 Print a single integer — the number of entrance that Allen will use.
     41 
     42 Examples
     43 
     44 Input
     45 
     46 ```
     47 4  
     48 2 3 2 0
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 3
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 2  
     61 10 10
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 1
     68 ```
     69 
     70 Input
     71 
     72 ```
     73 6  
     74 5 2 6 5 7 4
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 6
     81 ```
     82 
     83 Note
     84 
     85 In the first example the number of people (not including Allen) changes as follows: $[\textbf{2}, 3, 2, 0] \to [1, \textbf{2}, 1, 0] \to [0, 1, \textbf{0}, 0]$. The number in bold is the queue Alles stands in. We see that he will enter the fan zone through the third entrance.
     86 
     87 In the second example the number of people (not including Allen) changes as follows: $[\textbf{10}, 10] \to [9, \textbf{9}] \to [\textbf{8}, 8] \to [7, \textbf{7}] \to [\textbf{6}, 6] \to \\ [5, \textbf{5}] \to [\textbf{4}, 4] \to [3, \textbf{3}] \to [\textbf{2}, 2] \to [1, \textbf{1}] \to [\textbf{0}, 0]$.
     88 
     89 In the third example the number of people (not including Allen) changes as follows: $[\textbf{5}, 2, 6, 5, 7, 4] \to [4, \textbf{1}, 5, 4, 6, 3] \to [3, 0, \textbf{4}, 3, 5, 2] \to \\ [2, 0, 3, \textbf{2}, 4, 1] \to [1, 0, 2, 1, \textbf{3}, 0] \to [0, 0, 1, 0, 2, \textbf{0}]$.