Пешеход и велосипедист

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 8192 KB.

ввод: input.txt
вывод: output.txt

 

Два человека из одной команды говорили о жизни и совсем не наблюдали за временем. Неожиданно кто-то заметил, что они опаздывают на четвертьфинал чемпионата мира по программированию, а университет находится высоко на холме. Хорошо, что у одного из них оказался велосипед. По правилам соревнований, пока не соберутся все участники команды, ее не допускают к участию. Поэтому наиболее важен момент прибытия последнего члена команды. Если один из них сядет на велосипед и доедет до университета, то второму придется идти весь путь пешком. Ребята ездят на велосипеде с одинаковой скоростью и ходят пешком тоже с одинаковой скоростью. К сожалению, велосипед - одноместный.
Ребята быстро составили схему, по которой можно добраться до пункта проведения соревнований. Схема состоит из N перекрестков и M дорог, их соединяющих. Между каждой парой перекрестков существует не более одной дороги. Ребята находятся на перекрестке 1 и хотят добраться до перекрестка N, где и расположен университет. Перекресток 1 находится у подножья холма, а N - на вершине. Все дороги односторонние и ведут от перекрестков расположенных ниже к перекресткам расположенным строго выше.
Друзья быстро сообразили, что один из товарищей, проехав некоторый путь, может оставить велосипед другому и пойти дальше пешком. То есть ребята могут использовать велосипед по очереди. Велосипед можно оставлять исключительно на перекрестках. Действуя таким образом, можно уменьшить время путешествия.
Ребята хотят выбрать такой маршрут, чтобы последний из них прибыл как можно раньше. Ваша задача - найти минимальное время, которое они затратят на путешествие.

Входные данные

В первой строке входного файла записаны два натуральных числа N и M (2 <= N <= 150; 1 <= M <= N(N - 1) / 2). Далее следует M строк, каждая из которых содержит описание дороги. Описание состоит из четырех натуральных чисел ui, vi, bi, pi. Описание означает, что дорога ведет от перекрестка ui до перекрестка vi, по которой можно добраться на велосипеде за bi минут, а пешком за pi минут. При этом велосипед едет по дороге не медленнее пешехода, то есть 1 <= bi <= pi <= 30. Друзья находятся на перекрестке 1 и хотят попасть на перекресток N.

Выходные данные

Выведите единственное число - наименьшее время в минутах, которое потребуется, чтобы добраться до пункта назначения. Путешествие заканчивается, когда оба члена команды добрались до пункта назначения.

Пример

Ввод

Test #1
4 3
1 2 5 10
2 3 10 20
3 4 5 10

Test #2
5 6
1 2 3 3
1 4 1 5
4 2 1 5
3 5 3 6
2 5 5 11
2 3 3 6

Вывод

Test #1
30

Test #2
12

Пояснение

Пояснение к примеру 1. Первый товарищ дорогу 1-2 проедет на велосипеде. В это время второй пройдет половину этой же дороги пешком. Далее первый идет пешком до пункта 3, куда он пребывает на 25-ой минуте. В это время второй проходит до конца дорогу 1-2, садится на велосипед, доезжает до перекрестка 3, оставляет велосипед в нем и пешком идет в перекресток 4. Таким образом, на весь путь он тратит 30 минут. Первый товарищ садится на велосипед на перекрестке 3 и доезжает до 4, потратив на весь путь тоже 30 минут.

Пары

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 2048 KB.

ввод: input.txt
вывод: output.txt

 

На уроке информатики учитель дал Пете задачу следующего содержания. Заданы два числа A и B. Какое наименьшее количество чисел надо изменить, чтобы числа стали равны? Петя быстро написал решение. Так как он одинаково знает языки Pascal и C++, то решение он написал на обоих языках.

var a, b, p: longint; begin assign(input, 'input.txt'); reset(input); assign(output, 'output.txt'); rewrite(output); read(a, b); if a = b then p:= 0 else p:= 1; writeln(p); end.

#include <stdio.h> int main() { freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout); int a, b; scanf("%d %d ", &a, &b); int p; if (a == b) p = 0; else p = 1; printf("%dn", p); return 0; }

 

Учитель проверил решение Пети и сказал, что его программа работает правильно, после чего решил усложнить задачу. Заданы две пары чисел (A1, A2) и (B1, B2). Какое наименьшее количество чисел надо заменить, чтобы пары стали равны? В данной задаче пары подразумеваются неупорядоченными, например, пары (4, 1) и (1, 4) равны между собой. Немного подумав, Петя справился и с этой задачей. А сможете ли вы решить ее?
Разумеется, вам надо представить решение лишь на одном языке программирования.

Входные данные

Во входном файле содержатся натуральные числа A1, A2, B1, B2, записанные через пробел. Все числа не превосходят 100.

Выходные данные

В выходной файл выведите искомое наименьшее количество.

Пример

Ввод

Пример 1
6 7 6 6
Пример 2
1 2 3 4
Пример 3
1 8 8 1

Вывод

Пример 1
1
Пример 2
2
Пример 3
0

Предпростые числа

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 2048 KB.

ввод: input.txt
вывод: output.txt

 

Число называется предпростым, если оно имеет ровно 4 делителя. Вот начало бесконечного ряда предпростых чисел: 6, 8, 10, 14, 15, 21, 22, 26. Ваша задача найти сумму первых K членов этого ряда.

Входные данные

В первой строке входного файла содержится натуральное число K (1 <= K <= 300).

Выходные данные

В выходной файл выведите искомую сумму.

Пример

Ввод

Пример 1
4
Пример 2
200

Вывод

Пример 1
38
Пример 2
66262

Интересная последовательность

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 2048 KB.

ввод: input.txt
вывод: output.txt

 

Рассмотрим последовательность чисел 1, 11, 21, 1211, 111221, 312211,... Каждый очередной член описывается предыдущим членом. Например, пятое число в последовательности это 111221, или три единицы, две двойки, одна единица. Таким образом, шестой элемент это все названные числа записанные подряд - 312211.
Если начать с другого числа, можно получить новую последовательность. Например, начиная с 70, получаем: 70, 1710, 11171110, 31173110,...
Ваша задача вывести K-ое число этой последовательности, если ее начать с числа N.

Входные данные

В первой строке входного файла содержится натуральное число N (1 <= N <= 999). Во второй содержится натуральное число K (1 <= K <= 10).

Выходные данные

Пример

Ввод

Пример 1
1
6
Пример 2
788
7

Вывод

Пример 1
312211
Пример 2
31131122211711131221121113122118

Стрелки

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 2048 KB.

ввод: input.txt
вывод: output.txt

 

Петя нарисовал на координатной прямой N стрелок в ряд, i-ая стрелка направлена либо от числа i-1 к числу i, либо наоборот. Все стрелки занумерованы слева направо от 1 до N. Вот пример возможного положения стрелок для N = 7.

Если переориентировать некоторые стрелки, то можно достичь такой конфигурации, что найдется некоторое число X (0 <= X <= N), достижимое по стрелкам из любого другого числа Y (0 <= Y <= N). Например, если переориентировать стрелки 3 и 4, то найдется X (X = 6), что в него можно дойти по стрелкам из любого числа от 0 до 7.
Ваша задача переориентировать наименьшее количество стрелок таким образом, чтобы рисунок стал удовлетворять описанному свойству.

Входные данные

В первой строке входного файла содержится натуральное число N (1 <= N <= 10000). Во второй содержится последовательность A1, A2,..., AN (Ai = 1 или Ai = -1). Если i-ая стрелка направлена вправо, то Ai = 1, иначе Ai = -1.

Выходные данные

В первую строку выведите Q - наименьшее количество стрелок, которые надо переориентировать. Во вторую строку выведите количество наборов из Q стрелок, после переориентации которых набор будет удовлетворять свойству описанному выше. В третью строку Q чисел - номера стрелок из любого оптимального набора.

Пример

Ввод

Пример 1
7
1 1 -1 -1 1 1 -1
Пример 2
6
1 -1 1 -1 1 -1
Пример 3
3
1 1 -1

Вывод

Пример 1
2
2
3 4
Пример 2
2
3
2 5
Пример 3
0
1

Разнообразные строки

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 2048 KB.

ввод: input.txt
вывод: output.txt

 

Будем называть разнообразностью строки количество символов, которые встречаются в ней ровно по одному разу. Например, разнообразность строки "INFORMATICS" - 9, поскольку символы "A", "C", "F", "R", "M", "N", "O", "S" и "T" встречаются в ней ровно по одному разу.
Подстрокой строки S назовём произвольную последовательность идущих подряд элементов строки S. Для заданной строки S найдите подстроку, которая имеет наибольшую разнообразность. Если таких строк несколько, то найдите ту, которая минимальна в лексикографическом порядке (как в словаре).
Строка A меньше строки B в лексикографическом порядке, если выполняется одно из условий:
1) A является префиксом (то есть некоторым началом) B;
2) для некоторого i первые i символов A совпадают с первыми i символами B, а (i+1)-й символ A меньше (i+1)-го символа B.
Например, строка "SOL" меньше в лексикографическом порядке строк "SOLVE", "START", "TIME", "SOLUTION".

Входные данные

Входной файл содержит строку, состоящую только из заглавных букв латинского алфавита. Длина строки не превышает 2500 символов.

Выходные данные

Выведите в выходной файл подстроку исходной строки, имеющую максимальную разнообразность среди всех ее подстрок. Если таких подстрок несколько, выведите минимальную в лексикографическом порядке.

Пример

Ввод

Пример 1
CABBACC
Пример 2
OLYMP
Пример 3
AAA
Пример 4
AABBCC

Вывод

Пример 1
BAC
Пример 2
OLYMP
Пример 3
A
Пример 4
AB

Обмены

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 2048 KB.

ввод: input.txt
вывод: output.txt

 

Для заданного массива A длины N его организацией будем называть количество таких (1 <= i <= N), что A[i] = B[i], где B - это отсортированный в порядке неубывания массив A. Например, организация массива A = [2, 1, 1, 3] равна 2, а организация массива A = [1, 5, 3, 4, 2] равна 3.
Разрешено поменять два элемента массива местами, если эта операция увеличивает его организацию. Для заданного массива A найдите длину наидлиннейшей возможной последовательности обменов.

Входные данные

В первой строке входной файл содержит натуральное число N (1 <= N <= 50). Во второй строке содержится последовательность натуральных чисел A1, A2,..., AN (1 <= Ai <= 1000).

Выходные данные

Выведите в выходной файл искомое наибольшее количество обменов.

Пример

Ввод

Пример 1
4
2 1 1 3
Пример 2
4
7 5 3 4
Пример 3
4
2 1 4 3
Пример 4
6
2 3 3 1 1 2

Вывод

Пример 1
1
Пример 2
3
Пример 3
2
Пример 4
5

Вырубка деревьев

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 2048 KB.

ввод: input.txt
вывод: output.txt

 

Король Берляндии решил вырубить некоторые деревья, растущие перед его дворцом. Перед дворцом короля высажены в ряд N деревьев. Расстояния между соседними двумя - одинаковы.
После вырубки перед дворцом должно остаться M деревьев, и расстояния между соседними должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубить деревья.
Требуется написать программу, которая по заданным числам N и M определит, сколько существует способов вырубить некоторые из N деревьев так, чтобы осталось M деревьев, и соседние деревья находились на равном расстоянии друг от друга.

Входные данные

Входной файл содержит два целых числа N и M (0 <= M,N <= 1000).

Выходные данные

Выведите в выходной файл одно число - искомое количество способов.

Пример

Ввод

5 3

Вывод

4

Пояснение

Если обозначить условно исходное расположение деревьев перед дворцом как "TTTTT", то возможные результаты после вырубки следующие: "TTT..", ".TTT.", "..TTT", "T.T.T".