e-olymp 7457. Max-Min в двійковій системі счислення

Умова

Вивчаючи двійкову систему числення, Василько вирішив попрактикуватися і придумав таку вправу. Він із бітів числа створював найбільше і найменше число, переставляючи біти, після чого знаходив їх різницю. Проте хлопець не знає, чи правильно виконує вправу. Допоможіть йому. Напишіть програму, яка за даним числом $N$ знаходить різницю між найбільшим і найменшим числом, які утворюються із бітів заданого числа. У найбільшого числа найбільший біт співпадає з найбільшим бітом заданого числа.

Пояснення

$N=13_{10}$, в двійковій системі числення — $1101_2$, найбільше число $1110_2 = 14_{10}$, найменше число $0111_2 = 7_{10}$. $14−7=7$.

Вхідні дані

В єдиному рядку записане число $N (N<2^{31})$.

Вихідні дані

Єдине число — відповідь до вправи Василька.

Тести

Вхідні дані Вихідні дані
2 1
15 0
86 105
1000 945
40 45

Код програми

 

 

Рішення

Процес вирішення даної задачі поділяється на 4 кроки:

  1. За допомогою циклу рахуємо кількість одиниць та нулів у двійковому вигляді поданого числа $n$.
  2. Створимо функцію $max_number$, яка за поданою кількістю нулів та одиниць буде повертати найбільше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Очевидно, що отримати найбільше число в двійковому вигляді можна, якщо записати спочатку всі одиниці, а потім — усі нулі.
  3. Створимо функцію $min_number$, яка за поданою кількістю нулів та одиниць буде повертати найменше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Зрозуміло, що найменше число буде виглядати навпаки — спочатку будуть стояти всі нулі, а потім — усі одиниці.
  4. Виведемо на екран різницю підрахованих функціями $max_number$ та $min_number$ значень.

А329. Квадрат суммы цифр числа

Задача

Задача из сборника задач по программированию Абрамова С.А. 2000 г.
Даны натуральные числа $n$, $m$. Получить все меньшие натуральные числа, квадрат суммы цифр которых равен $m$.

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

Два положительных числа $n$ и $m$.

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

Все целые числа из $\left ( 0, n \right )$, удовлетворяющие условию.

Тесты

Входные данные Выходные данные
$1234 \ 9$ $3 \ 12 \ 21 \ 30 \ 102 \ 111 \ 120 \ 201 \ 210 \ 300 \ 1002 \ 1011 \ 1020 \ 1101 \ 1110 \ 1200$
$100 \ 4$ $2 \ 11 \ 20$
$49 \ 49$ $7 \ 16 \ 25 \ 34 \ 43$
$1000 \ 1$ $1 \ 10 \ 100$

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

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

Находим сумму цифр каждого числа от $1$ до $n$, проверяя равняется ли эта сумма, возведенная в квадрат, числу $m$. В случае положительного ответа, выводим число, сумму цифр которого мы проверяли.

Ссылки

Условие задачи (страница 135)
Код решения

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

Задача

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

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

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

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

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

Тесты

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

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

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

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

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 7367. Спортсмен

Задача

Спортсмен в первый день пробежал 10 км. Каждого следующего дня он увеличивал норму на 10% от нормы предыдущего дня. Опредилить через какое наименьшее количество дней спортсмен пробежит суммарный путь не меньший чем [latex]N[/latex] км.

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

Целое число [latex]N (0 < N≤ 1000)[/latex].

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

Единственное число – количество дней.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 9 1
2 45 4
3 324 16
4 1234 28
5 213213123 153

Код программы №1 (с использованием цикла):

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

Сначала вводим 4 переменные: [latex] k=1 [/latex] ( количество дней ), [latex] T=10 [/latex] ( количество километров которое спортсмен пробежал ), [latex] N [/latex] ( количество километров которое спортсмен должен пробежать ) и [latex] S [/latex] ( количество километров которое спортсмен пробегает в день ). Цикл каждый раз будет прибавлять к расстоянию которое пробежал спортсмен, количество километров которое спортсмен должен пробежать в течение следующего дня, с учетом того, что каждый день он будет пробегать на [latex] 10 [/latex] процентов больше, чем в прошлый день, параллельно увеличивая количество дней, пока [latex] N [/latex] будет больше [latex] T [/latex]. Если же [latex] N [/latex] при вводе изначально будет меньше [latex] T [/latex], то программа выведет, что спортсмену достаточно одного дня.

Ссылки

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

Код программы №2(с использованием линейных вычислений):

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

Также данную задачу можно решить с помощью формулы геометрической прогрессии [latex]S=\frac{b_1(q^n-1)}{q-1}[/latex] из которой нам нужно будет выразить степень [latex] n [/latex] через логарифм при условии того, что по условию задачи мы знаем, что [latex] q=1.1 [/latex] и [latex] b_1=1 [/latex]. И мы получаем, что [latex] \left(n=\log_{1.1}\left(\frac{s}{100}+1\right)\right) [/latex]. При записи логарифма по основанию в С++ мы пользуемся основным свойством логарифмов: [latex] \log_{a}\left(b\right)=\frac{\log_{c}\left(b\right)}{\log_{c}\left(a\right)} [/latex]. Также используем функцию сeil, которая округлит выходное число вверх, до ближайшего целого. ( [latex] S [/latex] — количество километров, которое должен пробежать спортсмен ).

Ссылки

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
Код решения

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

Задача

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

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

В первой строке натуральное четное число $M$ – количество украденных стручков, $2 \leq M \leq 1000.$

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

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

Тесты

Входные данные Выходные данные
$6$ $6 \ 0 \\ 2 \ 4$
$11$ $11 \ 0 \\ 7 \ 4 \\ 3 \ 8$
$18$ $18 \ 0 \\ 14 \ 4 \\ 10 \ 8 \\ 6 \ 12 \\ 2 \ 16$

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

Решение

Пусть $a$ — количество стручков, принесенных Хомой и $b$ — количество стручков, принесенных Сусликом. Так как по условию задачи Хома таскал только по четыре стручка, мы будем считать $a = a — 4$ и $b = b + 4$, чтобы таким образом перебрать все возможные сочетания количеств стручков, принесенных Сусликом и Хомой. В ответе выводим все возможные сочетания количеств стручков, принесенных друзьями по одному в строке, упорядоченные по убыванию первого числа.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 127. Баксы в банке

Задача

Папа Карло подарил Буратино [latex]1[/latex] доллар в его первый день рождения, а экономный Буратино сложил подарок в банку. Каждый последующий год папа Карло удваивал свой предыдущий подарок и прибавлял к нему столько долларов, сколько лет исполнилось Буратино, а тот в свою очередь продолжал складывать баксы в банку. На какой [latex]N[/latex]-й день рождения в банке будет не менее чем [latex]S[/latex] долларов?

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

Единственное число — значение [latex]S[/latex]. [latex]1 ≤ S ≤ 240[/latex].

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

Искомое значение [latex]N[/latex].

Тесты

# Входные данные Выходные данные
1 1 1
2 98 5
3 99 5
4 100 6
5 549755813888 38

Код

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

Для начала найдём формулу, по которому папа Карло дарит, а Буратино — складывает в банку доллары: [latex]x=2\cdot x+k[/latex].
А теперь установим допустимый предел суммы долларов в банке и начальные условия: [latex]s<n[/latex] и [latex]x=1[/latex], [latex]k=1[/latex], [latex]s=1[/latex].

Ссылки

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

e-olymp 8530. Печать матрицы

Задача

Задана матрица $n \times n$ — назовем ее $[1 \ldots n] \times [1 \ldots n]$ массивом. Для заданных $r$ и $c$ следует вывести $[1 \ldots r] \times [1 \ldots c]$ массив ($r$ строк и $c$ столбцов исходного массива).

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

Первая строка содержит число $n \space (1 \leq n \leq 100)$. Следующие строки содержат матрицу $n \times n$. Последняя строка содержит два числа $r$ и $c \space (1 \leq r, c \leq n)$. Все числа в матрице не превышают по модулю $100$.

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

Выведите матрицу $r \times c$.

Тесты

Входные данные Выходные данные
4
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7
3 2
1 2
5 6
9 1
5
18 25 34 44 -43
54 65 75 85 -32
95 15 25 35 -3
-4 15 -6 37 0
44 43 23 3 -12
4 3
18 25 34
54 65 75
95 15 25
-4 15 -6
6
30 -10 30 -69 -84 75
-3 -39 60 15 75 -74
36 68 35 23 25 -44
16 42 83 15 59 -18
71 43 35 -81 -38 51
37 -49 55 26 6 33
4 5
30 -10 30 -69 -84
-3 -39 60 15 75
36 68 35 23 25
16 42 83 15 59

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

Решение

Для того, чтобы вывести матрицу на экран, нам нужно запустить $2$ цикла, один из которых будет вложен в предыдущий:

  • первый цикл ($17$ строка кода) будет отвечать за количество выводимых строк матрицы — по условию, нужно вывести первые $r$ строк;
  • второй цикл ($18$ строка кода) будет отвечать за количество выводимых столбцов матрицы — по условию, нужно вывести первые $c$ столбцов.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone
Решение этой же задачи на C++

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 27. Циклические сдвиги

Задача

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

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

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

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

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

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

Тесты

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

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

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

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

Ссылки

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