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 908. Те, что делятся на 6

Задача: Те, что делятся на 6

Для [latex]N[/latex] целых чисел определить сумму и количество положительных чисел, которые делятся на 6 без остатка.

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

В первой строке задано количество чисел [latex]N[/latex]$\left(1 \leq N \leq 100\right)$, в следующей строке через пробел заданы сами числа, значения которых по модулю не превышают $10000$.

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

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

Тесты

Ввод Вывод

3

12 15 18

2 30
4

-10 -15 42 -24

1 42
2

6 0

1 6
3

-6 -12 -32

0 0

Решение

Заводим 2 переменные: сумму и количество. Каждый раз, когда мы читаем число, проверяем положительно ли оно и делится ли на 6 (Обычно желательно сначала проверять наимение вероятное условие, т.к. программа реже будет лишний раз проверять второе условие и, как следствие, сделает меньше действий, но в этой задачи это особой роли не играет из-за малого ввода), если оба условия выполняются, добавляем к счетчику 1, а к сумме введенное число. По окончанию ввода выводим сумму и количество через пробел.

Ссылки

e-olymp 1509. Раздел королевства.

Задача


Король страны Геометрии в заботах. У него есть три сына, которые постоянно ссорятся. Король применял разные методы примерения, но все напрасно. И это его очень беспокоило.

«А что если разделить королевство?» подумал король. Он пригласил советников и описал свой план. Король открыл карту.

Королевство имеет форму треугольника с вершинами [latex]A, B, C[/latex]. Король провел линию от [latex]B[/latex] к [latex]E[/latex] ([latex]E[/latex] — произвольная точка на отрезке [latex]AC[/latex]) и линию от [latex]C[/latex] к [latex]F [/latex]([latex]F[/latex] — произвольная точка на отрезке [latex]AB[/latex]). Пересечение [latex]BE[/latex] и [latex]CF[/latex] обозначено через [latex]X[/latex].

Теперь образовалось четыре части — [latex]a[/latex] (треугольник [latex]BFX[/latex]), [latex]b[/latex] (треугольник [latex]BCX[/latex]), [latex]c[/latex] (треугольник [latex]CEX[/latex]) и [latex]d[/latex] (четырехугольник [latex]AEXF[/latex]). Король решил отдать области[latex] a[/latex], [latex]b[/latex], [latex]c[/latex] трем сыновьям. А область [latex]d[/latex] станет новым королевством.

Вы — главный советник. Король сообщает Вам значения [latex]a, b, c[/latex]. Вам необходимо найти значение [latex]d[/latex]. Если его найти невозможно, то сообщить об этом.

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

Состоит из не более чем [latex]1000[/latex] тестов. Каждый тест содержит три неотрицательных действительных числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] (разделенных пробелом). Входные данные заканчиваются тестом у которого [latex]a = -1[/latex] и он не обрабатывается.

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

Для каждого теста вывести его номер, начиная с [latex]1[/latex]. В следующей строке вывести [latex]d[/latex] (величина области королевства после раздела) округленное до [latex]4[/latex] десятичных знаков или ‘Poor King!’ (без кавычек) если значение [latex]d[/latex] определить невозможно. Формат выходных данных показан в примере.

Тесты

Входные данные Выходные данные
1 1 2 1 Set 1:
2.0000
2 2 4 2 Set 2:
4.0000
3 1 3 3 Set 3:
5.0000
4 -1 0 0

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


 

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


Для решения задачи соединим точки  [latex]F[/latex] и [latex]E[/latex] линией. Получили два треугольника: [latex]d1[/latex] и [latex]d2[/latex]. Искомую площадь [latex]d[/latex] будем искать как сумму площадей [latex]d1[/latex] и [latex]d2[/latex]. Треугольники [latex]BFO[/latex] и [latex]EFO[/latex] имеют общее основание [latex]FO[/latex]. Следовательно их площади [latex]d1[/latex] и [latex]a[/latex] относятся как высоты, опущенные из вершин [latex]E[/latex] и [latex]B[/latex] на прямую [latex]FO[/latex]. Аналогично треугольники [latex]BCO[/latex] и [latex]ECO[/latex] имеют общее основание [latex]OF[/latex]. Значит их площади [latex]c[/latex] и [latex]b[/latex] относятся как высоты, опущенные из вершин [latex]E[/latex] и [latex]B[/latex] на прямую [latex]CO[/latex]. То есть $\frac{d_1}{a}=\frac{c}{b}$. Отсюда $d_1=\frac{ac}{b}$. Теперь рассмотрим треугольники [latex]CAF[/latex] и [latex]CBF[/latex] с основаниями [latex]AF[/latex] и [latex]BF[/latex]. Они имеют одинаковую высоту, опущенную из вершины [latex]С[/latex] на прямую [latex]AB[/latex]. Следовательно площади этих треугольников относятся как длины сторон [latex]AF[/latex] и [latex]BF[/latex]. Аналогично треугольники [latex]EAF[/latex] и [latex]EBF[/latex] имеют основания [latex]AF[/latex] и [latex]BF[/latex]. Они имеют одинаковую высоту, опущенную из вершины [latex]E[/latex] на прямую [latex]AB[/latex]. Площади этих треугольников относятся как длины сторон [latex]AF[/latex] и [latex]BF[/latex]. Тогда $$\frac{AF}{BF}=\frac{S_{\blacktriangle} CAF}{S\blacktriangle CBF}=\frac{c+d_1+d_2}{a+b}$$. $$\frac{AF}{BF}=\frac{S\blacktriangle EAF}{S\blacktriangle EBF}=\frac{d_2}{a+d_1}$$. Следовательно $\frac{c+d_1+d_2}{a+b}=\frac{d_2}{a+d_1}$. Поскольку [latex]d1[/latex] уже найдено, то имеем равенство с одним неизвестным [latex]d2[/latex] : $$d_2=\frac{(c+d_1)(a+d_1)}{b-d_1}$$. Если [latex]b \leqslant d1[/latex], то решения не существует.

Ссылки

  • Условие задачи на e-olymp
  • Код программы на ideone

e-olymp 7368. Средний балл для фигуристов

Задача взята с сайта e-olymp

Задача

Спортсменам-фигуристам [latex]n[/latex] судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей[latex]\left( 0 \lt n \leqslant 10, 0 \lt m \leqslant 100 \right)[/latex] для каждого из фигуристов.

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

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

Тесты

#   ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5 4
7 8 9 8 10
6 5 5 4 7
9 9 10 7 7
7 7 10 9 8
8.33 5.33 9.00 8.50
2 3 4
1 2 3
3 5 2
7 1 6
9 8 3
2.00 3.00 6.00 8.00
3 10 2
1 2 3 4 5 6 7 8 9 10
1 1 1 2 2 2 3 3 3 4
5.50 2.50

Код программы (Потоковая обработка)

Решение

Читая каждую оценку:

  1. Добавляем оценку к общей сумме;
  2. Если введенная оценка равна минимальной, то добавляем ее к сумме минимальных и увеличиваем счётчик количества минимальных.
  3. Если введенная оценка меньше минимальной, то минимальной становится введённая оценка. Счетчик количества минимальных равен [latex]1.[/latex] Сумма минимальных равна введённой оценке.
  4. Если введенная оценка равна максимальной, то добавляем ее к сумме максимальных и увеличиваем счётчик количества максимальных.
  5. Если введенная оценка больше максимальной, то максимальной становится введённая оценка. Счетчик количества максимальных равен [latex]1.[/latex] Сумма максимальных равна введённой оценке.

Тогда после введения всех [latex]n[/latex] оценок имеем:

  •  [latex]sumMax[/latex] — сумма максимальных оценок.
  •  [latex]sumMin[/latex] — сумма минимальных оценок.
  •  [latex]countMax[/latex] — количество максимальных оценок.
  •  [latex]countMin[/latex] — количество минимальных оценок.
  •  [latex]sumGl[/latex] — общая сумма оценок.

Для нахождения среднего арифметического значения оценок, соответствующего условию будем применять формулу:  [latex]S_с = \frac{sumGL-sumMin-sumMax}{n-countMin-countMax}[/latex]

Код программы (Массивы)

Решение

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

Ссылки

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

Код программы на ideone (Потоковая обработка)

Код программы на ideone (Массивы)

e-olymp 113. Шарики

Задача

У продавца воздушных шариков есть [latex]n[/latex] шаров. Каждый из них имеет некоторый цвет. Однако совсем недавно Три Толстяка издали указ, разрешающий торговать шариками какого-то одного цвета. Чтобы не нарушать закон, но при этом и не потерять прибыль, продавец решил перекрасить некоторые из своих шариков.

Напишите программу для определения минимального количества перекрашиваний.

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

В первой строке задано количество шаров [latex]n (1\leqslant n \leqslant 100000)[/latex]. Вторая строка состоит из [latex]n[/latex] целых чисел, в пределах от 1 до 9, определяющие цвета шаров (1 — синий, 2 — зеленый, 3 — голубой, 4 — красный, 5 — розовый, 6 — желтый, 7 — серый,8 — черный, 9 — белый).

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

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

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 4  3 1 2 1 2
2 1 1 0
3 6 1 1 1 2 2 2 3
4 3 1 2 3 2
5 4 3 3 3 8 1

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

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

Для того, чтобы найти количество шариков, которые необходимо перекрасить, нужно узнать максимальное количество шариков одного цвета и из общего количества шариков n вычесть найденный максимум. Для нахождения максимума считываем номер цвета шара в цикле и увеличиваем соответствующую переменную cl на единицу. По окончанию цикла ищем максимальное количество шаров одного цвета и выводим n-max.

Ссылки

e-olymp 8524. Сумма положительных в матрице

Задача взята с сайта e-olymp

Условие

Задана матрица размера [latex]n\times n[/latex]. Найдите сумму ее положительных элементов.

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

Первая строка содержит число [latex]n[/latex] [latex]\left(1 \leq n \leq 100 \right)[/latex]. Следующие строки содержат матрицу [latex]n\times n[/latex]. Элементы матрицы по модулю не больше [latex]100[/latex].

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

Выведите сумму положительных элементов матрицы.

Тесты

Inputs Outputs
1 3
4 -2 5
1 -4 -12
0 1 -3
11
2 4
-4 -2 -5 -7
-1-14 -4 -12
-12 -1 -3 -53
0
3 3
0 0 0
0 1 0
0 0 0
1
4 0 0
5 5
89 76 54 32 33
46 57 89 40 32
12 45 63 78 65
13 76 54 89 67
13 67 89 90 43
1412

Код

Решение

В условии сказано, что задана матрица размера [latex]n\times n[/latex], тогда вводов тоже будет, соответственно, [latex]n\cdot n[/latex]. В цикле ввода используется условный оператор для проверки на то, положительно число или нет.

Ссылки

e-olymp 914. Модуль максимального

Задача взята с сайта e-olymp

Задача

Задана послідовність дійсних чисел. Обчислимо їх модулі. Знайдіть максимальне значення серед цих модулей.

Вхідні дані

У першому рядку задано кількість елементів $n\left(n  \leqslant 100  \right)$ у послідовності. У наступному рядку задано $n$ дійсних чисел — елементи послідовності, значення яких не первищують за модулем 100.

Вихідні дані

Виведіть максимальне значення серед цих модулей з 2 десятковими знаками.

Тести

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 0 -1 1 1.00
2 3
-1.1 1.2 -1.3
1.30
3 5
5.16 0 -7.18 3 4.99
7.18
4 4
-75.111 7.5 -5.1 75.110
75.11
5 10
-1 -2 -3 -4 -5 -6 -7 -8 -9 1
9.00

Решение

Задача сходиться до пошуку максимального елемента послідовності. Зрозуміло, що найменше можливе значення модуля числа — 0. Тому, считуючи дані зі вхідного потоку будемо порівнювати їх зі змінною, що  дорівнює 0. Якщо значення модуля числа більше за змінну — надаємо змінній значення модуля числа. Таким чином після завершення вхідного потоку змінна буде дорівнювати найбільшому числу послідовності за модулем.

  • Зараховане рішення на e-olymp
  • Код задачі на ideone

e-olymp 441. Наиболее круглое число

Задача

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

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

В первой строке входных данных задано количество чисел [latex]N (1 \leqslant N \leqslant 100)[/latex]. Каждая из последующих [latex]N[/latex] строк содержит одно число в пределах от [latex]1[/latex] до [latex]10^9[/latex].

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

Вывести наиболее круглое число среди заданных [latex]N[/latex] чисел.

Тесты

Ввод Вывод
1 3
600000
1000
20000
600000
2 4
71200
10
200
10001
200
3 6
19
3
4580004
26
8302
5
3
4 4
32900
23090
20309
23900
23900

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

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

Основная цель задачи — среди a чисел выбрать то, которое будет иметь наибольшее число нолей в конце и при этом быть наименьшим среди чисел с таким же количеством ноле в конце. Заводим переменные max_number, value, local_number. Первая будет обозначать максимальное число нолей в конце. Вторая будет значением числа с максимальным количеством нолей. Третья же, как следует из её названия, означает локальное количество нолей, то есть того числа, с которым непосредственно идёт работа. Сперва считаем количество нолей в конце числа или, вернее, его копии, которую мы будем делить на десять, пока «крайняя» справа цифра равна 0. Число нолей будет равно числу проделанных делений. После имеет смысл рассматривать два случая: когда количество нолей введенного последним числа больше максимального и когда значения равны. В первом изменяются и максимум max_number, и само число value, получая значения соответственно количества нолей последнего введенного числа и его самого, если локальное число нолей больше максимального. Во втором же только value, если число из потока оказывается меньше и имеет то же кол-во нолей; в этом случае изменять max_number просто не имеет смысла.
В итоге выводим наиболее круглое число — value.

Ссылки

e-olymp 31. Суеверный Дед Мороз

Задача

Как известно, в разные годы дежурят и развозят подарки разные Деды Морозы. Но все они суеверны — развозят подарки на протяжении всего года, кроме дней, когда на календаре Деда Мороза «Пятница 13».

Сколько дней Дед Мороз не развозил подарки во время своего дежурства?

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

В первой строке задано количество смен $k$ дежурства Деда Мороза.

Далее в k строках указаны года $a$ и $b$ ($1920 ≤ a ≤ b ≤ 2050$ по григорианскому календарю), попадающие на очередную смену.

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

Вывести количество дней, когда Дед Мороз не будет развозить подарки.

Тесты

Ввод Вывод
1 2
1999 2000
1991 1997
13
2 3
1939 1945
1937 1938
1953 1964
37
3 3
1993 1996
2007 2017
1979 1981
32
4 4
1997 1999
1967 1972
2032 2032
1930 1933
24
5 4
1959 1960
1965 1966
1991 2011
1947 1959
63

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

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

Сперва стоит сказать, что полный цикл чередования лет с пятницей 13 в одни и те же месяца — 28 лет. Всего в году их может быть от 1 до 3. Всего в этих 28 годах будут 4 года с тремя пятницами 13 и по 12 с одной и двумя.
Все решение задачи сводится сводится к тому, чтобы посчитать количество пятниц 13 в каждом году данного нам отрезка времени. Создадим два массива — c2 и c3 — каждый будет содержать остатки от деления лет, содержащих 2 и 3 пятницы 13 соответсвенно, на 28. Все прочие остатки от деления «достанутся» годам, в которых 1 пятница 13; отдельный массив для них, очевидно, смысла создавать нет.
Сначала, по условию, вводим число смен и после в цикле года очередной смены. Для каждого года из отдельной смены считаем количество пятниц 13 путём проверки в соответствующих массивах остатка от деления этого года на 28. Если его нет в двух массивах, то, очевидно, в этом году всего одна пятница 13 и мы прибавляем к счетчику пятниц counter 1. Если все-таки есть, то прибавляем 2 или 3 в зависимости от того, в каком массиве нашлось необходимое число. В конце выводим значение счётчика.
Отметим, что задача решается и без использования массивов, но в таком случае придётся проверить остаток от деления каждого года на 28 на равенство числам, которые в данном случае находятся в массивах.

Ссылки

код на ideone
условие задачи на e-olymp

e-olymp 904. Увеличить на 2

Задача

Задана последовательность целых чисел. Увеличить на $2$ каждый ее неотрицательный элемент.

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

В первой строке задано количество элементов последовательности $n(n ≤ 100).$ Во второй строке заданы сами элементы, значение каждого из которых по модулю не превышает $100.$

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

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

Тесты

Входные данные Выходные данные
1 4
1 2 3 -4
3 4 5 -4
2 7
7 -3 4 -2 5 0 -1
9 -3 6 -2 7 0 -1
3 5
6 -12 28 -32 -1
8 -12 30 -32 -1
4 3
-2 -3 -4
-2 -3 -4

Код

Решение

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

Ссылки

e-olymp 1753. Младший бит

Задача

Для заданного положительного целого $A$ $(1 \leq A \leq 100),$ вывести младший бит $A$.

Например, если $A = 26$, то его мы можем записать в двоичном виде, как $11010$, и младший бит $A$ есть $10$, и на выходе должно быть $2.$

Другой пример выглядит следующим образом: при $A = 88$, это число $A$ мы можем записать в двоичной форме $1011000$, младший бит в $A$ есть $1000,$ и на выходе должно быть $8.$

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

Каждая строка входных данных содержит только одно целое число $A$ $(1 \leq A \leq 100).$ Строка, содержащая «0» означает конец ввода, и эта строка не является частью входных данных.

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

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

Тесты

Входные данные Выходные данные
 1 26
88
0
2
8
 2 99
45
66
20
1
1
2
4
 3 100
0
6
4
4 66
33
98
42
84
39
2
1
2
2
4
1

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

Решение

Объявляем переменную  a. Начинается цикл while, условием окончания которого будет введённая  a, неравная нулю. В цикле объявляем переменную  LSB = 1, после чего начинается новый цикл while, который сдвигает бит LSB  влево, пока выражение побитовой конъюнкции  a & LSB нулевое. Соответственно, как только выражение будет ненулевым — будет найден первый общий бит, который и будет младшим битом числа a. Его и выводим.

Ссылки

e-olymp 1325. Васькины дорожки

Задача. Васькины дорожки

Кот Василий узнал, что у соседа Димы, проживающего от него через какое-то количество заборов завелись мыши. Так как в своём хозяйстве всех мышей он уже давно выловил, кот отправляется на охоту за мышами к соседу, пролезая через дыры в ограде. На каждом участке Василий, как любой воспитанный кот, перемещается по уже проложенным там тропинкам. В деревне Старые Васюки, где проживает Василий, всего одна улица и та протянулась вдоль реки, поэтому домики расположены только по одну сторону улицы. Известно, что между любыми соседними участками в заборе ровно одна дыра. Сколькими способами Василий может попасть на участок Димы, если известно, что Дима проживает на участке под номером $k,$ а сам Василий проживает на участке под номером $m$?

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

В единственной строке находятся через пробел сначала количество домов в деревне $n,$ затем номер участка Василия $m,$ номер участка Димы $k,$ а далее $n$ чисел, обозначающее количество тропинок, ведущих либо к дыре в заборе, либо от дыры в заборе, либо между дырами в заборе соседей $i$ и $i+1.$ Все входные данные натуральные числа, не превышающие $10.$

 

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

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

Тесты

Ввод Вывод
1 3 2 3 4 5 3 15
2 10 5 7 1 2 3 4 5 6 7 8 9 10 210
3 4 2 1 3 4 7 8 12
4 10 8 8 1 9 6 7 5 3 8 2 4 10 2
5 1 1 1 1 1
6 10 1 10 1 1 1 1 1 1 1 1 1 10 10
7 7 5 3 2 2 2 4 4 4 5 32
8 10 1 10 10 10 10 10 10 10 10 10 10 10 10000000000
7 5 3 2 1 2 3 4 5 6 7 8 9 10 6

Решение

Что бы определить количество различных способов попасть на нужный участок мы должны, сначала, посчитать сколькими способами кот Василий может пересечь (по тропинкам) участок на котором он находится. Затем, для каждого из возможных вариантов пересечения первого участка посчитать сколькими способами Василий может пересечь второй участок и так далее, до заданного. Таким образом общее количество вариантов попасть, для нашего друга, из участка $m$ в участок $k$ является произведением количества вариантов пересечения каждого участка в отдельности.

Прочтём значения $n$, $m$ и $k$. Переменная rez будет хранить результат. В цикле от $1$ до наибольшего номера из участков Димы и Василия, будем проверять достигли ли мы наименьшего номера их участков. По достижении начинаем перемножать количества тропинок ведущих к дыркам в заборе. Мы можем это делать с начиная с любого из участков так как операция умножения коммутативна. Завершив цикл в переменной rez у нас уже будет правильный ответ. Выведем его.

Типа данных  unsigned long хватит по условию данной задачи, так как все числа натуральные, а значит большие $0$. И не превышают $10$, следовательно максимальное значение переменной  rez будет $10^{10}$ что помещается в unsigned long.

Код

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

Решение

Код на ideone

e-olymp 97. Числа Белла

Задача

Число Белла [latex]B_n[/latex] равно количеству разбиений множества из [latex]n[/latex] элементов на произвольное количество непересекающихся непустых подмножеств. Например, [latex]B_3 = 5[/latex], так как существует [latex]5[/latex] возможных разбиений множества [latex]\lbrace a, b, c\rbrace[/latex]: [latex]\lbrace\lbrace a\rbrace, \lbrace b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, c\rbrace, \lbrace b\rbrace\rbrace, \lbrace\lbrace a\rbrace, \lbrace b, c\rbrace\rbrace, \lbrace\lbrace a, b, c\rbrace\rbrace[/latex]. Дополнительно считаем, что [latex]B_0 = 1[/latex].
Рассмотрим определитель [latex]D_n[/latex]:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix}$$
Для заданного простого числа [latex]p[/latex] найти наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

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

Каждая строка ввода содержит два целых числа [latex]n[/latex] и [latex]p[/latex] ( [latex]\;0\leq\; n,\;p \;\leq\; 10000[/latex] ). Известно, что [latex]p[/latex] – простое.

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

Для каждой пары входных значений [latex]n[/latex] и [latex]p[/latex] в отдельной строке выведите наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

Тесты

Входные данные Выходные данные
1 5
3 2
4 2
4 3
10000 3
0
2
5
2
24962375
18 2
465 1009
9998 9221
548 11
134
0
778
14412
1093 1093
1103 1723
3931 617
4868 6113
9534 71
1
0
10635
0
639989
617 17
42 11
0 5
11295
63
0

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

 

Решение

Числа Белла обладают интересным свойством:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix} = \prod_{i=1}^n i! $$

Воспользуемся этим свойством для решения данной задачи. Найдём степень числа [latex]p[/latex] в разложении  на простые множители. Для этого узнаем степень вхождения этого числа в каждый из факториалов. Суммой полученных значений и будет являться искомое число [latex]k[/latex].

Ссылки

Условия задачи на e-olymp
Код задачи на ideone
Число Белла на wikipedia

e-olymp 441. Наиболее круглое число

Наиболее круглое число

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

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

В первой строке входных данных задано количество чисел [latex]N[/latex] [latex](1  ≤  N  ≤  100)[/latex]. Каждая из последующих N строк содержит одно число в пределах от [latex]1[/latex] до [latex]10^{9}[/latex].

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

Вывести наиболее круглое число среди заданных [latex]N[/latex] чисел.

Тесты

Входные данные Выходные данные
4
71200
10
200
10001
200
5
711
1
2
10001
234567
1
10
7
1
2
1
2
3
4
6
8
9
1
4
100000
200000
500000
800000
100000

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

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

Имеет смысл проверять каждое введенное число: не является ли оно меньше либо равно чем [latex]p[/latex], где [latex]p[/latex] — наименьшее число с количеством нулей равным [latex]maxk[/latex]. [latex]maxk[/latex] — текущее наибольшее количество нулей. Для того, чтобы найти [latex]p[/latex], мы в цикле умножаем [latex]1[/latex] [latex]maxk[/latex]-раз на [latex]10[/latex]. Очевидно, что [latex]p[/latex] нужно менять только тогда, когда меняется [latex]maxk[/latex], также следует до цикла полагать [latex]p=1[/latex]. Для того чтобы [latex]p[/latex] не умножалось на [latex]10[/latex] лишнее количество раз. Таким образом мы отсеиваем заведомо негодные числа и ускоряем код.
Положим [latex]maxn[/latex] — наиболее круглое число.
Так как по условию числа не могут быть больше чем [latex]10^{9}[/latex], имеет смысл изначально поставить переменную [latex]maxn=10^{9}[/latex]. Это делается для того случая, когда во всех числах [latex]m[/latex] не будет нулей и нужно будет выбрать наименьшее. Если мы положим в переменную [latex]maxn[/latex] любое другое число то [latex]maxn[/latex] может быть меньше чем [latex]m[/latex] и мы не сможем выбрать ответ так как все [latex]m[/latex] будут больше его.

Условие задачи на e-olimp
Код решения ideone

e-olymp 7368. Средний балл для фигуристов

Задача

Спортсменам — фигуристам [latex]n[/latex] судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей [latex](0 < n ≤ 10, 0 < m ≤ 100)[/latex] для каждого из фигуристов.

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

В одной строке вывести [latex]m[/latex] чисел с точностью до двух десятичных знаков — балл каждого спортсмена.

Тесты

# Входные данные Выходные данные
1 5 4
7 8 9 8 10
6 5 5 4 7
9 9 10 7 7
7 7 10 9 8
8.33 5.33 9.00 8.50
2 6 3
6 7 6 5 4 3
9 8 5 5 6 5
7 6 4 1 2 2
5.25 7.00 3.50
3 4 5
6 7 8 6
9 8 5 4
7 6 7 5
4 3 9 3
7 8 7 6
7.00 6.50 6.00 4.00 7.00
4 4 4
7 7 2 3
9 8 3 3
5 4 9 7
4 3 2 6
3.00 8.00 6.00 3.50
5 8 5
4 5 6 7 7 4 9 8
3 5 6 6 7 8 5 9
7 6 3 9 3 7 9 7
5 6 4 3 7 7 5 7
9 8 4 6 7 9 9 4
6.60 6.17 6.75 5.00 7.00

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

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

Для решения задачи нам необходимо изъять все минимальные и максимальные значения в каждой строчке. Переменные [latex]a[/latex] и [latex]b[/latex] — это количество вхождений максимума и минимума соответственно. Берем любой элемент строки, который обозначили переменной [latex]x[/latex], и будем считать, что он минимальный и максимальный. Далее сравниваем элементы между собой и находим максимум и минимум и подсчитываем их количество. Ещё нам необходимо посчитать сумму оставшихся значений, а также их количество по формуле [latex]n-a-b[/latex]. А затем вычисляем среднее арифметическое для оставшихся значений по формуле [latex]\frac{sum}{n-a-b}[/latex] и выводим результат.

Ссылка на e-olymp

Ссылка на ideone

e-olymp 419. Задача 3n + 1

Задача

Рассмотрим следующий алгоритм генерации последовательности чисел:

Например, для [latex]n[/latex] = 22 будет сгенерирована следующая последовательность чисел:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Полагают (но это еще не доказано), что этот алгоритм сойдется к [latex]n[/latex] = 1 для любого целого [latex]n[/latex]. По крайней мере, это предположение верно для всех целых [latex]n[/latex], для которых 0 < [latex]n[/latex] < 1,000,000.

Длиной цикла числа n будем называть количество сгенерированных чисел в последовательности включая 1. В приведенном примере длина цикла числа 22 равна 16.

Для двух заданных чисел [latex]i[/latex] и [latex]j[/latex] необходимо найти максимальную длину цикла среди всех чисел между [latex]i[/latex] и [latex]j[/latex] включительно.

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

Каждый тест задается в отдельной строке и содержит пару целых чисел [latex]i[/latex] и [latex]j[/latex]. Входные числа будут меньше 1000000 и больше 0. Считайте, что для вычислений достаточно использовать 32 битный целочисленный тип.

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

Для каждой пары чисел [latex]i[/latex] и [latex]j[/latex] выведите числа [latex]i[/latex] и [latex]j[/latex] в том же порядке, в каком они поступили на вход. После чего выведите максимальную длину цикла среди всех целых чисел между [latex]i[/latex] и [latex]j[/latex] включительно. Для каждого теста три числа следует выводить в отдельной строке, разделяя одним пробелом.

Тесты

Входные данные Выходные данные
1 10
100 200
201 210
900 1000
1 10 20
100 200 125
201 210 89
900 1000 174
1 10
10 1
1 10 20
10 1 20
5 25
70 54
38 250
5 25 24
70 54 113
38 250 128

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

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

Алгоритм, описанный в условии задачи используется для построения сиракузской последовательности. Интересный факт — какое бы число не взять, в конце получаем единицу. Нам же надо посчитать сколько раз должен сработать алгоритм для подсчитывания «длины цикла». Считывая пару чисел из потока ввода я высчитывал «длину цикла» для каждого числа из заданного введенной парой промежутка. После чего сравнивал количество итераций для каждого такого числа и находил максимальное. И так для каждой пары чисел.

Ссылки

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

e-olymp 520. Сумма всех

Сумма всех

Вычислите сумму всех заданных чисел.

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

Содержит [latex]n[/latex] [latex] (1 ≤ n ≤ 10^5) [/latex] целых чисел. Все числа не превосходят [latex]10^9[/latex] по абсолютной величине.

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

Выведите сумму всех заданных чисел.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]2[/latex] [latex]4[/latex] [latex]6[/latex]
2 [latex]3[/latex] [latex]3[/latex]
3 [latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex] [latex]9[/latex]
4 [latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex] [latex]10[/latex]
5 [latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex]

 

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

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

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

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

MS12. Линейные уравнения

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

Каждая пара чисел входного потока задает некоторое линейное уравнение. Выпишите через запятую решения этих уравнений (если это возможно).

Линейное уравнение

Линейное_уравнение

Тесты

Входные данные Выходные данные
1
0 0 1 0 0 1 Infinite set of roots;
0.0;
No roots;
2
2.02134 -0.52412 15.578 0 5.302 -89 -431.345 9.43 7 49 0.25929334006154336;
0.0;
16.786118445869484;
0.021861850722739336;
-7.0;
3
1 1 -6 -2 1 -2 10 0 -1.0;
-0.3333333333333333;
2.0;
0.0;

Код на языке C++

Код на языке Java

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

Линейное уравнение, зависящее от двух параметров, в общей форме имеет вид: [latex] ax + b = 0 [/latex]. Количество решений зависит от параметров [latex]a[/latex] и [latex]b[/latex].

Если [latex] a = b = 0 [/latex], то уравнение имеет бесконечное множество решений, поскольку [latex]\forall x\in \mathbb {R} :x\cdot 0=0[/latex].
Если [latex] a=0,b\neq 0[/latex], то уравнение не имеет решений, поскольку [latex] \not \exists x\in \mathbb {R} :0\cdot x=-b\neq 0[/latex].
Если [latex] a\neq 0[/latex], то уравнение имеет единственное решение [latex] x=-{\frac {b}{a}} [/latex].

Условие задачи.
Код программы на языке C++;
Код программы на языке Java.

e-olymp 1000. Задача a + b

Задача

Вычислите сумму [latex]\textbf {a + b}[/latex].

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

В каждой строке задано два целых числа [latex]\textbf{a}[/latex] и [latex]\textbf{b}[/latex] ([latex] \bigl| \textbf {a} \bigr|, \bigl| \textbf {b} \bigr| \textbf {≤ 30000}[/latex]).

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

Для каждого теста выведите сумму [latex]\textbf {a + b}[/latex] в отдельной строке.

Тесты

Входные данные Выходные данные
$4$ $8$
$5$ $0$
$-6$ $8$
$12$
$5$
$2$
$-3$ $3$ $0$
$12$ $8$
$10$ $10$
$20$
$20$
$30000$ $30000$
$3000$ $3000$
$300$ $300$
$30$ $30$
$3$ $3$
$60000$
$6000$
$600$
$60$
$6$
$10$ $23$
$613$ $2$
$-200$ $300$
$33$
$615$
$100$

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

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

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

Ссылки

Условие задачи на сайте E-Olymp
Код решения задачи

MS10. Зашифровка текста

Задача

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

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

Символьная последовательность.

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

Зашифрованная символьная последовательность.

Тесты

Входные данные Выходные данные
Where is the table? a8 c0 a5 d7 b2 92 fb 88 a8 dc b4 d1 f1 85 e4 86 ea 8f b0
What a nice day! a8 c0 a1 d5 f5 94 b4 da b3 d0 b5 95 f1 90 e9 c8

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

Решение

Выделяем участки памяти для символьных переменных, считываем первый символ и его инвертируем, затем выводим в шестнадцатеричной системе счисления с пробелом.
Используем цикл «while»: пока считываются данные в переменную x2, XORим предыдущий и новый символы, выводим новый символ и запоминаем новый зашифрованный символ, который становится предыдущим.

Ссылки

Условие задачи
Решение задачи на сайте Ideone.com