以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Problem G
Personality Test
Time limit: 3 seconds
There are n students taking a personality test consisting of m questions. The students are numbered from 1 to n and
the questions are numbered from 1 to m. For each question, each student can either answer it with a single uppercase
Latin character (A–Z) or not answer it. Let Si be a string of m characters representing the answers of student i, where
the j-th character of Si is an uppercase Latin character if they answered question j, or a period (.) if they did not.
Two students are considered similar if there is a set of at least k questions where both students answered all questions
in the set, and for each question in the set, they answered it with the same answer.
For example, let n = 3, m = 3, k = 2, S1 = BBC, S2 = ..C, and S3 = .BC. In this example, students 1 and 3 are
similar since they answered questions 2 and 3 with the same answer, while students 2 and 3 are not similar since they
answered only question 3 with the same answer.
You want to find a pair of integers (a, b) such that a < b and students a and b are similar, or determine if there is no
such pair. If there is more than one pair, find the one with the smallest b. If there is still more than one pair, find the
one with the largest a.
Input
The first line of input contains three integers n, m, and k (2 ≤n ≤5000; 1 ≤m ≤3000; 1 ≤k ≤5). Each of the
next n lines contains a string of m characters. The i-th line contains the string Si.
Output
Output one line containing the integers a and b representing the pair of similar students as mentioned in the problem
statement, or just the integer -1 if there is no such pair.
Sample Input #1 Sample Output #1
3 3 2 1 3
BBC
..C
.BC
Explanation for the sample input/output #1
This is the example in the problem statement.
ICPC Asia Pacific Championship 2024 Problem G: Personality Test
Sample Input #2 Sample Output #2
3 3 1 1 2
BBC
..C
.BC
Explanation for the sample input/output #2
Students 1 and 2 are similar.
Sample Input #3 Sample Output #3
3 3 3 -1
BBC
..C
.BC
Explanation for the sample input/output #3
There is no pair of similar students.
Sample Input #4 Sample Output #4
4 12 2 2 3
GOOD.LUCK.IN
WINNING.ICPC
ASIA.PACIFIC
CHAMPIONSHIP
ICPC Asia Pacific Championship 2024 Problem G: Personality Test