Информатика

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более короткой дороги из дорог ДЖ и ДЗ. В ответе запишите целое число – так, как оно указано в таблице.
 

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более длинной дороги из дорог ДЕ и ДЖ. В ответе запишите целое число – так, как оно указано в таблице.
 

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более короткой дороги из дорог ДЕ и ДЖ. В ответе запишите целое число – так, как оно указано в таблице.
 

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более короткой дороги из дорог ЕЗ и ЖЗ. В ответе запишите целое число – так, как оно указано в таблице.
 

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более длинной дороги из дорог ЕЗ и ЖЗ. В ответе запишите целое число – так, как оно указано в таблице.
 

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

Входные данные
Заданы сначала количество учащихся n, затем n строк, каждая из которых содержит фамилию, имя и три числа (оценки по трем предметам: математике, физике, информатике). Данные в строке разделены одним пробелом. Оценки принимают значение от 1 до 5.

Выходные данные
Необходимо вывести пары фамилия-имя по одной на строке, разделяя фамилию и имя одним пробелом. Выводить оценки не нужно. Порядок вывода должен быть таким же, как в исходных данных.
 
 

Примеры

№	Входные данные	Выходные данные
1	3 Yakovlev Ivan 5 5 5 Yapryntsev Aleksey 5 5 5 Kozlov Georgiy 5 5 5	Yakovlev Ivan Yapryntsev Aleksey Kozlov Georgiy

Давилон - самый крупный город на Луне. На Давилоне есть собственная система метро, состоящая из N станций и M железнодорожных линий. Станции пронумерованы от 1 до N. Каждой линией управляет компания. У каждой компании есть идентификационный номер. I-я (1<=i<=M) линия соединяет станцию pi и qi двунаправленно. Промежуточной станции нет. Этой линией управляет компания ci . Можно делать пересадки на станции, где доступно несколько линий. Система оплаты проезда, используемая в этой системе метро, немного странная. Когда пассажир использует только те линии, которые обслуживаются одной и той же компанией, тариф составляет 1 сантик (валюта Давилона). Каждый раз, когда пассажир переходит на линию, которой управляет компания, отличная от текущей линии, с пассажира взимается дополнительная плата за проезд в размере 1 сантик. В случае, если пассажир, перешедший с линии компании А на линию другой компании, снова переходит на линию компании А, дополнительный тариф взимается снова. Незнайка сейчас на станции 1 и хочет добраться до станции N на метро. Найдите минимально необходимый тариф.

Входные данные
В первой строке задается два целых числа N (2<=N<=10⁵) и M (0<=M<=2*10⁵). В каждой из следующих M строк записаны по 3 числа: pi, qi и ci; 1<=pi<=N (1<=i<=M), 1<=qi<=N, 1<=ci<=10⁶, pi ≠ qi. 

Выходные данные
Выведите минимальный требуемый тариф. Если добраться до станции N на метро невозможно, выведите -1.

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 1 2 1 2 3 1 3 1 2	1	Используйте линии компании 1: 1 → 2 → 3. Стоимость проезда 1 сантик.
2	8 11 1 3 1 1 4 2 2 3 1 2 5 1 3 4 3 3 6 3 3 7 3 4 8 4 5 6 1 6 7 5 7 8 5	2	Сначала используйте линии компании 1: 1 → 3 → 2 → 5 → 6. Затем используйте линии компании 5: 6 → 7 → 8. Стоимость проезда 2 сантика.
3	2 0	-1

 

Вам дана строка S, состоящая из цифр от 1 до 9 включительно. Вы можете вставить символ + в некоторые позиции (возможно, ни в одну) между двумя цифрами в этой строке. Здесь знак + не должен появляться последовательно после вставки (т.е. не должно быть два и больше знака + подряд). Все строки, которые можно получить таким образом, можно оценить как формулы. Оцените все возможные формулы и распечатайте сумму результатов, полученных при вычислении всех возможных формул.

Входные данные
На вход подается непустая строка S, состоящая из цифр от 1 до 9 включительно. Длина строки не более 10 символов.

Выходные данные
Выведите сумму результатов, полученных при вычислении всех возможных формул.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	125	176	Всего можно получить 4 формулы: 125, 1 + 25, 12 + 5 и 1 + 2 + 5. Результат после вычисления каждой формулы: 125 1 + 25 = 26 12 + 5 = 17 1 + 2 + 5 = 8 Таким образом, сумма 125 + 26 + 17 + 8 = 176.
2	9999999999	12656242944

 

У Громозеки есть следующие два личных принципа: он никогда не преодолевает расстояние больше L за один день. Он никогда не спит под открытым небом. То есть он должен находться в отеле в конце дня.
На планете Блук N отелей и все расположены на одной улице. Координата i-го отеля (1<=i<=N) равна xi.
Путешествуя по планете Блук, Громозека запланировал Q переездов. Каждым переездом он планирует менять отель aj на bj (1<=j<=Q). Для каждого переезда найдите минимальное количество дней, которое нужно Громозеке, чтобы добраться от aj-го отеля до bj-го, следуя его принципам.
Гарантируется, что он всегда может поехать из aj-го отеля до bj-го отеля.

Входные данные
В первой строке задается целое число N (2<=N<=10⁵) - количество отелей на планете Блук. Во второй строке - N чисел xi - координаты i-го отеля (1<=x₁<x₂<...<x_N<=10⁹ , x_i+1−x_i<=L). В третьей строке записано число L (1<=L<=10⁹).  В четвертой строке - число Q (1<=N<=10⁵). 
В последних Q строчках находится по два различных числа aj и bj (1<=a_j,b_j<=N). Все числа целые.

Выходные данные
Выведите Q строк. В j-й строке (1<=j<=Q) должно быть указано минимальное количество дней, которое Громозеке нужно, чтобы добраться из  aj-го отеля до bj -го отеля.

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	9 1 3 6 13 15 18 19 29 31 10 4 1 8 7 3 6 7 8 5	4 2 1 2	По 1-му переезду он может проехать от 1-го отеля до 8-го за 4 дня следующим образом: День 1: Переезд из 1-го отеля во 2-й отель. Пройденное расстояние - 2. День 2: Переезд из 2-го отеля в 4-й. Пройденное расстояние - 10. День 3: Переезд из 4-го отеля в 7-й. Пройденное расстояние - 6. День 4: Переезд из 7-го отеля в 8-й. Пройденное расстояние - 10.

 

Для целых чисел b ( b >= 2 ) и n ( n >= 1 ) пусть функция f(b, n) определяется следующим образом:
\(f (b, n) = n, когда\ n < b \\ f (b, n) = f (b, floor (n / b)) + (n \ mod \ b), когда \ n >= b\)

Здесь
floor(n / b) обозначает наибольшее целое число, не превышающее n / b;
n mod b обозначает остаток от n, деленный на b.

Менее формально f(b, n) равно сумме цифр n, записанных в базе b. Например, справедливо следующее:
\(f (10,87654) = 8 + 7 + 6 + 5 + 4 = 30\\ f (100,87654) = 8 + 76 + 54 = 138\)

Вам даны целые числа n и s. Определите, существует ли целое число b (b >= 2) такое, что f(b, n) = s. Если ответ положительный, найдите наименьшее из таких b.


Входные данные
В первой строке вводится целое число n (1 <= n <= 10¹¹). Во второй строке - целое число s (1 <= s <= 10¹¹).

Выходные данные
Выведите ответ на задачу. Если ответа нет, то выведите -1.
 

 

Примеры

№	Входные данные	Выходные данные
1	87654 30	10
2	87654 138	100
3	87654 45678	-1
4	31415926535 1	31415926535
5	1 31415926535	-1

 

У Громозеки N печенек. На i-й (1<=i<=N) печеньке написано целое число xi. Он выбирает одну или несколько из этих печенек, так чтобы среднее значение целых чисел, записанных на выбранных печеньках, было равно А.
Какими способами он может сделать свой выбор?

Входные данные
В первой строке вводятся два целых числа N (1<=N<=50) и A (1<=A<=50). Во второй строке N целых чисел - xi (1<=xi<=50).

Выходные данные
Выведите одно число - количество способов выбрать такие печеньки, чтобы среднее значение всех записанных чисел на печеньках было ровно A.
 

 

Примеры

№	Входные данные	Выходные данные	Примечение
1	4 8 7 9 8 9	5	Ниже приведены 5 способов выбрать печеньки так, чтобы в среднем было 8. 1) Выберите 3-ю печеньку. 2) Выберите 1-ю и 2-ю печеньки. 3) Выберите 1-ю и 4-ю печеньки. 4) Выберите 1-ю, 2-ю и 3-ю печеньки. 5) Выберите 1-ю, 3-ю и 4-ю печеньки.
2	3 8 6 6 9	0
3	8 5 3 6 2 8 7 6 5 9	19
4	33 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3	8589934591	Ответ может не соответствовать 32-битному целому числу.

 

Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
 - Издевается! - подумал Борман.
 - Кольцевая! - догадался Штирлиц.

В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...

Естественно, что Штирлицу хочется проезжать мимо точки, в которой, как он воображает, стоит Борман, как можно чаще. Для этого, естественно, выбранный Штирлицем маршрут должен быть как можно короче. Напишите программу, которая выберет оптимальный для Штирлица маршрут.

Входные данные
В первой строке задается  число N (3 <= N <= 100). В последующих строках содержится матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

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

Примеры

№	Входные данные	Выходные данные
1	5 0 1 9 9 2 1 0 9 9 9 9 9 0 9 9 9 9 9 0 9 2 9 9 9 0	1 2 5

Даны два натуральных числа N и K. Требуется вывести  все цепочки x₁, x₂, ..., x_N такие, что xi - натуральное и 1 ≤ x_i ≤ K.

Входные данные
Вводятся два натуральных числа N и K (N, K ≤ 6).

Выходные данные
Выведите все требуемые цепочки в произвольном порядке – по одной на строке. Никакая цепочка не должна встречаться более одного раза.

Примеры

№	Входные данные	Выходные данные
1	2 3	1 1  1 2  1 3  2 1  2 2  2 3  3 1  3 2  3 3

Дано натуральное число N. Рассмотрим его разбиение на натуральные слагаемые. Два разбиения, отличающихся только порядком слагаемых, будем считать за одно, поэтому можно считать, что слагаемые в разбиении упорядочены по невозрастанию.

Входные данные
Задано единственное число N. (N ≤ 40)

Выходные данные
Необходимо вывести все разбиения числа N на натуральные слагаемые в лексикографическом порядке.
 

Примеры

№	Входные данные	Выходные данные
1	5	1 1 1 1 1  2 1 1 1  2 2 1  3 1 1  3 2  4 1  5

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узоров из черных и белых плиток, каждая из которых имеет размер 1 х 1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника N х M метров. Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во-первых, каждый новый клиент, очевидно, захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во-вторых, этот узор должен быть симпатичным.

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2 х 2 метра, полностью покрытого плитками одного цвета. Для составления финансового плана директору Васе необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!

Входные данные
Вводятся два положительных целых числа N и M (1 ≤ N · M ≤ 30).

Выходные данные
Выведите единственное число –  количество различных симпатичных узоров, которые можно выложить во дворе размера N х M. Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.
 

Примеры

№	Входные данные	Выходные данные
1	1 2	4
2	2 3	50

Алиса и Боб управляют роботом. У каждого из них есть по одной кнопке, которая управляет роботом. Алиса начала удерживать кнопку через A секунд после запуска робота и отпустила кнопку  через B секунд после запуска. Боб начал удерживать кнопку через C секунд после запуска и отпустил кнопку через D секунд после запуска. Сколько секунд Алиса и Боб удерживали свои кнопки одновременно?

Входные данные
На вход 4 целых числа: A, B, C и D (\(1<=A<B<=100\), \(1<=C<D<=100\)).

Выходные данные
Выведите продолжительность времени (в секундах), в течение которого Алиса и Боб удерживали свои кнопки одновременно.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	0 75 25 100	50	Алиса начала удерживать кнопку через 0 секунд после запуска робота и отпустила ее через 75 секунд после запуска. Боб начал удерживать кнопку через 25 секунд после запуска и отпустил ее через 100 секунд после запуска. Следовательно, время, когда они оба удерживали свои кнопки, составляет 50 секунд от 25 секунд после запуска до 75 секунд после запуска.
2	0 33 66 99	0	Алиса и Боб не удерживали кнопки одновременно, поэтому ответ - ноль секунд.
3	10 90 20 80	60

 

Дано целое число N (\(1<=N<=10^{10}\)).
Для двух положительных целых чисел A и B определим \(F (A, B)\) как большее из двух: 
- количество цифр в десятичной записи числа A;
- количество цифр в десятичной записи числа B.
Например, \(F (3,11) = 2\), поскольку 3 состоит из одной цифры, а 11 - из двух.
Найдите минимальное значение \(F (A, B)\) среди всех пар положительных целых чисел A и B, таких что \(N = A \cdot B\).

Входные данные
На вход подается целое число N (\(1<=N<=10^{10}\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10000	3	\(F(A,B) \) имеет минимальное значение при \((A,B)=(100,100)\).
2	1000003	7	Есть две пары A и B, таких чтобы выполнялость условие задачи: \((1,1000003)\) и \((1000003,1)\). Для этих пар, \(F(1,1000003)=F(1000003,1)=7\).
3	9876543210	6

 

Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию "пузырьком" работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N – 1) раз.

Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1 или 1 и 4, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.

Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.

Входные данные
Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.

1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.

Выходные данные
Требуется вывести массив после сортировки.

Примеры

№	Входные данные	Выходные данные
1	4 1 4 2 3 2 4 3 1 2	1 2 4 3

Группа солдат-новобранцев прибыла в армейскую часть N666. После знакомства с прапорщиком стало очевидно, что от работ на кухне по очистке картофеля спасти солдат может только чудо.

Прапорщик, будучи не в состоянии запомнить фамилии, пронумеровал новобранцев от 1 до N. После этого он велел им построиться по росту (начиная с самого высокого). С этой несложной задачей могут справиться даже совсем необученные новобранцы, да вот беда, прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине.

После трех дней обучения новобранцам удалось выяснить, что знает (а точнее, думает, что знает) прапорщик. Помогите им, используя эти знания, построиться так, чтобы товарищ прапорщик остался доволен.

Входные данные
Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны.

Выходные данные
В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений.

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 2 3 3 4 1 4 4 1	No

Автомат обрабатывает десятичное натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа.
2. К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей, и 1 в обратном случае.
3. К полученному числу справа дописывается бит четности (0, если количество единиц четное, и 1 в обратном случае).
4. Полученное число переводится в десятичную систему счисления и является результатом работы автомата.
При каком наибольшем значении N результатом работы будет число, не превышающее 155?