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 6261. Устройство для анализа бюллетеня

    Задача

    Избирательная комиссия Флатландии готовится к президентским выборам. Чтобы свести к минимуму человеческий фактор при подсчете голосов, они решили разработать автоматическое устройство для анализа бюллетеней (УАБ).

    На пост президента баллотируются $n$ кандидатов. Бюллетень содержит одно квадратное поле для каждого кандидата. Избиратель должен отметить ровно одно из полей. Если поле не помечено или имеется два или более отмеченных поля, бюллетень недействителен. Каждый избиратель ставит свой бюллетень на специальный сканер в УАБ. Сканер анализирует отметки в бюллетене и создает специальную строку голосования из $n$ символов: ‘X’ для отмеченного поля и ‘.’ для немаркированного. Теперь строки голосования должны быть проанализированы, чтобы получить отчет. Ваша задача — разработать генератор отчетов для УАБ.

    С учетом строк голосования для всех бюллетеней Ваша программа должна распечатать отчет о голосовании. Кандидаты в протоколе должны быть расположены в порядке убывания количества голосов. Если два кандидата имеют одинаковое количество голосов, они должны иметь тот же порядок, что и в бюллетене для голосования. Для каждого кандидата рассчитайте его / ее результат в процентах (если кандидат получил p голосов, результат в процентах составляет $ \frac{100p}{m}$ ). В последней строке отчета должен быть указан процент недействительных бюллетеней.

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

    Первая строка содержит два целых числа $n$ и $m (2 \leqslant n \leqslant 10, 1 \leqslant m \leqslant 1000$) — количество кандидатов и количество бюллетеней. Следующие $n$ строк содержат фамилии кандидатов. Каждое имя представляет собой строку не более 100 английских букв. Нет ни одного кандидата с именем «Invalid».

    Затем следуют $m$ строк, каждая из которых содержит одну строку голосования.

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

    Выведите $n+1$ строк. Сначала выведите результаты для кандидатов в процентах. Для каждого кандидата выведите его / ее фамилию, затем пробел, а затем его / ее результат в процентах и знак процента ‘%‘. В последней строке должен быть указан процент недействительных бюллетеней: слово «Invalid», за которым следуют пробел, процент недействительных бюллетеней и знак процента.

    Округлите все числа до двух цифр после десятичной точки. Если число находится точно посередине двух представимых чисел, выведите большее (например, выведите «12.35» для 12.345).

    Тесты

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

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

    1 4 7
    Loudy
    Apples
    Dogman
    Miller
    .X..
    X…
    ….
    ..X.
    ..XX
    ..X.
    ..X.
    Dogman 42.86%
    Loudy 14.29%
    Apples 14.29%
    Miller 0.00%
    Invalid 28.57%
    2 4 10
    Loudy
    Apples
    Dogman
    Miller
    X………………..
    X…………………..
    X………………
    X………………….
    X…………..
    x………………………..
    X……………….
    X……………
    X..x
    xxxx
    Loudy 70.00%
    Apples 0.00%
    Dogman 0.00%
    Miller 0.00%
    Invalid 30.00%

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

    Решение

    Чтобы решить задачу создадим структуру с именами и результатами кандидатов. Сначала создадим массив кандидатов и заполним его. По вводу бюллетеней будем проверять не испорчены ли они. Если кроме «X» есть любой другой символ, или буква, или еще символы «X», то бюллетень испорчен, в остальных случаях он не испорчен. Если он не испорчен, добавляем к результату кандидата единицу, если нет — добавляем к счетчику испорченых бюллетеней единицу. Выводим в процентном соотношении с количеством бюллетеней результат каждого кандидата и количество испорченых бюллетеней.

    Ссылки

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

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

    e-olymp 972. Сортировка времени

    Задача

    Отсортируйте время согласно заданному критерию

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

    Сначала задано число $n\, \left ( 1\leqslant n\leqslant 100 \right )$, а затем n моментов времени. Каждый момент времени задается 3 целыми числами — часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60)

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

    Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно)

    Тесты

    Входные данные Выходные данные
    1 [latex]\begin{matrix}
    4 & & \\
    10 &20 &30 \\
    7 &30 &00 \\
    23&59 &59 \\
    13&30 &30
    \end{matrix}[/latex]
    [latex]\begin{matrix}
    7 & 30 &00 \\
    10&20 &30 \\
    13&30 &30 \\
    23& 59 & 59
    \end{matrix}[/latex]
    2 $\begin{matrix}
    6\\
    12 &55 &59 \\
    8 &33 &34 \\
    6 &56 &46 \\
    10 &23 &52 \\
    3 &20 &00 \\
    19 &31 &0\\
    10&23&52
    \end{matrix}$
    $\begin{matrix}
    3 &20 &0 \\
    6 &56 &46 \\
    8 &33 &34 \\
    10 &23 &52 \\
    12 &55 &59 \\
    19 &31 &0
    \end{matrix}$

    Решение

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

    Ссылки

    e-olymp
    ideone

    e-olymp 8358. Среднее значение — 1

    Задача. Среднее значение — 1

    Проект «Средний вес школьника школы» решили выполнить Мамед с Самедом. Что они будут делать с этим числом, они не раскрывают. Они попросили взвеситься всех учеников школы и занесли результаты в таблицу. Помогите им подсчитать средний вес учеников. Но они просят, чтобы учеников с самым большим и с самым маленьким весом не учитывать. Единственное их упущение, они не подсчитали общее количество учеников, но это, конечно, не помешает вам подсчитать то, что они просят.

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

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

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

    Средний вес учеников школы без учета учеников с самым большим и самым маленьким весом. Ответ выводить с точностью до килограмм.

    Тесты

    Ввод Вывод
    1 40 23 27 59 68 23 84 27 53 46 46
    2 21 22 23 24 25 26 27 28 20 30 29 25
    3 10 20 10 20 10 20 10 20 11 11
    4 60 45 70 90 55 62
    5 80 80 80 70 83 90 90 90 81
    6 50 90 70 70 70 70 70 70 70 70 74 70
    7 70 70 70 70 70 70 70 70 70 70 70 70 70 60 50 90 69

    Решение

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

    Код через потоковую обработку

    Код через vector

    Код через map

    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 2375. Квартира

    Задача

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

    • общую площадь комнат;
    • общую площадь всех спален;
    • стоимость квартиры.

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

    Первая строка содержит два целых числа [latex]n [/latex] [latex](1 \leqslant n \leqslant 10)[/latex] и [latex]c[/latex] [latex](1 \leqslant c \leqslant 100000)[/latex] — количество комнат в квартире и стоимость квадратного метра соответственно. Каждая из следующих [latex]n[/latex] строк содержит целое число [latex]a_i (1 \leqslant a_i \leqslant 100)[/latex] и слово [latex]t_i[/latex] — площадь [latex]i[/latex]-ой комнаты и ее тип соответственно. Слово [latex]t_i[/latex] может содержать только одно из следующих значений: [latex] «bedroom»[/latex], [latex] «bathroom»[/latex], [latex] «kitchen»[/latex], [latex] «balcony»[/latex], [latex] «other»[/latex].

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

    Первая строка содержит одно целое число — общую площадь всех комнат квартиры. Вторая строка содержит одно целое число — общую площадь всех спален в квартире. Третья строка содержит одно действительное число — стоимость квартиры с точностью не больше [latex]10^{-6}[/latex].

    Следующий рисунок отображает план квартиры, заданной в первом примере.

    Тесты

    Входные данные Выходные данные
    1 6 75000 46
    8 other 16
    3 bathroom 3187500.000000
    2 bathroom
    10 kitchen
    16 bedroom
    7 balcony
    2 2 75123 25
    10 kitchen 0
    15 balcony 1314652.500000
    3 4 110000 41
    7 other 18
    4 bathroom 4510000.000000
    12 kitchen
    18 bedroom

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

    Считываем данные из потока. При этом используем цикл for(int i=1; i=n; i++). Общую площадь квартиры рассчитываем по формуле S += ai. Площадь спален вычисляем по формуле Ss += ai, учитывая, что ti=="bedroom". Для дальнейшего вычисления стоимости квартиры вычисляем площадь балконов по формуле Sb += ai, учитывая, что ti=="balcony". Стоимость квартиры рассчитываем по формуле Ck=(S-Sb/2.)*c.

    Ссылки

    e-olymp
    ideone

    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 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