e-olymp 2061. Юные программисты

Задача 

Известно, что в школе не менее чем $k_{1}$учеников, но не более чем $k_{2}$ учеников. Также известно, что каждый мальчик дружит с $n$ девочками, а каждая девочка с $m$ мальчиками. Какое минимальное количество учеников может быть в школе, и сколько в школе мальчиков и девочек?

Юные программисты, как Вы видите, до сих пор решают эту задачку. Помогите им.

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

В первой строке входного файла находится $4$ числа, разделённых пробелами: $k_{1}$, $k_{2}$, $n$ и $m$. Все входные данные натуральные числа, не превышающие $10000$, $k_{1}\leq k_{2}$.

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

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

Тесты

Входные данные Выходные данные
20 30 4 5 27 15 12
5 10000 54 44 98 44 54
1 10000 100 100 200 100 100
1 2 1 1 2 1 1
100 120 2 3 100 60 40
50 50 25 25 50 25 25
9900 10000 99 56 9920 3584 6336
9999 10000 9998 2 10000 2 9998
101 110 2 3 105 63 42

Решение

Объяснение 

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

e-olymp

ideone

e-olymp 1452. Кролики

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

Задача

Как-то наконец земляне нашли обитаемую планету, назвали ее ТТВ, и отправили вместе с кораблем туда одного кролика. Кролику понравился климат новой планеты и через месяц он произвел на свет еще одного кролика. Известно, что каждый месяц каждый кролик, присутствующий на планете, производил на свет еще одного кролика. На планете откуда-то взялся монстр, который в начале месяца съедал [latex] k [/latex] кроликов, если только их становилось строго больше [latex] k [/latex]. В задаче необходимо определить количество кроликов, которое будет на планете через [latex] n [/latex]месяцев после прибытия туда космического корабля с первым кроликом.

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

Первая строка содержит количество месяцев [latex] n [/latex] [latex] (0 ≤ n ≤ 100) [/latex], вторая — число кроликов [latex] k [/latex] [latex]  (0 ≤ k ≤ 10000) [/latex], которое съедал монстр.

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

Определить количество кроликов, которое будет находиться на планете ТТВ через [latex] n [/latex] месяцев после поселения туда первого кролика. Известно, что результат для любого теста всегда не больше [latex] 2 \cdot 10^9 [/latex].

Тесты

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

1

0 10

1

2

1 10

2

3

10 7

128

4

7 128

12

5

30 0

1073741824

6

29 29

2

7

20 20

16

8

90 90

64

Cпособ 1 (с циклом)

Код

 

Решение

Известно, что изначально на планете был один кролик. Создадим цикл, который будет высчитывать популяцию кроликов на планете через [latex] n [/latex] месяцев после прибытия. Цикл будет работать до тех пор, пока количество месяцев будет больше нуля. В нем будем высчитывать популяцию кроликов по простой формуле [latex] r = r \cdot 2 [/latex], где [latex] r [/latex] — количество кроликов. Если же количество кроликов, съедаемых монстром в начале месяца строго больше того количества, которое уже есть на планете, то от этой популяции отнимем [latex]  k [/latex]кроликов : [latex] r = r[/latex] $-$ [latex] k [/latex]. Внутри цикла также не забываем от данного количества [latex] n [/latex] месяцев отнимать по одному каждый раз.

Способ 2 (без цикла)

Код

Решение

Сам алгоритм похож на 1 способ, однако здесь мы будем использовать рекурсивную функцию, а не цикл. Функция  int f2();  будет вызывать сама себя до тех пор, пока количество месяцев [latex] n [/latex] не станет равным нулю.

Ссылки

Засчитанное решение на e-olymp.

1 Код в ideone.

2 Код в ideone.

e-olymp 891. Покупка цветов

Задача. Покупка цветов

На День учителя Вася решил купить букет цветов. В магазине продаются ромашки по $a$ рублей за штуку и гладиолусы по $b$ рублей за штуку ($a < b$). У Васи есть $c$ рублей. Он хочет составить букет из максимально возможного количества цветов, и при этом потратить как можно больше денег. Другими словами, из всех букетов с максимально возможным количеством цветов он хочет выбрать самый дорогой, но не дороже $c$ рублей. Помогите ему вычислить стоимость такого букета.

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

Три целых числа $a$, $b$, $c$ ($1 ≤ a < b ≤ 100, 0 ≤ c ≤ 1000$).

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

Выведите одно число — стоимость самого дорогого букета из максимального количества цветов.

Тесты

Ввод Вывод
1 5 7 0 0
2 3 5 10 9
3 2 3 11 11
4 48 64 306 304
5 17 20 100 100
6 13 15 260 260
7 29 53 999 986
8 17 28 16 0
7 75 100 1000 1000

Решение

Рассмотрим частный случай. Если можно купить по минимальной цене ромашки так, что у нас не будет остатка, то полученное количество цветов будет максимальным и увеличить их стоимость будет невозможно. Значит ответом будет количество денег в кошельке у Васи.

Далее, что бы найти решение для оставшихся вариантов, необходимо найти наибольшую сумму стоимостей максимального количества цветов не превышающую $c$ рублей. Максимальное количество цветов n будет равно количеству цветов с минимальной стоимостью которое можно купить за имеющиеся у Васи деньги. ($c / a$).

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

Код

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

Решение

Код на ideone

e-olymp 8533. Числа с разными цифрами

Задача

Выведите все четырехзначные числа от $a$ до $b$, содержащие разные цифры.

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

Два целых числа $a$ и $b$ ([latex]1000 \le a \le b \le 9999[/latex]).

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

Выведите в одной строке все числа от $a$ до $b$ с разными цифрами.

Тесты

 Входные данные Выходные данные
 2000 2015  2013 2014 2015
 9875 9999  9875 9876
 1000 1234  1234
 3612 3612  3612
 8800 8888  Standart output is empty
 1000 1000  Standart output is empty

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

 

Решение

Для каждого числа из заданного промежутка [latex][a;b][/latex] выделяем его цифры и сравниваем их между собой. Искомые числа будут состоять из неравных между собой цифр.

Ссылки

Ideone

e-olymp

e-olymp 446. Ровные делители

Задача

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

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

Натуральное число $n \space (1 ≤ n ≤ 10^{6})$.

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

Выведите искомое количество ровных делителей числа $n$.

Тесты

Входные данные Выходные данные
5 1
20 2
200 6
653 1
5982 4

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

Решение

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

Ссылки

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

Строчная таблица

Задача

В тридесятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $1 \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Задача участников — начертить таблицу наименьшей высоты и вычислить ширину каждой ячейки. Алиса очень хочет победить, но она плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

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

Первая строка содержит натуральное число $n, \ (1 \leqslant n \leqslant 100).$ Вторая строка содержит $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

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

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

Тесты

Входные данные Выходные данные
$3$ $0.1333 \ 0.3333 \ 0.5333$
$2 \ 5 \ 8$
$6$ $0.0736 \ 0.2638 \ 0.3313 \ 0.0736 \ 0.1963 \ 0.0613$
$12 \ 43 \ 54 \ 12 \ 32 \ 10$
$2$ $0.3333 \ 0.6667$
$1 \ 2$
$3$ $0.3333 \ 0.3333 \ 0.3333$
$10 \ 10 \ 10$
$7$ $0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.2500$
$1 \ 1 \ 1 \ 1 \ 1 \ 1 \ 2$
$1$ $1.0000$
$2$
$4$ $0.5102 \ 0.1735 \ 0.2653 \ 0.0510$
$100 \ 34 \ 52 \ 10$
$2$ $0.9901 \ 0.0099$
$100 \ 1$
$6$ $0.0702 \ 0.2515 \ 0.3158 \ 0.0351 \ 0.1287 \ 0.1988$
$12 \ 43 \ 54 \ 6 \ 22 \ 34$
$2$ $0.5000 \ 0.5000$
$2 \ 2$
$10$ $0.0182 \ 0.0364 \ 0.0545 \ 0.0727 \ 0.0909 \ 0.1091 \ 0.1273 \ 0.1455 \ 0.1636 \ 0.1818$
$1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10$
$3$ $0.0098 \ 0.9804 \ 0.0098$
$1 \ 100 \ 1$

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

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

Пусть $h=\displaystyle\frac{1}{\gamma}$ — высота таблицы, а $x_1, \ x_2, \ \cdots, \ x_{n-1}, \ 1-x_1-x_2- \cdots -x_{n-1}$ – ширина каждой клетки. Тогда $\displaystyle\frac{x_1}{\gamma} \geqslant s_1, \ \displaystyle\frac{x_2}{\gamma} \geqslant s_2, \ \cdots, \ \displaystyle\frac{x_{n-1}}{\gamma} \geqslant s_{n-1}, \ \displaystyle\frac{1-x_1-x_2- \cdots -x_{n-1}}{\gamma} \geqslant s_n.$ Получаем $x_1 \geqslant s_1\gamma, \ x_2 \geqslant s_2\gamma, \ \cdots, \ x_{n-1} \geqslant s_{n-1}\gamma, \ 1-x_1-x_2- \cdots -x_{n-1} \geqslant s_n\gamma.$
Сделаем из неравенств равенства: $x_1=s_1\gamma+\varepsilon_1, \ x_2=s_2\gamma+\varepsilon_2, \ \cdots, \ x_{n-1}=s_{n-1}\gamma+\varepsilon_{n-1}.$
Имеем
$1-(s_1\gamma+\varepsilon_1)-(s_2\gamma+\varepsilon_2)- \cdots -(s_{n-1}\gamma+\varepsilon_{n-1}) \geqslant s_n\gamma \\
1 \geqslant (s_1+s_2+ \cdots +s_{n-1}+s_n)\gamma+\varepsilon_1+\varepsilon_2+ \cdots +\varepsilon_{n-1}
\\
\gamma \leqslant \displaystyle\frac{1-\varepsilon_1-\varepsilon_2- \cdots -\varepsilon_{n-1}}{s_1+s_2+ \cdots +s_{n-1}+s_n}.$
Максимальное значение $\gamma$ достигается при $\varepsilon_1=\varepsilon_2= \cdots =\varepsilon_{n-1}=0.$ Следовательно $\gamma \leqslant \displaystyle\frac{1}{s_1+s_2+ \cdots +s_{n-1}+s_n},$ а $h=s_1+s_2+ \cdots +s_{n-1}+s_n.$ Тогда ширина каждой ячейки будет равняться $\displaystyle\frac{s_i}{h}$

Ссылки

Код решения

e-olymp 2814. Быстрое возведение в степень.

Задача

Очень часто возникает задача эффективного вычисления xn по данным $x$ и $n$, где $n$ — положительное целое число.

Предположим, например, что необходимо вычислить $x^{16}$. Можно просто начать с $x$ и 15 раз умножить его на $x$. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя $x^{2}$, $x^{4}$, $x^{8}$, $x^{16}$.

Эта же идея, в целом, применима к любому значению $n$ следующим образом. Запишем $n$ в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую «1» парой символов SX, а каждый «0» — символом S и вычеркнем крайнюю слева пару символов SX. Результат представляет собой правило вычисления $x^{n}$, в котором «S» трактуется как операция возведения в квадрат, а «X» — как операция умножения на $x$. Например, $n = 23$ имеет двоичное представление $10111$. Таким образом, мы формируем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо «возвести в квадрат, возвести в квадрат, умножить на $x$, возвести в квадрат, умножить на $x$, возвести в квадрат и умножить на $x$», т.е. последовательно вычислить значения $x^{2}$, $x^{4}$, $x^{5}$, $x^{10}$, $x^{11}$, $x^{22}$, $x^{23}$.

Вам нужно для заданного n сформулировать соответствующее правило быстрого возведения числа $x$ в степень $x^{n}$

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

Одно натуральное число $n$, не превышающее $2 \cdot 10^{9}$.

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

Выведите строку для правила возведения числа $x$ в степень $n$ для получения $x^{n}$.

Тесты

# Входные данные Выходные данные
1 23 SSXSXSX
2 1
3 16 SSSS
4 1000000 SXSXSXSSXSSSSSXSSSXSSSSSS
5 2018 SXSXSXSXSXSSSSXS

Решение

Создаём две строки $s$ и $s1$ для двоичного представления числа $n$ и для правила нахождения числа $n$ соответственно. Далее мы проверяем $n$ на чётность, добавляя к строке $s$

  • $0$ при чётном $n$
  • $1$ при нечётном $n$

и делим $n$ на $2$. Продолжаем это пока $n \neq 0$. Таким образом мы получили двоичный код, записанный в обратном порядке от двоичного кода числа $n$. После мы присваиваем цифрам «0» и «1» соответственно «S» и «SX» справа налево (в порядке двоичного кода числа $n$). В конце, удаляем первые символы «SX» с помощью метода erase(), таким образом получая ответ

Условие задачи можно найти на e-olymp
Код решения — ideone

e-olymp 2817. Двоичные числа

Задача

Для заданного положительного целого числа $n$, распечатать позиции всех $1$ в двоичном его представлении. Позиция младшего бита имеет номер $0$.
Позиции $1$ в двоичном представлении числа $13$ — это $0$, $2$, $3$.
Напишите программу, которая для каждого набора данных:

  • читает натуральное число $n$,
  • вычисляет позиции $1$ в двоичном представлении $n$,
  • выводит результат.

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

В первой строке входного файла содержится одно натуральное число $d$, указывающее количество наборов входных данных, $1 \leq d \leq 10$. Входные данные заданы ниже.

Каждый набор данных состоит ровно из одной строки, содержащей ровно одно целое число $n$, $0 \leq n \leq 10^6$.

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

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

Строка $i$, $1 \leq i \leq d$, должна содержать возрастающую последовательность целых чисел, разделенных одним пробелом — позиции $1$ в двоичном представлении $i$-го числа, полученного во входных данных.

Тесты

 

Входные данные
Выходные данные
$3$
$17$
$7$
$5$
$0$ $4$
$0$ $1$ $2$
$0$ $2$
$4$
$1945$
$1337$
$1000000$
$999999$
$0$ $3$ $4$ $7$ $8$ $9$ $10$
$0$ $3$ $4$ $5$ $8$ $10$
$6$ $9$ $14$ $16$ $17$ $18$ $19$
$0$ $1$ $2$ $3$ $4$ $5$ $9$ $14$ $16$ $17$ $18$ $19$
$10$
$0$
$1$
$2$
$3$
$4$
$5$
$6$
$7$
$8$
$9$
$0$
$1$
$0$ $1$
$2$
$0$ $2$
$1$ $2$
$0$ $1$ $2$
$3$
$0$ $3$

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

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

Для решения этой задачи нужно понять, что остаток от деления $n$ на $2$ это последняя цифра в двоичном коде числа $n$, а деление целочисленной переменной $n$ на $2$ это отбрасывание последней цифры в двоичном коде. Цикл с счетчиком $i$ до момента, как $n$ не станет равняться $0$, очевиден, как и внешний цикл от $0$ до $d$, который реализовывает $d$ итераций ввода числа $n$. Стоит отметить, что тесты на e-olymp (все, кроме первого) чувствительны к пробелам в конце строки, из-за чего появляется необходимость каким-то образом его избежать.

Ссылки

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

e-olymp 1494. Санта Клаус

Задача

Санта Клаус

Санта Клаус

Санта Клаус готовится к Рождеству. В этот праздник он хочет вручить подарки [latex]n[/latex] детям. Его помощники Эльфы уже собрали два мешка, с которыми он отправится в новогоднее путешествие по всем странам мира. И чтобы Санта не запутался, Эльфы составили список детей, чьи подарки уже лежат в каждом из мешков. Санта хочет помочь Эльфам, и поэтому решил положить в третий мешок подарки для тех детей, которым они еще не подготовлены.

Помогите Санте, составьте список детей, чьи подарки надо положить в третий мешок.

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

Первая строка входного файла содержит три целых числа: [latex]n[/latex] — число детей, [latex]m[/latex] и [latex]k[/latex] — число подарков в первом и втором мешке соответственно [latex](1\leq n,\;m,\;k\leq 100;m+k\leq n)[/latex]. Вторая строка входного файла содержит [latex]m[/latex] целых чисел — номера детей, подарки для которых лежат в первом мешке. Третья строка входного файла содержит [latex]k[/latex] целых чисел — номера детей, подарки для которых лежат во втором мешке.

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

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

В первой строке выведите одно число [latex]a[/latex] — сколько подарков должно быть в третьем мешке. Во второй строке выведите в произвольном порядке [latex]a[/latex] чисел — номера детей, которым эти подарки должны быть доставлены.

Тесты

Входные данные Выходные данные
2 1 1
2
1
0
3 1 2
1
2 3
0
7 2 1
7 3
1
4
2 4 5 6
100 14 4
2 93 30 56 17 19 75 22 23 5 49 11 8 33
91 40 81 54
82
1 3 4 6 7 9 10 12 13 14 15 16 18 20 21 24 25 26 27 28 29 31 32 34 35 36 37 38 39 41 42 43 44 45 46 47 48 50 51 52 53 55 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 76 77 78 79 80 82 83 84 85 86 87 88 89 90 92 94 95 96 97 98 99 100
10 3 5
2 5 8
3 7 1 4 9
2
6 10
61 40 5
61 20 5
3 4 9 8 49 31 20 33 35 34 61 1 32 53 51 7 21 44 46 47
2 60 50 19 25
36
5 6 10 11 12 13 14 15 16 17 18 22 23 24 26 27 28 29 30 36 37 38 39 40 41 42 43 45 48 52 54 55 56 57 58 59
12 3 3
1 2 3
11 10 8
6
4 5 6 7 9 12

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

Решение

Создадим массив типа  bool , в котором каждому [latex]i[/latex]-ому ребёнку соответствует элемент с индексом [latex]i — 1[/latex], принимающий значение [latex]0[/latex], если для ребёнка ещё нет подарка, и [latex]1[/latex], если подарок уже имеется в одном из мешков. Далее, отмечаем детей, подарки для которых уже лежат в мешках. Наконец, выводим номера тех детей, подарки для которых не были найдены ни в одном из мешков.

Ссылки

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

e-olymp 338. Моя любимая, несократимая…

Задача

“Название задачи можно напевать на мотив марша или строевой песни…”

Сколько существует правильных несократимых дробей на промежутке [[latex]0[/latex]..[latex]1[/latex]], знаменатель которых не превышает [latex]n[/latex]?

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

Натуральное число [latex]n[/latex] ([latex]n < 10001[/latex]).

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

Вывести количество правильных несократимых дробей на промежутке [[latex]0..1[/latex]], знаменатель которых не превышает [latex]n[/latex].

Тесты

 

Входные данные Выходные данные
1 0
10000 30397485
5 9
80 1965
37 431
5168 8119803
9973 30237929

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

Для решения данной задачи вопользуемся функцией Эйлера [latex] \varphi (n)[/latex], равной количеству натуральных чисел, меньших [latex]n[/latex] и взаимно простых с ним. Очевидно, что количество правильных несократимых дробей со знаменателем [latex]n[/latex] равно [latex] \varphi (n)[/latex]. И тогда количество правильных дробей со знаменателем, не превыщающим [latex]n[/latex] равно [latex] \sum\limits_{i=2}^{n}{\varphi (n)}[/latex] (тут мы учли, что при [latex]i[/latex] = 1 знаменатель дроби равен 1 и дробь не будет правильной).

Ссылки

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

код задачи на Ideone

описание функции Эйлера на Wikipedia

e-olymp 842. Разложение на простые множители

Условие задачи
Вывести представление целого числа [latex] n [/latex] в виде произведения простых чисел.

Входные данные
Единственное число [latex] n [/latex] [latex] (2 ≤ n ≤ 2^{31} — 1). [/latex]

Выходные данные
Вывести список простых множителей в порядке не убывания, разделённых знаком [latex] «*» [/latex] .
Continue reading

e-olymp 1489. Шоколад

Задача

Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник $n \cdot m$, который полностью состоит из маленьких шоколадных долек — прямоугольников $2 \cdot 1$.

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

Помогите Пете поделиться шоколадкой с Машей.

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

В первой строке входного файла два целых числа $n$ и $m$ ($1 \le n, m \le 20$, хотя бы одно из чисел $n$ и $m$ — четно). Далее следуют $n$ строк по $m$ чисел в каждой — номера долек, в которые входят соответствующие кусочки шоколадки. Дольки имеют номера от $1$ до $\frac{n \cdot m}{2}$, и никакие две дольки не имеют одинаковые номера.

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

В выходной файл выведите «$Yes$», если Петя может разломать шоколадку, не повредив дольки. Иначе выведите «$No$».

TESTS

Входные данные Выходные данные
2 3
1 1 2
3 3 2
Yes
5 6
1 2 2 3 3 4
1 5 6 7 7 4
8 5 6 9 10 10
8 11 11 9 12 13
14 14 15 15 12 13
No
4 7
1 1 2 5 8 11 6
2 14 4 7 3 9 5
3 7 10 6 13 2 3
4 3 8 12 5 7 7
Yes

Код решения

 

Решение

Для решения данной задачи нужно представить шоколадку как двухмерный массив и проверить, можно ли разломать плитку шоколада ровно, то есть одинаковое ли количество «строк» и «столбцов» шоколада. Если так, то возвращается значение true, и false в обратном случае. Для этого были созданы функции BreakRow и BreakColumn с возвращаемым значением типа bool. Затем стоит проверить возвращаемое значение. Если одна из функций принимает значение true, то выводим положительный ответ. В противном случае ответ отрицательный.

Ссылки

Условие решения на e-olymp.com
Код решения на ideone.com

e-olimp 2864. Табулирование функции

Задача

Напишите программу, которая выводит на экран таблицу значений функции [latex]y = 3\sin\left(x\right) [/latex] на промежутке от [latex]a[/latex] до [latex]b[/latex] включительно с шагом [latex]h[/latex].

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

В одной строке через пробел заданы три вещественных числа [latex]a[/latex], [latex]b[/latex] и [latex]h[/latex].

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

В каждой строке выведите по два числа [latex]x[/latex] и [latex]y[/latex] соответственно, по возрастанию [latex]x[/latex] с тремя десятичными знаками.

Тесты

Входные данные Выходные данные
1 2 0.5 1.000 2.524
1.500 2.992
2.000 2.728
0 0 1 0.000 0.000
20 10 5 10.000 -1.632
15.000 1.951
20.000 2.739
-3 -1 1 -3.000 -0.423
-2.000 -2.728
-1.000 -2.524

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

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

Подключим модули cmath, чтобы использовать функцию синус, и iomanip, для установления точности ответа. Далее, с помощью цикла от [latex]a[/latex] до [latex]b[/latex] с шагом [latex]h[/latex] выведем на экран таблицу значений функции на заданном промежутке.

Ссылки

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

Код решения

e-olymp 622. Единицы

Единицы

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

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

Одно целое число [latex]n[/latex] [latex](0 ≤ n ≤ 2\cdot10^9)[/latex].

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

Вывести количество единиц в двоичной записи числа [latex]n[/latex].

Тесты

Входные данные Выходные данные
20 2
0 0
1 1
5 2
2000000000 13

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

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

Алгоритм заключается в последовательном делении заданного числа [latex]n[/latex] на [latex]2[/latex] и нахождении количества остатков от деления (по условию), равных единице. Полагаем начальное количество единиц [latex]k[/latex] равное нулю. Затем, нужно прибавить остаток от деления к имеющемуся у нас [latex]k[/latex]. Если остаток равен единице то мы получим [latex]k+1[/latex] что нам и требуется.

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

e-olymp 340. Раз – горох, два – горох…

Задача

Приближалась зима, и Хома с Сусликом решили запастись горохом. Весь день они бегали в амбар и таскали по несколько стручков: Хома по четыре, а Суслик по два. К вечеру они пересчитали все стручки, что они натаскали, и задумались, как теперь этот горох делить. Хома утверждал, что если он за раз тащил в два раза больше, чем Суслик, то и гороха ему должно достаться в два раза больше. Суслик на это резонно возражал, что, во-первых, скорость у Хомы заметно меньше, чем у Суслика, а, во-вторых, кто его знает, может Хома всего раз-два сбегал, а остальное время бездельничал…

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

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

В первой строке натуральное четное число [latex]M[/latex] – количество украденных стручков, [latex]2 ≤ M ≤ 1000[/latex].

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

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

Тесты

Входные данные Выходные данные
[latex]6[/latex] [latex] \\ 6 \; 0 \\ 2 \; 4[/latex]
[latex]11[/latex] [latex]\\ 11\;0 \\ 7\;4 \\ 3\;8[/latex]
[latex]18[/latex] [latex]\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16[/latex]

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

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

Пусть [latex]a[/latex] — количество стручков, принесенных Хомой и [latex]b[/latex] — количество стручков, принесенных Сусликом. Так как по условию задачи Хома таскал только по четыре стручка, мы будем считать [latex]a = a-4[/latex] и [latex]b = b + 4[/latex], чтобы таким образом перебрать все возможные сочетания количеств стручков, принесенных Сусликом и Хомой. Также воспользуемся циклом while, который будет повторять действие, описанное выше, до тех пор, пока [latex]a \geq 0[/latex]. В ответе выводим все возможные сочетания количеств стручков, принесенных друзьями по одному в строке, упорядоченные по убыванию первого числа.

Ссылки

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

e-olymp 9. N-значные числа

Задача

Найти количество [latex]N[/latex]-значных чисел, у которых сумма цифр равна их произведению. Вывести наименьшее среди таких чисел для заданного [latex]N[/latex] ([latex]N < 10[/latex]).

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

Число [latex]N[/latex] не превышающее [latex]10[/latex].

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

В выходном файле через пробел вывести [latex]2[/latex] числа: количество искомых чисел и наименьшее среди них.

Тесты

Входные данные Выходные данные
[latex]1[/latex] [latex]10[/latex] [latex]0[/latex]
[latex]2[/latex] [latex]1[/latex] [latex]22[/latex]
[latex]4[/latex] [latex]12[/latex] [latex]1124[/latex]
[latex]5[/latex] [latex]40[/latex] [latex]11125[/latex]
[latex]9[/latex] [latex]144[/latex] [latex]111111129[/latex]

Код программы (Цикл)

Решение задачи (Цикл)

Для решения задачи напишем функции [latex]Sum[/latex] и [latex]Mult[/latex]. Первая считает сумму цифр [latex]N[/latex]-значного числа, а вторая — произведение цифр. С помощью цикла создаем последовательность [latex]N[/latex]-значных чисел и вводим каждое из них в функции [latex]Sum[/latex] и [latex]Mult[/latex]. Если возращаемые значения равны между собой, то мы выводим данное число и присваиваем переменной [latex]b[/latex] значение [latex]false[/latex]. Также продолжаем считать количество [latex]N[/latex]-значных чисел у которых сумма цифр равна их произведению. Также создаем случаи, когда [latex]N=1[/latex], [latex]N=8[/latex] и [latex]N=9[/latex], ибо в цикле эти значения долго считаются. Задача решена.

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

Решение задачи (Массив)

Для решения задачи заранее просчитали все ответы и записали их в массив [latex]x[/latex]. Так как ответы идут подряд составили формулу для вывода искомых значений: для количества чисел у которых сумма цифр совпадает с их произведением — [latex]2n-2[/latex], для минимального числа — [latex]2n-1[/latex]. Задача решена (также задачу можно решить с помощью циклов).

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com (цикл)
Код решения на ideone.com (массив)

e-olymp 2807. Кубики — 3

Задача

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

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

В первой строке задано количество найденных Витеком кубиков [latex]n (1 ≤ n ≤ 10^5)[/latex], а во второй строке [latex]n[/latex] символов, изображённых на каждом из кубиков.

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

Выведите букву, изображённую на потерявшемся кубике, либо сообщение [latex] «Ok»[/latex], если Витек ошибся и ни один из кубиков не потерялся.

Тесты

# Входные данные Выходные данные
1 5 abcac b
2 8 ryirhiyh Ok
3 3 AVA V
4 6 DjkjDk Ok
5 7 LnCsCnL s

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

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

Для того, чтобы решить задачу, мы проверяем четное ли количество кубиков, найденных Витеком. Если условие выполняется, то выводим на экран сообщение с текстом [latex] «Ok»[/latex]. Если нет, то рассматриваем второй случай. Создаем массив, в котором будем хранить количество кубиков для каждой буквы. Обнуляем ячейки массива, в которых будут храниться данные. Далее мы будем считывать символы в соответствии с их числовыми кодами. После прочтения входного потока, найдем элемент массива с нечетным числом вхождений и выведем его на экран.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 27. Циклические сдвиги

Задача

Циклический сдвиг

Циклический сдвиг

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

Например, если $n = 11$, то в двоичной системе это $1011$$2$, его циклические сдвиги: $0111$$2$, $1110$$2$, $1101$$2$, $1011$$2$. Максимальное значение $m$ у всех полученных таким образом чисел будет иметь число $1110$$2$ $=$ $14$$10$.

Для заданного числа $n$ определить максимальное значение $m$.

Входные данные: одно число $n \left(1 ≤ n ≤ 2 \cdot 10^9\right)$.

Выходные данные: искомое число $m$.

Тесты

Входные данные Выходные данные
11 14
23 30
256 256
257 384
34132 43664

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

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

  1. Сначала мы находим степень двойки, большую данного числа;
  2. Далее мы циклически сдвигаем влево данное число на один бит и из полученных чисел выбираем наибольшее.

Возможный вариант решения задачи

Возможно избавиться от первого цикла путем нахождения количества двоичных разрядов кратных степени двойки с помощью:
1. взятия логарифма числа по основанию $2$ с последующим округлением до целого;
2. возведение двойки в степень, полученную выше, и увеличенную на единицу.
То есть $2^{\lfloor \log_{2}n \rfloor + 1}$.

Тогда код будет выглядеть так:

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com
Возможное решение задачи на ideone.com

e-olymp 513. Проблема Николая

Задача

Николаю нужно доставить подарки для [latex]n[/latex] [latex](n ≤ 10^{18})[/latex] детей. Его интересует сколькими способами он может это сделать. Вам нужно дать ответ на этот простой вопрос. Так как это количество может быть очень большим, выведите результат по модулю [latex]m[/latex] [latex](m ≤ 2009)[/latex].

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

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex].

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

Вывести искомое количество способов.

Тесты

Входные данные Выходные данные
[latex]500[/latex] [latex]2001[/latex] [latex]0[/latex]
[latex]4[/latex] [latex]5[/latex] [latex]4[/latex]
[latex]4[/latex] [latex]7[/latex] [latex]3[/latex]
[latex]15[/latex] [latex]213[/latex] [latex]147[/latex]
[latex]10[/latex] [latex]3[/latex] [latex]0[/latex]

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

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

Если [latex]m[/latex] является членом произведения [latex]n![/latex], то остаток от деления на [latex]m[/latex] равен [latex]0[/latex].В остальных случаях ищем [latex]n![/latex] с вычислением остатка от деления после каждого перемножения.

Ссылки

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

Код решения на ideone.com.

e-olymp 481. И опять: сколько можно?

Задача

Задано натуральное число [latex]N[/latex]. От данного числа вычтем сумму цифр этого числа, от полученного числа опять вычтем сумму цифр и т.д. Данную операцию будем продолжать до тех пор, пока полученное число положительно. Сколько раз будем выполнять данную операцию?

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

Во входной строке находится число [latex]N[/latex], которое не превышает [latex]2147483647[/latex].

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

Количество выполненных операций.

Тесты

Входные данные Выходные данные
[latex]23[/latex] [latex]3[/latex]
[latex]55555[/latex] [latex]3000[/latex]
[latex]1234567[/latex] [latex]49877[/latex]
[latex]999999999[/latex] [latex]25632473[/latex]
[latex]2147483647[/latex] [latex]54682584[/latex]

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

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

Данную задачу можно решить, вычитая от данного числа [latex]N[/latex] суммы цифр, пока само число не станет равным [latex]0[/latex], с помощью циклов. Но этого нам не позволяет ограничение по времени.
Поэтому мы найдем максимально возможное число, которое мы можем получить при вычитании из больших чисел сумм цифр и которое проходит по времени. Это число — [latex]999999999[/latex] (найдено экспериментальным путем). Из него необходимо вычесть суммы цифр [latex]25632473[/latex] раз, чтобы получился [latex]0[/latex].
Тогда из чисел, которые больше данного, достаточно вычитать суммы цифр, пока они не станут равными [latex]999999999[/latex] и прибавить к количеству вычитаний [latex]25632473[/latex].
Если [latex]N[/latex] меньше найденного нами числа, то можно из него просто вычитать суммы цифр, пока оно не станет равным [latex]0[/latex].

Ссылки

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