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

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

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

printЗадачи

1496. Перепись населения

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

Британские ученые обнаружили в джунглях затерянную деревню и решили выяснить возраст всех жителей. Аборигены из-за отсутствия календаря и письменности не могут указать свой год рождения, но они смогли вспомнить на сколько примерно сезонов дождей один из жителей старше другого для некоторых пар жителей.
Напишите программу, которая на основании полученной информации установит минимально возможный возраст каждого жителя деревни.
Первая строка ввода содержит два целых числа — количество жителей в деревне `N` (`2\ ≤\ N\ ≤\ 1000`) и количество сравнений жителей по возрасту `M` (`1\ ≤\ M\ ≤\ N*(N-1)/2`). Далее следует `M` строк, в каждой строке четыре целых числа — номера жителей `X` и `Y`, сравниваемых по возрасту, (1 ≤ X, Y ≤N), затем минимум и максимум разницы в возрасте между ними `a` и `b` (`1≤\ a\ ≤\ b\ ≤\ 100`). Каждая такая запись означает следующее "Житель `X` старше жителя `Y` не менее чем на `a` лет, но не более чем на `b` лет". Каждая пара жителей встречается в записях не более одного раза.
Вывести `N` строк, на `i`-й строке вывести минимально возможный возраст `i`-го жителя. Если в данных ученых есть противоречия, то вместо возрастов жителей вывести сообщение "No solution" (без кавычек).

Пример ввода

5 3
1 3 10 12
2 1 25 40
4 3 30 40

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

10
35
0
30
0
loading