No.1220 yukipoker
タグ : / 解いたユーザー数 144
作問者 :
anagohirame
/ テスター :
Jiro_tech15
Problem Statement
Answer $Q$ queries of the following form.
-----
A deck of playing cards in the Kingdom of yukicoder has $M$ suits (card designs), and for each suit it has one card of each number from $1$ to $N$, for a total of $NM$ cards.
Poker in the Kingdom of yukicoder is played with a hand of $K$ cards, and there are the following two kinds of hands. Note that whether each hand is formed is determined independently.
- Flush: all cards in the hand are of the same suit.
- Straight: the cards in the hand have consecutive numbers. That is, there exists an integer $i$ greater than or equal to $1$ such that the hand consists of one card each of the numbers from $i$ to $i+K-1$. Suits do not matter.
More specifically, let $F$ be the probability that a Flush is formed and $S$ be the probability that a Straight is formed when drawing $K$ cards at random (*) from a deck of $NM$ cards. Then print
Flushif $F \lt S$Straightif $F \gt S$
*Starting with a hand of 0 cards, the operation "choose one card uniformly at random from all cards not in the hand and add it to the hand" is repeated $K$ times.
Input
$Q$ $N_1\ M_1\ K_1$ $\vdots$ $N_Q\ M_Q\ K_Q$
- All inputs are integers.
- $1\leq Q \leq 10^5$
- $1\leq N_i \leq 10^5$
- $1\leq M_i \leq 10^5$
- $1\leq K_i \leq N_i$
Output
Print $Q$ lines.
On the $i\,\,(1\leq i \leq Q)$-th line, print the answer for $(N,\,M,\,K)=(N_i,\,M_i,\,K_i)$,
which is either Flush or Straight.
Sample
Sample 1
Input
2 2 2 2 100000 1 5000
Output
Flush Straight
When $(N,\,M,\,K)=(2,\,2,\,2)$, we have $\displaystyle F=\frac{1}{3},\,S=\frac{2}{3}$.
When $(N,\,M,\,K)=(100000,\,1,\,5000)$, we have $F=1$ (a Flush is always formed).
Note that with the playing cards of our world $((N,\,M,\,K)=(13,\,4,\,5))$, Flush is a stronger hand than Straight, but since this does not satisfy $\displaystyle\,\,\textrm{max}\left(\frac{F}{S}, \frac{S}{F}\right) \geq 2\,$, it is not included in the test cases.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。