[Solution] Card Game solution codeforces

Card Game solution codeforces – Consider a game with 𝑛n cards (𝑛n is even). Each card has a number written on it, between 11 and 𝑛n. All numbers on the cards are different. We say that a card with number 𝑥x is stronger than a card with number 𝑦y if 𝑥>𝑦x>y.

Table of Contents

[Solution] Card Game solution codeforces

Two players, Alex and Boris, play this game. In the beginning, each of them receives exactly 𝑛2n2 cards, so each card belongs to exactly one player. Then, they take turns. Alex goes first, then Boris, then Alex again, and so on.

On a player’s turn, he must play exactly one of his cards. Then, if the opponent doesn’t have any cards stronger than the card played, the opponent loses, and the game ends. Otherwise, the opponent has to play a stronger card (exactly one card as well). These two cards are removed from the game, and the turn ends. If there are no cards left, the game ends in a draw; otherwise it’s the opponent’s turn.

Consider all possible ways to distribute the cards between two players, so that each of them receives exactly half of the cards. You have to calculate three numbers:

  • the number of ways to distribute the cards so that Alex wins;
  • the number of ways to distribute the cards so that Boris wins;
  • the number of ways to distribute the cards so that the game ends in a draw.

You may assume that both players play optimally (i. e. if a player can win no matter how his opponent plays, he wins). Two ways to distribute the cards are different if there is at least one card such that, in one of these ways, it is given to Alex, and in the other way, it is given to Boris.

[Solution] Card Game solution codeforces

The first line contains one integer 𝑡t (1𝑡301≤t≤30) — the number of test cases.

Then, 𝑡t lines follow. The 𝑖i-th line contains one even integer 𝑛n (2𝑛602≤n≤60).

Output

For each test case, print three integers:

  • the number of ways to distribute the cards so that Alex wins;
  • the number of ways to distribute the cards so that Boris wins;
  • the number of ways to distribute the cards so that the game ends in a draw.

Since the answers can be large, print them modulo 998244353998244353.

Example
input

Copy
5
2
4
6
8
60
output

Copy
1 0 1
3 2 1
12 7 1
42 27 1
341102826 248150916 1

[Solution] Card Game solution codeforces

In the first test case, Alex wins if he receives the card 22 (he plays it, and Boris cannot respond). If Alex receives the card 11, the game ends in a draw.

In the second test case:

  • Alex wins if he receives the cards [3,4][3,4][2,4][2,4] or [1,4][1,4];
  • Boris wins if Alex receives the cards [1,2][1,2] or [1,3][1,3];
  • the game ends in a draw if Alex receives the cards [2,3][2,3].

For Solution

“Click Here”

Leave a Comment