問題一覧 > 通常問題

No.1220 yukipoker

レベル : / AI推定難易度 : 1125 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 144
作問者 : anagohirame / テスター : Jiro_tech15
お気に入りにしたユーザー ProblemId : 3888 / 自分の提出
問題文最終更新日: 2020-09-03 22:43:45
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 264 (順位表) の他の問題:

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.
Determine which of Flush and Straight is the stronger hand.
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
  • Flush if $F \lt S$
  • Straight if $F \gt S$
Here, it is guaranteed for the given input that $\displaystyle\,\,\textrm{max}\left(\frac{F}{S}, \frac{S}{F}\right) \geq 2\,$.

*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もしくは右上の雲マークをクリックしてアカウントを作成してください。