Годинник | |
|
Minodd
|
Задача Minodd
Пан Дивак вирішив поїхати до своєї сестри. Плануючи поїздку, він дізнався про вартість проїзду в усіх автобусних рейсах їхнього району. Але пан таки був дивак, бо вирішив, що вартість його проїзду до сестри повинна дорівнювати непарній кількості копійок. А з другого боку, він хоче дістатися якнайдешевше, тобто знайти найдешевший серед тих маршрутів, в яких сумарна вартість поїздки є непарною. Пересадки Дивака не лякають. Окремі частини маршруту можуть коштувати парну кількість копійок; непарною має бути сума вартостей усіх використаних рейсів.
Рейси виконуються між N населеними пунктами, серед яких село пана Дивака позначене як №1, сестри — як №2. Для кожної пари пунктів або взагалі не існує прямого сполучення, або вартість проїзду відома й однакова в обох напрямках. Із будь-якого пункту гарантовано можна дістатися до інших, але не виключено, що всі можливі способи коштуватимуть парну кількість копійок.
Технічні умови
Програма Minodd в першому рядку читає з клавіатури числа N та M — кількість населених пунктів та кількість рейсів. Далі зчитує M рядків по три натуральні числа i, j та cij — номери пунктів, які з’єднує рейс, та вартість проїзду. Серед цих M рядків жодного разу не повторюється одна й та сама пара пунктів (у т. ч., коли ті самі два пункти переставлені місцями). Ніякий рейс не з’єднує пункт сам із собою. (4≤N,M ≤ 500, 1≤c≤1000). Програма виводить на екран два числа через пропуск - мінімальну можливу сумарну вартість проїзду серед усіх «непарних» та мінімальну можливу вартість проїзду серед усіх можливих («парних» чи «непарних»). Якщо не існує жодного способу дістатися за «непарну» вартість, перше число буде -1.
Приклад
Введення
4 5
1 2 202
1 3 202
1 4 202
2 4 202
3 4 101
Виведення
505 202
Задача Triangles
У Країні Правильних Трикутників (КПТ) міста розташовано у вузлах нескінченної сітки доріг, що показана на малюнку. Довжина дороги між найближчими містами складає 1 УК (умовний кілометр), тобто кожне місто з'єднано дорогами з 6 іншими містами. Міста задаються своїми координатами, столиця країни – початок координат. Король КПТ планує відвідати деяке місто.
Звичайно, маршрут повинен починатись у столиці. Одначе Його Величності хочеться проїжджати тільки дорогами і тільки так, щоб кожне наступне місто знаходилося строго ближче до мети (в геометричному сенсі, тобто по прямій), ніж будь-яке раніше відвідане, включаючи столицю. Щоб підрахувати кілкість різних маршрутів короля, радники Його Величності звернулись до Вас.
Допоможіть їм.
Технічні умови
Програма Triangles читає з клавіатури через пропуск координати міста x,y – цілі числа, що не перевищують 200 за
абсолютною величиною. Програма виводить на екран шукану кількість маршрутів по модулю 1000000007.
Приклад
Введення
2 -2
Виведення
5
|
|
|
