PROBLEM LINKS
DIFFICULTY
CAKEWALK
PREREQUISITES
Ad Hoc
PROBLEM
We are given several questions. Answer each question such that the answer has no logic, i.e. has no common letters with the corresponding question.
QUICK EXPLANATION
Iterate over all allowed letters. For each letter, check whether it is present in the question. If it is not, then a string consisting of the letter is valid as an answer to the question. If all possible letters are present, then there is no possible answer.
EXPLANATION
There are many ways to solve this problem. However, since this problem appears in a cook-off contest, we obviously want the simplest solution that just works. Here we will present such solution.
The problem asks for an answer (a string) that has no common letters with the corresponding question. Therefore, the simplest answer is just a letter that is not present in the question. We can iterate the letters in the question and mark them as “used”, and then iterate all allowed letters and print one that is not marked as “used”. If all allowed letters are “used”, then there is no answer to the question.
Here is the pseudocode that produces the answer for each question. Note that we have to be aware that lowercase and uppercase letters should be considered equal.
for i := 0 to length(question) - 1:
used[question[i]] = true
found := false
for i := 0 to 25:
if not used['a' + i] and not used['A' + i]:
found := true
println('a' + i)
break
if not found:
println('~')
NOTES TO C/C++ USERS
This applies to those that use I/O functions in <stdio.h>. Since each question can contain spaces, we can use gets() to read the question. A very common way to do this is as follows:
scanf("%d\n", &T);
for (int tc = 0; tc < T; tc++) {
gets(question);
}
Here we use “%d\n” format to read the number of test cases and the following new line. This is wrong if the first test case only consists of spaces! The “\n” format will skip all whitespaces until it finds a non-whitespace character. Therefore, the first test case will not be read at all.
The correct way is to use “%d%*c” format to skip exactly one character (i.e. ‘\n’), or
scanf("%d", &T);
gets(question);
for (int tc = 0; tc < T; tc++) {
gets(question);
}
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
