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 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 8654. Целочисленное умножение

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

    Задача

    Даны три целых числа $a, b, c.$ Вычислить значение выражения $a \cdot b \text{ mod } c.$

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

    Три целых положительных числа $a, b, c \left( a, b, c < 2^{63} \right).$

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

    Вывести значение выражения $ a \cdot b \text{ mod } c.$

    Тесты

    # ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
    1 2 3 2 0
    2 11 3 2 1
    3 123456789
    987654321
    17
    0
    4 5000400000023
    23000400400500
    100000000070707
    68238553233174
    5 10000018585
    10000000000005
    101020304050607080
    85850050000993845

    Решение

    Для решения задачи напишем рекурсивную функцию умножения, основанную на том, что [latex]\displaystyle a\cdot b =\displaystyle[/latex][latex] \begin{cases}\left(a+a\right)\cdot\frac{b}{2} &\text{} b\equiv_{2} 0 \\a+a\cdot\left(b-1\right) &  \text{} b \not \equiv_{2} 0\ \end{cases}.[/latex] Поскольку максимальное значение из условия задачи в два раза меньше максимального числа из 64-битных беззнаковых чисел и[latex]\left(a\cdot b\right)\text{ mod } c =\left(a\text{ mod } с \cdot b\text { mod }c\right)\text{ mod }c,[/latex] мы можем на каждом шагу применять к $a$ и $b$  операцию остатка от деления на $c$ , за счет чего произведение никогда не будет превосходить $2^{64}-1$.

    • Засчитанное решение на e-olymp
    • Код на ideone

    e-olymp 8371. Четное или нечетное

    Задача

    Задано натуральное число $n$. Определить его четность.

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

    Одно натуральное число $n$ $\left(1 \leq n \leq 10^{9}\right)$.

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

    Если число $n$ четное, то вывести EVEN. Если нечетное, то вывести ODD.

    Тесты

    # ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
    1 1 ODD
    2 99 ODD
    3 500 EVEN
    4 1000000000 EVEN

    Код программы (Линейные вычисления)

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

    Если число четное, то будет выполняться условие n%2==0, тогда выводим EVEN. Если число нечетное, то будет выполняться условие n%2==1, тогда выводим ODD.

    Код программы (Ветвление)

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

    Число четное, если оно делится на $2$ без остатка, значит выполняется условие: n % 2 == 0. В противном случае, число будет нечетным.

    Ссылки

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

    Код программы на IdeOne (Линейные вычисления)

    Код программы на IdeOne (Ветвление)

    e-olymp 8522. Делимость

    Задача

    Заданы два натуральных числа $a$ и $b$. Проверьте, делится ли $a$ на $b$.

    Входные данные: Два натуральных числа $a$ и $b$ $(1 \le a, b \le 10^9)$

    Выходные данные: Если $a$ не делится на $b$ нацело, вывести в одной строке частное и остаток от деления $a$ на $b$. Иначе вывести "Divisible".

    Тесты

    $a$ $b$ Вывод программы
    15 3 Divisible
    12 7 1 5
    15 23 0 15
    1000000000 889879 1123 665883

    Continue reading

    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 108. Среднее число

    Задача

    Дано три различных числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]. Вывести среднее из них.

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

    Числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] целые и по модулю не превышают 1000.

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

    Вывести среднее среди трех чисел.

    Тесты

    Входные данные Выходные данные
    10 4 9 9
    2 256 8 8
    1 2 3 2

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

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

    Я рассмотрел все возможные случаи, а именно 2 на каждую переменную, в которых она может оказаться «средней», удовлетворяя условию. [latex]a[/latex] средняя, если она лежит между [latex]b[/latex] и [latex]c[/latex] или между [latex]c[/latex] и [latex]b[/latex], [latex]b[/latex] если она лежит между [latex]a[/latex] и [latex]c[/latex] или между [latex]c[/latex] и [latex]a[/latex], и [latex]c[/latex] — остальных случаях.

    Ссылки

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

    A321. Циклы

    Задача

    Даны натуральные числа [latex]m, n[/latex], действительные числа [latex] a_1, a_2, …, a_{mn}[/latex]. Вычислить [latex]a_1 a_2 … a_m + a_{m+1} a_{m+2} … a_{2m} + a_{(n – 1) m + 1} a_{(n – 1) m + 2} … a_{nm}[/latex].

    Входные данные:
    [latex]m, n[/latex] — натуральные числа.
    В следующей строке содержится [latex]m \cdot n[/latex] действительных чисел.

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

    Тесты:

    Входные данные Выходные данные
    1
    3 3
    1.1342 2.82113 3.5431 4.541 5.081 6.761 7.35781 8.456451 9.6461 10.9321
    767.5218903911781
    2
    5 4
    23.2312 -13.016 0.78 1.0 73.48992
    -3441.32150 39.94 87.04 0.1 -0.02
    94.094 23.0001 0.005 -2.0 -1.0
    0.004 -1.01 42.0 0.454 1.5
    6593.637250058031
    3
    3 2
    1.1 2.2 3.3 4.4 5.5 6.6
    327.426

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

    Код на языке Java:

    Решение задачи:
    Заведём массив для хранения чисел. Пользуясь циклом [latex]for[/latex] от [latex]1[/latex] до [latex]m \cdot n[/latex], по мере заполнения массива будем считать слагаемые нашего выражения. Для этого воспользуемся оператором [latex] if [/latex], проверяя индексы элементов массива.

    Код программы на C++: Ideone
    Код программы на Java: Ideone
    Условия задачи(стр.134): 321

    A303. Вычисления с хранением последовательности значений

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

    Даны действительные числа [latex]x_1,\;…,\;x_{200}[/latex], принадлежащие интервалу [latex](0, 1][/latex]. Полуинтервал разбивается на 100 равных частей. Вычислить [latex]p_1, …, p_{100}[/latex], где [latex]p_k = \frac{m_k}{2000}[/latex], а [latex]m_k[/latex] — количество заданных чисел, принадлежащих полуинтервалу [latex](0.01(k – 1), 0.01k] \ \ (k = 1, …, 100)[/latex].

    Входные данные
    Входной файл содержит 200 действительных чисел, принадлежащих интервалу [latex](0, 1][/latex].

    Выходные данные
    В выходной файл выведите 100 чисел [latex]p_k \ (k = 1, …, 100)[/latex].

    Тесты

    Входные данные Выходные данные
    1
    Последовательность [latex]\frac{1}{i}, \ i=1, …, 200[/latex] p[1]=0.067 p[2]=0.013 p[3]=0.006 p[4]=0.003 p[5]=0.002 p[6]=0.0015 p[7]=0.001 p[8]=0.001 p[9]=0.0005 p[10]=0.0005
    p[11]=0.0005 p[12]=0 p[13]=0.0005 p[14]=0.0005 p[15]=0 p[16]=0 p[17]=0.0005 p[18]=0 p[19]=0 p[20]=0.0005
    p[21]=0 p[22]=0 p[23]=0 p[24]=0 p[25]=0.0005 p[26]=0 p[27]=0 p[28]=0 p[29]=0 p[30]=0
    p[31]=0 p[32]=0 p[33]=0.0005 p[34]=0 p[35]=0 p[36]=0 p[37]=0 p[38]=0 p[39]=0 p[40]=0
    p[41]=0 p[42]=0 p[43]=0 p[44]=0 p[45]=0 p[46]=0 p[47]=0 p[48]=0 p[49]=0 p[50]=0.0005
    p[51]=0 p[52]=0 p[53]=0 p[54]=0 p[55]=0 p[56]=0 p[57]=0 p[58]=0 p[59]=0 p[60]=0
    p[61]=0 p[62]=0 p[63]=0 p[64]=0 p[65]=0 p[66]=0 p[67]=0 p[68]=0 p[69]=0 p[70]=0
    p[71]=0 p[72]=0 p[73]=0 p[74]=0 p[75]=0 p[76]=0 p[77]=0 p[78]=0 p[79]=0 p[80]=0
    p[81]=0 p[82]=0 p[83]=0 p[84]=0 p[85]=0 p[86]=0 p[87]=0 p[88]=0 p[89]=0 p[90]=0
    p[91]=0 p[92]=0 p[93]=0 p[94]=0 p[95]=0 p[96]=0 p[97]=0 p[98]=0 p[99]=0 p[100]=0.0005

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

    Код на языке Java:

    Решение задачи
    Для сортировки чисел по полуинтервалам разделим каждое [latex]x_i[/latex] на [latex]0.01[/latex](т.е. умножим на 100) и округлим вправо. Заведём массив для подсчета количества чисел, принадлежащих полуинтервалам [latex](0.01(k – 1), 0.01k] \ \ (k = 1, …, 100)[/latex]. Выведем [latex]p_k \ (k = 1, …, 100)[/latex].

    Условие задачи (стр. 127)
    Код задачи на C++: Ideone
    Код задачи на Java: Ideone

    e-olymp 519. Сумма квадратов

    Как лучше кодировать квадрат?

    Как лучше кодировать квадрат?

    Условие задачи
    Найти сумму квадратов двух чисел.

    Входные данные
    Два целых числа [latex]a[/latex] и [latex]b[/latex]. Числа не превышают [latex]10^9[/latex] по абсолютной величине.

    Выходные данные
    Выведите одно целое число [latex]a^2 + b^2.[/latex]
    Continue reading

    MS2. Сумма чисел во входном потоке

    Условие

    Сосчитайте сумму чисел во входном потоке.

    Тесты

    Ввод
    Вывод
    1 2 3 4 5 6 21
    12 13 14 39
    1-100

    5050

    Решение

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

    Код на ideone C++
    Код на ideone Java

    KM194. Взаимно простые числа

    Задача

    Даны два взаимно простых натуральных числа [latex]a[/latex] и [latex]b[/latex]. Рассмотрим множество [latex]M[/latex] целых чисел, представимых в виде [latex][ax+by],[/latex]
    где [latex]x[/latex] и [latex]y[/latex] — целые неотрицательные числа. Каково наибольшее целое число [latex]c[/latex], не принадлежащее множеству [latex]M[/latex]?

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

    [latex]a[/latex] и [latex]b[/latex] — два взаимно простых натуральных числа.

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

    [latex]c[/latex] — наибольшее целое число c, не принадлежащее множеству [latex]M[/latex].

    Тесты

    Входные данные Выходные данные
    [latex]a[/latex] [latex]b[/latex] [latex]c[/latex]
    5 3 7
    2 1 -1
    3 2 1

    Код программы на C++

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

    Решение

    Нарисуем на плоскости систему координат [latex]Oxy[/latex] и сформулируем нашу задачу на геометрическом языке. Каждую пару целых чисел [latex]\left(x,y\right)[/latex] мы будем называть «целой точкой» и изображать красной точкой, если обе её координаты неотрицательны [latex]\left(x\geq0, y\geq0\right)[/latex], и синей точкой — если хотя бы одна координата отрицательна.

    Взаимно простые натуральные числа [latex]a[/latex] и [latex]b[/latex] мы считаем фиксированными (для примера возьмём [latex]a=5, b=3[/latex]). Для каждого [latex]n[/latex] уравнение [latex]ax+by=n[/latex] определяет, как известно, прямую. Обозначим её через [latex]l_{n}[/latex]. Разумеется, все прямые [latex]l_{n}[/latex] параллельны друг другу. Пусть [latex]n[/latex] — целое. Будем считать прямую [latex]l_{n}[/latex] красной, если она проходит хотя бы через одну красную точку, и синей — в противном случае. Мы должны выяснить, каково наибольшее [latex]c[/latex], которому соответствует синяя прямая [latex]l_{с}[/latex], и доказать, что тогда из двух прямых [latex]l_{n}[/latex] и [latex]l_{c-n}[/latex] одна-синяя и одна-красная ([latex]n[/latex] — любое целое число).
    Мы будем пользоваться в нашем решении перемещениями плоскости, которые отображают множество целых точек на себя и одновременно каждую прямую [latex]l_{n}[/latex] переводят в ту же самую или некоторую другую прямую [latex]l_{\acute{n}}[/latex] из нашего семейства. Это, во-первых, параллельные переносы на любой вектор [latex]\left(p, q\right)[/latex] с целыми [latex]p[/latex] и [latex]q:[/latex] [latex]\left(x,y\right)|\dashrightarrow \left(x+p, y+q\right),[/latex] и, во-вторых, повороты на [latex]180^{\circ}[/latex] (или, что то же самое, симетрии относительно точки) с любыми центрами [latex]\left(\frac{p}{2}, \frac{q}{2}\right)[/latex], где [latex]p[/latex] и [latex]q[/latex] — целые: [latex]\left(x,y\right)|\dashrightarrow \left(p-x, q-y\right).[/latex]
    Докажем, что на каждой прямой [latex]l_{n}[/latex] целые точки встречаются через равные промежутки.
    Лемма. Если [latex]\left(x_{0},y_{0}\right)[/latex] — целая точка на прямой [latex]l_{n}[/latex], то ближайшими к ней целыми точками на [latex]l_{n}[/latex] будут [latex]\left(x_{0}-b,y_{0}+a\right)[/latex] и [latex]\left(x_{0}+b,y_{0}-a\right)[/latex] ([latex]a[/latex] и [latex]b[/latex] взаимно просты).
    Рассмотрим прямую [latex]l_{0}[/latex], проходящую через [latex]\left(0, 0\right)[/latex]. Пусть [latex]\left(-b_{1}, a_{1}\right)[/latex] — ближайшая к [latex]\left(0, 0\right)[/latex] целая точка [latex]l_{0}[/latex] такая, что [latex]b_{1}>0[/latex], [latex]a_{1}>0[/latex] (мы ещё не знаем, что [latex]b_{1}=b, a_{1}=a[/latex]), [latex]\left(x_{0}, y_{0}\right)[/latex] — целая точка [latex]l_{n}[/latex]. При переносе на вектор [latex]\left(x_{0}, y_{0}\right)[/latex] отрезок прямой [latex]l_{0}[/latex] от [latex]\left(0, 0\right)[/latex] до [latex]\left(-b_{1}, a_{1}\right)[/latex] перейдет в отрезок [latex]l_{n}[/latex] от [latex]\left(x_{0}, y_{0}\right)[/latex] до [latex]\left(x_{0}-b_{1}, y_{0}+a_{1}\right)[/latex] будет ближайшей к [latex]\left(x_{0}, y_{0}\right)[/latex] точкой [latex]l_{n}[/latex] сверху. Точно так же при переносе на вектор [latex]\left(x_{0}+b_{1}, y_{0}-a_{1}\right)[/latex] — тот же отрезок прямой [latex]l_{0}[/latex] перейдёт в отрезок прямой [latex]l_{n}[/latex] от [latex]\left(x_{0}+b_{1}, y_{0}-a_{1}\right)[/latex] до [latex]\left(x_{0}, y_{0}\right)[/latex]. Следовательно, и на этом отрезке целыми точками будут только его концы.
    Отсюда уже следует, то на любой прямой [latex]l_{n}[/latex] (уесли на ней есть хоть одна целая точка) промежуток между соседними целыми точками один и тот же: [latex]a_{1}[/latex] единиц по оси [latex]Oy[/latex] и [latex]b_{1}[/latex] — по оси [latex]Ox[/latex]. Это, в частности, относится и к прямой [latex]l_{0}[/latex]. Поскольку [latex]\left(-b, a\right)[/latex] принадлежит [latex]l_{0}[/latex], то отсюда следует, что [latex]b=db_{1}, a=da_{1}[/latex], где [latex]d[/latex] — некоторое целое число. Но числа [latex]a[/latex] и [latex]b[/latex] по условию взаимно просты. Значит, [latex]d=1[/latex], то есть [latex]a=a_{1}, b=b_{1}[/latex]. Лемма доказана.
    Из этой леммы следует, что каждая прямая [latex]l_{n}[/latex], где [latex]n[/latex] — целое, переходит ровно через одну точку внутри полосы [latex]0\leq x\leq b-1[/latex]. При этом, очевидно, если прямая красная, то есть где-то переходит через красную точку, то её целая точка в выделенной полосе тоже будет красной (а точка синей прямой, разумеется, синяя).
    Теперь заметим, что при симетрии относительно точки [latex]\left(\frac{b-1}{2} -\frac{1}{2}\right)[/latex] [latex]\left(x,y\right)\mapsto\left(\acute{x}, \acute{y}\right) =\left(b-1-x, -1-y\right)[/latex], полоса [latex]0\leq x\leq b-1[/latex] переходит в себя, причем красные точки переходят в синие, и наоборот. Прямая [latex]l_{n}[/latex] после этой симметрии переходит в прямую [latex]l_{ab-a-b-n}[/latex]: если [latex]ax+by=n[/latex], то [latex]a\acute{x}+b\grave{y}=a\left(b-1-x\right)+b\left(-1-y\right)=ab-a-b-n.[/latex] (Через центр симметрии, где [latex]a\left( \frac{b-1}{2}\right)+b\left(- \frac{1}{2}\right) = \frac{ab-a-b}{2},[/latex] ни одна из наших прямых может и не проходить.)
    Ясно, что самая нижняя красная прямая — это [latex]l_{0}[/latex]. Следовательно, самая верхняя синяя прямая — это [latex]l_{ab-a-b}.[/latex] Итак, наибольшее число, не принадлежащее множеству, — это [latex]c=ab-a-b,[/latex] и из двух чисел [latex]n[/latex] и [latex]c-n[/latex] одно принадлежит [latex]M[/latex], а другое — нет.

    Ссылки

    Ideone C++;
    Ideone Java;
    Решение задачи Журнал «Квант» №11 г.1973 (стр. 44-45);
    Условие задачи Журнал «Квант» №3 г.1973 (стр. 35).

    MS1. Количество чисел в потоке

    Задание

    Сосчитайте количество чисел во входном потоке.

    Тесты

    Вход Выход
    20 16 11 3
    17 22.4 41.9 74.5 4
    122 347 1567 21 40 5
    13 28 17 8 2 5
    abc 123 5.5 21 go 4 4

    Код на C++

    Код на Java

     

    Решение

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

    Ссылки

    1.Код на C++

    2.Код на Java

    e-olymp 141. Минимальная сумма цифр

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

    Сколько натуральных чисел из промежутка [latex][M,N][/latex] имеют наименьшую сумму цифр ?

    Задачу также можно найти здесь.

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

    Во входном файле два числа [latex]M[/latex] и [latex]N[/latex] ( [latex]1\le M\le N\le 1000000[/latex] ) .

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

    В выходной файл нужно записать ответ — одно число.

    Тесты

    M N Вывод
    1 1 100 3
    2 2 17 1
    3 32 1024 2
    4 1 1000000 7
    5 10 10 1

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

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

    Для решения данной задачи зададим функцию, которая возвращает сумму чисел вводимого нами числа. После ввода границ необходимого промежутка присваиваем минимальную сумму (sumMin) сумме цифр первого числа [latex] M [/latex]. Теперь задаём цикл со счётчиком [latex] i [/latex] от [latex] M + 1 [/latex] до [latex]\le N[/latex]. В случае, когда сумма чисел счётчика меньше сумме цифр числа [latex] M [/latex], присваиваем ей (сумме цифр счётчика i) минимальную сумму цифр и выводим единицу. В противном случае увеличиваем счётчик на единицу и выводим полученный результат. Выводимое число и будет количеством натуральных чисел на промежутке, имеющих наименьшую сумму цифр.

    Код программы можно найти здесь.

    Ссылка на полностью засчитанное решение на сайте e-olymp.

    e-olymp 22. «Зеркально простые» числа

    Назовем число «зеркально простым», если само число является простым, и простым является число, записанное теми же цифрами в обратном порядке.

    Найти количество «зеркально простых» чисел на промежутке от [latex]a[/latex] до [latex]b[/latex].

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

    Два числа [latex]a[/latex] и [latex]b[/latex] ( [latex]1[/latex][latex]\le[/latex] [latex]a[/latex], [latex]b[/latex] [latex]\le[/latex] [latex]10000[/latex]).

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

    Вывести количество «зеркально простых» чисел на промежутке от [latex]a[/latex] до [latex]b[/latex] включительно.

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

    Тесты

     Границы промежутка   Количество «зеркально простых» чисел
    1  10 4
    100  200 12
    1008 1230 19
    3340  3950 31
    9900 10000 4

     

    Алгоритм

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

    1. Инициализируем две логические переменные, значение которых отвечает за прохождение теста на простоту самим числом и «зеркальным» соответственно.
    2. Методом последовательного перебора делителей определяем является ли данное число простым. Если данное утверждение истинно, переходим к последующим пунктам. В противном случае переходим на новый виток главного цикла.
    3. Выполняем последовательную сборку числа, записанного в обратном порядке.
    4. Проводим аналогичную проверку на простоту для «зеркального» числа.
    5. При условии, что это число также является простым, инкрементируем счетчик.

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

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

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

    Засчитанное решение

    e-olymp 29. Уровень палиндромности

    Задано натуральное [latex]M[/latex]. Если число не палиндром – записываем его в обратном порядка и слагаем с заданным. Действия повторяем до тех пор, пока не получим число-палиндром. Количество выполненных операций назовем уровнем палиндромности заданного числа.

    Найти уровень палиндромности заданного числа [latex]M[/latex].

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

    Единственное число [latex]M[/latex] ([latex]0[/latex] [latex] <[/latex] [latex]M[/latex] [latex] <[/latex] [latex]10000[/latex]).

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

    Единственное число – уровень палиндромности.

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

    Тесты

      Входные данные   Выходные данные
    1 0
    79 6
    101 0
    198 5
    865 2
    9998 6

    Алгоритм

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

    1. Для начала инициализируем счетчик, который хранит в себе текущее значение уровня палиндромности, и логическую переменную, значение которой ложно до тех пор пока палиндром не найден. Данное условие и будет критерием для выполнения тела основного цикла.
    2. Присвоив значения переменным в цикле, выполняем последовательный разбор введенного числа на цифры и сборку «зеркального» числа.
    3. Проверяем равенство числа и ему обратного.
    4. Выполнение условного оператора сигнализирует о том, что палиндром найден, следовательно выводим «уровень», изменяем значение логической переменной на противоположное и выходим из цикла.
    5. В противном случае суммируем текущее число и «зеркальное», инкрементируем счетчик.
    6. Повторяем пункты 2, 3, 5 до истинности пункта и перехода к 4.

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

     

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

    Засчитанное решение

    Ю 3.14

    Задача

    Проверить численно второй замечательный предел:[latex]\lim_{x\to\infty}\left(1+\frac{1}{n}\right)^n=e[/latex] , задавая n значения 1,2,3…При каком n исследуемое выражение отличается от менее, чем на заданную погрешность [latex]\varepsilon[/latex]?

    Тесты

    [latex]\varepsilon[/latex] n Полученное e e Разность Комментарий
    1.1   1  2.0000000000 2.7182818284  0.7182818284 Пройден
     0.005  271 2.7132834531 2.7182818284 0.0049983753 Пройден
    0.0000000314 32890950 2.7182817970 2.7182818284 0.0000000313 Пройден
     0 Погрешность равна 0, тогда e=2.7182818284, а n=бесконечность Не пройден

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

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

    Для этого в цикле высчитывалось значение формулы [latex](1+\frac{1}{n})^{n}[/latex] при [latex]n\to \infty[/latex] и находилась разность [latex]dife=e-(1+\frac{1}{n})^{n}[/latex]. Если[latex]dife>\varepsilon[/latex] , то цикл заканчивался и программа запоминала последнее значение n и после этого выводила его на экран.

    Код на Java