images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
27/04/2024 09:46:36

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2108. Ящики

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Мирко имеет `N` предметов (пронумерованных от 1 до `N`) и L ящиков (пронумерованных от 1 до `L`). Все предметы сейчас разбросаны по всей комнате, поэтому Мирко решил убрать их. Каждый ящик может содержать ровно один предмет, и для того, чтобы Мирко было проще найти их позже, он определил ровно два ящики (`A_i` и `В_i`) для каждого предмета.
Мирко убирает предметы в порядке от 1 до `N`, используя первое из следующих правил, которое он сможет применить:
  • Если ящик `A_i` пуст, он кладет предмет `i` в этот ящик
  • Если ящик `B_i` пуст, он кладет предмет `i` в этот ящик
  • Пробует переместить элемент из `A_i` в его альтернативный ящик; если он уже заполнен, то пробует переместить этот предмет в альтернативный ящик, и так далее, пока этот процесс не звершится успешно, или пока он не вернется к ранее рассматриваемому ящику. В случай успеха, кладет предмет `i` в ящик `A_i`. В случае неудачи использует правило 4.
  • Пробует переместить элемент из `B_i` в его альтернативный ящик; если он уже заполнен, то пробует переместить этот предмет в альтернативный ящик, и так далее, пока этот процесс не звершится успешно, или пока он не вернется к ранее рассматриваемому ящику. В случай успеха, кладет предмет `i` в ящик `B_i`. В случае неудачи использует правило 5.
  • Выбрасывает предмет `i` в мусорное ведро.
Для заданных пар ящиков для каждого предмета, определить, какие предметы будут сохранены, а какие будут выброшены.
В первой строке ввода содержатся два целых числа, `N` и `L` (`1\ ≤\ N,\ L\ ≤\ 300\ 000`), количество предметов и количество ящиков.
Каждая из следующих `N` строк содержит два целых числа: `A_i` и `В_i` (`1\ ≤\ A_i,\ В_i\ ≤\ L`, `A_i\ ≠\ B_i`) – пара ящиков для предмета `i`.
Для каждого предмета выведите одну строку. В случае если предмет успешно сохранен, выведите "LADICA" (без кавычек, хорватское слово для ящика). В случае если предмет выбрасывается, выведите "SMECE" (без кавычек, хорватское слово для мусора).

Пример ввода 1

5 3
1 2
1 3
1 2
1 3
1 2

Пример вывода 1

LADICA
LADICA
LADICA
SMECE
SMECE

Пример ввода 2

9 10
1 2
3 4
5 6
7 8
9 10
2 3
1 5
8 2
7 9

Пример вывода 2

LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
Пояснение к первому примеру: Первый предмет идет в ящик 1 по правилу 1). Второй предмет идет в ящик 3 по правилу 2). Третий предмет идет в ящик 2 по правилу 2). Для четвертого и пятого предмета, оба ящики уже заняты и не могут быть очищены.
Пояснение ко второму примеру: первые шесть предметов идут в ящики 1, 3, 5, 7, 9, 2 (соответственно), по правилу 1). Для седьмого предмета, применяя правило 3), мы стараемся переместить элемент из ящика 1 в ящик 2, предмет из ящика 2 в ящик 3, предмет из ящика 3 в ящик 4, который пуст.
Восьмой предмет идет в ящик 8, который был пуст с самого начала. Для девятого предмета, применяя правило 3), мы стараемся, чтобы переместить предмет из ящика 7 в ящик 8, предмет из ящика 8 в ящик 2, предмета из ящика 2 в ящик 1, предмет из ящика 1 в ящик 5, предмет из ящика 5 в ящик 6, на этом процесс премещения заканчивается, потому что ящик пуст.
Source: COCI 2013/2014, contest #5
loading