e-olymp-7842. Четные индексы

Четные индексы

Задан массив из $n$ целых чисел. Выведите все его элементы с четными индексами. Нумерация начинается с $0$.

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

В первой строке записано число $n$. В следующей строке записано $n$ целых чисел. Все числа по модулю не превышают $100$.

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

Выведите все элементы массива с четными индексами.

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

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

1 7
14 16 3 7 17 19 9
14 3 17 9
2 4
12 15 21 9
12 21
3 8
12 80 67 58 5900 473 78 64
12 67 5900 78

Решение

Вводим число $n$ — количество чисел в потоке. Как видим, эту задачу можно решить без объявления массива, просто во время ввода чисел проверяем индекс введенного числа и если индекс четный, то выводим введенное число.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

e-olymp 8956. Вывести массив 4

Задача

Задан массив из [latex]n[/latex] целых чисел. Выведите только его отрицательные элементы, изменив первоначальный порядок на противоположный.

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

Первая строка содержит число [latex]n (1 \leqslant n \leqslant 100)[/latex]. Во второй строке записаны [latex]n[/latex] целых чисел, каждое из которых не превышает по модулю [latex]100[/latex].

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

В первой строке выведите количество отрицательных элементов массива. Во второй строке выведите сами отрицательные элементы в обратном порядке. Если отрицательных элементов в массиве нет, то выведите [latex]«NO»[/latex].

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 7
-2 5 4 -3 7 -1 0
3
-1 -3 -2
2 5
2 1 0 1 5
NO
3 3
-1 -2 -3
3
-3 -2 -1

Код программы

Решение задачи

Для решения этой задачи, прежде всего, необходимо объявить две целочисленные переменные ― [latex]n[/latex] и [latex]count[/latex]. Переменная [latex]n[/latex] считывает первое число в строке ввода, и после объявления некоторого массива arr[n], она становится значением числа его элементов. Переменной [latex]count[/latex] обязательно присваиваем значение [latex]0[/latex], ведь именно она позднее будет отвечать за подсчет отрицательных элементов заданного массива.

С помощью цикла for задаем массив, начиная с нулевого элемента и заканчивая [latex]n[/latex]-ым элементом (не включительно!). Внутри цикла размещаем условный оператор if, который прибавляет единицу к переменной count каждый раз, когда элемент массива отрицателен. После окончания цикла важно не забыть о еще одном условном операторе, который будет выводить [latex]«NO»[/latex] и заканчивать работу программы, если значение [latex]count[/latex] равно нулю (то есть именно в том случае, если в массиве не будет ни одного отрицательного элемента). Но если в массиве всё же есть отрицательные элементы, то программа должна продолжить работу, что мы и предусматриваем, выполняя все остальные операции в рамках оператора else. Отлично! Теперь полученное значение переменной [latex]count[/latex] (если оно больше нуля) можно вывести, однако это еще не конец, ведь также необходимо вывести все отрицательные элементы в обратном порядке, так что переходим на новую строку с помощью endl и продолжаем.

Реализация подобной процедуры не так сложна, как кажется. Для этого необходимо создать еще один цикл for, перебирающий массив с конца (то есть от [latex]n-1[/latex] до [latex]0[/latex] включительно). Внутри цикла вновь создаем условный оператор if, который каждый раз выводит элемент массива (с пробелом), если он оказывается отрицательным. Не забываем закрыть скобку оператора else, ведь эта процедура также выполняется внутри условного оператора.

Готово!

e-olymp 8666. Коровий котильон

Задача

В коровьем котильоне — причудливом танце весны — участвуют коровы (обозначаются $ «\gt»$) и быки (обозначаются $ «\lt»$), они кланяются друг другу во время танца. Схематически обозначим пару кланяющихся животных следующим образом: $ «\gt \lt»$. Иногда вторая пара скота может находиться между кланяющейся парой: $ «\gt \gt \lt \lt»$.

Иногда и большее количество коров и быков встречается на танцевальной площадке: $ «\gt \gt \lt \lt \gt \lt»$ (имеется вторая пара кланяющихся коров справа). Сложные аранжировки могут быть совершенно легальными танцевальными образованиями:

Фермер Джон замечает, что бездомная корова иногда пробирается в группу и разбалансирует ее: $ «\gt \gt \lt \lt \lt \lt»$. Это строго запрещено; Фермер Джон хочет наказать нарушителей.

Фермер Джон скопировал данные о том, как $500$ коров участвуют в танцевальной линии, и задался вопросом, правильно ли уравновешена танцевальная линия (то есть весь скот может быть спарен как минимум одним способом чтобы правильно кланяться друг другу). Он скопировал только направление, в котором кланялась каждая корова, без каких-либо лишних пробелов, чтобы можно было определить, какая корова какому быку кланяется. Строки похожи на пример из предыдущего абзаца: «>><&lt». Фермер Джон хочет чтобы Вы написали программу, определяющую правильность танцевальной линии.

Фермер Джон имеет $n$ записей танца $P_{i}$ состоящих из символов $ «\gt»$ и $ «\lt»$;’ различной длины $K_{i} (1 \leqslant K_{i} \leqslant 200)$. Выведите «legal» для тех строк, которые содержат правильные пары кланяющихся коров и «illegal» иначе.

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

Первая строка содержит одно число $n$ $(1 \leqslant n \leqslant 1000)$. Каждая из следующих $n$ строк содержит число и строку из $K$ символов $ «\gt»$ и $ «\lt»$: $K_{i}$и $P_{i}$.

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

Выведите в каждой строке «legal» или «illegal» в зависимости от того, содержит ли соответствующая входная строка допустимую конфигурацию.

Тесты

Входные данные Выходные данные
1 2
6 >><<><
4 ><<>
legal

illegal

2 3
8 <>><><><
6 ><>><<
9 >><>><<><
illegal
legal
illegal
3 5
4 ><><
10 >>><<>><<<
8 >><<<>><
3 >><
12 ><>><>>><<<<
legal
legal
illegal
illegal
legal

Код

 

Решение

Пара начинается с коровы и каждой из них должен соответствовать один бык, стоящий после неё. Для того, чтобы проверить правильность танцевальной линии, будем фиксировать количество встречающихся коров, а при встрече быка это число уменьшать. Отрицательное значение показывает на наличие быка без пары. В таком случае баланса уже не будет и проверять дальше смысла нет.  В случае конечного результата $0$, в линии соблюден баланс — у каждого есть своя пара.

Ссылки

e-olymp 8674. Игра

Задача

Мурад и Ибрагим играют в следующую игру. Изначально дается число $1$. На своем ходу каждый игрок должен умножить текущее число на одно из целых чисел от $2$ до $9$ включительно. Цель состоит в том, чтобы получить число не меньше заданного целого числа $n$. Игрок, получивший такой номер первым, объявляется победителем. Мурад всегда начинает первым. Выясните, кто победит, если Мурад и Ибрагим будут играть оптимально.

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

Первая строка содержит одно число $t$ $(1 \leqslant t \leqslant 2500)$ — количество тестов. Каждая из следующих $t$ строк содержит одно целое число $n$ $(2 \leqslant n \leqslant 10^9)$.

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

Для каждого теста выведите в отдельной строке $1$, если Мурад выиграет игру, и $2$ иначе.

Тесты

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

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

1 4
9
10
1149729
999999999
1
2
2
1
2 3
6
163
1234567
1
2
2
3 3
42
100
1000
1
1
1

 

Код программы

Решение с циклом для каждого отдельного теста:

 

Решение без цикла для каждого отдельного теста:

 

Решение

Для начала заметим, что победит тот игрок, чей ход выпадет на число из промежутка $[\frac{n}{9},n)$, так как любое число из этого промежутка можно умножить на соответствующее целое число из $[2,9]$ и получить число не меньшее чем $n$. Назовем такой промежуток «зеленой зоной» (в общем виде будет $[\frac{2n}{18^k},\frac{n}{18^{k-1}})$, $k \in \mathbb {N}$). Тогда очевидно, что проиграет тот игрок, чей ход выпадает на число из промежутка $[\frac{n}{18},\frac{n}{9})$, так как при умножении числа из этого промежутка на любое целое число из $[2,9]$, приводит к тому, что получается число из «зеленой зоны». Назовем такой промежуток «красной зоной» (в общем виде будет $[\frac{n}{18^k},\frac{2n}{18^k})$, $k \in \mathbb {N}$). Получаем, что промежуток $(0,n)$ делится на «красные» и «зеленые зоны». Тогда задача сводится к нахождению вида «зоны» в которой находится $1$.

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

Рассмотрим цепочку неравенств (учитывая, что $2 \leqslant n$ ):  $$\lfloor \log _{18} n \rfloor \leqslant \log _{18} n \leqslant \lceil  \log _{18} n \rceil$$

$$ 18^{\lfloor \log _{18} n \rfloor} \leqslant n \leqslant 18^{\lceil  \log _{18} n \rceil}$$

$$\frac{1}{18^{\lceil  \log _{18} n \rceil}} \leqslant \frac{1}{n} \leqslant \frac{1}{18^{\lfloor \log _{18} n \rfloor}}$$

$$\frac{n}{18^{\lceil  \log _{18} n \rceil}} \leqslant 1 \leqslant \frac{n}{18^{\lfloor \log _{18} n \rfloor}}$$

Из общего вида «красной зоны» видно, что левый ее конец это число вида $\frac{n}{18^k}$, значит $\frac{n}{18^{\lceil  \log _{18} n \rceil}}$ является левым концом «красной зоны», обозначим его как $l$. Тогда, $2l$ будет правым концом «красной зоны» исходя из её общего вида. Из полученного неравенства видно, что $1$ лежит между левыми концами соседних «красных зон». Получаем, что если $2l \leqslant 1$, то единица лежит в «зеленой зоне», а иначе — в «красной».

Ссылки

Условие задачи на e-olymp

Решение с циклом для каждого отдельного теста на ideone

Решение без цикла для каждого отдельного теста на ideone

e-olymp 6388. Муха Фон-Неймана

Задача

Следующая задача была предложена Джону Фон-Нейману:

Два велосипедиста [latex]a[/latex] и [latex]b[/latex] начинают поездку навстречу друг другу в одно и то же время с мест, находящихся на расстоянии [latex]250[/latex] друг от друга, [latex]a[/latex] движется со скоростью [latex]10[/latex] миль в час, [latex]b[/latex] движется со скоростью [latex]15[/latex] миль в час. В это же время муха взлетает с колеса велосипедиста [latex]a[/latex] и движется навстречу к [latex]b[/latex], затем разворачивается и летит обратно. Пока велосипедисты приближаются друг к другу, муха продолжает летать между ними, касаясь каждый раз переднего колеса велосипедистов, пока, наконец, не будет раздавлена колесами встретившихся велосипедов. Так как муха летает быстрее каждого из велосипедистов, она совершает бесконечное количество полетов, при этом пройдя конечное расстояние (бесконечный ряд сходится). Какое расстояние пролетела муха?

Фон-Нейман немедленно вычислил бесконечный ряд (в уме!), и получил верный ответ: [latex]200[/latex] миль.

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

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

Первая строка содержит количество тестов [latex]p (1 \leqslant p \leqslant 1000)[/latex].

Каждый тест состоит из одной строки, содержащей пять чисел: номер теста [latex]n[/latex] и четыре действительных числа: начальное расстояние между велосипедистами [latex]d (10 \leqslant d \leqslant 1000)[/latex], скорость первого велосипедиста [latex]a (1 \leqslant a \leqslant 30)[/latex] в милях в час, скорость второго велосипедиста [latex]b (1 \leqslant b \leqslant 30)[/latex] в милях в час и скорость мухи [latex]f (a \leqslant b < f \leqslant 50)[/latex] в милях в час.

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

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

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5
1 250 10 15 20
2 10.7 3.5 4.7 5.5
3 523.7 15.3 20.7 33.3
4 1000 30 30 50
5 500 15 15 25
1 200.00
2 7.18
3 484.42
4 833.33
5 416.67

Код программы

Решение задачи

Безусловно, многие ознакомленные с курсом математического анализа люди (или же юные подражатели Фон-Неймана) после ознакомления с условием задачи мгновенно подумали о сумме сходящегося бесконечного ряда. Однако, если абстрагироваться от пестрых намеков содержания и попробовать мыслить менее глобально, можно прийти к куда более простому варианту решения. На самом деле под витиеватой формулировкой таится обыкновенная задача на движение с некоторым дополнительным фактором!

Согласно условию, велосипедисты [latex]a[/latex] и [latex]b[/latex] двигаются навстречу друг другу, а следовательно их скорость сближения (общая скорость) будет равна сумме скоростей каждого из велосипедистов: [latex]a + b[/latex]. По знакомой из школьного курса математики формуле [latex]S = V \times t[/latex] (тогда [latex]t = \frac { S }{ V }[/latex]), разделив расстояние между велосипедистами [latex]d[/latex] на их скорость сближения, найдем время [latex]t[/latex], спустя которое велосипедисты встретятся: [latex]t = d / (a + b)[/latex]. Муха, перелетающая с одного колеса на другое со скоростью [latex]f[/latex] достигнет момента своей погибели ровно тогда же, когда встретятся велосипедисты, то есть спустя то же время [latex]t[/latex]. Тогда, умножив скорость мухи на это время, то есть [latex]f\times t[/latex], получим расстояние [latex]flyDist[/latex], преодолённое мухой.
Для корректной реализации кода задачи сначала считываем количество тестов [latex]p[/latex], затем создаём цикл, внутри которого считываем все необходимые для вышеописанных действий переменные, производим нужные вычисления и, с помощью функции cout.precision и замечания fixed, выводим номер теста и его результат с точностью до двух десятичных знаков.

Конечно, данную задачу можно решить и используя сумму ряда, однако этот способ получился бы намного более сложным и громоздким. Поэтому такое удивительное высказывание, скорее всего, было лишь тонкой шуткой остроумного Фон-Неймана. Сам же он мог решить задачу в уме простым путем, описанным выше, но назвать более сложный, чтобы удивить современников и последователей.

e-olymp 7841. Нечетные элементы

Условие

Задана последовательность из $n$ целых чисел. Выведите все ее нечетные элементы.

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

Первая строка содержит число $n$. Следующая строка содержит $n$ ($n$ $⩽$ $100$)  целых чисел, которые по модулю не превосходят $100$.

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

Вывести все нечетные элементы последовательности в том же порядке как они встречаются на входе.

Тесты

Входные данные Выходные данные
1 7
14 17 16 3 7 19 9
17 3 7 19 9
2 5
2 4 3 11 5
3 11 5

Код

Решение

Для решения задачи, проверим каждое число последовательности на четность.

Ссылки

  • Задача на e-olymp
  • Код программы на Ideone

e-olymp 9104. Плоская земля

Условие

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

Настало время урегулировать этот конфликт раз и навсегда. Вы путешествовали по всему земному шару и встречались с ведущими учеными Плоской Земли. Вместе Вы разработали блестящий план.

Ради противоречия предположим, что Земля — это сфера в трехмерном пространстве. Тогда, если предположить, что небо является бесконечной плоскостью в пространстве, такая Земля явно бросит на него тень! Эта тень была бы ортогональной проекцией Земли на небо. Поскольку в действительности на небе нет видимой тени, мы достигаем противоречия.

Осталось только выполнить расчеты. По заданным центру и радиусу Земли, а также уравнению небесной плоскости в виде [latex]ax + by + cz + d = 0[/latex] необходимо определить площадь ортогональной проекции Земли на небо. Обратите внимание, что в некоторых Ваших экспериментах Земля может пересекать небо — Вы не хотели бы вводить слишком много ненужных предположений, не так ли?

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

Первая строка содержит количество тестов [latex]n[/latex] [latex]\left(1\leqslant n\leqslant 10\right)[/latex]. Далее следует описание тестов.

Каждый тест описывается строкой, содержащей восемь целых чисел [latex] x, y, z, r, a, b, c, d [/latex]. Они обозначают координаты центра Земли, его радиус и уравнение неба соответственно. Все числа от [latex]1[/latex] до [latex]1000[/latex] включительно.

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

Для каждого теста выведите одно число: площадь проекции с не менее [latex]6[/latex] десятичными цифрами.

Тесты

Входные данные Выходные данные
1 1
2 3 5 7 1 2 4 8
153.938040026
2 2
2 3 5 7 1 2 4 8
4 5 3 9 2 6 8 10
153.938040026
254.469004941
3 3
2 3 5 7 1 2 4 8
4 5 3 9 2 6 8 10
23 45 87 8 100 200 65 89
153.938040026
254.469004941
201.06192983

Код программы

Решение

Для начала, определимся, чего от нас хотят авторы задачи.  По сути, самой важной частью условия является третий абзац, из которого мы узнаем, что Земля — сфера, а также, что ортогональная проекция Земли на небо — это тень от Земли на небесную плоскость. Но, если существует тень, значит существует и светило (Солнце). Для того, что бы стало более понятно, проведём эксперимент. Представим, что Земля — это, к примеру, сфера, Солнце — это настольная лампа (Важно! Лампа будет давать параллельный пучок лучей), а небесная плоскость — это обычный лист бумаги. (Важно! В данном эксперименте размеры светила и размеры «Земли» будут совпадать). При направлении света на сферу, на лист бумаги будет отбрасываться тень (площадь которой нам и надо найти). Итак, как мы видим на рисунке, площадь проекции — это ничто иное, как площадь сечения сферы, проходящее по центральной оси этой сферы. А площадь сечения сферы по центральной оси — это площадь круга, которая вычисляется по формуле [latex]S=\pi r^2[/latex]. Таким образом, что бы рассчитать площадь проекции, из всех входящих данных нам понадобится только радиус Земли. Что бы у нас было число [latex]\pi[/latex], мы подключаем библиотеку cmath. Чтобы вывести число с [latex]6[/latex] десятичными знаками после запятой, подключаем библиотеку iomanip .

e-olymp 1327. Ладьи на шахматной доске

Задача

Ещё в детстве маленького Гарика заинтересовал вопрос: а сколькими способами на шахматной доске размером [latex]n \times n[/latex] можно расставить [latex] n [/latex] ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

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

Размер шахматной доски — натуральное число, не превышающее [latex] 1000 [/latex].

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

Выведите ответ, найденный Гариком.

Тесты

Входные данные Выходные данные
2 2
10 3628800
500 122013682599111006870123878542304692625357434280319284219241
358838584537315388199760549644750220328186301361647714820358
416337872207817720048078520515932928547790757193933060377296
085908627042917454788242491272634430567017327076946106280231
045264421887878946575477714986349436778103764427403382736539
747138647787849543848959553753799042324106127132698432774571
554630997720278101456108118837370953101635632443298702956389
662891165897476957208792692887128178007026517450776841071962
439039432253642260523494585012991857150124870696156814162535
905669342381300885624924689156412677565448188650659384795177
536089400574523894033579847636394490531306232374906644504882
466507594673586207463792518420045936969298102226397195259719
094521782333175693458150855233282076282002340262690789834245
171200620771464097945611612762914595123722991334016955236385
094288559201872743379517301458635757082835578015873543276888
868012039988238470215146760544540766353598417443048012893831
389688163948746965881750450692636533817505547812864000000000
000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000
999 402387260077093773543702433923003985719374864210714632543799
910429938512398629020592044208486969404800479988610197196058
631666872994808558901323829669944590997424504087073759918823
627727188732519779505950995276120874975462497043601418278094
646496291056393887437886487337119181045825783647849977012476
632889835955735432513185323958463075557409114262417474349347
553428646576611667797396668820291207379143853719588249808126
867838374559731746136085379534524221586593201928090878297308
431392844403281231558611036976801357304216168747609675871348
312025478589320767169132448426236131412508780208000261683151
027341827977704784635868170164365024153691398281264810213092
761244896359928705114964975419909342221566832572080821333186
116811553615836546984046708975602900950537616475847728421889
679646244945160765353408198901385442487984959953319101723355
556602139450399736280750137837615307127761926849034352625200
015888535147331611702103968175921510907788019393178114194545
257223865541461062892187960223838971476088506276862967146674
697562911234082439208160153780889893964518263243671616762179
168909779911903754031274622289988005195444414282012187361745
992642956581746628302955570299024324153181617210465832036786
906117260158783520751516284225540265170483304226143974286933
061690897968482590125458327168226458066526769958652682272807
075781391858178889652208164348344825993266043367660176999612
831860788386150279465955131156552036093988180612138558600301
435694527224206344631797460594682573103790084024432438465657
245014402821885252470935190620929023136493273497565513958720
559654228749774011413346962715422845862377387538230483865688
976461927383814900140767310446640259899490222221765904339901
886018566526485061799702356193897017860040811889729918311021
171229845901641921068884387121855646124960798722908519296819
372388642614839657382291123125024186649353143970137428531926
649875337218940694281434118520158014123344828015051399694290
153483077644569099073152433278288269864602789864321139083506
217095002597389863554277196742822248757586765752344220207573
630569498825087968928162753848863396909959826280956121450994
871701244516461260379029309120889086942028510640182154399457
156805941872748998094254742173582401063677404595741785160829
230135358081840096996372524230560855903700624271243416909004
153690105933983835777939410970027753472000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000

Программный код

Алгоритм решения

Алгоритм решения данной задачи заключается в том, что нужно вычислить [latex]n! = 1\times 2\times 3\times \cdots\times n [/latex] , используя длинную арифметику ( умножение длинного числа на короткое ).
Иллюстрация для восьми ладей:

В коде № 1 разбиваем вектор на ячейки по три цифры. Но, некоторые ячейки могут иметь менее чем три цифры. С учетом того, что перенос может состоять не из трех цифр, следует выводить результат так: cout << setw(3) << setfill('0') << res[i];.
В коде № 2 разбиваем строку посимвольно.

Детали реализации

  • Безусловно, для использования векторов и строк нам понадобятся соответствующие  библиотеки: #include <vector> и #include <string>.
  • Для вывода данных в коде № 1 стоит подключить библиотеку #include <iomanip>.

Ссылки :
Задача на e-olymp
Код № 1 на ideone
Код № 2 на ideone
Засчитанное решение № 1
Засчитанное решение № 2

e-olymp 6387. Острова в потоке данных

Задача

Задана последовательность целых чисел $a_{1}, a_{2}, a_{3}, \ldots, a_{n}$. Островом в последовательности называется набор последовательно идущих чисел, каждый из которых больше элементов, находящихся перед и после самой подпоследовательности. В приведенных ниже примерах каждый остров в последовательности обозначен внизу скобкой. Скобка острова, который находится в другом острове, находится под соответствующей скобкой.

prb6387

Напишите программу, на вход которой поступает последовательность из $15$ неотрицательных целых чисел, где каждое число отличается от предыдущего не более чем на $1$, и выводит количество островов в последовательности.

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

Первая строка содержит количество тестов $p \ (1 \leqslant p \leqslant 1000)$.

Каждый тест состоит из одной строки. Она содержит номер теста $k$, за которым следует $15$ неотрицательных целых чисел, разделенных пробелом. Первое и последнее число последовательности равны $0$. Каждое число отличается от предыдущего не более чем на $1$.

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

Для каждого теста вывести в отдельной строке его номер $k$, пробел, и количество островов в последовательности.

Тесты

Входные данные Выходные данные
1 4
1 0 0 1 1 2 2 1 1 0 1 2 2 1 1 0
2 0 1 2 3 4 3 2 1 2 3 4 3 2 1 0
3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
4 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0
1 4
2 7
3 7
4 7
2 3
1 0 1 2 3 2 1 0 1 2 3 4 3 2 1 0
2 0 0 1 2 2 2 1 1 1 0 0 1 1 0 0
3 0 1 1 1 2 2 2 2 3 4 3 2 2 1 0
1 7
2 3
3 4
3 6
1 0 1 2 2 2 3 4 5 6 5 4 3 2 1 0
2 0 1 0 0 0 0 1 1 1 0 1 2 1 1 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0
5 0 1 0 1 2 1 0 1 2 2 2 1 0 0 0
6 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0
1 6
2 4
3 0
4 7
5 5
6 2

Код

Решение

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

Ссылки

e-olymp 6260. Организация соревнования

Задача

Маленькие Дима и Петя хотят организовать соревнование. Их маленькие друзья выслали им несколько задач. Теперь Дима и Петя должны выбрать несколько задач для соревнования. Поскольку они еще маленькие, то не могут оценить качество задач, однако они знают что в хорошем контесте заглавия первой задачи начинаются с буквы $ A $ , заглавия второй задачи — с буквы $ B $ и так далее.

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

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

Первая строка содержит одно число $ n $ — количество предложенных задач, полученных маленькими братьями  [latex](1 \leqslant n \leqslant 100)[/latex]

Следующие $ n $ строк содержат заглавия предложенных задач, по одной в строке. Длина каждого заглавия не превосходит $ 30 $  символов. Каждое заглавие начинается с заглавной буквы и содержит буквы только латинского алфавита, цифры и символы подчеркивания.

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

Вывести одно число — наибольшее возможное количество задач в хорошем соревновании. Если хорошего соревнования устроить нельзя, вывести $0$.

Тесты

Входные данные Выходные данные
1. 10
Use
Algorithm_of
Branch
Chill
Cout_Hello_World
General
Duck
Ping_pong
Pong_ping
End
5
2. 4
Spasibo_tebe
John_von_Neumann
Za
Nuli_i_edunichki
0
3. 6
All
Sample
Simple
Games_of_mind
Google
Bee
2
4. 7
Andreev_Borys
Borys_Andreev
C_P_P
Demo_version
E_Olymp
Fraction
General
7

Код

Объяснение

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

Алгоритм решения задачи:

  1. Создаем массив.
  2. Читаем строку циклом и определяем первую букву.
  3. Кладем первую букву в массив, если разница отлична от нуля.

Ссылки

e-olymp 124. Квадрат

Условие задачи

Найдите периметр и площадь квадрата.

Входные данные:
Каждая строка является отдельным тестом и содержит одно целое число — длину стороны квадрата $n$ (1 $\leqslant$ $n$ $\leqslant$ 1000).

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

Тесты

Входные данные Выходные данные
1 3
5
10
12 9
20 25
40 100
2 3
3
3
12 9
12 9
12 9
3 1000
1
500
4000 1000000
4 1
2000 250000

Код

Решение

У нас дана сторона квадрата $n$.

  • Находим периметр квадрата, используя формулу $P = 4n$.
  • Находим площадь квадрата, используя формулу $S = n^{2}$.
  • Так как каждая новая строка — новое значение для стороны квадрата и таких строк неизвестное количество то используем while (cin >> n) для потоковой обработки данных.

Ссылки

  • Задача на сайте e-olymp
  • код решения Ideone

e-olymp 566. Письмо почтальона Печкина

Задача

Дорогие ребята!
Наблюдая за тем, как Шарик распиливал нестандартную шахматную доску, я также решил задать для вас задачку: “А сколько разных квадратных и прямоугольных (не считая квадратных) досок мог бы получить при распиливании Шарик из найденной им нестандартной прямоугольной шахматной доски размером $M\times N$?”

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

В первой строке количество заданий Печкина $K$, в последующих $K$ строках по два целых числа $M$ и $N$ $(1 \leqslant K, M, N \leqslant 100)$, разделённых пробелом.

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

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

Тесты

Входные данные Выходные данные
1. 1
3 2
8 10
2. 2
4 4
2 2
30 70
5 4
3. 4
3 3
25 46
100 100
1 1
14 22
12350 338975
338350 25164150
1 0

Код программы

Объяснение

Ответом на каждый запрос будет количество квадратов и прямоугольников которые можно получить из нашей шахматной доски размера $M\times N$. Для вычисления количества квадратов нам надо посчитать, сколько квадратов каждого возможного размера поместится в нашей шахматной доске. Аналогично для прямоугольников. Пример с доской $3\times 2$ разобран на картинке.

Пояснение к первому тесту

Для подсчёта квадратов, нам следует отдельно считать их количество для каждого возможного размера.  Таким образом сначала идут квадраты $1\times 1$, то есть $M\cdot N$ квадратов. Далее, квадратов $2\times 2$ помещаются ровно на $1$ меньше горизонтально и на $1$ меньше вертикально, значит получаем $(M-1)\times (N-1)$. Соответственно, $(M — 2)\times (N — 2)$ для квадратов $3\times 3$. И так продолжаем пока квадрат помещается в нашу доску.

Аналогично мы поступаем и с прямоугольниками. Однако считая количество прямоугольников каждого размера, нам нужно считать сколько поместится прямоугольников размера $(1\times 1), (1\times 2)\dots (1\times N)$. Также $(2\times 1), (2\times 2)\dots (2\times N)$. И так до $(M\times 1), (M\times 2)\dots (M\times N)$. Это довольно просто реализовать используя вложенный цикл.

Не стоит забывать, что квадрат — тот же прямоугольник, но с равными сторонами и в нашем цикле мы считаем все прямоугольники. А так как квадраты мы не должны учитывать, то после нахождения числа прямоугольников, нам нужно вычесть из него количество квадратов. В коде после нахождения и вывода числа квадратов, мы домножили это число на $(-1)$ и и уже после прибавили к нему количество прямоугольников, таким образом не учитывая квадраты.

Ссылки

Условие на e-olymp.

Код на ideone.

 

e-olymp 4142. Большой XOR

Задача

Для заданного целого $x$ найти количество таких $a$, удовлетворяющих условию:

  • $ a $ xor $x > x $
  • $ 0 < a < x $

где $a$ и $x$ — целые, xor — битовый XOR оператор.

Имеются $q$ запросов, каждый из которых содержит целое число $x$. Для каждого запроса выведите общее количество значений $a$, удовлетворяющих условиям выше.

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

Первая строка содержит число запросов $q$ $(1 \leqslant q \leqslant 10^5)$. Каждая из следующих $q$ строк содержит значение $x$ $(1 \leqslant x \leqslant 10^{10})$.

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

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

Тесты

Входные данные Выходные данные
1 2
2
10
1
5
2 3
13
3
16
2
0
15
3 5
1
7
4294967295
42
451
0
0
0
21
60

Код

Решение

XOR выдаёт число, биты которого равны $1$, когда лишь у одного из чисел соответствующий бит равен $1$. Числа большие чем $x$ получаем лишь тогда, когда $2^{k}\leqslant a<2^{k+1}$, где $k$- номер бита числа $x$, который равен нулю. Таких $a$ существует $2^k$ штук для каждого такого бита.

  • Задача на e-olymp
  • Код программы на ideone
  • Засчитанное решение
  • e-olymp 6261. Устройство для анализа бюллетеня

    Задача

    Избирательная комиссия Флатландии готовится к президентским выборам. Чтобы свести к минимуму человеческий фактор при подсчете голосов, они решили разработать автоматическое устройство для анализа бюллетеней (УАБ).

    На пост президента баллотируются $n$ кандидатов. Бюллетень содержит одно квадратное поле для каждого кандидата. Избиратель должен отметить ровно одно из полей. Если поле не помечено или имеется два или более отмеченных поля, бюллетень недействителен. Каждый избиратель ставит свой бюллетень на специальный сканер в УАБ. Сканер анализирует отметки в бюллетене и создает специальную строку голосования из $n$ символов: ‘X’ для отмеченного поля и ‘.’ для немаркированного. Теперь строки голосования должны быть проанализированы, чтобы получить отчет. Ваша задача — разработать генератор отчетов для УАБ.

    С учетом строк голосования для всех бюллетеней Ваша программа должна распечатать отчет о голосовании. Кандидаты в протоколе должны быть расположены в порядке убывания количества голосов. Если два кандидата имеют одинаковое количество голосов, они должны иметь тот же порядок, что и в бюллетене для голосования. Для каждого кандидата рассчитайте его / ее результат в процентах (если кандидат получил p голосов, результат в процентах составляет $ \frac{100p}{m}$ ). В последней строке отчета должен быть указан процент недействительных бюллетеней.

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

    Первая строка содержит два целых числа $n$ и $m (2 \leqslant n \leqslant 10, 1 \leqslant m \leqslant 1000$) — количество кандидатов и количество бюллетеней. Следующие $n$ строк содержат фамилии кандидатов. Каждое имя представляет собой строку не более 100 английских букв. Нет ни одного кандидата с именем «Invalid».

    Затем следуют $m$ строк, каждая из которых содержит одну строку голосования.

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

    Выведите $n+1$ строк. Сначала выведите результаты для кандидатов в процентах. Для каждого кандидата выведите его / ее фамилию, затем пробел, а затем его / ее результат в процентах и знак процента ‘%‘. В последней строке должен быть указан процент недействительных бюллетеней: слово «Invalid», за которым следуют пробел, процент недействительных бюллетеней и знак процента.

    Округлите все числа до двух цифр после десятичной точки. Если число находится точно посередине двух представимых чисел, выведите большее (например, выведите «12.35» для 12.345).

    Тесты

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

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

    1 4 7
    Loudy
    Apples
    Dogman
    Miller
    .X..
    X…
    ….
    ..X.
    ..XX
    ..X.
    ..X.
    Dogman 42.86%
    Loudy 14.29%
    Apples 14.29%
    Miller 0.00%
    Invalid 28.57%
    2 4 10
    Loudy
    Apples
    Dogman
    Miller
    X………………..
    X…………………..
    X………………
    X………………….
    X…………..
    x………………………..
    X……………….
    X……………
    X..x
    xxxx
    Loudy 70.00%
    Apples 0.00%
    Dogman 0.00%
    Miller 0.00%
    Invalid 30.00%

    Код программы

    Решение

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

    Ссылки

    Условие задачи на e-olymp

    Код программы на ideone

    e-olymp 972. Сортировка времени

    Задача

    Отсортируйте время согласно заданному критерию

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

    Сначала задано число $n\, \left ( 1\leqslant n\leqslant 100 \right )$, а затем n моментов времени. Каждый момент времени задается 3 целыми числами — часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60)

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

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

    Тесты

    Входные данные Выходные данные
    1 [latex]\begin{matrix}
    4 & & \\
    10 &20 &30 \\
    7 &30 &00 \\
    23&59 &59 \\
    13&30 &30
    \end{matrix}[/latex]
    [latex]\begin{matrix}
    7 & 30 &00 \\
    10&20 &30 \\
    13&30 &30 \\
    23& 59 & 59
    \end{matrix}[/latex]
    2 $\begin{matrix}
    6\\
    12 &55 &59 \\
    8 &33 &34 \\
    6 &56 &46 \\
    10 &23 &52 \\
    3 &20 &00 \\
    19 &31 &0\\
    10&23&52
    \end{matrix}$
    $\begin{matrix}
    3 &20 &0 \\
    6 &56 &46 \\
    8 &33 &34 \\
    10 &23 &52 \\
    12 &55 &59 \\
    19 &31 &0
    \end{matrix}$

    Решение

    Создадим 4 массива где мы будем хранить время(отдельно часы, минуты, секунды), а также четвертый в котором мы будем хранить все время в одной удобной для нас единице измерения — секундах. Читаем поток ввода и переводим полученные данные, сравниваем их потом сортируем полученные результаты и выводим ответ.

    Ссылки

    e-olymp
    ideone

    e-olymp-751. Клад

    Условие

    Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: «Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, …, наконец десять шагов в сторону большого булыжника. Клад находится под ним«. Большая часть таких указаний просто сводится к прохождению какого-то количества шагов в одном из восьми направлений ([latex]1[/latex] – север, [latex]2[/latex] – северо-восток, [latex]3[/latex]– восток, [latex]4[/latex] – юго-восток, [latex]5[/latex] – юг, [latex]6[/latex] – юго-запад, [latex]7[/latex] – запад, [latex]8[/latex] – северо-запад) (см. рис). Длина шага в любом направлении равна 1. Путешествие по такому пути обычно является прекрасным способом посмотреть окрестности, однако в наше время постоянной спешки ни у кого нет времени на это. Поэтому кладоискатели хотят идти напрямую в точку, где зарыт клад. Например, вместо того, чтобы проходить три шага на север, один шаг на восток, один шаг на север, три шага на восток, два шага на юг и один шаг на запад, можно пройти напрямую, использовав около 3.6 шага (см. рис).

    prb751

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

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

    Первая строка входного файла содержит число [latex]N[/latex] – число указаний $(1 ≤ N≤ 40)$. Последующие [latex]N[/latex] строк содержат сами указания – номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.

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

    В выходной файл выведите координаты [latex]X[/latex] и [latex]Y[/latex] точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось [latex]Ox[/latex] направлена на восток, а ось [latex]Oy[/latex] – на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с точностью [latex]10^{-3}[/latex].

    Тесты

    Ввод Вывод
    1 6
    1 3
    3 1
    1 1
    3 3
    5 2
    7 1
    3.000 2.000
    2 1
    8 10
    -7.071 7.071

    Код программы

    Решение

    Как видно из рисунка направление 1 совпадает с осью [latex]y[/latex], а 3 — с осью [latex]x[/latex]. Допустим, направление — переменная [latex]dir[/latex], а шаг-[latex]z[/latex]. Тогда, для направления 1 можно записать $y=z\cdot\cos((45^0)\cdot(dir — 1))$ , $x=z\cdot\sin((45^0)\cdot(dir-1)) $. Выражение $\cos((45^0)\cdot(1-1))=\cos(0^0)=1$ , то есть для 1 направления [latex]y=z[/latex], а выражение $\sin((45^0)\cdot(dir-1))=\sin((45^0)\cdot(1-1))=0 $. Следовательно, для направления 1 координаты [latex]y[/latex] и [latex]x[/latex] принимают значения: [latex]y=z[/latex], а [latex]x=0[/latex] .Рассмотрите значения приведенных выражений для всех направлений и увидим, что для всех направлений можно применить данные выражения для вычисления координат. А это позволяет сократить код программы.

    Ссылки

    e-olymp 8358. Среднее значение — 1

    Задача. Среднее значение — 1

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

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

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

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

    Средний вес учеников школы без учета учеников с самым большим и самым маленьким весом. Ответ выводить с точностью до килограмм.

    Тесты

    Ввод Вывод
    1 40 23 27 59 68 23 84 27 53 46 46
    2 21 22 23 24 25 26 27 28 20 30 29 25
    3 10 20 10 20 10 20 10 20 11 11
    4 60 45 70 90 55 62
    5 80 80 80 70 83 90 90 90 81
    6 50 90 70 70 70 70 70 70 70 70 74 70
    7 70 70 70 70 70 70 70 70 70 70 70 70 70 60 50 90 69

    Решение

    Считываем все числа, считаем их количество и сумму. Затем из количества вычитаем количество минимальных и максимальных значений, а из суммы их соответственные произведения на эти числа.

    Код через потоковую обработку

    Код через vector

    Код через map

    e-olymp 497. Лентяй

    Задача

    Студент Валера являет собой классический пример лентяя. На занятия он практически не ходит, и только в конце семестра появляется в университете и сдает ”хвосты”. Его заветная мечта: найти такой день, когда можно будет сдать сразу все долги. У него есть расписание работы преподавателей, из которого точно известно, с какого и по какой день месяца каждый преподаватель ежедневно будет доступен. Помогите Валере написать программу, которая по расписанию будет определять, сможет ли Валера сдать все долги за один день или нет.

    Входные данные:
    Первая строка содержит количество тестов. Каждый тест состоит из количество предметов $n$ $(1 \le n \le 100)$, которые нужно сдать Валере. Далее идет $n$ строк, каждая из которых состоит из двух чисел $a$ и $b$ $(1 \le a \le b \le 31)$, задающих интервал работы очередного преподавателя.

    Выходные данные:
    Для каждого теста вывести в отдельной строке "YES" если возможно встретить всех преподавателей за один день, или "NO", если это невозможно.

    Тесты

    Входные данные Вывод программы
    2
    1
    1 2
    2
    1 2
    3 4
    YES
    NO
    1
    1
    5 6
    YES
    2
    2
    1 4
    7 9
    3
    1 30
    2 5
    5 10
    NO
    YES

    Continue reading

    e-olymp 928. Сумма наибольшего и наименьшего

    Задача

    Задан массив целых чисел. Определить сумму наименьшего и наибольшего элементов массива.

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

    В первой строке задано количество элементов массива [latex]n[/latex] ([latex]n \leq 100[/latex]). Во второй строке заданы [latex]n[/latex] элементов массива, значение каждого из которых по модулю не превышает [latex]100[/latex].

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

    Вывести сумму наименьшего и наибольшего элементов массива.

    Тесты

    # ВХОДНЫЕ ДАННЫЕ  ВЫХОДНЫЕ ДАННЫЕ
    1 4
    1 2 3 4
    5
    2 5
    2 4 6 8 5
    10
    3 6
    6 2 4 5 7 9
    11
    4 7
    7 5 4 6 8 16 1
    17
    5 5
    16 20 65 34 86
    102

    Код программы

    Решение задачи

    Для решения задачи достаточно воспользоваться условными операторами внутри цикла. В данном цикле проверяем каждое число из заданного массива на минимум и максимум. Затем суммируем переменные.

    Ссылки

    e-olymp 2375. Квартира

    Задача

    Вы являетесь одним из разработчиков программного обеспечения для агентства недвижимости. Вам следует реализовать различные статистические функции для квартир, которые продает агентство. Каждая квартира состоит из различных типов комнат: спальня, ванная комната, кухня, балкон и другие. Стоимость квартиры равна произведению уменьшенной общей площади и стоимости одного квадратного метра. Уменьшенной общей площадью считается общая площадь всех помещений кроме балконов плюс половина площадей всех балконов.
    Вам будет предоставлена информация о площади каждой комнаты в квартире и стоимость одного квадратного метра. Необходимо рассчитать следующие значения для квартиры:

    • общую площадь комнат;
    • общую площадь всех спален;
    • стоимость квартиры.

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

    Первая строка содержит два целых числа [latex]n [/latex] [latex](1 \leqslant n \leqslant 10)[/latex] и [latex]c[/latex] [latex](1 \leqslant c \leqslant 100000)[/latex] — количество комнат в квартире и стоимость квадратного метра соответственно. Каждая из следующих [latex]n[/latex] строк содержит целое число [latex]a_i (1 \leqslant a_i \leqslant 100)[/latex] и слово [latex]t_i[/latex] — площадь [latex]i[/latex]-ой комнаты и ее тип соответственно. Слово [latex]t_i[/latex] может содержать только одно из следующих значений: [latex] «bedroom»[/latex], [latex] «bathroom»[/latex], [latex] «kitchen»[/latex], [latex] «balcony»[/latex], [latex] «other»[/latex].

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

    Первая строка содержит одно целое число — общую площадь всех комнат квартиры. Вторая строка содержит одно целое число — общую площадь всех спален в квартире. Третья строка содержит одно действительное число — стоимость квартиры с точностью не больше [latex]10^{-6}[/latex].

    Следующий рисунок отображает план квартиры, заданной в первом примере.

    Тесты

    Входные данные Выходные данные
    1 6 75000 46
    8 other 16
    3 bathroom 3187500.000000
    2 bathroom
    10 kitchen
    16 bedroom
    7 balcony
    2 2 75123 25
    10 kitchen 0
    15 balcony 1314652.500000
    3 4 110000 41
    7 other 18
    4 bathroom 4510000.000000
    12 kitchen
    18 bedroom

    Решение задачи

    Считываем данные из потока. При этом используем цикл for(int i=1; i=n; i++). Общую площадь квартиры рассчитываем по формуле S += ai. Площадь спален вычисляем по формуле Ss += ai, учитывая, что ti=="bedroom". Для дальнейшего вычисления стоимости квартиры вычисляем площадь балконов по формуле Sb += ai, учитывая, что ti=="balcony". Стоимость квартиры рассчитываем по формуле Ck=(S-Sb/2.)*c.

    Ссылки

    e-olymp
    ideone