Programming contests

DEIK Regionális Programozó Csapatverseny, nyílt kategória, 2019. december 8.

December 8, 2019 10:15 AM – December 8, 2019 3:15 PM

Game Strategy

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.

Input Specification

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 'Y', cells occupied by an opponent are denoted with 'N', system cells are denoted with 'S', and free cells are denoted with 'F'.

Output Specification

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

  1. 12
download as text file

Output for Sample Input 1

  1. 8
  2. 0 8
download as text file

Sample Input 2

  1. 16
download as text file

Output for Sample Input 2

  1. 17
  2. 11 4
  3. 14 0
download as text file


This problem was inspired by the 2019 Loxon Java Challenge.

University of Debrecen; Faculty of Informatics; v. 03/01/2019