Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

ˇ

University of Zilina

Masaryk University

Matej Bel University in Bansk´ Bystrica

a

University of West Bohemia

CTU Open Contest 2016

Suspicious Samples

samples.c, samples.cpp, samples.c11, Samples.java, samples.py

Fatima is a researcher. She currently studies water circulation in her country river basins. She

collects data samples from various meteorological stations that measure diverse climate-related

values. Fatima then searches for interesting patterns in those samples. She uses a program which

reads incoming samples' data in real time and outputs those samples which are interesting or

suspicious in some way. The decision whether a sample is "interesting" or "suspicious" is based

on a fixed set of conditions, such as "the value is greater than the average of the last two hours"

or "the value is lower than anything else in the last five minutes" which are easy to program

into a computer.

Today, Fatima is in doubt about her yesterday's results and she came to see you, an experienced

programmer. She thinks that her program did not evaluate the data correctly and she asks you

to help her verify its results. In particular, she brings the complete sequence of samples and

describes the set of conditions to you. Your program has to read the samples and produce the

output according to the conditions. Fatima will then compare the output of your program to

the output of her program and decide what has to be done next.

Input Specification

There are more test cases. The first line of each test case contains one integer N (1 ≤ N ≤ 105),

giving the number of samples. Then there are N lines, each describing one sample. The line

contains two integers Ti and Vi (1 ≤ Ti ≤ 109, 1 ≤ Vi ≤ 104), meaning that the sample value Vi

was acquired in time Ti. The times are given in seconds elapsed since some fixed moment in the

past and they form a strictly increasing sequence (∀i, k 1 ≤ i < k ≤ N : Ti < Tk ).

The next line of the input contains one integer C (1 ≤ C ≤ 10), the number of conditions to

evaluate. Each of the following C lines specifies one condition Cj . The line contains three tokens

separated with a space:

· A relation operator Rj , which is either "gt" (greater than) or "lt" (less than).

· An aggregate function Fj , one of the "min" (minimum), "max" (maximum), or "avg"

(average).

· An integer number Lj specifying the length of the time interval to be concerned, in seconds.

In general, a condition applied to a sample value Vi checks how Vi is related to some aggregate

feature of the samples which were acquired before Vi. The function Fj specifies exactly that

feature.

To be more specific, let Sij be the set of all samples which were acquired before Vi but no more

than Lj seconds earlier. The sample value Vi satisfies the condition Cj if and only if the relation

ViRj Fj (Sij ) holds. For example, the sample value 800 in conjunction with "lt min 300" can be

read as "is 800 less than the minimum sample value acquired in the previous 5 minutes before

this 800 was obtained?". Note that sample Vi is not an element of Sij .

Output Specification

For each condition, print one integer: the number of samples whose values satisfy that particular

condition. If there are no samples in the time interval specified by the condition, the condition

is never considered satisfied.

Sample Input

10

60 30

120 28

180 35

240 34

300 40

360 31

420 28

480 2

540 42

600 30

2

gt avg 7200

lt min 300

Output for Sample Input

4

2