Extending Rock-Paper-Scissors
InterviewTime limit2sMemory limit512 MB
Label n elements so every element beats exactly half the others, and print one ordered winner-loser line for each unordered pair.
- Level
Medium5 of 10
- Topics
- Math, Implementation
- Solved
- No attempts yet
Problem
Rock-paper-scissors is a game between two players, where each player chooses one of three elements: rock, paper or scissors. The rules are simple: rock beats scissors, scissors beats paper and paper beats rock. If the players choose the same element, they tie. On the television show The Big Bang Theory, Sheldon extended rock-paper-scissors with two extra elements: lizard and Spock.
The rules are scissors cuts paper, paper covers rock, rock crushes lizard, lizard poisons Spock, Spock smashes scissors, scissors decapitates lizard, lizard eats paper, paper disproves Spock, Spock vaporizes rock and rock crushes scissors.
Sheldon's setup is valid because each element beats exactly half of the other elements and loses to the remaining half. Whenever the number of elements is odd, a game satisfying these criteria can be found. Extend the game to n elements.
Input
The input consists of a single line with one integer n (3 ≤ n ≤ 99), the number of elements. It is guaranteed that n is odd.
Output
Display one valid extension of rock-paper-scissors to n elements. Display exactly n(n−1)/2 lines containing two integers each, b and c (b ≠ c), meaning that element b beats element c. The elements are numbered 1, 2, . . . , n.
For each pair of distinct elements, x and y, exactly one of 'x y' or 'y x' must be displayed. The lines may be displayed in any order. If there are multiple solutions, any one will be accepted.