e-olymp 1327. Ладьи на шахматной доске

Задача

Ещё в детстве маленького Гарика заинтересовал вопрос: а сколькими способами на шахматной доске размером [latex]n \times n[/latex] можно расставить [latex] n [/latex] ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

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

Размер шахматной доски — натуральное число, не превышающее [latex] 1000 [/latex].

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

Выведите ответ, найденный Гариком.

Тесты

Входные данные Выходные данные
2 2
10 3628800
500 122013682599111006870123878542304692625357434280319284219241
358838584537315388199760549644750220328186301361647714820358
416337872207817720048078520515932928547790757193933060377296
085908627042917454788242491272634430567017327076946106280231
045264421887878946575477714986349436778103764427403382736539
747138647787849543848959553753799042324106127132698432774571
554630997720278101456108118837370953101635632443298702956389
662891165897476957208792692887128178007026517450776841071962
439039432253642260523494585012991857150124870696156814162535
905669342381300885624924689156412677565448188650659384795177
536089400574523894033579847636394490531306232374906644504882
466507594673586207463792518420045936969298102226397195259719
094521782333175693458150855233282076282002340262690789834245
171200620771464097945611612762914595123722991334016955236385
094288559201872743379517301458635757082835578015873543276888
868012039988238470215146760544540766353598417443048012893831
389688163948746965881750450692636533817505547812864000000000
000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000
999 402387260077093773543702433923003985719374864210714632543799
910429938512398629020592044208486969404800479988610197196058
631666872994808558901323829669944590997424504087073759918823
627727188732519779505950995276120874975462497043601418278094
646496291056393887437886487337119181045825783647849977012476
632889835955735432513185323958463075557409114262417474349347
553428646576611667797396668820291207379143853719588249808126
867838374559731746136085379534524221586593201928090878297308
431392844403281231558611036976801357304216168747609675871348
312025478589320767169132448426236131412508780208000261683151
027341827977704784635868170164365024153691398281264810213092
761244896359928705114964975419909342221566832572080821333186
116811553615836546984046708975602900950537616475847728421889
679646244945160765353408198901385442487984959953319101723355
556602139450399736280750137837615307127761926849034352625200
015888535147331611702103968175921510907788019393178114194545
257223865541461062892187960223838971476088506276862967146674
697562911234082439208160153780889893964518263243671616762179
168909779911903754031274622289988005195444414282012187361745
992642956581746628302955570299024324153181617210465832036786
906117260158783520751516284225540265170483304226143974286933
061690897968482590125458327168226458066526769958652682272807
075781391858178889652208164348344825993266043367660176999612
831860788386150279465955131156552036093988180612138558600301
435694527224206344631797460594682573103790084024432438465657
245014402821885252470935190620929023136493273497565513958720
559654228749774011413346962715422845862377387538230483865688
976461927383814900140767310446640259899490222221765904339901
886018566526485061799702356193897017860040811889729918311021
171229845901641921068884387121855646124960798722908519296819
372388642614839657382291123125024186649353143970137428531926
649875337218940694281434118520158014123344828015051399694290
153483077644569099073152433278288269864602789864321139083506
217095002597389863554277196742822248757586765752344220207573
630569498825087968928162753848863396909959826280956121450994
871701244516461260379029309120889086942028510640182154399457
156805941872748998094254742173582401063677404595741785160829
230135358081840096996372524230560855903700624271243416909004
153690105933983835777939410970027753472000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000

Программный код

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

Алгоритм решения данной задачи заключается в том, что нужно вычислить [latex]n! = 1\times 2\times 3\times \cdots\times n [/latex] , используя длинную арифметику ( умножение длинного числа на короткое ).
Иллюстрация для восьми ладей:

Детали реализации

  • Для реализации алгоритма я использовала класс java.math.BigInteger, подробнее о нем можно почитать здесь.
  • Также для ввода данных я использовала класс java.util.Scanner, подробнее о нем можно почитать тут и вот тут.

Ссылки :
Задача на e-olymp
Код на ideone
Засчитанное решение

e-olymp 1704. Умная черепашка

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

Имеется клетчатое поле размером $m\times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?

Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.

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

Два натуральных числа $m$ и $n$, не превышающие 30.

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

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

Тесты

Ввод Вывод
1 4 5 10
2 3 14 105
3 11 17 5311735
4 20 21 68923264410
5 30 30 30067266499541040

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

Решение

Для нахождения количества способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний, мы воспользуемся формулой из комбинаторики: $\frac{\left(n+m-2\right)!}{(n-1)!\times(m-1)!}$.  Для того, чтобы избежать больших чисел,  делим на наибольший множитель знаменателя (пусть это будет $\left(n-1\right)!$ ). Получаем: $ \frac{n\times(n+1)\times…\times(n+m-2)}{1\times2\times…\times(m-1)}$. Домножаем числитель, пока он не делится на очередной сомножитель знаменателя. Если делится, то делим и переходим к следующему сомножителю знаменателя.

Ссылки (циклы)

Код программы (динамическое программирование)

Решение

Заполним треугольную матрицу ответами для всех возможных значений $m$ и $n$ . Логика заполнения такая — если поле выглядит как полоска клеток, черепахе идти можно будет только вправо. Значит в первой строке (как и в столбце) будут все элементы равные 1. Поскольку в каждой клетке есть два варианта движения (вправо или вверх), остальные элементы будут заполняться как сумма ранее найденных значений для клеток справа текущей и над ней. Для диагональных элементов оба соседних расположены симметрично (то есть они равны), поэтому диагональный элемент будет равен удвоенному соседу справа. Решение намного быстрее, если нужно пройти много тестов, но тратит память на запоминание всех ответов.

Ссылки (динамическое программирование)

e-olimp 7848. Переставить соседние

Задача

Задан массив из $n$ целых чисел. Переставьте соседние элементы массива ($a_{0}$ с $a_{1}$, $a_{2}$ с $a_{3}$ и так далее). Если элементов нечетное количество, то последний элемент следует оставить на своем месте.

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

В первой строке записано число $n$. В следующей строке записано $n$ целых чисел. Все числа по модулю не превышают $100$.

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

Вывести обновленный массив.

Тесты

Входные данные Выходные данные
7
3 5 -7 7 5 -9 -4
5 3 7 -7 -9 5 -4
8
-9 81 27 -38 2 6 -56 -21
81 -9 -38 27 6 2 -21 -56
2
25 -76
-76 25
3
55 44 33
44 55 33
1
99
99

Код

Решение

Будем переставлять соседние элементы массива следующим образом: arr[1] с arr[0], arr[3] с arr[2] и так далее до конца массива (т.е. каждый нечетный по счету элемент меняем местами с предыдущим). При этом совершенно неважно, четное кол-во элементов или нечетное.

Ссылки

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

e-olimp 8234. Сходинки

Задача

Скількома способами можна потрапити на $n$-ту сходинку, якщо можна ступати на наступну, переступати через одну і через дві сходинки.

Вхідні дані

Одне число $n$ — номер сходинки $(n \leqslant 60)$.

Вихідні дані

Вивести кількість способів, якими можна потрапити на $n$-ту сходинку.

Тести

Вхідні дані Вихідні дані
0 1
5 13
15 5768
32 181997601
60 4680045560037375

Код № 1

Рішення

Розіб’ємо задачу на декілька простих. Спочатку розрахуємо кількість способів для однієї сходинки (1 спосіб), потім для двох (2 способи: 0 $\rightarrow$ 1 $\rightarrow$ 2; 0 $\rightarrow$ 2) і також потрібно врахувати випадок, коли кількість сходинок дорівнює нулю (1 спосіб). Далі легко помітити, що кожне наступне значення дорівнює сумі трьох попередніх звідки і отримуємо формулу:
arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
Також цю задачу можна вирішити за допомогою рекурсії. Я використала рекурсію з запам’ятовуванням для того, щоб уникнути переповнення стеку викликів (загальна ідея така: при кожному виклику функції перевіряємо, чи маємо ми вже це значення, і якщо ні, рахуємо його. Таким чином ми будемо використовувати кожне значення лише один раз).

Код № 2

Посилання

Умова задачі на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone

e-olimp 9536. Сумма матриц

Задача

Заданы две матрицы $A$ и $B$. Найдите их сумму $C$ = $A$ + $B$.

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

Первая строка содержит размеры матриц $n$ и $m$ $(1 \leqslant n, m \leqslant 100)$. Следующие $n$ строк содержат по $m$ целых чисел и описывают матрицу $A$. Далее следует пустая строка, после чего в таком же формате задается матрица $B$.

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

Выведите матрицу $С$: $n$ строк по $m$ целых чисел.

Тесты

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

3

5
1 5
4 3 7 2 1

3 2 2 1 6

7 5 9 3 7
2 2
0 4
2 3

5 4
1 6

5 8
3 9
3 4
3 4 5 6
1 2 3 4
7 6 5 4

0 0 -3 -2
-1 3 4 5
5 6 1 2

3 4 2 4
0 5 7 9
12 12 6 6
3 3
2 -128 47
-365 5 56
243 42 12

678 43 76
4 345 -23
97 -453 18

680 -85 123
-361 350 33
340 -411 30

Код

Решение

Чтобы найти сумму двух матриц, необходимо сложить их соответствующие элементы.

Ссылки

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

e-olimp 1658. Факториал

Задача

Вычислите факториал числа.

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

Одно целое число [latex]n[/latex] ([latex] 0 \leqslant n \leqslant 20[/latex]).

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

Выведите значение [latex]n! = 1 · 2 · 3 · … · n.[/latex]

Тесты

Входные данные Выходные данные
3 6
0 1
20 2432902008176640000

Код № 1

Решение № 1

Факториал натурального числа [latex]n[/latex] определяется как произведение всех натуральных чисел от [latex]1[/latex] до [latex]n[/latex] включительно.

Код № 2

Решение № 2

Также факториал числа можно найти при помощи рекурсивной функции (функции, которая вызывает сама себя).

Ссылки

Условие задачи на E-Olymp
Код задачи № 1 на Ideone
Код задачи № 2 на Ideone

e-olymp 8680. Чётные соседи

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

Задана последовательность целых чисел. Подсчитать количество элементов, у которых чётные соседи.

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

В первой строке задано количество элементов последовательности $n$ $(n \leqslant 100)$. Во второй строке заданы сами элементы, значение каждого из которых по модулю не превышает $100$.

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

Вывести в одной строке количество элементов последовательности с чётными соседями.

Тесты

Входные данные Выходные данные
1 6
1 2 3 4 5 6
2
2 9
3 6 3 5 2 9 1 2 5
0
3 3
2 1 2
1
4 6
13 24 54 66 44 77
2
5 4
100 224 666 222
2

Программный код

Решение

Идея решения задачи состоит в том, чтобы создать три переменные: $prev$ (предыдущий), $pres$ (настоящий, текущий) и $fut$ (будущий). Затем в цикле мы перезаписываем эти переменные т.е.: настоящий становится прошлым, будущий настоящим, а новый будущий мы читаем из cin. Так же, в ходе решения задачи обнаружилась проблема с чтением количества элементов. Допустим, если мы записали, что $n=6$, а дальше ввели $10$ элементов, то количество элементов с чётными соседями будет считаться для $10$ элементов. Чтобы избежать этого мы ограничиваем количество читаемых элементов с помощью счётчика i++ и цикла while.

Ссылки

e-olymp 9410. Студенческая любовь

Задача

Нурдаулет и Жарасхан тренируют студентов. К каждому студенту у них имеется свое собственное отношение, которое выражается как числа $a_{i}$ (для Нурдаулета) и $b_{i}$ (для Жараскана), которые называются индексом любви студентов. Аскар попросил их рассчитать коэффициент несправедливого отношенияКоэффициент несправедливого отношения — это разница между самым большим и самым маленьким индексом любви. Чтобы не показывать свои, возможно, большие коэффициенты несправедливого отношения, они решили обмануть: каждый перемешивает свой массив, после чего формируется новый массив $c_{i}$ = $a_{i}$ + $b_{i}$, и его коэффициент несправедливого отношения передается Аскару. Какое минимально возможное значение коэффициента они могут достичь?

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

Первая строка содержит одно целое число $n$ $(1 ⩽ n ⩽ 200000)$. Вторая строка содержит $n$ целых чисел $a_{i}$ $(-10^6 ⩽ a_{i} ⩽ 10^6)$. Третья строка содержит $n$ целых чисел $b_{i}$ $(-10^6 ⩽ b_{i} ⩽ 10^6)$.

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

Выведите одно число — ответ на задачу.

Тесты

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

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

1
2
-3 -5
3 5
0
2 1
5
-2
0
3 5
-5 -2 -1 0 4
5 4 0 0 -1
4
4 9
1000 -22 333 -56 1 2 -77 -650 10
-7 166 -333 90 -565 12 788 -800 111
523

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

Решение

Коэффициент будет минимальным в том случае, когда все элементы массива $c_{i}$ будут отличаться друг от друга как можно меньше. Для этого отсортируем один массив по убыванию, другой — по возрастанию и почленно сложим. После этого останется только найти максимальный и минимальный элементы полученного массива.

Ссылки

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

Код решения ideone

e-olymp 4439. Возведение в степень

Задача

Вычислить значение $a^b$.

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

Два натуральных числа $a$ и $b$.

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

Выведите значение $a^b$, если известно что оно не превосходит $10^{18}$.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 1 100 1
 2 2 10 1024
 3 3 7 2187
 4 8 9 134217728
 5 10 10 10000000000
 6 100 9 1000000000000000000

Код

Решение

Для решения задачи создадим функцию «pow()», заметим, что для любого числа $a$ и чётного числа $b$ выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
$$a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$$
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного $b$ мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень b нечётна. Здесь мы поступаем очень просто: перейдём к степени b-1, которая будет уже чётной:
$$a^b = a^{b-1} \cdot a$$
Итак, мы фактически нашли рекуррентную формулу: от степени $b$ мы переходим, если она чётна, к $\frac{b}{2}$, а иначе — к $b-1$.

Примечание

Задача требует использование быстрого алгоритма, так как прямое умножение $b$ раз для возведение в $b$-ю слишком медленно, из-за большого количества перемножений. Алгоритм быстрого возведения в степень — это предназначенный для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени.

Ссылки

Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp

e-olymp 8916. Первые парные

Первые парные

Программа должна ввести с консоли натуральное число [latex] n [/latex] и вывести в порядке возрастания [latex] n [/latex] первых четных натуральных чисел.

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

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

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

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

Тесты

Входные данные Выходные данные
1 3 2 4 6
2 8 2 4 6 8 10 12 14 16
3 5 2 4 6 8 10

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

 

Решение

Решением этой задачи является вывод через пробел удвоенных чисел от 1 до [latex] n [/latex].

Ссылки

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