codeforces-scrape

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

2052A.md (2949B)


      1 Source: https://codeforces.com/problemset/problem/2052/A
      2 
      3 A. Adrenaline Rush
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 1024 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Alice's friend is a big fan of the Adrenaline Rush racing competition and always strives to attend every race. However, this time, Alice is the one watching the race. To ensure her friend does not miss any important details, Alice decides to take notes on everything that happens on the track.
     22 
     23 The first thing Alice notices before the race begins is the numbering of the cars. All the cars line up in front of the starting line in a specific order. The car closest to the line is numbered $1$, the second car is numbered $2$, and so on, up to the last car, which is numbered $n$. How convenient! — Alice thought.
     24 
     25 The race begins with the countdown: "Three! Two! One! Go!". Alice observes that the cars start in their original order. However, as the race progresses, their order changes. She records whenever one car overtakes another, essentially swapping places with it on the track.
     26 
     27 During the race, Alice notices something curious: no car overtakes another more than once. In other words, for any two cars $x$ and $y$, there are at most two overtakes between them during the race: "$x$ overtakes $y$" and/or "$y$ overtakes $x$".
     28 
     29 At the end of the race, Alice carefully writes down the final order of the cars $c_1, c_2, \ldots, c_n$, where $c_1$ represents the winner of the race.
     30 
     31 Alice's friend, however, is only interested in the final ranking and discards all of Alice's notes except for the final ordering. As Alice is quite curious, she wonders: What is the longest possible sequence of overtakes she could have observed during the race? Your task is to help Alice answer this question.
     32 
     33 Input
     34 
     35 The first line of the input contains a single integer $n\;(1 \le n \le 1000)$ — the number of cars in the race.
     36 
     37 The second line contains a permutation $c_1, c_2, \ldots, c_n\;(1 \le c_i \le n, c_i \ne c_j)$ — the final order of the cars.
     38 
     39 Output
     40 
     41 The first line of the output should contain a single integer $m$ — the maximum possible number of overtakes that can occur during the race.
     42 
     43 Each of the next $m$ lines should contain two integers $x$ and $y$ ($1 \le x, y \le n$, $x \ne y$) representing an overtake event, where car $x$ overtakes car $y$. This means that car $x$ was directly behind car $y$ and overtakes it. The overtakes must be listed in the order they occurred during the race.
     44 
     45 After all $m$ overtakes have occurred, the cars must arrive at the finish line in the order $c_1, c_2, \ldots, c_n$. Note that any car $x$ should not overtake another car $y$ more than once.
     46 
     47 If there are multiple possible longest sequences of overtakes, output any of them.
     48 
     49 Examples
     50 
     51 Input
     52 
     53 ```
     54 3
     55 
     56 2 3 1
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 4
     63 2 1
     64 3 1
     65 3 2
     66 2 3
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 1
     73 
     74 1
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 0
     81 ```
     82 
     83 Input
     84 
     85 ```
     86 2
     87 
     88 1 2
     89 ```
     90 
     91 Output
     92 
     93 ```
     94 2
     95 2 1
     96 1 2
     97 ```