codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1739C.md (3423B)


      1 Source: https://codeforces.com/problemset/problem/1739/C
      2 
      3 C. Card Game
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Consider a game with $n$ cards ($n$ is even). Each card has a number written on it, between $1$ 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 \gt y$.
     22 
     23 Two players, Alex and Boris, play this game. In the beginning, each of them receives exactly $\frac{n}{2}$ cards, so each card belongs to exactly one player. Then, they take turns. Alex goes first, then Boris, then Alex again, and so on.
     24 
     25 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.
     26 
     27 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:
     28 
     29 * the number of ways to distribute the cards so that Alex wins;
     30 * the number of ways to distribute the cards so that Boris wins;
     31 * the number of ways to distribute the cards so that the game ends in a draw.
     32 
     33 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.
     34 
     35 For example, suppose $n = 4$, Alex receives the cards $[2, 3]$, and Boris receives the cards $[1, 4]$. Then the game may go as follows:
     36 
     37 * if Alex plays the card $2$, then Boris has to respond with the card $4$. Then, Alex's turn ends, and Boris' turn starts. Boris has only one card left, which is $1$; he plays it, and Alex responds with the card $3$. So, the game ends in a draw;
     38 * if Alex plays the card $3$, then Boris has to respond with the card $4$. Then, Alex's turn ends, and Boris' turn starts. Boris has only one card left, which is $1$; he plays it, and Alex responds with the card $2$. So, the game ends in a draw.
     39 
     40 So, in this case, the game ends in a draw.
     41 
     42 Input
     43 
     44 The first line contains one integer $t$ ($1 \le t \le 30$) — the number of test cases.
     45 
     46 Then, $t$ lines follow. The $i$-th line contains one even integer $n$ ($2 \le n \le 60$).
     47 
     48 Output
     49 
     50 For each test case, print three integers:
     51 
     52 * the number of ways to distribute the cards so that Alex wins;
     53 * the number of ways to distribute the cards so that Boris wins;
     54 * the number of ways to distribute the cards so that the game ends in a draw.
     55 
     56 Since the answers can be large, print them modulo $998244353$.
     57 
     58 Example
     59 
     60 Input
     61 
     62 ```
     63 5
     64 
     65 2
     66 
     67 4
     68 
     69 6
     70 
     71 8
     72 
     73 60
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 1 0 1
     80 3 2 1
     81 12 7 1
     82 42 27 1
     83 341102826 248150916 1
     84 ```
     85 
     86 Note
     87 
     88 In the first test case, Alex wins if he receives the card $2$ (he plays it, and Boris cannot respond). If Alex receives the card $1$, the game ends in a draw.
     89 
     90 In the second test case:
     91 
     92 * Alex wins if he receives the cards $[3, 4]$, $[2, 4]$ or $[1, 4]$;
     93 * Boris wins if Alex receives the cards $[1, 2]$ or $[1, 3]$;
     94 * the game ends in a draw if Alex receives the cards $[2, 3]$.