F. Game on a Tree

Codeforces

IDCF10239F

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Alice and Bob play a game on a tree. Initially, all nodes are white. Alice is the first to move. She chooses any node and put a chip on it. The node becomes black. After that players take turns. In each turn, a player moves the chip from the current position to an ancestor or descendant node, as long as the node is not black. This node also becomes black. The player who cannot move the chip looses. Who wins the game? An _ancestor_ of a node $v$ in a rooted tree is any node on the path between $v$ and the root of the tree. A _descendant_ of a node $v$ in a rooted tree is any node $w$ such that node $v$ is located on the path between $w$ and the root of the tree. We consider that the root of the tree is $1$. The first line contains one integer $n$ ($1 <= n <= 100 thin 000$) — the number of nodes. Each of the next $n -1$ lines contains two integers $u$ and $v$ ($1 <= u, v <= n$) — the edges of the tree. It is guaranteed that they form a tree. In a single line, print "_Alice_" (without quotes), if Alice wins. Otherwise, print "_Bob_". In the first test case, the tree is a straight line and has $4$ nodes, so Bob always can choose the last white node. In the second test case, the optimal strategy for Alice is to place the chip on $3$. This node will become black. Bob has to choose the node $1$. Alice can choose any of $4$, $5$, $6$, or $7$. Bob can only choose $2$. Alice chooses any of the white sons of $2$, and Bob cannot make a move. ## Input The first line contains one integer $n$ ($1 <= n <= 100 thin 000$) — the number of nodes.Each of the next $n -1$ lines contains two integers $u$ and $v$ ($1 <= u, v <= n$) — the edges of the tree. It is guaranteed that they form a tree. ## Output In a single line, print "_Alice_" (without quotes), if Alice wins. Otherwise, print "_Bob_". [samples] ## Note In the first test case, the tree is a straight line and has $4$ nodes, so Bob always can choose the last white node.In the second test case, the optimal strategy for Alice is to place the chip on $3$. This node will become black. Bob has to choose the node $1$. Alice can choose any of $4$, $5$, $6$, or $7$. Bob can only choose $2$. Alice chooses any of the white sons of $2$, and Bob cannot make a move.

**Definitions** Let $ n \in \mathbb{Z} $ be the initial number of cupcakes, with $ 1 \leq n \leq 10^9 $. Players: Mahmoud (first), Bashar (second). On each turn, a player must eat exactly 1 cupcake. A player loses if, at the start of their turn, exactly 1 cupcake remains. **Constraints** - Players alternate turns, starting with Mahmoud. - Each player plays optimally. - Only legal move: reduce cupcake count by 1. **Objective** Determine the winner: If the number of turns before the losing state (1 cupcake) is odd, Mahmoud wins; if even, Bashar wins. The game ends when a player faces 1 cupcake. The number of moves until the end is $ n - 1 $. Mahmoud wins if $ n - 1 $ is even → $ n $ is odd. Bashar wins if $ n - 1 $ is odd → $ n $ is even. Thus: $$ \text{Winner} = \begin{cases} \text{Mahmoud} & \text{if } n \equiv 1 \pmod{2} \\ \text{Bashar} & \text{if } n \equiv 0 \pmod{2} \end{cases} $$

API Response (JSON)

{
  "problem": {
    "name": "F. Game on a Tree",
    "description": {
      "content": "Alice and Bob play a game on a tree. Initially, all nodes are white.  Alice is the first to move. She chooses any node and put a chip on it. The node becomes black. After that players take turns. In ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10239F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice and Bob play a game on a tree. Initially, all nodes are white. \n\nAlice is the first to move. She chooses any node and put a chip on it. The node becomes black. After that players take turns. In ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the initial number of cupcakes, with $ 1 \\leq n \\leq 10^9 $.  \nPlayers: Mahmoud (first), Bashar (second).  \nOn each turn, a player must eat exactly 1 cupc...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments