1. Військові навчання
(за матеріалами ІІІ (міського) етапу 2011 року)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 64 MБ
Вхідний файл: відсутній
Вихідний файл: відсутній
Програма: military.*

Маленький Петрик в дитинстві дуже любив грати у солдатів. Тепер він виріс і став генералом. Нещодавно йому доручили керувати військовими навчаннями. Під час навчань він із допомогою рації дає солдатам команди, які ті виконують і одразу ж доповідають йому про результат.

Навчання проходять на полігоні, який можна вважати квадратом площини із запровадженою декартовою системою координат. Генерал Петро вирішив давати команди лише трьох типів:

1. Висадити солдата у точку з координатами (x, y) та надати йому номер s;

2. Відкликати солдата з номером s, якщо такий є на полігоні;

3. Визначити кількість солдатів, які перебувають на відстані від точки (x, y), що не перевищує d.

При цьому відстанню між точками (x₁, y₁) та (x₂, y₂) називають таку суму:

Завдання
Напишіть програму military.*, яка б реалізувала таке:

1. Процедуру addSoldier, яку мовами Pascal або C++ потрібно оголосити так:

   procedure addSoldier(x,y,s:longint);
   void addSoldier(int x,y,s);

   При кожному виклику цієї процедури ваша програма має додавати солдата у точку з координатами (x,  y) та надавати йому номер s. Гарантовано, що у цей час солдата з таким номером не буде на полігоні.

2. Функцію removeSoldier, яку мовами Pascal або C++ потрібно оголосити так:

   function removeSoldier(s:longint):longint;
   int removeSoldier(int s);

   При кожному виклику цієї функції ваша програма має видалити солдата з номером s з полігона та повернути 1, якщо солдат з таким номером був на полігоні до виклику функції, або повернути 0 без виконання жодних дій, якщо такого солдата не було.

3. Функцію query, яку мовами Pascal або С++ потрібно оголосити так:

   function query(x,y,d:longint):longint;
   int query(int x,y,d);

   При кожному виклику цієї функції ваша програма має порахувати кількість солдат, що перебувають на відстані від точки (x, y), що не перевищує d, і повернути цю кількість.

Нижче подано приклади реалізації програм мовами C++ і Pascal.

/* GCC */
#include <algorithm>
#include <iostream>
using namespace std;

bool was[50001];
void addSoldier(int x,int y,int s)
{
	was[s]=true;
}
int removeSoldier(int s)
{
	int ret=0;
	if (was[s]) ret=1;
	was[s]=0;
	return ret;
}
int query(int x,int y,int d)
{
	return 1;
}

{ Free Pascal }
unit military;

interface

	procedure addSoldier(x,y,s:longint);
	function removeSoldier(s:longint):longint;
	function query(x,y,d:longint):longint;

implementation
	var
	was:array[1..50000] of boolean;
	procedure addSoldier(x,y,s:longint);
	begin
		was[s]:=true;
	end;
	
	function removeSoldier(s:longint):longint;
	var ret:longint;
	begin
		if (was[s]=true) then ret:=1 else
		ret:=0;
		was[s]:=false;
		removeSoldier:=ret;
	end;

	function query(x,y,d:longint):longint;
	begin
		query:=1;
	end;
end.

У поданих кодах масив was створено для того, щоб нагадати учасникам, яким чином і в якому місці коду потрібно запроваджувати змінні, які потім можна використовувати. Створення саме такого масиву не є обов’язковим, тоді як функції і процедуру потрібно назвати саме так, як це вказано в умові.

Обмеження на параметри. Загальна кількість викликів усіх процедур не перевищує 50 000. В усіх викликах процедур аргументи x, y та d не перевищують за модулем 300, 0 ≤ d, аргумент s не перевищуватиме 50 000, 0 < s.

Інтерактивність. Результат компіляції вашого коду буде підключено як модуль до програми перевірки, що буде здійснювати взаємодію з системою тестування й викликати згадану процедуру addSoldier та функції removeSoldier та query. Будь-які дані можуть бути введені або виведені лише через програму grader.*. Цю програму Вам здавати не потрібно. Її для перевірки надасть журі. Код учасника не має містити звертання до будь-яких файлів.

Оцінювання. Якщо програма відповість неправильно хоча б на один запит, за відповідний тест присуджують 0 балів.

Компіляція:

• для того, щоб скомпілювати розв’язання за допомогою GNU C++, потрібно створити проект, у який додати файли grader.*, military.* (у випадку C++ треба ще military.h), виділити grader.* і провести компіляцію;

• для того, щоб скомпілювати розв’язання за допомогою Free Pascal, потрібно скомпілювати grader.pas, причому military.pas має лежати у тій самій теці.

Приклади реалізації є в архіві military.zip

Для перевірки на тесті, відмінному від запропонованого в архіві, потрібно змінити вміст military.in, скомпілювати та запустити grader.*, що міститься у згаданому архіві military.exe. Результат виконання програми буде записано у файл military.out.

Формат наданого в архіві файлу military.in такий. Перший рядок містить число N — кількість запитів. Кожний з наступних N рядків починається з числа 1, 2 або 3 — типу запиту:

• якщо перше число 1, то слідом йдуть три цілих числа x, y, s — параметри addSoldier;

• якщо перше число 2, то слідом йде одне ціле число s — параметр removeSoldier;

• якщо перше число 3, то слідом йде три цілих числа x, y, d — параметри query.

Формат наданого в архіві або створеного grader.* файлу military.out такий:

• файл містить N рядків;

• j-ий рядок відповідає запиту j вхідного файлу. Усі рядки, що відповідають запитам першого типу, порожні, а інші містять результати виконання процедур (описано вище).

Наданий варіант програми перевірки не аналізує вхідній файл щодо справдження обмежень умови та відповідності формату. При перевірці обмежень буде дотримано.

2. Гра
(за матеріалами ІІІ (міського) етапу 2012 року)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Модуль для отримання вхідних даних
і повідомлення вихідних даних: gamelib.pas, gamelib.h
Програма: game.*

      Сашко та Олеся грають у таку гру. Олеся загадує два різні натуральні числа від 1 до N, а Сашко намагається їх вгадати. Для цього він кілька разів називає підмножини Q множини {1, 2, …, N}, а Олеся відповідає про одне із загаданих чисел, чи належить воно до Q. При цьому вона може довільним чином вибирати число, про яке відповідає. Тобто інколи відповідати про одне, інколи — про інше. Сашко перемагає, якщо може назвати таку підмножину A множини {1, 2, …, N}, що в ній загаданих Олесею чисел більше, ніж не загаданих. Інакше кажучи, A — це:

• або одноелементна множина, що містить одне із загаданих чисел;
• або двоелементна множина, що містить обидва загадані числа;
• або триелементна множина, що містить обидва загадані числа.

      Наприклад, якщо було загадано числа 3 та 5, то одна з таких остаточних відповідей: {3}, {5}, {3, 5}, {2, 3, 5} — призводить до виграшу Сашка, а одна з таких відповідей:{5, 10} чи {2, 3, 4, 5} — призводить до його програшу.

      Завдання
      Створіть програму, яка:

• використовує модуль (бібліотеку) gamelib, наданий журі;
• грає в цю гру на боці Сашка і гарантує йому виграш.

      Для Free Pascal модуль має такі складові:

• procedure init(var n:integer);
• function query(q: string): boolean;
• procedure finish(a: string);

      Для C++ бібліотека має такі складові:

• void init(int &n);
• bool query(char q[]);
• void finish(char a[]);

1. Оголосіть використання модуля рядками uses gamelib; або #include "gamelib.h" залежно від мови програмування.

2. Викличте процедуру (функцію) init(N) один раз на початку програми, щоб дізнатись величину N (2 ≤ N ≤ 100). Повторний виклик init призведе до оцінки 0 балів за тест.

3. Ви можете викликати функцію query(q) не більше ніж 10 000 разів, щоб отримати інформацію про загадані Олесею числа. Рядковий параметр q задає множину чисел Q. Він має складатись точно з N символів «0» та/або «1». Одиниця в i-й позиції рядка (q[i] в Pascal, q[i-1] в C++) означає, що число i належить до Q, нуль — що не належить. Функція повертає true, якщо вибране Олесею загадане нею число належить до заданої множини, а false — в іншому разі. Перевищення максимальної кількості викликів або порушення формату параметра q призведе до оцінки 0 балів за тест.

4. Викличте процедуру (функцію) finish(a) один раз в кінці програми, щоб сповістити про виграш Сашка. Параметр a має задавати виграшну множину A. Його формат збігається з форматом q для query. Повторний виклик finish або порушення формату параметра a призведе до оцінки 0 балів за тест.

      Оцінювання результатів роботи програми Програму буде перевірено на серії тестів. Для кожного тесту число N стале для всіх учасників, а загадані числа можуть відрізнятися для кожного з учасників. При цьому вони одні й ті самі для програми з детермінованим (не стохастичним, тобто без елементів випадковості) алгоритмом. Якщо при проходженні тесту програма порушила технічні умови (формат параметрів, кількість викликань тощо) або повідомила підмножину A, що не є виграшною, то присуджують 0 балів за цей тест. Інакше присуджують таку кількість балів:
m ⋅ (1 + b) / (1 + y), де:
m — максимальна кількість балів, призначена автором завдання за тест (від англ. maximum);
y — кількість викликів query, що зробила ваша програма (від англ. yours);
b — найменша кількість викликів query, що зробила програма якогось учасника на цьому тесті й повідомила виграшну множину A (від англ. best).
      Ці значення буде округлено до 6 знаків десяткового запису після коми і підсумовано за всіма тестами. Отримана сума, округлена до найближчого цілого, і буде остаточною оцінкою Вашої програми. Програми членів журі участі в оцінюванні не беруть.