LCC '18 Contest 2 S2 - False Report

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Jocelyn is a police officer who runs a local TIPS service which allows people to submit eyewitness reports of various crimes. However, Jocelyn finds that she often receives false reports which hamper the effectiveness of the service. She has asked for your help in filtering out the false reports.

Jocelyn has identified \(M\) traits that are commonly found in the reports and assigned each trait a credibility weight: a number which represents the impact that the trait has on the authenticity of the report. The credibility score of the report is then defined as the sum of the credibility weights of the traits in the report. If a report contains a trait to which Jocelyn has not assigned a credibility weight, it is considered to have weight zero. A non-negative credibility score indicates a real report while a negative score indicates a false report.

Given Jocelyn's data and \(N\) reports, determine which of the reports are real.

Input Specification

The first line of input contains two integers \(N\), \(M\) \((1 \le N, M \le 10\ 000)\), the number of reports to be processed and the number of traits that Jocelyn has identified.

The next \(M\) lines each contain a string \(S_i\) and real number \(W_i\), which represent a trait and its credibility score. It is guaranteed \(1 \le |S_i| \le 20\) and \(-100 \le W_i \le 100\).

The next \(N\) lines each describe a single report using a comma separated list of traits found in the report. Each report will have at most \(20\) traits.

Output Specification

For each of the \(N\) reports, output a single line containing real if the report is to be considered real, or false if the report is considered to be false.

Sample Input

2 4
gun 3
tall 1
robbery 10
monster -3

Sample Output



There are no comments at the moment.