시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB28151451.852%

문제

It is the 25th of July, 2525. Now that the usage of Large Language Models (LLMs) is so ubiquitous, it has become nearly impossible to find actual human-made articles on the internet and not get lost in all the gibberish produced by LLMs.

(Un)fortunately, LLM technology has regressed significantly. Neural networks have been trained on data that is mostly generated by older LLMs, which in turn were trained on even older recycled data. As a result, the output produced by most LLMs is a long string of lowercase letters, each chosen uniformly at random and independently of the others.

You decided to make a program to scavenge the internet in search of human-made articles. Your program must determine whether a given text is human-made or generated by an LLM.

A given text is guaranteed to be exactly one of the following:

  • Human-made, in which case it is a fixed concatenation (without spaces) of words from a given word list.
  • Not human-made and, therefore, generated by an LLM, in which case each character is chosen independently and uniformly at random.

입력

The input consists of:

  • One line with a string $s$, the given text to check.
  • One line with an integer $n$, the number of words in the word list.
  • $n$ lines, each with a string $w$ ($6 \leq |w| \leq 10$), the words in the word list. The words in the word list are distinct and fixed per test case.

All input strings only consist of English lowercase letters (a-z).

Your submission will be run on exactly $100$ test cases, all of which will have $|s| = 3\cdot10^5$ and $n = 5000$. The samples are smaller and for illustration only.

For each test case where $s$ is human-made, $s$ is fixed and does not change between each of your submissions. For each test case where $s$ is generated by an LLM, each of your submissions will receive a new string $s$, generated from independently and uniformly picking random English lowercase letters (a-z).

출력

If the given string was human-made, output "yes". Otherwise, if it was generated by an LLM, output "no".

예제 입력 1

ballooncodingballoonacceptedchallengechallengecoding
5
accepted
balloon
challenge
coding
algorithms

예제 출력 1

yes

예제 입력 2

nlaiueakuyclocedxlwvxdbiifqjbinucjabzyaqakhohgympi
5
aaaaaaaaaa
bbbbbbbbbb
aababbb
aaabbbaaa
abaaba

예제 출력 2

no

예제 입력 3

aaaaaaaaaaabbbbbbbbbbaaaaaaaaaaaaaaabbbbbbbbbbbbbb
5
aaaaaaaaa
bbbbbbbbbb
aabbbbb
aaaaabbbb
bbbbba

예제 출력 3

yes

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2025 G번

  • 문제를 만든 사람: Jeroen Op de Beek

채점 및 기타 정보

  • 예제는 채점하지 않는다.