Задача 2 от конкурса на PC Magazine & Musala Soft
(2002/2003 г.)
СТАТИСТИКА
Най-новият клиент на Монблан Ложи е статистическата фирма
Фън-стат. При едно от провежданите от Фън-стат изследвания се
получават голямо количество цели числа, като характеристики на
изследваните обекти – по едно число за всеки обект. При това доста
често се появяват нови обекти, а някои от старите не са актуални и
не са от интерес за текущото състояние. В никой момент не е нужно
да се съхраняват два или повече обекта с еднаква характеристика;
но след изключването на обект с дадена характеристика, след време
може да се появи друг обект със същата характеристика. Във всеки
момент броят на актуалните обекти е не повече от 4 000 000. При
изготвянето на резултатите (например в хистограма) за някакъв
текущ момент, естествен е въпросът: колко актуални в момента
обекта имат характеристика в зададен интервал? Като съвсем наскоро
назначен програмист Пиер получи тази лесна задача. Той трябва да
направи програма, която да регистрира нови числа (характеристики
на обекти), да изтрива числа от текущите (характеристики на
неактуални обекти), както и да намира броя на обектите, чиито
характеристики са в зададен целочислен интервал.
Входните данни са зададени в текстов файл STAT.INP. Всеки ред на
входния файл съдържа една от командите:
1 N – добави обект с характеристика числото N.
2 N – изтрий обект с характеристика числото N.
3 М N – намери броя на обектите с характеристика, намираща се в
затворения интервал [M,N].
4 – край на входните данни.
Входният файл винаги съдържа команда за край на входните данни и
тя е на последния ред. Числата N и М ще са между 1 и 4 000 000 000
включително.
Изходът на програмата трябва да е в текстовия файл STAT.OUT, който
съдържа по един ред за всяка команда, различна от командата за
край на входните данни. За командата добави се извежда 1, ако няма
актуален обект с тази характеристика (тогава се добавя обект с
тази характеристика) или 0, ако е имало обект с такава
характеристика (в този случай командата не променя броя на
съхранените обекти). За командата изтрий се извежда 1, ако е
изтрит обект с дадената характеристика или 0, ако не е имало обект
с тази характеристика (и в този случай командата не променя броя
на съхранените обекти). За командата намери се извежда търсеният
брой. Пиер се справи и с тази задача, а Вие?
Пример
STAT.INP
1 10
1 5
1 7
1 5
3 1 10
2 5
3 1 10
2 5
4
STAT.OUT
1
1
1
0
3
1
2
0
Statistics
Mont Blanc Lodge's newest client is the Fengstat statistical firm.
One of the Funstat surveys yields a large number of integers as the
characteristics of the objects - one for each object. Frequently new
objects appear and some of the old ones are out of date and not of
interest to the current state. At no time is it necessary to store
two or more objects of the same characteristics; but after excluding
an object with a characteristic, another object with the same
characteristic may appear over time. At any given time, the number
of current objects is no more than 4,000,000. When drawing up the
results (for example in a histogram) for any current moment, the
natural question is: how many currently relevant objects have a
characteristic at a given interval? As a newly hired programmer,
Pierre was given this easy task. It must create a program that
registers new numbers (object characteristics), deletes numbers from
current numbers (features of outdated objects), and finds the number
of objects whose characteristics are in an integer interval.
The input is specified in the STAT.INP text file. Each line of the
input file contains one of the commands:
1 N - Add an object with the number N.
2 N - delete an object with the number N.
3 M N - find the number of objects within the closed interval [M,
N].
4 - end of input data.
The input file always contains a command to end the input data and
it is on the last line. The numbers N and M will be between 1 and
4,000,000,000 inclusive.
The output of the program must be in the text file STAT.OUT, which
contains one line for each command other than the end data input
command. For command add 1 is displayed if there is no current
object with this feature (then an object with this feature is added)
or 0 if there was an object with such feature (in this case the
command does not change the number of stored objects). The delete
command displays 1 if an object with the given characteristic is
deleted or 0 if there is no object with this characteristic (and in
this case the command does not change the number of stored objects).
The search number is displayed for the find command. Pierre did the
job, too, and you?
Example
STAT.INP
1 10
1 5
1 7
1 5
3 1 10
2 5
3 1 10
2 5
4
STAT.OUT
1
1
1
0
3
1
2
0