Темы
    Информатика(2609 задач)
---> 36 задач <---
Источники --> Личные олимпиады --> Турнир Архимеда
    2014(8 задач)
    2015(8 задач)
    2016(10 задач)
    2017(10 задач)
Страница: 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Помогите Матроскину узнать уровень его гордости, то есть найдите средний вес всех родившихся за $n$ лет телят.

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

Вводится одно целое число $1 \le n \le 1000$ — количество лет, которое у Мурки рождались телята.$

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

Выведите средний вес всех родившихся телят.

Примеры
Входные данные
3
Выходные данные
3
#113081
  
Источники: [ Личные олимпиады, Турнир Архимеда, 2014, Задача B ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Недавно дядя Фёдор прочитал в журнале «Мурзилка», что самый высокий водопад в мире — это водопад Анхель, высота которого составляет 1054 метра. «Вот было бы здорово посмотреть на такой водопад!», — размечтался он.

Но Венесуэла далеко, поэтому пока дядя Фёдор решил начать с исследования речки Сметанки, которая течет рядом с Простоквашино. Она начинается в холмах и постепенно спускается вниз, к деревне. Дядя Фёдор вместе с Шариком прошли вдоль всего течения Сметанки от ее истока. Иногда по пути им встречались водопады. Как дядя Фёдор узнал из той статьи в «Мурзилке», водопадом считается участок реки с постоянным углом наклона, превышающим 45 градусов, то есть такой участок, высота которого больше его длины.

Уже после путешествия, раз за разом перерисовывая карту Сметанки на бумагу, дядя Фёдор заметил, что если нарисовать вид Сметанки сбоку (то есть чем выше нарисована точка — тем выше она над уровнем моря, а чем правее — тем дальше она от истока и ближе к Простоквашино), то получается невозрастающая ломаная, которую очень легко анализировать. Каждый отрезок этой ломаной — это как раз участок реки с постоянным углом наклона, который может оказаться водопадом!

Проведя несколько вечеров за изучением карты Сметанки, дядя Фёдор вспомнил, что кроме водопадов бывают еще и каскады водопадов. Каскадом водопадов называется один или несколько идущих подряд водопадов. Высота каскада — это разница между высотами самой верхней и самой нижней точек, принадлежащих этому каскаду.

Теперь дяде Фёдору стало интересно, а какова высота самого высокого каскада водопадов на Сметанке? Помогите ему: по описанию реки, сделанному Шариком и дядей Фёдором, найдите это число.

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

В первой строке вводится число $n$ ($2 \le n \le 10^5$ ) — количество вершин ломаной, описывающей речку Сметанку. В следующих $n$ строках перечислены координаты этих точек, в $i$-й строчке записаны числа $x_i$ и $y_i$ — расстояние от точки до истока по горизонтали и высота точки над уровнем моря ($0 \le x_i \le 10^9 , 0 \le y_i \le 10^9$ ). Точки перечислены начиная от истока реки, то есть начиная с точки, $x$-координата которой равна нулю, а $y$-координата — максимальная среди всех точек. Гарантируется, что река течет сверху вниз и слева направо, то есть каждая следующая точка находится не выше и не левее предыдущей.

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

Выведите одно целое число: высоту самого высокого каскада водопадов на этой реке. Если на реке на самом деле нет водопадов, выведите 0.

Примеры
Входные данные
3
0 15
1 10
5 5
Выходные данные
10
#113082
  
Источники: [ Личные олимпиады, Турнир Архимеда, 2014, Задача C ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Однажды утром во время традиционной инспекции картофельного поля кот Матроскин обнаружил на одном из кустиков колорадского жука. Придя в ужас, он тут же помчался расспрашивать дядю Фёдора (как наиболее образованного из друзей) о том, как эти жуки размножаются и как с ними бороться.

Картофельные поля обычно очень аккуратно устроены: кусты картофеля рассажены на них так, что образуют клетчатое поле, где каждая клетка — картофельный куст. Как только на каком-то из кустов появляется колорадский жук, он начинает активно есть и размножаться. Поэтому каждый час на каждый куст будет добавляться столько же жуков, сколько соседних с ним по стороне кустов, уже зараженных жуками. Например, если у куста ровно один сосед, на котором уже есть жуки, то на него добавится один жук, а если все четыре соседа заражены жуками, то на куст добавится четыре новых жука. И если жуков не остановить, они заполнят собой все поле. Но к счастью, когда-то давно дядя Фёдор, прочитав статью в «Мурзилке», сделал отпугиватель колорадских жуков...

Если честно, Матроскин не очень понял, как работает этот отпугиватель. Но главное он запомнил: его надо установить на один из кустиков картофеля, и как только на этом кустике окажется ровно $k$ колорадских жуков, что-то (вот этого Матроскин и не понял) произойдет и все жуки сбегут с поля.

Зная координаты куста картофеля, на который Матроскин установил отпугиватель, посчитайте, через сколько часов после появления первого колорадского жука на поле он подействует. Матроскин поставил ловушку в первый час после появления жука на поле.

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

Вам даны три числа: $x$ и $y$ — координаты кустика картофеля, на который Матроскин установил отпугиватель, и $k$ — параметр отпугивателя ($1 \le k \le 10^9 , |x| \le 10^9 , |y| \le 10^9$ ). Тот из кустов, на котором был найден первый жук, имеет координаты $(0, 0)$. Координаты всех кустов поля не превосходят $10^9 + 1$ по модулю.

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

Выведите одно целое число: через сколько часов ловушка сработает. Если же ловушка никогда не сработает, выведите −1.

Примеры
Входные данные
0 0 1
Выходные данные
0
Входные данные
0 0 5
Выходные данные
2
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Когда Дядя Фёдор уехал домой в город, следить за хозяйством остались Матроскин и Шарик. Но поскольку Дядю Фёдора очень волновали дела в Простоквашино, они договорились, что каждую неделю Матроскин будет писать письмо с отчетом о делах. Довольно скоро Матроскин понял, что письма идут слишком долго, поэтому решил отправлять телеграммы. Обычно отчеты очень длинные, поэтому Матроскину пришлось отправлять несколько телеграмм. Чтобы Дяде Фёдору было удобнее разобраться в пришедших телеграммах, Матроскин следует следущим правилам:

  • В каждой телеграмме должно быть не более 140 символов, включая пробелы и знаки препинания.
  • Исходный текст должен быть разбит на телеграммы по пробелам, при этом пробел, по которому разбивается телеграмма, уничтожается.
  • Если телеграмма не является последней, в её конец нужно дописать три точки.
  • Если телеграмма не является первой, в её начало нужно дописать три точки.

Чтобы сэкономить деньги на отправке телеграмм, Матроскин хочет разбить текст на как можно меньшее количество.

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

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

На вход подается строка из маленьких латинских букв и пробелов. Она не начинается и не заканчивается пробелами и никакие два пробела в ней не идут подряд. Длина строки не превышает 10000.

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

В первой строке выведите число $N$ – количество телеграмм, на которое надо разбить исходную строку. В следующих $N$ строках выведите сами телеграммы. Если текст передать заданным способом невозможно, выведите −1.

Примеры
Входные данные
deesecnj vmguhee xhled rrr dfjhj fdytiaf baulvovt kvhygzhv wfaocftf scugmcqsk wadi bjeiq coesxqgnry tmlko gpmwns rcf dtdey bvirmlv gzl bwuoio
Выходные данные
2
deesecnj vmguhee xhled rrr dfjhj fdytiaf baulvovt kvhygzhv wfaocftf scugmcqsk wadi bjeiq coesxqgnry tmlko gpmwns rcf dtdey bvirmlv gzl...
...bwuoio
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В деревне Простоквашино часть домов перестала пользоваться услугами бумажной почты, перейдя на электронную. Всего в деревне $N$ домов, из которых $M$ ещё не перешли на использование только электронной почты. Почтальон Печкин решил перенумеровать дома, которые все ещё пользуются бумажной почтой так, чтобы они имели номера с 1 по $M$. При этом Печкину не важно, что дома с соседними номерами не будут стоять рядом друг с другом. Поскольку почтальону не очень хочется запоминать новые номера для всех домов, в которые он ещё носит письма и телеграммы, он хочет перенумеровать только некоторые из них. Какое минимальное количество домов потребуется перенумеровать, чтобы они шли по порядку

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

В первой строке записаны два числа $N$ и $M$ ($1 \le M \le N \le 1000$) – количество домов в Простоквашино и количество тех домов, которые ещё пользуются услугами почтальона Печкина, соответственно. Во второй строке записано $M$ чисел $a_i$ , ($1 \le a_i \le N$) возрастающем порядке – номера домов, которые ещё используют бумажную почту.

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

В ответ выведите одно число – минимальное количество домов, которое потребуется перенумеровать.

Замечание

В приведенном примере дому, который имел номер 8, нужно дать номер 3. Тогда 5 домов, которые ещё используют бумажную почту, как раз будут иметь номера от 1 до 5.

Примеры
Входные данные
8 5
1 2 4 5 8
Выходные данные
1

Страница: 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест