Наконец удалось
обнаружить древнюю тайну – звук лисы. Вы пошли в лес, вооружившись очень
хорошим цифровым диктофоном. Однако лес полон голосов животных, и на Вашей
записи могут быть слышны много различных звуков. Но Вы хорошо подготовлены для
выполнения задачи: Вы точно знаете все звуки, которые издают другие животные.
Поэтому остальную часть записи – все неустановленные шумы – должны были сделаны
лисами.
Вход. Первая строка
содержит количество тестов t. Первая
строка каждого теста содержит саму запись – слова английского алфавита,
разделенные пробелом. Каждая строка содержит не более 100 букв и не более 100
слов. Следующие несколько строк содержат информацию о других животных в формате
животное goes звук. Всего не более
100 животных, их названия содержат не более 100 букв и задаются по-английски.
Строки fox goes ... среди них нет.
Последняя строка теста является вопросом, на который Вам
следует ответить: что сказала лиса?
Выход. Для каждого
теста выведите в отдельной строке звуки, сделанные лисой, в порядке их записи.
Считайте, что лиса не молчит (вопреки распространенному мнению, лисы не
общаются азбукой Морзе).
Пример
входа |
1 toot woof wa
ow ow ow pa blub blub pa toot pa blub pa pa ow pow toot dog goes
woof fish goes
blub elephant
goes toot seal goes ow what does
the fox say? |
Пример выхода |
wa pa pa pa
pa pa pow |
структуры
данных
Слова,
произнесенные в лесу, сохраним в массиве words. Слова других животных сохраним
во множестве animals. Далее выводим все слова из words, которых нет в animals –
это слова лисы.
#define MAX 200
vector<string>
words;
set<string>
animals;
char s[MAX], s1[MAX], s2[MAX];
Читаем входные данные.
scanf("%d\n",&tests);
while(tests--)
{
words.clear();
animals.clear();
Читаем слова, произнесенные в лесу и заносим их в массив words. Количество слов не задано, читаем
их до конца строки.
while(scanf("%s%c",s,&ch))
{
words.push_back(s);
if(ch == '\n') break;
}
Читаем информацию о других животных. Слова
других животных заносим во множество animals. Как только вторым прочитанным
словом будет does, а не goes, останавливаемся.
while(scanf("%s %s %s\n",s,s1,s2), s1[0] != 'd')
animals.insert(s2);
Фраза what does the уже прочитана в последней итерации предыдущего цикла.
Пропускаем фразу fox say?, так как
входные данные состоят из нескольких тестов и их нам еще следует обработать.
scanf("%s
%s\n",s1,s2); // skip 'fox say?'
Перебираем слова, произнесенные в лесу.
Если слово не найдено в базе слов других животных animals, то оно произнесено
лисой. Выводим его.
for(i = 0; i
< words.size(); i++)
if
(animals.find(words[i]) == animals.end())
printf("%s
",words[i].c_str());
printf("\n");
}
Java реализация
//import
java.io.*;
import
java.util.*;
public class
Main
{
public static void
main(String[] args) //throws IOException
{
//Scanner con =
new Scanner(new FileReader ("6767.in"));
Scanner con = new
Scanner(System.in);
int tests =
con.nextInt(); con.nextLine();
while(tests--
> 0)
{
String s[] = con.nextLine().split(" ");
TreeSet<String> tree = new TreeSet<String>();
while(true)
{
String animal = con.next();
String command = con.next();
String word = con.next();
if
(command.equals("does")) break;
tree.add(word);
}
String skip = con.nextLine(); // skip "fox say?"
for(String
word : s)
if
(!tree.contains(word)) System.out.print(word + "
");
System.out.println();
}
con.close();
}
}