e-olymp 8688. Количество чисел без 8

Задача

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

Входные данные:
В первой строке задано число $n$ $(1 \le n \le 10^{18})$.

Выходные данные:
Выведите одно число — количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Тесты

Входные данные Вывод программы
10 9
25833798135522720 4918510377816614
88888888888888 20334926626631

Continue reading

e-olymp 8701. Кузнечик-попрыгунчик

Задача

Кузнечик-попрыгунчик долго сидел на отметке [latex]0[/latex] числовой прямой, так долго, что придумал инновационную методологию своего перемещения. Такую, что за каждую итерацию движения он выполняет ровно два прыжка, перемещаясь сначала на [latex]a[/latex], а затем на [latex]b[/latex] единичных отрезков по числовой прямой, причем, если число положительное, то он движется вправо, а если отрицательное, то влево. Продолжительность прыжка в секундах равна соответствующему количеству единичных отрезков, на которое переместится кузнечик.

Например, если [latex]a = 3[/latex], а [latex]b = — 2[/latex], то через [latex]3[/latex] сек. он будет на отметке [latex]3[/latex], а через [latex]5[/latex] сек. от начала движения попадет на отметку [latex]1[/latex]. Далее, на [latex]8[/latex] секунде переместится на отметку [latex]4[/latex], а на [latex]10[/latex] секунде вернется на [latex]2[/latex].

При заданных [latex]a[/latex] и [latex]b[/latex] найти сколько необходимо времени в секундах, чтобы допрыгать до отметки x числовой прямой или вывести [latex]-1[/latex], если это невозможно.

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

Целочисленные значения [latex]a[/latex], [latex]b[/latex], [latex]x[/latex] — в одной строке через пробел. Значение по модулю не превышают [latex]10^{9}[/latex].

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

Ответ на задачу.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 3 -2 1 5
2 100 200 0 0
3 -10 -20 -900 900
4 5 -6 3 27
5 1 3 10 -1

Код программы (с использованием условных операторов)

Решение задачи (с использованием условных операторов)

Для решения данной задачи сначала проверим не находимся ли мы уже в точке [latex]0[/latex], после проверим не равна ли сумма дистанций прыжков [latex]0[/latex], если равна, то также проверим можно ли добраться до точки x за один прыжок a. Если возможно выводим a. После проверяем возможность добраться до точки x двумя способами:

  1. Сначала добравшись до точки x-a прыжками вида a+b, а после совершив один прыжок на дистанцию a
  2. Добраться до точки x исключительно прыжками вида a+b

Если одним из способов невозможно добраться, то присваиваем переменной соответствующей потраченному времени MAX, а после выводим минимум из переменных possible_ans1, possible_ans2(в случае, если обеими способами невозможно добраться, т.е. обе переменные равны MAX выводим -1).

Код программы (без использования условных операторов)

Решение задачи (без использования условных операторов)

Заранее вычислим значения s(пройденное расстояние за один прыжок вида a+b) и t(время, потраченное на один прыжок вида a+b). После поочередно проверим выполнение всех условий, описанных ранее. При выполнении какого-либо из условий, выводим соответствующее время, если ни одно из условий не выполнилось то выводим [latex]-1[/latex].

e-olymp 497. Лентяй

Задача

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

Входные данные:
Первая строка содержит количество тестов. Каждый тест состоит из количество предметов $n$ $(1 \le n \le 100)$, которые нужно сдать Валере. Далее идет $n$ строк, каждая из которых состоит из двух чисел $a$ и $b$ $(1 \le a \le b \le 31)$, задающих интервал работы очередного преподавателя.

Выходные данные:
Для каждого теста вывести в отдельной строке "YES" если возможно встретить всех преподавателей за один день, или "NO", если это невозможно.

Тесты

Входные данные Вывод программы
2
1
1 2
2
1 2
3 4
YES
NO
1
1
5 6
YES
2
2
1 4
7 9
3
1 30
2 5
5 10
NO
YES

Continue reading

e-olymp 2322. Столбцы

Столбцы

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

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

В первой строке задано число [latex]x[/latex], не превышающее по модулю 2 [latex]\cdot[/latex] 109. Во второй строке задано число [latex]n \left(1 \leqslant n \leqslant 100\right)[/latex]. Каждая из следующих [latex]n[/latex] строк содержит [latex]n[/latex] целых чисел, не превышающих по модулю 2 [latex]\cdot[/latex] 109 — числа в ячейках таблицы.

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

Для каждого столбца в отдельной строке выведите YES, если в нем есть число [latex]x[/latex], и NO в противном случае.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1
2
0 1
0 0
NO
YES
2 23
3
23 0 23
21 12 23
11 13 23
YES
NO
YES
3 7
1
0
NO
4 13
3
13 33 75
23 45 31
13 13 13
YES
YES
YES

Код

Решение

Для решения этой задачи заведём массив на [latex]n[/latex] элементов, в котором каждый элемент будет счётчиком соответствующего столбца. В цикле будем смотреть все элементы и, если нам встретится элемент [latex]x[/latex], увеличим соответствующий счётчик. Затем в другом цикле смотрим счётчик каждого столбца, если он больше нуля, то выводим YES, иначе — NO.

Запустить код (ideone) можно здесь
Задача на E-olymp

Коды Грея

Задача

Frank Gray (13 September 1887 – 23 May 1969) was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic

Frank Gray (13 September 1887 – 23 May 1969) was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic

Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.
Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: «двоичный отражённый (рефлексный) код Грея». Именно этот код обычно имеется в виду, когда говорят о неконкретном «коде Грея».
Отображённый двоичный код Грея строится следующим образом. Начинаем со строк [latex]0[/latex] и [latex]1[/latex], которые представляют соответственно целые числа [latex]0[/latex] и [latex]1[/latex].
[latex]0[/latex]
[latex]1[/latex]
Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим [latex]1[/latex] слева от новых записей списка, а слева от уже имевшихся разместим [latex]0[/latex].
[latex]00[/latex]
[latex]01[/latex]
[latex]11[/latex]
[latex]10[/latex]
Таким образом получен отражённый код Грея для [latex]n = 2[/latex]. Чтобы получить код для [latex]n = 3[/latex], повторим описанную процедуру и получим:
[latex]000[/latex]
[latex]001[/latex]
[latex]011[/latex]
[latex]010[/latex]
[latex]110[/latex]
[latex]111[/latex]
[latex]101[/latex]
[latex]100[/latex]
При таком способе построения легко увидеть по индукции по [latex]n[/latex], что, во-первых, каждая из [latex]2n[/latex] комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.
Для каждого заданного числа [latex]k[/latex] вывести десятичное значение [latex]k[/latex]-го кода Грея.

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

Во входном файле содержится некоторый набор тестовых данных, каждое число [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает [latex]10^5[/latex].

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

Для каждого заданного числа [latex]k[/latex] вывести в отдельной строке десятичное значение [latex]k[/latex]-го кода Грея.

Тесты

Входные данные Выходные данные
1 3 2
14 9
5 7
12 10
2 0 0
72 108
265 397
4781 7163
50642 42811
3 1010234 581415
96721758 119682801
640214927 893162568
2456987013 3679188807
51027963402 60418988303
1000000000000000000 797398725282889728

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

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

Объявляем переменную [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) типа unsigned long int для считывания чисел из входного потока. Цикл while работает столько раз, сколько чисел во входном потоке (по условию задачи их количество [latex]\le 10^5[/latex]). В цикле вычисляется Код Грея числа [latex]k[/latex] путем побитовой операции «исключающее ИЛИ», применимого к [latex]k[/latex] и к результату побитового сдвига [latex]k[/latex] на [latex]1[/latex] бит вправо ([latex]k \gg 1[/latex]).
Ссылка на алгоритм ниже.

Ссылки

Code Gray: theory
e-olymp
ideone

e-olymp 75. Пираты и монеты

Задача

[latex]n[/latex] пиратам удалось справедливо разделить клад из [latex]m[/latex] золотых монет — каждый получил свою часть согласно своему пиратскому рангу и стажу. Самый молодой пират взял [latex]a[/latex] монет, а каждый следующий пират брал на одну монету больше, чем предыдущий его коллега. Последним был капитан, которому досталось вдвое больше от запланированного, очевидно, что после него монет больше не осталось.

Сколько было пиратов вместе с капитаном, если известны [latex]a[/latex] и [latex]m[/latex]. Так как капитан без команды просто пират, то [latex]n > 1[/latex].

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

Два натуральных числа [latex]a[/latex] и [latex]m[/latex] ([latex]1 \leq a \leq 100, m < 15150[/latex]). Входные данные корректны.

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

Количество пиратов [latex]n[/latex].

Тесты

 #  ВХОДНЫЕ ДАННЫЕ  ВЫХОДНЫЕ ДАННЫЕ
 1  5 25  3
 2  3 24  4
 3  4 38  5
 4  5 55  6
 5  6 75  7

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

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

Для решения задачи воспользуемся формулой арифметической прогрессии, которая в данном случае равна: [latex](2a + n — 1)\frac{n}{2} + a + n — 1[/latex]. Отсюда получаем квадратное уравнение : [latex]\frac{n^{2}}{2} + n(a + \frac{1}{2}) + a — 1 = m[/latex], упростим и получим: [latex]n^{2} + 2an + n + 2a — 2 = 2m[/latex]. В коде задаем чему равно [latex]b[/latex], [latex]c[/latex] и [latex]d[/latex]. Где [latex]b[/latex] и [latex]c[/latex] — коэффициенты квадратного уравнения, а [latex]d[/latex] — дискриминант квадратного уравнения, который вычисляем по формуле: [latex]b^{2} — 4c[/latex]. Они нужны для нахождения корня данного квадратного уравнения. При этом ответом на задачу будет только один корень квадратного уравнения, так как количество пиратов не может принимать отрицательное значение. Поэтому вычисляем корень квадратного уравнения по формуле: [latex]\frac{-b + \sqrt{b}}{2}[/latex], тем самым получаем ответ на нашу задачу.

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

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

В данном способе используем цикл. Как он работает: в условии цикла задаем проверку, когда наступит очередь капитана и будет выполнятся равенство вида [latex]m — 2a = 0[/latex] цикл прекратит свою работу. Пока это равенство не будет выполнятся цикл будет выполнять работу арифметической прогрессии, постоянно увеличивая количество монет [latex]a[/latex] на каждого пирата при этом, вычитая каждый раз из общего клада [latex]m[/latex], также, пока не выполняется данное равенство, считаем количество пиратов [latex]n[/latex], путем прибавления [latex]n + 1[/latex], пока работает цикл. И когда цикл прекращает свою работу, в конце учитываем капитана и к полученному количеству пиратов [latex]n[/latex] прибавляем [latex]n + 1[/latex]. И получаем ответ на нашу задачу.

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

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

В данном способе воспользуемся рекурсивной функцией и условными операторами. Как это работает: внутри рекурсивной функции расписываем условные операторы, которые определяют равенством [latex]m — 2a = 0[/latex] — когда наступила очередь капитана, а пока это условие не выполняется, функция будет вызывать сама себя пока это условие не удовлетворится, функция каждый раз вызывается с новыми параметрами соответственно. Где [latex]a[/latex] — количество монет даваемое пиратам, увеличивается по рангу каждого пирата, [latex]m[/latex] — клад, от него отнимаем текущее [latex]a[/latex], и [latex]n[/latex] — количество пиратов, считаем пиратов. И в конце выводит количество пиратов. Задача решена.

Ссылки

e-olymp 458. Черно-белая графика

Задача

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной $w$ и высотой $h,$ разбитых на $w × h$ единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

Во многих областях очень часто возникает задача комбинации изображений. Одним из простейших методов комбинации, который используется при работе с черно-белыми изображениями, является попиксельное применение некоторой логической операции. Это означает, что значение пиксела результата получается применением этой логической операции к соответствующим пикселам аргументов. Логическая операция от двух аргументов обычно задается таблицей истинности, которая содержит значения операции для всех возможных комбинаций аргументов. Например, для операции «ИЛИ» эта таблица выглядит так.

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

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

Первая строка содержит два целых числа $w$ и $h$ $(1 \leq w, h \leq 100).$ Последующие $h$ строк описывают первое изображение и каждая из этих строк содержит $w$ символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента нули, второе – результат в случае, если первый аргумент ноль, второй единица, третье – результат в случае если первый аргумент единица, второй ноль, а четвертый – в случае, если оба аргумента единицы.

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

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

Тесты

Входные данные Выходные данные
 1 5 3
01000
11110
01000
10110
00010
10110
0110
11110
11100
11110
2 2 3
010
111
000
101
1010
11
10
10
3 4 4
1111
0101
0000
1110
0011
0101
0111
1111
0011
1111
0101
0000
1110
4 3 6
100011
000111
000000
111011
001100
010101
1000
000
100
110
000
101
010

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

( использован одномерный массив)

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

(использован двумерный массив)

Решение

Объявляем два булевых динамических массива под две пиксельные таблицы и один статический для таблицы истинности, вводим входные данные. Затем поочерёдно сравниваем соответствующие элементы массивов с помощью функции my_operation, которая принимает две переменные a и b булевского типа и булев массив res с таблицей истинности, и возвращает соответствующее значение из таблицы для комбинации значений a и b. Результат сравнения выводим.

Ссылки

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 1519. Коды Грея

Задача

Френк Грей. Bell Lab 1930

Френк Грей. Bell Lab 1930

Бинарные коды Грея генерируются следующим образом. Рассмотрим последовательность
0
1
Отобразим строки вниз относительно горизонтальной черты, припишем к первой половине строк спереди 0, а ко второй отображенной половине 1. Получим последовательность:
00
01
11
10
Продолжая процесс, на следующем шаге получим последовательность из 8 чисел. Справа от кода находится его десятичное значение
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
Приведенные последовательности называются кодами Грея длины $n = 1, 2, 3$. Всего существует $2n$ разных кодов длины $n$. Каждые два соседних кода отличаются одним битом.

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

Первая строка содержит количество тестов $n$ (не более 250000). Каждая следующая строка содержит два числа: $n$ $(1 ≤ n ≤ 30)$ и $k$ $(0 ≤ k < 2^n)$.

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

Для каждого теста в отдельной строке вывести число, которое находится в $k$ — ой позиции последовательности кодов Грея длины $n$.

Тесты

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

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

Решение

В случае, если значение бинарного кода находится в первой части последовательности, т.е. $x$ < $2^{n-1}$, то ищем число, стоящее в позиции $k$ кода Грея длины $n-1$. В другом же случае ищем число, прибавив к
$2^{n-1}$ число в позиции $2^n-k-1$ длины $n-1$. Оформим данный алгоритм в виде рекурсивной функции.

e-olymp

ideone

e-olymp 8380. Эскалатор

Задача: Эскалатор

В Баку вскоре откроется новая станция метро. Эскалатор в метро состоит из n ступенек, пронумерованных целыми числами от $1$ до $n$. На ступеньках с номерами, кратными десяти, а также на первой и последней ступеньке, пишут их номера. При записи номера на каждую записанную цифру уходит одно и то же количество краски.

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

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

Одно целое число $n\;\left(1 \leq n \leq 10^{18}\right)$ — количество ступеней эскалатора.

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

Выведите суммарное количество цифр в номерах подписанных ступенек.

Тесты

Ввод Вывод
1000000000000000000 1788888888888888908
242 67
250 67
999 292
1000 293
1 1
2 2

Решение

Идея решения заключается в том чтобы искать количество помеченных ступенек на  отрезках $10-99,100-999,\ldots,10^{x}-\left(10^{x+1}-1\right).$ Легко понять что помеченных ступенек $9\cdot 10^{x}.$ Это суть метода, а остальное это реализация, которую я покажу в программе.

Ссылки

e-olymp 479. Вышивка “крестиком”

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

Задача

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

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

Сначала кол-во макетов, потом их номера. Все номера узоров у Вали имели одну странность — всегда были нечетными и не превышали 80.

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

Макеты, в порядке, перечисленном во входном файле, разделенные пустой строкой.

Тесты

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

1

2 3 5 X X
 X
X X

X   X
 X X
  X
 X X
X   X

2

1 9 X       X
 X     X
  X   X
   X X
    X
   X X
  X   X
 X     X
X       X

Код

 

Решение

В данной задаче будем использовать потоковую обработку. Сначала считываем количество макетов [latex] n [/latex]. Затем в цикле for (int l = 0; l < n; l ++);   считываем номера узоров.  Выводить [latex] X [/latex] будем по диагоналям (справа налево и наоборот). Однако, стоит учесть, что после последнего символа [latex] X [/latex] в строке, выводить пробел не стоит. В условии задачи данный факт не фигурирует, однако, если же сделать иначе, то задача на сайте e-olymp не пройдет. Из этого вытекает, что пробелы должны располагаться исключительно до последнего крестика в строке. Для этого во внутреннем цикле ставим соответсвующее условие, чтобы при достижении последнего крестика в строке осуществлялся переход на другую строку, если это возможно. Также стоит не забыть, что между разными узорами нужно пропускать строку.

Ссылки

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

Код в ideone.

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

Анаграммы

Анаграммы

Игорю стало интересно какое количество перестановок букв его фамилии существует. Для этого он выписал на листке бумаге все буквы своей фамилии по алфавиту и начал создавать новые перестановки этих букву в лексикографическом порядке, записывая их на листок.

После того как он закончил выписывать все перестановки Игорь устал и пошел учиться. Он взял словарь и начал учить новые слова. Через некоторое время Игорь заметил что некоторые из слов в словаре совпадают с записанными им перестановками на листке и задался вопросом, — а какие можно получить слова переставляя буквы из других в словаре.

Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.

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

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

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

Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.

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

Вывести все слова что имеют максимальное количество анаграмм в нем.

Решение

Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.

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

На выходе получим массив индексов слов у которых существует максимальное количество анаграмм, в данном словаре. Выведем эти слова и все анаграммы к ним в исходном варианте. Для этого нам и нужна строка  first.

Тесты

Ввод Вывод
 

1

 

2500 слов английского языка

trace react crate

dear dare read

post stop spot

Код

Код на ideone

e-olymp 8519. Сумма четных цифр

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

Задача

Задано длинное число. Найти сумму его четных цифр.

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

Одно натуральное число $n  (n ≤ 10^{100} )$.

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

Вывести сумму четных цифр числа $n$.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2345 6
2 3458937487534533459 32
3 888888888888888888888888888888 240

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

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

Переменная c — является переменной типа char, что означает, что cin в этом случае будет считывать по одному символу с потока. По этой причине, чтобы решить данную задачу, нужно считывать заданное число с помощью cin в цикле while до тех пор, пока происходит ввод данных с клавиатуры.  Проверяя каждую цифру введенного числа на четность, будем прибавлять четные к переменной sum.
Для работы с символом  c как с числом, будем писать c - '0'.

Ссылки

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

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

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

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

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

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

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

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

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

Тесты

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

Решение

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

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

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

Код

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

Решение

Код на ideone

e-olymp 2812. Уголок

Задача

Дана прямоугольная доска [latex]M×N[/latex], некоторые клетки в которой вырезаны. Сколькими способами можно поставить на неё «уголок» из трёх клеток так, чтобы все три клетки уголка находились внутри доски и не были вырезаны?

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

В первой строке входного файла даны два числа [latex]M[/latex] и [latex]N[/latex] [latex](1 \leq M, N \leq 100)[/latex], разделённые пробелом. В следующих [latex]M[/latex] строках содержится по [latex]N[/latex] символов в каждой; [latex]i[/latex]-ый символ [latex]j[/latex]-ой из этих строк равен ‘X’ (большая буква икс), если клетка вырезана, и ‘.’ (точка) в противном случае.

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

Выведите одно число — сколько существует способов поставить уголок на данную доску.

Тесты

Входные данные Выходные данные
2 2
..
..
4
2 3
..X
.X.
1
5 4
….
X.XX
….
X..X
..XX
12

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

Решение

Для решения данной задачи создаем динамический массив типа bool x на y. Заполняем соответствующий элемент значением true, когда вводится «.» и значением false в противном случае. Далее увеличиваем значение количества уголков на $1$, если существуют не пустые клетки.

Ссылки

e-olymp
Ideone

e-olymp 1226. Обмен иностранцами

Задача

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

Программа обмена работает следующим образом. Каждый из участников дает информацию о месте своем проживания и месте, куда бы он хотел переехать. Программа считается успешной, если каждый студент найдет для обмена подходящего партнера. Другими словами, если некоторый студент желает переехать из $A$ в $B$, то обязательно должен быть другой студент, который хочет переехать из $B$ в $A$. Это простая задача, если участников программы всего $10$. Но что делать если их будет $100001$?

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

Первая строка содержит количество тестов $t$. Первая строка каждого теста содержит количество студентов $n$ $(1 ≤ n ≤ 100001)$, за которыми следуют $n$ строк, описывающие данные по обмену. Каждая из этих строк содержит информацию об одном студенте — два целых числа, разделенные пробелом, соответствующих текущему месту проживания студента и месту, куда он желает переехать. Места описываются неотрицательными целыми числами, не большими $10^9$. Ни у одного из кандидатов место проживания и место желаемого переезда не совпадают.

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

Для каждого теста в отдельной строке вывести $«YES»$ если существует возможность успешно выполнить программу обмена и $«NO»$ иначе.

Тесты

Входные данные Выходные данные
2
2
1 2
2 1
2
31 13
13 31
YES
YES
1
4
17 3
28 15
15 28
3 17
YES
1
4
17 3
28 15
15 28
3 18
NO
3
2
1 2
3 4
2
47 7
7 47
2
12 34
12 34
NO
YES
NO

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

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

После задания переменной $n$ (количества студентов) очищаем мультимножество $M$. Для каждой пары $(a, b)$ нашего мультимножества проверяем, есть ли в нем пара $(b, a)$:
1. Если есть, то удаляем пару $(b, a)$.
2. Если нет, то вставляем $(a, b)$.
Если в конце мультимножество $M$ пустое, то у каждой пары $(a, b)$ существует соответствующая ей пара $(b, a)$, следовательно обмен студентами может быть произведен успешно.

Ссылки

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

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

Задача

Санта Клаус

Санта Клаус

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

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

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

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

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

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

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

Тесты

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

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

Решение

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

Ссылки

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

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

Задача

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

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

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

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

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

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

Тесты

 

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

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

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

Ссылки

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

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

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

e-olymp 7492. Будильник

Задача

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

Часы Алисы содержат четыре цифры: две для часов и две для минут. Например, часы ниже показывают [latex]9[/latex]:[latex]30[/latex] (ведущий ноль высвечивается).

Часы имеют следующее представление цифр:

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

Одно целое число [latex]n (0≤ n ≤30)[/latex] — количество подсвеченных сегментов на часах Алисы во сне.

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

Вывести пять символов в формате [latex]hh:mm[/latex] — время, показываемое часами Алисы во сне. Время должно быть корректным: [latex]0 ≤ hh < 24[/latex] and [latex]0 ≤ mm < 60[/latex]. Если существует несколько решений, то вывести любое. Если решения не существует, то вывести [latex]Impossible[/latex].

Тесты

Входные данные Выходные данные
23 00:02
28 Impossible
0 Impossible
15 01:12

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

Решение

Перебираем i и j (от 0 до 24 и 60 соответственно). a=seg[i/10] (для десятков) и a=seg[i%10] (для остальных чисел) то же самое делаем для j. Тем самым, мы перебираем все возможные варианты количества сегментов. Если a==n (количество сегментов) при переборе и в входных данных совпадает, то выводим наше время и выходим из цикла. Если же при переборе не было такого же числа сегментов, как в входных данных, то решения нет и мы, соответственно, выводим [latex]Impossible[/latex].

Ссылки

e-olymp
Ideone