e-olymp 8680. Чётные соседи

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

Задана последовательность целых чисел. Подсчитать количество элементов, у которых чётные соседи.

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

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

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

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

Тесты

Входные данные Выходные данные
1 6
1 2 3 4 5 6
2
2 9
3 6 3 5 2 9 1 2 5
0
3 3
2 1 2
1
4 6
13 24 54 66 44 77
2
5 4
100 224 666 222
2

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

Решение

Идея решения задачи состоит в том, чтобы создать три переменные: $prev$ (предыдущий), $pres$ (настоящий, текущий) и $fut$ (будущий). Затем в цикле мы перезаписываем эти переменные т.е.: настоящий становится прошлым, будущий настоящим, а новый будущий мы читаем из cin. Так же, в ходе решения задачи обнаружилась проблема с чтением количества элементов. Допустим, если мы записали, что $n=6$, а дальше ввели $10$ элементов, то количество элементов с чётными соседями будет считаться для $10$ элементов. Чтобы избежать этого мы ограничиваем количество читаемых элементов с помощью счётчика i++ и цикла while.

Ссылки

e-olymp 8916. Первые парные

Первые парные

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

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

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

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

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

Тесты

Входные данные Выходные данные
1 3 2 4 6
2 8 2 4 6 8 10 12 14 16
3 5 2 4 6 8 10

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

 

Решение

Решением этой задачи является вывод через пробел удвоенных чисел от 1 до [latex] n [/latex].

Ссылки

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

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 8283. Музыка

    Задача

    Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.

    Малыши часто просили его научить играть на каком-нибудь инструменте. Гусля не отказывал, но сначала предлагал взять инструмент с первым номером, а если ученику хотелось играть на другом, то он выбирал шестой следующий по кругу и так далее. Напишите программу, которая определяла номер попытки, с которой ученик мог получить желаемый инструмент с номером $k$.

    Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.

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

    Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.

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

    Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.

    Тесты

    Входные данные Выходные данные
    1 11 3 5
    2 6 2 0
    3 13 13 3
    4 9 8 0
    5 5 5 5

    Код

    Решение

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

    1. Если пользователь вводит разные числа.
    2. Если пользователь вводит одинаковые числа.

    В первом случае мы рассматриваем две ситуации:
    1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
    2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
    Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.

    Во втором случае мы также рассматриваем две ситуации:
    1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
    2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
    Также не забываем про подводный камень, указанный выше.

    Ссылки

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

    e-olymp 123. Количество нулей у факториала

    Задача

    Найти количество нулей в конце записи факториала числа $n$.

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

    Одно число $n$ $(1 \leqslant n \leqslant2\cdot10^9)$

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

    Количество нулей в конце записи $n!$

    Тесты

    ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
     1 1 0
     2 7 1
     3 12 2
     4 100 24
     5 306 75
     6 5000 1249

    Код

    Решение

    Каждый нуль в конце искомого числа возникает от произведения чисел 2 и 5 — других вариантов нет. Очевидно, множителей 5 будет меньше множителей 2. Значит, количество нулей определяется исключительно количеством множителей-пятерок. Один такой множитель содержат числа 5, 10, 15, 20, 25, …, $n$ — всего их насчитывается $\frac{n}{5}$. Два множителя содержат числа 25, 50, …, $n$ всего их $\frac{n}{5^2}$.Три множителя содержат $\frac{n}{5^3}$.Складывая количество множителей с учетом их повторения, найдем общее их количество:

    $\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\ldots+\lfloor\frac{n}{5^k}\rfloor$

    Суммирование происходит до тех пор, пока очередное слагаемое не станет равным 0.

    Ссылки

    Формула разложения на простые множители

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

    Код на Ideone

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

    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 271. Факториал!

    Задача

    Найти значение факториала целого числа [latex]n[/latex]

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

    Одно целое число [latex]n(0\leq n\leq 3000)[/latex].

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

    Выведите факториал числа [latex]n[/latex].

    Тесты

    Входные данные Выходные данные
    3 6
    5 120
    1 1

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

    Решение

    Факториал натурального числа [latex]n[/latex] определяется как произведение всех натуральных чисел от [latex]1[/latex] до [latex]n[/latex] включительно.
    Для решения данной задачи создаем класс [latex]factorial[/latex] для вычисления факториала. А потом используем метод [latex]factorial[/latex] в классе [latex]main[/latex].

    Ссылки

    e-olymp
    Ideone

    e-olymp 922. Сдвинь элементы

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

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

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

    Решение задачи
    Создаем динамический массив, размером в number элементов. Создаем переменную last, в которой записан последний элемент массива. Создаём цикл, в котором меняется каждый элемент массива с предыдущим. Кладем на $1$ место (точнее $0$ место) бывший последний элемент массива.
    Выводим массив.
    Ссылки
    Задача на сайте e-olymp
    Код решения в Ideone

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

    Единицы

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

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

    Одно целое число $n$ $(0 ≤ n ≤ 2 \cdot 10^{9})$.

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

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

    Тесты

    ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
    20 2
    0 0
    1 1
    5 2
    2000000000 13

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

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

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

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

    e-olymp 1607. Число в обратном порядке

    Задача

    Запишите целое неотрицательное число $n$ в обратном порядке.

    Вводные данные

    Одно целое неотрицательное $64$-х разрядное число.

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

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

    Тесты

    Входные данные Выходные данные
    $1234$ $4321$
    $100$ $001$
    $34567$ $76543$
    $10983743$ $34738901$
    $98352374234$ $43247325389$

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

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

    Для решения задачи вводим строку. Узнаем ее длину с помощью функции с.length(), затем циклом выводим строку в обратном порядке. Задача решена.

    Ссылки

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