Олимпиады для начинающих 02

Подборка из нескольких задач для подготовки к олимпиаде по информатике.


Содержание



Морской бой

Чтобы разнообразить игру «морской бой» Боря решил добавить в неё новый тип кораблей. Эти корабли состоят из двух прямоугольников. Первый прямоугольник имеет ширину w1 и высоту h1, а второй прямоугольник — w2 и h2 соответственно. Прямоугольники располагаются один над другим и выровнены по левому краю (см. рисунки после примеров): введем на поле систему координат так, чтобы левая нижняя клеточка первого прямоугольника имела координаты (1, 1). Тогда верхняя правая клеточка первого прямоугольника имеет координаты (w1, h1), левая нижняя клеточка второго прямоугольника имеет координаты (1, h1 + 1), а правая верхняя клеточка второго прямоугольника имеет координаты (w2, h1 + h2).

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

Определите, сколько клеток надо будет отметить после уничтожения корабля, придуманного Борей. Поле, на котором, происходит игра, бесконечно во все стороны.

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

В четырех строках заданы четыре целых числа w1, h1, w2 и h2 (1 ⩽ w1, h1, w2, h2 ⩽ 108) — ширина первого прямоугольника, высота первого прямоугольника, ширина второго прямоугольника и высота второго прямоугольника, соответственно.

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

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

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

input.txt output.txt
2
1
2
1
12
2
2
1
2
16

Примечание

В первом примере поле выглядит так (красным обозначен первый прямоугольник, синим обозначен второй прямоугольник, зеленым обозначены отмеченные точки):
В первом примере поле выглядит так
Во втором примере поле выглядит так:
Во втором примере поле выглядит так


Автобусы

В Берляндии плачевная ситуация с междугородним автобусным сообщением. Во всей стране есть всего три автобусных маршрута, по каждому из которых курсирует лишь один автобус. В первый день нового года ровно в полночь все три автобуса отправляются по своим маршрутам из столицы Берляндии. Известно, что первому автобусу на то, чтобы проехать весь маршрут и вернуться в столицу требуется a минут, второму — b минут, а третьему — c минут. Таким образом, первый автобус отправляется из столицы Берляндии в моменты времени 0, a, 2a, 3a, …, второй — в моменты времени 0, b, 2b, 3b, …, а третий в моменты времени 0, c, 2c, 3c, ….

Момент времени называется подходящим для пересадки, если в этот момент все три автобуса отправляются из столицы Берляндии. Например если a = 1, b = 2, c = 1, то моменты времени 0 и 2 являются подходящими для пересадки, а момент времени 1 не является, потому что в этот момент времени второй автобус находится в пути. Берляндия — особая страна с особым измерением времени, поэтому в берляндских сутках ровно t минут. Это означает, что в первый день происходят все моменты времени с 0-го по (t — 1)-й включительно, во второй день — c t-го по (2t — 1)-й включительно, в третий — с 2t-го по (3t — 1)-й включительно и так далее.

Министерство транспорта Берляндии заинтересовалось, сколько подходящих для пересадки моментов времени произойдtт в d-й день в Берляндии. К сожалению, местные чиновники заняты другими делами, поэтому ответить на этот вопрос было поручено вам.

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

В пяти строках заданы пять целых чисел a, b, c, t и d (1 ⩽ a, b, c ⩽ 106, 1 ⩽ t, d ⩽ 109) — время полного прохождения маршрута первым, вторым и третьим автобусами, соответственно, количество минут в сутках и номер дня, которым интересуется министерство транспорта Берляндии.

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

Выведите одно целое число — количество подходящих для пересадки моментов времени в d-й день.

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

input.txt output.txt
1
2
1
3
1
2
2
3
4
7
2
1
2
3
4
3
3
0

Примечание

В первом примере сутки длятся 3 минуты, поэтому все моменты времени в день с номером 1 — это 0, 1, 2, из них моменты времени 0 и 2 являются подходящими для пересадки.

Во втором примере рассматриваются вторые сутки с моментами времени 7, 8, 9, 10, 11, 12, 13. Первый автобус отправляется в моменты времени 8, 10, 12, второй автобус — в моменты времени 9 и 12, а третий — в моменты времени 8 и 12. Таким образом, только момент времени 12 является подходящим для пересадки.

В третьем примере нет ни одного подходящего для пересадки момента времени.


День рождения

У ковбоя Влада день рождения! На праздник собрались n детей. Чтобы поздравить ковбоя, дети решили водить вокруг Влада хоровод. Среди детей, пришедших к Владу, есть и высокие, и низкие, поэтому если они встанут в хороводе как угодно, многим из них может быть неудобно, потому что если в хороводе рядом стоят очень высокий и очень низкий ребёнок, им трудно держаться за руки. Поэтому дети решили встать в хоровод так, чтобы максимальная разность ростов двух соседних детей была минимальной.

Более формально, пусть n детей выстроились в хоровод. Пронумеруем их целыми числами от 1 до n так, чтобы справа от ребёнка с номером i стоял ребёнок с номером i+1, а справа от ребёнка с номером n стоял ребёнок с номером 1. Тогда неудобством этого хоровода назовём максимальную разность между ростом детей, которые стоят рядом. Обратите внимание, что разностью в росте двух детей называется разность между ростом более высокого и более низкого ребёнка, таким образом, разность в росте двух детей всегда неотрицательна.

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

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

В первой строке содержится одно целое число n (2 ≤ n ≤ 105) — количество детей, которые пришли на день рождения ковбоя Влада.

Во второй строке заданы n целых чисел ai (1 ≤ ai ≤ 109) — рост каждого из детей. Рост детей задан в нанометрах и уменьшен на 109, таким образом, рост ребёнка с ai=1 чуть выше метра, а рост ребёнка с ai=109 составляет два метра.

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

Выведите n целых чисел — значения роста детей в порядке, в котором они должны встать в хоровод. В этом порядке соседними будут дети с номерами i и i+1, а также дети с номерами 1 и n. Если оптимальных хороводов несколько, то выведите любой из них.

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

input.txt output.txt
5
2 1 1 3 2
1 2 3 2 1
3
30 10 20
10 30 20

Примечание

В первом примере неудобство хоровода равно 1, так как разность в росте между соседними детьми равна 1, 1, 1, 1 и 0 соответственно.

Обратите внимание, что последовательности [2,3,2,1,1], [3,2,1,1,2] задают те же хороводы и отличаются только выбором ребёнка с номером 1.

Во втором примере неудобство хоровода равно 20, так как разность в росте детей высотой 10 и 30 равна 20.


Произведение строк

Рома и Денис отправились на соревнование по программированию. В долгой дороге ребята вспоминали операции над строками. Денис сказал, что в Python строки можно умножать на число, тогда Рома, программирующий на С++, решил придумать операцию перемножения строк. По версии Ромы, умножение строки s длины n на строку t обозначается как s⋅t и равно строке t+s1+t+s2+…+t+sn+t, где si обозначает i-й символ строки s, а знаком «+» обозначено сложение (конкатенация) строк. Например, произведением строк «abc» и «de» является строка «deadebdecde», а произведением строк «z» и «ab» является строка «abzab». Обратите внимание, что, в отличие от умножения чисел, произведение строк s и t, вообще говоря, не равно произведению строк t и s.

Денис решил продолжить мысль Ромы — он, как ценитель прекрасного, решил определить красоту строки как максимальную длину подряд идущей группы одинаковых букв. Например, красота строки «xayyaaabca» равна 3, так как самая длинная группа подряд идущих одинаковых букв — это «aaa», а красота строки «qwerqwer» равна 1, потому что все соседние буквы в ней различны.

Чтобы развлечь Дениса, Рома написал ему на листочке n строк p1, p2, p3, …, pn и попросил его вычислить красоту строки (…((p1⋅p2)⋅p3)⋅…)⋅pn. Денис не до конца понял, как работает умножение Ромы, но не хочет признаваться в этом, поэтому просит посчитать красоту этой строки вас. Рома знает, что Денис слишком впечатлительный, поэтому гарантирует, что красота полученной строки не превосходит 109.

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

В первой строке содержится число n (1 ≤ n ≤ 100000) — количество строк, которые написал Рома.

В следующих n строках содержатся непустые строки p1, p2, …, pn, состоящие из маленьких букв английского алфавита.

Гарантируется, что суммарная длина строк не превосходит 100000, а также, что красота произведения всех строк не превосходит 109.

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

Выведите одно целое число — красоту произведения строк.

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

input.txt output.txt
3
a
b
a
3
2
bnn
a
1

Примечание

В первом примере произведение трёх строк равно «abaaaba».

Во втором примере произведение двух строк равно «abanana».


Выбор гурмана

Гурман Яблочков работает редактором известного гастрономического издания. Он разъезжает по всему миру, дегустируя новые изыски именитых шеф-поваров самых фешенебельных ресторанов высокой кухни. У Яблочкова есть свой фирменный способ ревью: в каждом заведении Яблочков заказывает два набора блюд в разные дни. Все заказанные блюда разные, так как Яблочков не любит есть одно и то же. Для каждой пары блюд из разных наборов он точно помнит, какое из них лучше по его ощущениям, или что они одинаковы по вкусовым качествам. Затем гурман оценивает каждое блюдо положительным целым числом.

Однажды, во время очередной ревизии, ресторан кельтской средневековой кухни «Пуассон», подающий суп из каштанов с пихтой, теплый содовый хлеб, пряный лимонный пирог и другую народную еду, очень приятно удивил гурмана своим разнообразным меню, и эксперт заказал слишком много. Поэтому ему нужна помощь в оценке блюд.

Гурман в первый день дегустировал набор из n блюд, во второй день набор из m блюд. Он составил таблицу ощущений a размером n×m, в которой описал свои впечатления. Если по мнению эксперта блюдо i из первого набора лучше блюда j из второго набора, то aij равно «>», в противоположном случае aij равно «<». Блюда также могут быть равны по уровню, тогда aij равно «=».

Теперь Яблочков хочет, чтобы вы помогли ему оценить каждое блюдо в наборах целым положительным числом. Так как Яблочков очень строгий дегустатор, то постарается оценить блюда так, чтобы максимальная из оценок была как можно меньше. В то же время Яблочков очень справедливый, поэтому никогда не оценивает блюда так, чтобы это шло вразрез с его ощущениями. Другими словами, если aijравно «<», то оценка блюда i из первого набора должна быть меньше оценки блюда j из второго набора, если aij равно «>», то должна быть больше, а если aij равно «=», то должна совпадать.

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

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

В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 1000) — количества блюд в каждый из двух дней.

Каждая из следующих n строк содержит строку из m символов. j-й символ в i-й строке задаёт значение aij. Все строки состоят только из символов «<», «>» и «=».

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

В первой строке выведите «Yes» (без кавычек), если можно сделать корректную оценку всем блюдам и «No» (без кавычек), если иначе.

В случае, если сделать корректную оценку можно, во второй строке выведите n целых чисел — оценки блюд первого набора, а в третьей строке m целых чисел — оценки блюд второго набора.

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

input.txt output.txt
3 4
>>>>
>>>>
>>>>
Yes
2 2 2
1 1 1 1
3 3
>>>
<<<
>>>
Yes
3 1 3
2 2 2
3 2
==
=<
==
No

Примечание

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

В третьем примере таблица противоречива: нет ни одного набора оценок, который удовлетворял бы ей.



Комментарии (1)

  • Avatar

    Никита

    |

    // Морской бой
    uses crt;
    var w1,h1,w2,h2,x,i:integer;
    begin
    writeln('first ship');
    readln(w1,h1);
    writeln('second ship');
    readln(w2,h2);
    x:=0;
    if w1 > h1 then for i:=1 to w1 do x:=x+3;
    if w2 > h2 then for i:=1 to w2 do x:=x+3;
    if h1 > w1 then for i:=1 to h1 do x:=x+5;
    if h2 > w2 then for i:=1 to h2 do x:=x+5;
    if w1 = h1 then x:=x+6;
    if w2 = h2 then x:=x+6;
    writeln(x);
    readkey();
    end.
    

    Reply

Оставить комментарий