Задача C. Заправки
Условие
В стране N городов, некоторые из которых соединены между собой дорогами.
Для того, чтобы проехать по одной дороге, требуется один бак бензина.
В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться
из первого города в N-ый, потратив как можно меньшее количество денег.
При этом есть еще канистра для бензина, куда входит столько же бензина,
сколько входит в бак. В каждом городе можно заправить бак, залить
бензин в канистру, залить и туда и туда, или же перелить бензин из
канистры в бак.
Формат входного файла
Во входном файле записано сначала число
N, затем идет
N чисел,
i-ое из которых задает стоимость бензина в
i-ом городе (все это целые числа из диапазона от 0 до 100).
Затем идет число
M — количество дорог в стране, далее идет описание
самих дорог. Каждая дорога задается двумя числами — номерами городов,
которые она соединяет. Все дороги двухсторонние (то есть по ним можно
ездить как в одну, так и в другую сторону), между двумя городами всегда
существует не более одной дороги, не существует дорог, ведущих
из города в себя.
Формат выходного файла
В выходной файл выведите одно число — суммарную стоимость маршрута
или &1, если добраться невозможно.
Ограничения
1 ≤
N ≤ 100
Примеры тестов
| № |
Входной файл (filling.in) |
Выходной файл (filling.out) |
|---|
| 1 |
4
1 10 2 15
4
1 2 1 3 4 2 4 3
|
2
|
| 2 |
4
1 10 2 15
0
|
-1
|
Задача E. Форматирование таблицы
Условие
Вам предлагается отформатировать таблицу, данную во входном файле.
Формат входного файла
Первая строка входного файла содержит несколько букв
l,
c,
r.
Их количество равно количеству столбцов в таблице. Каждая буква задает
расположение текста в соответствующем столбце (
l значит, что текст сдвинут до упора влево,
с — что текст расположен по середине,
r — что текст сдвинут вправо).
Далее следуют не менее двух и не более 100
строк данных, каждая из которых задает соответствующую строку таблицы.
Каждая строка содержит несколько записей, разделенных амперсантом ('&')
Количество записей в каждой строке равно количеству столбцов. Каждая
запись должна располагаться в соответствующем столбце.
Первая строка данных задает заголовок таблицы, а остальные — тело таблицы.
Знак '&' не содержится в ячейках таблицы.
Формат выходного файла
В выходной файл выведите таблицу в соответствии с форматом,
приведенным в примере.
Примечания:
- самая длинная запись должна быть отделена от правого и левого
краев ячейки ровно одним пробелом.
- если запись не может быть расположена точно посередине, то
все дополнительные пробелы появляются справа от нее.
Ограничения
- длина любой строки входного файла не превышает 250 символов
- в таблице не более 100 строк
- в таблице не более 100 столбцов
Примеры тестов
| № |
Входной файл (format.in) |
Выходной файл (format.out) |
|---|
| 1 |
lr
EXPRESSION&RESULT
2+2&4
2+2*2&6
|
+------------+--------+
| EXPRESSION | RESULT |
+------------+--------+
| 2+2 | 4 |
| 2+2*2 | 6 |
+------------+--------+
|
| 2 |
lcr
LEFT&CENTER&RIGHT
1&2&3
the&the&the
longest&longest&longest
kitten&kitten&kitten
blitz&blitz&blitz
|
+---------+---------+---------+
| LEFT | CENTER | RIGHT |
+---------+---------+---------+
| 1 | 2 | 3 |
| the | the | the |
| longest | longest | longest |
| kitten | kitten | kitten |
| blitz | blitz | blitz |
+---------+---------+---------+
|
Задача G. Лабиринт знаний
Условие
Участникам сборов подарили билеты на аттракцион ``Лабиринт знаний''. Лабиринт
представляет собой N комнат, занумерованных от 1 до N,
между некоторыми из которых есть двери. Когда человек проходит
через дверь, показатель его знаний изменяется на определенную
величину, фиксированную для данной двери. Вход в лабиринт
находится в комнате 1, выход — в комнате N.
Каждый участник сборов
проходит лабиринт ровно один раз и наибрает некоторое количество знаний
(при входе в лабиринт этот показатель равен нулю).
Ваша задача — показать наилучший результат.
Формат входного файла
Первая строка входного файла содержит целые числа
N — количество комнат и
M —
количество дверей. В каждой из следующих
M строк содержится описание
двери — номера комнат, из которой она ведет и в которую она ведет
(через дверь в лабиринте можно ходить только в одну сторону),
а также целое число, которое прибавляется к количеству знаний при
прохождении через дверь (это число по модулю не превышает 10000).
Двери могут вести из комнаты в нее саму, между двумя комнатами
может быть более одной двери.
Формат выходного файла
В выходной файл выведите
:) — если можно получить
неограниченно большой запас знаний,
:( —
если лабиринт пройти нельзя, и максимальное количество
набранных знаний в противном случае.
Ограничения
1 ≤
N ≤ 2000
1 ≤
M ≤ 10000
Примеры тестов
| № |
Входной файл (maze.in) |
Выходной файл (maze.out) |
|---|
| 1 |
2 2
1 2 5
1 2 -5
|
5
|
