|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||0||0||0||0.000%|
When you are presented with a “news” story, it can be hard to tell whether it is true or fake, in particular if it has been designed to sound “believable” to you or someone with your biases. However, sometimes, you get lucky and know facts that contradict the story. Here, you will be given several facts about the whereabouts of several people at different times, and then a text that makes claims about where these people were and whom they met. You are supposed to count how many definitely false statements you can find in the text based on the knowledge we provided you.
The background knowledge we give you will be of the form that person X was at place Y from time t1 until time t2, for different persons, places, and times. (The same person, place, or time may of course appear multiple times; but we will never claim that a person was in two places at the same time.) When there is a time at which we didn’t tell you where a person was, that person could have been anywhere. (It’s something you don’t know.)
The text will make claims about who met whom and who was where when. (It will also make many other claims, but you will ignore those.) Text consists of letters (upper case and lower case), spaces (including tabs and newlines), periods, and commas. Commas and all kinds of spaces separate words. Periods separate sentences. To simplify your parsing task (natural language is hard to parse), we follow the following rules:
The creators of the fake news story know enough to avoid internal contradictions (like claiming that Bernie was at Philadelphia from 30–50 and at Vermont from 20–30), so you don’t need to look for them. Instead, you are supposed to count the false statements implied by the text. In the examples above, if Flynn met Trump, but neither Flynn nor Trump met Putin, that would be two false statements. If neither Bernie nor Hillary was at Philadelphia for the entire interval 30–50 (maybe Hillary was there from 30–45 and Bernie from 40–50), then that would also be two false statements.
We consider a claim that X met Y to be true if based on our background knowledge, the two were in the same place at the same time at least once. (For instance, if Flynn was at MarALago from 10 to 20 and Trump was at MarALago from 20 to 22, then they met.) If we have no such evidence, we consider the statement false. On the other hand, we consider a “was at” statement false only if we have evidence that the person was somewhere else for at least one time unit in the interval.
The first line contains a number K ≥ 1, which is the number of input data sets in the file. This is followed by K data sets of the following form:
The first line of a data set contains four integers p, ℓ, m, n. 1 ≤ p ≤ 20 is the number of people, 1 ≤ ℓ ≤ 20 is the number of locations. 0 ≤ m ≤ 1000 is the number of facts you are given, and 0 ≤ n ≤ 30 is the number of lines of the news story.
This is followed by a single line with the names of the p people, each a string of 1–16 letters, separated by spaces and/or tabs. (Names have no spaces in them.) Next is a single line with the names of the ℓ locations, each also a string of 1–16 letters, separated by spaces and/or tabs.
After that are m lines, each stating a fact i by giving four integers pi, ℓi, si, fi. Here 1 ≤ pi ≤ p is the person, 1 ≤ ℓi ≤ ℓ is the location, and 0 ≤ si ≤ fi ≤ 10000 is the time interval when person pi was at ℓi. (From si until fi, inclusive.)
Finally, there are n lines of text, as described above. Each line is at most 120 characters long.
For each data set, first output “Data Set x:” on a line by itself, where x is its number. Then, on a line by itself, output the number of false statements made in the text.
Each data set should be followed by a blank line.
1 6 6 11 7 Trump Flynn Putin Hillary Bernie Jill Philadelphia Moscow USC MarALago NYC washington 3 2 0 100 4 1 20 40 4 5 42 50 4 6 60 90 5 1 30 50 1 5 30 70 1 4 71 100 2 5 69 69 2 2 80 81 5 6 80 100 6 4 100 101 USC is the best university, much better than UCLA. Trump and Flynn and Putin met at USC. was at,philadelphia Bernie not at the same time from 20 HIllAry until 40. Bernie, Hillary met Jill,Trump. We hold these truths to be self-evident. Jill until 80,was at,nyc,FROM 3. until 40 from 39, Government of the people, by the people, for the people was a moscow shall not perish from the Earth putiN.
Data Set 1: 4