RamWar is a multiplayer game where the players fight for the memory of a server. The memory is a contiguous, one-dimensional array with N elements. The cells of the array are indexed from 0 to N – 1. Adjacent cells are divided into blocks of 4 units (so cells 0–3 is a block, cells 4–7 is another block, etc.). The size of the memory is always divisible by four. Players can manipulate the memory cells in various ways in order to have the highest possible score by the end of the game. Each occupied cell is worth one point, and occupying an entire block is awarded with additional 4 points. The winner is the player who scores the most points, so the goal is to occupy as many cells and as many blocks as possible. To achieve this goal, when the end of the game approaches, we gather our scattered cells into blocks. Luckily enough, the swap operation can be executed for any two cells.
The first line of the input contains a positive integer N, denoting the size of the
memory (4 ≤ N ≤ 1024). The next line consists of a
string of exactly N characters, describing the current state of the memory. This
string contains the following characters: cells occupied by us are denoted with
The first line of the output should contain the maximum score we can achieve by reorganizing the cells occupied by us. Each of the following lines should contain one swap operation in the form X Y, where X and Y are indexes of two cells to be swapped.
Sample Input 1
Output for Sample Input 1
Sample Input 2
Output for Sample Input 2
This problem was inspired by the 2019 Loxon Java Challenge.
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|