Завдання № 28
відбірково-тренувальних зборів
команди міста Києва


за матеріалами ІІІ (міського) етапу 2011 року

1. Військові навчання

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

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

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

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

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

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

При цьому відстанню між точками (x1y1) та (x2y2) називають таку суму:

|x1x2| + |y1y2|.

Завдання
Напишіть програму 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 балів.

Компіляція:

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

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

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

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

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

2. Розклад уроків

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

Уявіть, що Вам потрібно скласти розклад уроків на тиждень. Для кожного класу відомо, які предмети мають викладати у цьому класі та скільки уроків припадає на кожен предмет. Кожний предмет викладає лише один учитель, тому уроки з одного предмета не можуть бути у двох класах одночасно. Уроки мають суцільну нумерацію: наприклад, якщо у школі щодня буває не більше за 7 уроків, то перший урок вівторка має номер 8, другий урок вівторка — номер 9 і т. д. Уроки з одним і тим самим номером проходять для всіх класів у один і той самий час. У розкладі допускають «вікна» — випадки, коли один або декілька уроків пропускають, а перед цим і після цього уроки проводять.

Завдання
Подайте приклад потрібного розкладу або вкажіть, що розв’язку немає.

Вхідні дані
Перший рядок вхідного файлу містить у вказаному порядку цілі числа N (1 ≤ N ≤ 50) та T (1 ≤ T ≤ 50), де N — кількість класів, а T — максимально можлива кількість уроків протягом тижня. Кожний з наступних N рядків задає перелік предметів, уроки з яких потрібно проводити у відповідному класі (по рядку на клас). У кожному такому рядку записано T невід’ємних цілих чисел:

Позначимо через Q(i, j) кількість чисел, які дорівнюють j й розташовані у рядку, що задає перелік предметів для i-го класу (1 ≤ iN). При 1 ≤ j ≤ 50 справджується така нерівність:

Q(1, j) + Q(2, j) + … + Q(N, j) ≤ T.

Інакше кажучи, розклад потрібно скласти за умови, що кожному вчителю призначено провести протягом тижня не більше ніж T уроків.

Вихідні дані
Вихідний файл має містити N рядків по Т чисел. Для k = 1, 2, …, N у k-му рядку вихідного файлу має бути заданий розклад для класу, описаного (k + 1)-м рядком вхідного файлу. Кожне число у k-му рядку вихідного файлу має траплятися стільки разів, скільки воно трапилося у (k + 1)-му рядку вхідного файлу. При кожному j (1 ≤ j ≤ T) на j-х місцях різних рядків не може бути однакових додатних чисел — нулів це не стосується. Якщо шуканих розкладів багато, подайте будь-який з них. Якщо потрібного розкладу немає, виведіть число –1.

Приклади

schedule.inschedule.out
2 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
2 3 4 5 6 7 1

3 5
1 1 2 3 2
9 3 3 3 0
1 3 0 0 0
2 1 3 1 2
3 3 0 9 3
1 0 0 3 0