CF442A.Borya and Hanabi

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Have you ever played Hanabi? If not, then you've got to try it out! This problem deals with a simplified version of the game.

Overall, the game has 25 types of cards (5 distinct colors and 5 distinct values). Borya is holding n cards. The game is somewhat complicated by the fact that everybody sees Borya's cards except for Borya himself. Borya knows which cards he has but he knows nothing about the order they lie in. Note that Borya can have multiple identical cards (and for each of the 25 types of cards he knows exactly how many cards of this type he has).

The aim of the other players is to achieve the state when Borya knows the color and number value of each of his cards. For that, other players can give him hints. The hints can be of two types: color hints and value hints.

A color hint goes like that: a player names some color and points at all the cards of this color.

Similarly goes the value hint. A player names some value and points at all the cards that contain the value.

Determine what minimum number of hints the other players should make for Borya to be certain about each card's color and value.

你玩过《花火》(Hanabi)吗?如果没有,那一定要试试!本题涉及该游戏的一个简化版本。

总体而言,游戏中共有 25 种不同的卡牌(5 种互异的颜色 × 5 种互异的数值)。博里亚(Borya)手中持有 $ n $ 张卡牌。游戏的一个特殊之处在于:除博里亚本人外,其他所有人都能看到他手中的卡牌;而博里亚知道自己手中有哪些卡牌,却完全不知道它们的排列顺序。注意,博里亚手中可能有多张相同的卡牌(且他对每种卡牌——共 25 种——的数量都完全清楚)。

其他玩家的目标是让博里亚最终确切知道每张卡牌的颜色与数值。为此,其他玩家可以向他提供提示(hints)。提示分为两类:颜色提示与数值提示。

颜色提示的形式如下:一名玩家说出某种颜色,并指出博里亚手中所有该颜色的卡牌。

数值提示同理:一名玩家说出某个数值,并指出博里亚手中所有具有该数值的卡牌。

请确定:其他玩家至少需要给出多少条提示,才能确保博里亚能够唯一确定每张卡牌的颜色与数值?

输入格式

The first line contains integer n (1 ≤ n ≤ 100) — the number of Borya's cards. The next line contains the descriptions of n cards. The description of each card consists of exactly two characters. The first character shows the color (overall this position can contain five distinct letters — R, G, B, Y, W). The second character shows the card's value (a digit from 1 to 5). Borya doesn't know exact order of the cards they lie in.

第一行包含一个整数 nn(1≤n≤1001 \leq n \leq 100)—— 表示 Borya 拥有的卡片数量。
接下来的一行包含 nn 张卡片的描述。每张卡片的描述恰好由两个字符组成:

  • 第一个字符表示颜色(该位置总共可能出现五种不同的字母:R、G、B、Y、W);
  • 第二个字符表示卡片的点数(为数字 1 到 5 中的一个)。
    Borya 并不知道这些卡片的实际排列顺序。

输出格式

Print a single integer — the minimum number of hints that the other players should make.

输出一个整数——其他玩家需要给出的最少提示次数。

输入输出样例

  • 输入#1

    2
    G3 G3

    输出#1

    0
  • 输入#2

    4
    G4 R4 R3 B3

    输出#2

    2
  • 输入#3

    5
    B1 Y1 W1 G1 R1

    输出#3

    4

说明/提示

In the first sample Borya already knows for each card that it is a green three.

In the second sample we can show all fours and all red cards.

In the third sample you need to make hints about any four colors.

在第一个样例中,Borya 已经知道每张牌都是一张绿色的 3。

在第二个样例中,我们可以展示所有的 4 和所有红色的牌。

在第三个样例中,你需要对任意四种颜色给出提示。

输入解题思路,AI测评打分。不知道怎么写?

首页