CF883E.Field of Wonders

普及/提高-

通过率:0%

时间限制:3.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

Polycarpus takes part in the "Field of Wonders" TV show. The participants of the show have to guess a hidden word as fast as possible. Initially all the letters of the word are hidden.

The game consists of several turns. At each turn the participant tells a letter and the TV show host responds if there is such letter in the word or not. If there is such letter then the host reveals all such letters. For example, if the hidden word is "abacaba" and the player tells the letter "a", the host will reveal letters at all positions, occupied by "a": 1, 3, 5 and 7 (positions are numbered from left to right starting from 1).

Polycarpus knows m words of exactly the same length as the hidden word. The hidden word is also known to him and appears as one of these m words.

At current moment a number of turns have already been made and some letters (possibly zero) of the hidden word are already revealed. Previously Polycarp has told exactly the letters which are currently revealed.

It is Polycarpus' turn. He wants to tell a letter in such a way, that the TV show host will assuredly reveal at least one more letter. Polycarpus cannot tell the letters, which are already revealed.

Your task is to help Polycarpus and find out the number of letters he can tell so that the show host will assuredly reveal at least one of the remaining letters.

波利卡普斯参加了电视节目《奇迹之地》。节目的参赛者需要尽快猜出一个隐藏的单词。最初,该单词的所有字母均处于隐藏状态。

游戏由若干轮组成。在每一轮中,参赛者说出一个字母,节目主持人会告知该字母是否存在于隐藏单词中。如果存在,则主持人会揭示该字母在单词中所有出现的位置。例如,若隐藏单词为 "abacaba",而选手说出字母 "a",则主持人将揭示所有 "a" 所在的位置:第 1、3、5 和 7 位(位置编号从左至右,起始为 1)。

波利卡普斯知道恰好与隐藏单词等长的 mm 个单词。隐藏单词也已知,并且是这 mm 个单词之一。

当前,游戏已进行若干轮,隐藏单词中已有若干字母(可能为零)被揭示出来。此前波利卡普斯所报出的字母恰好就是目前已揭示出的那些字母。

现在轮到波利卡普斯行动。他希望报出一个字母,使得主持人必定至少揭示一个尚未揭示的字母。波利卡普斯不能报出那些已被揭示的字母。

你的任务是帮助波利卡普斯,计算出他可以报出的、能确保主持人至少揭示一个剩余字母的字母个数。

输入格式

The first line contains one integer n (1 ≤ n ≤ 50) — the length of the hidden word.

The following line describes already revealed letters. It contains the string of length n, which consists of lowercase Latin letters and symbols "*". If there is a letter at some position, then this letter was already revealed. If the position contains symbol "*", then the letter at this position has not been revealed yet. It is guaranteed, that at least one letter is still closed.

The third line contains an integer m (1 ≤ m ≤ 1000) — the number of words of length n, which Polycarpus knows. The following m lines contain the words themselves — n-letter strings of lowercase Latin letters. All words are distinct.

It is guaranteed that the hidden word appears as one of the given m words. Before the current move Polycarp has told exactly the letters which are currently revealed.

第一行包含一个整数 nn(1≤n≤501 \leq n \leq 50)—— 隐藏单词的长度。

接下来的一行描述了目前已揭示的字母。该行是一个长度为 nn 的字符串,由小写拉丁字母和字符“*”组成。若某位置上是一个字母,则该字母已被揭示;若某位置上是字符“*”,则该位置上的字母尚未被揭示。保证至少有一个字母仍未被揭示。

第三行包含一个整数 mm(1≤m≤10001 \leq m \leq 1000)—— Polycarpus 所知的长度为 nn 的单词个数。接下来的 mm 行为这些单词本身——每个均为由小写拉丁字母组成的 nn 字母字符串。所有单词互不相同。

保证隐藏单词恰好是所给 mm 个单词中的一个。在当前操作之前,Polycarpus 恰好已猜中目前已被揭示的那些字母。

输出格式

Output the single integer — the number of letters Polycarpus can tell so that the TV show host definitely reveals at least one more letter. It is possible that this number is zero.

输出一个整数——Polycarpus 能够确定说出的字母个数,使得电视节目主持人必定会再揭示至少一个字母。该数值可能为零。

输入输出样例

  • 输入#1

    4
    a**d
    2
    abcd
    acbd

    输出#1

    2
  • 输入#2

    5
    lo*er
    2
    lover
    loser

    输出#2

    0
  • 输入#3

    3
    a*a
    2
    aaa
    aba

    输出#3

    1

说明/提示

In the first example Polycarpus can tell letters "b" and "c", which assuredly will be revealed.

The second example contains no letters which can be told as it is not clear, which of the letters "v" or "s" is located at the third position of the hidden word.

In the third example Polycarpus exactly knows that the hidden word is "aba", because in case it was "aaa", then the second letter "a" would have already been revealed in one of previous turns.

在第一个例子中,Polycarpus 可以确定地猜出字母 “b” 和 “c”,因为这两个字母必定会被揭示。

第二个例子中不存在可以确定猜出的字母,因为无法判断隐藏单词的第三个位置上究竟是字母 “v” 还是 “s”。

在第三个例子中,Polycarpus 准确地知道隐藏单词是 “aba”,因为如果它是 “aaa”,那么第二个字母 “a” 就会在之前某一轮中已被揭示。

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

首页