問題一覧 > 通常問題

No.2463 Straight Flush

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 76
作問者 : 👑 Nachia / テスター : 👑 Kazun
お気に入りにしたユーザー ProblemId : 5710 / 自分の提出
問題文最終更新日: 2023-09-05 06:39:26
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 404 (順位表) の他の問題:

Problem Statement

There are $NM$ kinds of cards, with exactly $1$ card of each kind. Each card has $1$ positive integer between $1$ and $N$, inclusive, and $1$ symbol among symbol $1$ through symbol $M$ written on it. The cards are stacked in a pile, and the $i$-th card from the top has the positive integer $n_i$ and the symbol $m_i$ written on it.

A set of $5$ of these cards is a straight flush if it satisfies all of the following conditions.

  • The symbols written on the cards are all the same.
  • The numbers written on the cards are $5$ consecutive integers, or $1,N,N-1,N-2,N-3$. The order of the cards does not matter here.

First, you take the top $5$ cards of the pile into your hand. You repeat the following operation any number of times so that the set of cards in your hand becomes a straight flush before the cards in the pile run out.

  • Choose $1$ or more of the cards in your hand, discard them, and take the same number of cards from the top of the pile into your hand.

Find the minimum number of times this operation is performed.

Input

The input is given from Standard Input in the following format.
$N$ $M$
$n_1$ $m_1$
$n_2$ $m_2$
$\hspace{5pt} \vdots $
$n_{NM}$ $m_{NM}$

The input satisfies the following constraints.

  • All values are integers.
  • $5 \le N \le 500$
  • $1 \le M \le 500$
  • $1 \le n_i \le N$
  • $1 \le m_i \le M$
  • If $i \ne j$, then $(n_i,m_i) \ne (n_j,m_j)$
  • Output

    Print the answer on $1$ line. End the output with a newline.

    Sample

    Sample 1
    Input
    7 1
    7 1
    2 1
    5 1
    6 1
    4 1
    1 1
    3 1
    
    Output
    1
    

    All $7$ cards have symbol $1$ written on them. The numbers written on the cards are, from the top, $7,2,5,6,4,1,3$.

    The numbers written on the cards you take first are $7,2,5,6,4$. This set of cards is not a straight flush. If you discard the card with $2$ and symbol $1$ written on it and take $1$ card from the pile, the numbers written on the cards in your hand become $7,5,6,4,1$, and the set of cards becomes a straight flush.

    Sample 2
    Input
    5 2
    1 1
    2 1
    3 1
    4 1
    1 2
    2 2
    3 2
    4 2
    5 1
    5 2
    
    Output
    2
    

    By discarding all the cards with symbol $1$ written on them, you can achieve the minimum value $2$.

    Sample 3
    Input
    10 1
    8 1
    5 1
    6 1
    9 1
    7 1
    2 1
    10 1
    3 1
    4 1
    1 1
    
    Output
    0
    

    No cards need to be discarded.

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。