CF 1063306 - Камень, ножницы, бумага

The game has three participants: Fyodor, Matroskin, and Sharik. Each of them chooses one of the three classic moves: rock, paper, or scissors. A player wins only if their move defeats the moves of both other players at the same time.

codeforcescompetitive-programming

CF 1063306 - \u041a\u0430\u043c\u0435\u043d\u044c, \u043d\u043e\u0436\u043d\u0438\u0446\u044b, \u0431\u0443\u043c\u0430\u0433\u0430

Rating: -
Tags: -
Solve time: 30s
Verified: yes

Solution

Problem Understanding

The game has three participants: Fyodor, Matroskin, and Sharik. Each of them chooses one of the three classic moves: rock, paper, or scissors. A player wins only if their move defeats the moves of both other players at the same time. The task is to determine whether such a player exists and print their identifier, or print ? if the round does not have a unique winner. The original task uses the usual rules: rock beats scissors, scissors beats paper, and paper beats rock.

The input consists of three strings, one for each participant in fixed order. The output is a single character: F, M, or S for the corresponding winner, or ? when nobody can be declared the winner.

The constraints are tiny because the input always contains exactly three moves. This means any solution that checks all possible relationships between the three players will run in constant time. There is no need for advanced data structures or algorithms. The main challenge is not performance, but correctly handling the game logic and avoiding assumptions that are true for two-player rock-paper-scissors but false for three players.

The first tricky case is when all players choose the same move. For example:

rock
rock
rock

The correct output is:

?

No player beats the other two, because every comparison is a draw. A careless solution might count the repeated move as a "majority" and incorrectly select a winner.

Another tricky case is when two players have the same move and the third player has a move that loses to it:

paper
rock
rock

The correct output is:

F

The paper player beats both rock players. A common mistake is to think that two equal moves always cancel the possibility of a winner, but in this game one move can defeat the other two identical moves.

A final edge case is when all three moves are different:

scissors
paper
rock

The correct output is:

?

Each move beats one other move and loses to one other move, so nobody dominates the whole group.

Approaches

A direct approach is to simulate the definition literally. For each player, compare their move with the other two moves and check whether both comparisons are wins. If exactly one player satisfies this condition, that player is the answer. This works because the winner is defined entirely by pairwise comparisons against the other two participants.

The brute-force version checks a constant number of cases. With three players, it performs only a few comparisons, so its operation count is already minimal. In a larger variation with many players, trying every possible winner against every other participant would become expensive, but this problem does not have that structure.

The key observation is that there are only three possible moves, and a winner must be the only player whose move defeats both other moves. We do not need to count scores or simulate rounds. We only need to recognize the three winning patterns: rock against two scissors, scissors against two paper, and paper against two rock.

The brute-force works because the number of participants is fixed, but the simpler pattern check removes unnecessary comparisons and makes the logic easier to verify.

Approach Time Complexity Space Complexity Verdict
Brute Force O(1) O(1) Accepted
Pattern Check O(1) O(1) Accepted

Algorithm Walkthrough

  1. Read the three moves in the order they belong to the participants. Keeping the order matters because the output letter depends on the original player positions.
  2. Check each possible winning situation. A player wins if their move appears twice against the move that it defeats. For example, rock wins exactly when the other two moves are both scissors.
  3. If one of these patterns matches, print the corresponding player's letter. The three valid patterns cannot overlap, because two different moves cannot both defeat the same two moves.
  4. If none of the winning patterns matches, print ?. This covers draws and circular cases where every move has both a winner and a loser.

Why it works:

A valid winner must defeat both opponents. In rock-paper-scissors there is exactly one move that defeats each of the three possible opposing moves. Therefore, the only possible winning configurations are a single move repeated against the two moves it beats. The algorithm checks every such configuration, so if a winner exists it will find that player. If no configuration matches, nobody defeats both opponents, meaning the result is correctly unknown.

Python Solution

import sys

input = sys.stdin.readline

def solve():
    moves = [input().strip() for _ in range(3)]

    if moves[0] == "rock" and moves[1] == "scissors" and moves[2] == "scissors":
        print("F")
    elif moves[0] == "scissors" and moves[1] == "paper" and moves[2] == "paper":
        print("F")
    elif moves[0] == "paper" and moves[1] == "rock" and moves[2] == "rock":
        print("F")
    elif moves[1] == "rock" and moves[0] == "scissors" and moves[2] == "scissors":
        print("M")
    elif moves[1] == "scissors" and moves[0] == "paper" and moves[2] == "paper":
        print("M")
    elif moves[1] == "paper" and moves[0] == "rock" and moves[2] == "rock":
        print("M")
    elif moves[2] == "rock" and moves[0] == "scissors" and moves[1] == "scissors":
        print("S")
    elif moves[2] == "scissors" and moves[0] == "paper" and moves[1] == "paper":
        print("S")
    elif moves[2] == "paper" and moves[0] == "rock" and moves[1] == "rock":
        print("S")
    else:
        print("?")

if __name__ == "__main__":
    solve()

The program first stores the three input strings in an array, where index 0 is Fyodor, index 1 is Matroskin, and index 2 is Sharik. This preserves the connection between the input order and the required output letters.

The condition blocks directly encode the winning states. Each block describes one participant choosing a move that beats the identical moves of the other two participants. Since there are only nine possible winning arrangements, checking them explicitly avoids mistakes in a compact problem.

The final else handles every remaining state. It includes all draws, all three-different-move cases, and cases where no player defeats both opponents.

Worked Examples

For the input:

rock
rock
rock

the trace is:

Step Fyodor Matroskin Sharik Result
Read input rock rock rock no winning pattern
Check rock beats scissors false continue
Check other patterns false print ?

This demonstrates that identical moves do not create a winner. The invariant is that every reported winner must defeat both other entries.

For the input:

paper
rock
rock

the trace is:

Step Fyodor Matroskin Sharik Result
Read input paper rock rock no result yet
Check Fyodor with paper paper beats rock rock rock winner found
Output F

This demonstrates the main winning pattern: one player can defeat two equal opposing moves.

Complexity Analysis

Measure Complexity Explanation
Time O(1) The algorithm checks a fixed number of possible configurations.
Space O(1) Only three input strings are stored.

The limits easily allow this approach because the algorithm performs only a small constant number of operations.

Test Cases

import sys
import io

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    solve()

    result = sys.stdout.getvalue()

    sys.stdin = old_stdin
    sys.stdout = old_stdout

    return result

# provided samples
assert run("rock\nrock\nrock\n") == "?\n", "sample 1"
assert run("paper\nrock\nrock\n") == "F\n", "sample 2"
assert run("scissors\nrock\nrock\n") == "?\n", "sample 3"
assert run("scissors\npaper\nrock\n") == "?\n", "sample 4"

# custom cases
assert run("rock\nscissors\nscissors\n") == "F\n", "Fyodor wins with rock"
assert run("paper\npaper\nrock\n") == "?\n", "same moves do not win"
assert run("scissors\npaper\npaper\n") == "F\n", "two losing opponents"
assert run("rock\npaper\npaper\n") == "M\n", "Matroskin wins with paper"
Test input Expected output What it validates
rock / scissors / scissors F A player winning against two identical opponents
paper / paper / rock ? Duplicate moves alone do not determine a winner
scissors / paper / paper F The winner can be the first player with any valid move
rock / paper / paper M The player position is handled correctly

Edge Cases

For the input:

rock
rock
rock

the algorithm checks every possible winning pattern and finds none. Although the moves are equal, no player defeats the other two, so the output is ?.

For the input:

paper
rock
rock

the algorithm reaches the condition for Fyodor's paper defeating two rocks. It immediately identifies Fyodor as the winner and prints F.

For the input:

scissors
paper
rock

the algorithm checks all possible dominant configurations. None match because each move beats exactly one other move and loses to another one. The result is correctly ?.

For the input:

rock
scissors
scissors

the first winning pattern matches. Fyodor's rock defeats both scissors, so the algorithm prints F. This case confirms that having two equal opponents does not prevent a player from winning.