ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Остап и партнёры

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Разнорабочий Иван остался без работы. Но не из-за опозданий и прогулов, и не из-за того, что завод, на котором он работал, остался без заказов. Всему виной был просроченный холодец, подаренный начальнику на недавний праздник.
После очередного дня безуспешных поисков работы он зашёл в гастроном неподалёку от дома. Поскольку деньги у него ещё оставались, он заглянул и в винный отдел. И вот, уже стоя в очереди на кассе, он вдруг узнал в мужчине, покупавшем дорогой коньяк, своего давнего знакомого — Василия. После горячих приветствий и споров о том, какой коньяк выбрать, они, наконец, вышли на улицу.
— Ну как дела, дружище? — спросил Василий.
— Да вот, работу ищу, — устало ответил ему приятель.
— А я и сам искал работу ещё совсем недавно и ведь нашёл такой отличный вариант! — Василий был очень бодр. — Находится в нашем районе и платить обещали прилично. И ты приходи к нам!
— Что же за работа такая? — заинтересовался безработный Иван.
— Про фирму «Остап и партнёры» слышал? Уже несколько лет занимается заготовкой рогов и копыт. И вот, я — заготовщик третьего разряда! — гордо произнёс Василий.
— А много ли платят? — задал резонный вопрос Иван.
— А мне пока ещё не платят, — немного разочарованно ответил новоиспечённый заготовщик, — я первый месяц на испытательном сроке. А мужики свою зарплату не говорят, это у фирмы политика такая. — Тут он сделал паузу и произнёс почти шёпотом: — Но зато наш бригадир на Мерседесе ездит!
— Эх, вот знать бы всё-таки, сколько они получают, — мечтательно произнёс безработный, уже представляя себя за рулём Мерседеса.
— Так ведь я могу узнать! — внезапно обрадовался Василий. — Мужики на перекурах любят похвастаться, на сколько их зарплата больше, чем у кого-то другого. Например, Степан недавно сказал, что получает больше чем Фёдор на 1200 рублей. А вот Фёдор как раз жаловался, что получает меньше чем бригадир на 5500 рублей.
— Так ты собери побольше таких сравнений, и мы все зарплаты узнаем! — обрадовался Иван.
— Так и сделаю!
Через неделю Василий принёс блокнот со множеством записей о сравнениях зарплат заготовщиков. И стали они с Иваном считать…

Исходные данные

Первая строка содержит целые числа n и m — количество сотрудников в фирме и количество записей в блокноте соответственно (1 ≤ n, m ≤ 50000). Каждая из следующих m строк содержит по три целых числа: i, j и d, означающих, что зарплата i-го сотрудника больше чем зарплата j-го сотрудника на d рублей (0 ≤ i, jn−1; |d| ≤ 20000). Все сотрудники пронумерованы от 0 до n−1, начиная с Василия. Известно, что размер его зарплаты равен нулю, а никто из остальных не получает больше 109 рублей.

Результат

Если можно найти такие зарплаты, что их размеры лежат в нужном диапазоне и удовлетворяют всем сравнениям из блокнота, то в первой строке выведите «Possible» и далее по одному в строке выведите n целых чисел — найденные размеры зарплат в рублях в порядке возрастания номеров сотрудников. Если вариантов ответа может быть несколько, выведите любой.
Если ответа нет, в единственной строке выведите «Impossible after i statements», где число i равно номеру первой записи в блокноте, такой, что с учётом только предыдущих записей ответ найти можно, но вместе с текущей — уже нет. Нумерация записей идёт с единицы в порядке их следования в блокноте.

Примеры

исходные данныерезультат
5 6
3 4 1200
4 1 -5500
2 3 4300
3 0 8200
0 4 -7000
2 1 0
Possible
0
12500
12500
8200
7000
3 5
1 2 5
0 2 0
1 0 -5
1 2 5
2 2 0
Impossible after 3 statements
3 2
1 0 871
1 2 903
Impossible after 2 statements
Автор задачи: Дмитрий Иванков
Источник задачи: XIII чемпионат Урала по спортивному программированию, 4 апреля 2009 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1701. Остап и партнёры