e-olymp 8374. Нечетное количество раз

Задача 

Найдите число, которое встречается в последовательности нечетное количество раз.

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

Первая строка содержит натуральное число $n (n < 500000)$. Далее следуют $n$ натуральных чисел, каждое из которых меньше $10^6$.

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

Во входной последовательности только одно число $x$ повторяется нечетное количество раз. Другие числа повторяются четное число раз. Выведите $x$.

Замечание

В условии задачи на e-olymp опечатка, но, проанализировав входные и выходные данные примеров, несложно понять суть задачи. 

Тесты

Ввод Вывод
1 9
3 1 2 2 17 1 3 17 3
3
2 5
12 13 14 13 12
14
3 3
20 0 20
0
4 15
5 7 1 2 3 5 7 2 7 5 1 2 3 5 2
7
5 11
10 100 1000 100 100 100 1000 10 100 1000 100
1000

Код 1

Код 2

 

Решение

Для начала создадим динамический одномерный массив и считаем с потока ввода все его элементы. Конечно, можно было создать статический массив на 500000 элементов, но, скорее всего, памяти выделилось бы намного больше, чем было бы использовано.

Первый способ

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

Затем, заведём две переменные: счётчик и число. Последней присваиваем значение первого элемента массива. Сравниваем следующий элемент с тем, что лежит в переменной. Если они равны, увеличиваем счетчик. В счетчик с самого начала положим единицу, так как предполагаем, что в массиве есть хоть один элемент.

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

Второй способ

Применим исключающее «или» ко всем элементам массива. Предварительно создадим переменную равную нулю, в которой будем это проделывать. 

Так как xor двух одинаковых чисел равен нулю, то для любого количества пар одинаковых чисел он будет  равен нулю. А вот xor нуля и любого числа равен самому числу.

Таким образом, исключив все пары одинаковых чисел, наша переменная примет значение повторяющегося нечетное количество раз числа. 

Ссылки

Задача 8374 на e-olymp

Код 1 на Ideone

e-olymp 8376. Рамка

Задача

prb8376.gifРамка $x × y$ представляет собой прямоугольник $x × y$, из середины которого вырезали прямоугольник размером $(x — 2) × (y — 2)$. У нас имеется неограниченный запас плиток $a × 1$. Можно ли полностью замостить рамку $x × y$ плитками $a × 1$?

Например, рамку $5 × 6$ можно замостить плитками $3 × 1$, но нельзя плитками $4 × 1$.

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

Первая строка содержит два натуральных числа $x$ и $y (3 ≤ x, y ≤ 10^6)$. Вторая строка содержит количество типов плиток $n (1 ≤ n ≤ 1000)$. Третья строка содержит n натуральных чисел, не больших $10^6$ — длины плиток.

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

Выведите n строк, содержащих YES или NO. i-ая строка содержит YES если можно замостить рамку плитками i-го типа. Выведите NO иначе.

Тесты

Ввод Вывод
1 5 6
2
3 4
YES

NO

2 18 5
2
6 3
NO

YES

3 3 3
1
1
YES
4 200 4
3
2 3 4
YES

NO

NO

5 1000000 1000000
5
100000 2 1689 11 9004
NO

YES

NO

YES

NO

Код

Решение

Рассмотрим три случая размещения плиток. Для примера возьмем входные данные c e-olymp — $5 × 6$.

Обратим внимание, что ширина плитки равна одному. 

Первый случай. На рисунке изображен самый простой пример, когда длина плитки равна одному. Плитки по горизонтали идеально вписываются в размеры рамки. Это значит, что длина рамки кратна длине плитки. Если снизу и сверху рамку уложить плитками, то ширина рамки уменьшится, в связи с тем, что углы являются общими для ширины и длины. Получаем, что для того чтобы уложить остаток рамки плитками, длина плитки должна быть ещё и делителем ширины рамки, уменьшенной на две единицы.

Второй случай. На рисунке длина плитки равна двум. Тут по горизонтали плитки занимают всю длину без одного уголка. Это означает, что длина рамки минус один кратна длине плитки. Ширине ничего не остается как тоже «отдать» свою единицу. В результате, ширина рамки минус один тоже кратна длине плитки.

Третий случай. На рисунке длина плитки равна трём. Плитки укладываются тут не от края до края, а оставляя уголки рамки свободными. Так получаем, что длина рамки минус две единицы (уголки) кратна длине плитки. Ширина тоже кратна длине плитки, но только в полном размере.

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

Ссылки

Задача на e-olymp

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

e-olymp 8362. Множители

Задача

Найти число от $1$ до $n$ включительно такое, что в разложении его на простые множители количество множителей максимально. Если таких чисел несколько, выбрать максимальное из них.

Например, если $n = 7$, то ответом будет число $6$, как наибольшее число, имеющее в своем разложении $2$ простых множителя $2$ и $3$.

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

Одно целое число $n$ $(1 ≤ n ≤ 2^{31}- 1)$.

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

Вывести одно искомое число.

Тесты

Ввод Вывод
1 1 1
2 10 8
3 100 96
4 363 256
5 2147483647 1610612736

Код программы с использованием цикла

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

 

Решение

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

Заметим, что если заданное число будет единицей, двойкой или тройкой, то его и надо вывести на экран.

Условные операторы

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

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

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

Цикл

Создадим две переменные равные двум и трём и будем увеличивать их вдвое до тех пор, пока полученное число не превосходит заданное.

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

Ссылки

Задача множители на e-olymp

Решение задачи на Ideone циклом

Решение задачи на Ideone условными операторами

e-olymp 421. Йо-йо

Задача

Игрушка йо-йо состоит из катушки, на которую намотана нитка. Если, держа за конец нитки, отпустить катушку, то она будет, вращаясь, сначала опускаться вниз, а затем по инерции подниматься вверх. Но высота, на которую катушка поднимется, будет в $k$ раз меньше, чем высота, с которой она опустилась. Будем считать, что катушка остановилась, если высота её очередного подъема не превышает $1$.

Напишите программу, которая по длине нитки $l$ и коэффициенту $k$ считает количество подъемов катушки до остановки. Например, пусть $l = 17$ и $k = 2$, тогда катушка будет подниматься на высоты $8.5$, $4.25$, $2.1254$, $1.0625$, а затем остановится. Таким образом получится $4$ подъема.

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

Два целых числа $l (1 ≤ l ≤$ 109$)$ и $k (2 ≤ k ≤ 100)$.

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

Вывести одно число – количество подъемов.

Тесты

Ввод Вывод
1 17 2 4
2 4 2 1
3 135 9 2
4 1 2 0
5 1000000000 100 4

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

Решение

Для решения данной задачи достаточно найти максимальную степень $k$, которая будет меньше числа $l$. Значение показателя степени и будет количеством подъемов йо-йо. Ответ найдем с помощью логарифма, подключив библиотеку <cmath>. Используем формулу перехода логарифма к новому основанию, а каким будет это основание значения не имеет. Заметим, что нас интересует только целая часть логарифма — число подъемов.

Также необходимо учесть, что кaтушка остановится в случае, если высота её очередного подъема будет меньше либо равна $1$. Это означает, что, если $l$ будет степенью $k$, полученный с помощью логарифма ответ будет на единицу больше верного. Введем очень маленькую константу с для разрешения этой проблемы. На ответ она особо не повлияет, а вот от единицы поможет избавиться.

Ссылки

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

Задача 421 на e-olymp