Counter game

  • + 0 comments
    // Problem Understanding:
    // Players: Two players take turns, starting with Player 1.
    // Objective: Start with a number n and on each turn, a player can either:
    // Halve the number (if it's even).
    // Subtract 1 from the number (if it's odd).
    // The game continues until the number becomes 1. The player who makes the number reach 1 wins.
    // The goal is to determine the winner, assuming both players play optimally.
    // Steps to Solve:
    // Input and Output:
    
    // Input: A number n.
    // Output: The winner (either "Richard" or "Louise").
    // Alternating Moves:
    
    // Players alternate turns, starting with Player 1 (often called "Louise").
    // If the number is even, the optimal move is to halve it.
    // If the number is odd, the optimal move is to subtract 1 to make it even, so the next player can halve it.
    // Determining the Winner:
    
    // Keep track of the number of moves.
    // The game ends when n becomes 1. The player who makes the last move is the winner.
    // Approach:
    // Game Simulation: Simulate the game with a while loop until n becomes 1.
    // If n is even, halve it.
    // If n is odd, subtract 1.
    // Count the number of moves.
    // Decide the Winner: The winner depends on the number of moves:
    // If the number of moves is odd, the first player ("Louise") wins.
    // If the number of moves is even, the second player ("Richard") wins.
    #include <stdio.h>
    
    int popcount(unsigned long long int n) {
      int count = 0;
      while (n) {
        n &= (n - 1);
        count++;
      }
      return count;
    }
    
    int main() {
      int t;
      scanf("%d\n", &t);
      while (t--) {
        unsigned long long int n;
        scanf("%llu\n", &n);
        printf("%s\n", popcount(n - 1) & 1 ? "Louise" : "Richard");
      }
      return 0;
    }