e-olymp 1488. Шахматная головоломка

Задача

prb1488

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

В этот раз Борис задал Вове следующую головоломку: на шахматном поле размером $8 × 8$ клеток стоит одна шахматная фигура — конь. Необходимо расположить на поле еще две шахматные фигуры — ладью и слона, таким образом, чтобы они били коня, но не били друг друга, и конь не бил их. Так как Вова еще не очень силен в программировании, он попросил вас помочь ему с решением данной головоломки.

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

Ладья бьет те клетки, которые находятся на той же горизонтали или вертикали, что и она. Слон бьет те клетки, которые находятся на той же диагонали, что и он.

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

Первая строка входного файла содержит положение коня в следующем формате. Сначала буква от $a$ до $h$, обозначающая номер столбца в котором находится конь, потом цифра от $1$ до $8$, обозначающая номер строки.

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

В первую строку выведите положение ладьи в аналогичном формате, во вторую строку выведите положение слона.

Гарантируется, что требуемая расстановка всегда существует.

Тесты

Ввод Вывод
1 a1 a4
b2
2 h8 h5
g7
3 e5 d5
f6
4 c8 b8
d9
5 h6 e6
g7

Код

Решение

Самое первое, что важно заметить это то, что почти всегда существует больше одного варианта размещения ладьи и слона. Нас интересует любое. Разумеется, что чем более общая для всех случаев расстановка, тем проще будет код.

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

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

Остается только аккуратно прописать все  случаи.

Также можно не хранить массивы для ладьи и слона, а выводить частями. Это сэкономит немного памяти, но код станет менее разборчивым.

Код для общего случая

Решение для общего случая

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

Так как размер может быть не однозначным числом, массив на два элемента не подойдет. Будем использовать переменные.

Ссылки

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

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

Код для общего случая на Ideone

e-olymp 1485. Серия степеней матриц

Задача

По заданной матрице A размера n×n и положительному целому значению $k$ вычислить сумму $S = A + A^2+ A^3 + … + A^k.$

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

Первая строка содержит три положительных целых числа $n (n ≤ 30)$, $k (k ≤ 10^9)$ и $m (m < 10^4)$. Каждая из следующих $n$ строк содержит $n$ неотрицательных целых чисел меньших $32768$, задающих элементы матрицы $A$ в порядке возрастания строк.

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

Вывести элементы матрицы $S$ по модулю $m$ в таком же виде как и входная матрица $A$.

Тесты

Ввод Вывод
1 2 2 4
0 1
1 1
1 2
2 3
2 4 7 2
3 5 12
10 8 9
2 16 7
1 0 0 0
0 1 0 0
1 1 0 0
0 1 0 0
3 5 10 78
7 6 0 1 6
12 9 1 1 8
1 1 3 1 9
8 5 34 1 7
5 5 5 5 5
2 67 36 32 48
2 6 10 49 65
67 14 58 4 29
64 54 33 45 46
41 4 50 8 55
4 3 2 4
3 3 3
3 3 3
3 3 3
2 2 2
2 2 2
2 2 2
5 5 100 1000
1846 4675 8090 4539 1234
4567 7453 9564 6548 1111
5674 9876 5432 1010 1515
0 478 3 11 0
68303 7777 32767 14 8008
614 7 945 925 381
22 332 981 689 527
351 627 130 686 420
340 628 819 758 629
913 426 396 871 91

Код

Решение

Для решения данной задачи опишем матрицу как структуру и функциями зададим простейшие операции над матрицами — сложение и умножение. Результат обеих функций будем будем брать по модулю $m$, чтоб уменьшить числа, с которыми работаем.

Далее создадим функцию быстрого возведения в степень. $A^k$ представим как $\left(A^2\right)^\frac{k}{2}$ при четном  $k$ и $A × \left(A^2\right)^{\frac{k — 1}{2}}$ в противном случае. Такой алгоритм позволяет значительно уменьшить количество умножений.

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

Все, что еще необходимо сделать — вывести результат по модулю $m$.

Замечание

Тесты на e-olymp требуют отсутствия пробела после последнего столбца.

Ссылки

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

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

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

Код 3 (без массива)

 

Решение

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

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

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

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

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

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

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

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

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

Третий способ 

Идейно такой же как предыдущий. Отличается только тем, что мы не записываем числа в массив, а исключающее «или» работает сразу после того как число было прочитано.

Ссылки

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

Код 1 на Ideone

Код 2 на 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