Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
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
