e-olymp 8659. Байтик та шахи

Задача

Вкотре запізнившись на урок, Байтик, проходячи повз ігрову кімнату, помітив шахову дошку. Порахував усі клітинки на ній, і йому стало цікаво: скільки різних квадратів зі стороною $k(1 \leqslant k \leqslant n)$ можна розмістити на дошці розміру $n$.

Вхідні дані

Натуральне число $n$ $( n\leqslant 10000)$ розмір шахової дошки.

Вихідні дані

Єдине число – кількість різних квадратів, які можна розмістити на шаховій дошці.

Тести

Входные данные Выходные данные
1 3 14
2 10 385
3 99 328350
4 999 332833500
5 10000 333383335000

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

Рішення

Вирішити цю задачу можна за допомогою квадратного пірамідального числа — числа, яке висловлює кількість квадратів з різними сторонами в сітці $n$*$n$. Загальна формула для пірамідального числа порядку $n$: $\sum\limits_{k = 1}^{n} k^{2} = \frac{n(n+1)(2n+1)}{6}$. Використаємо виведену формулу для лінійного обчислення, щоб не використовувати цикли і зменшити час роботи програми.

Посилання

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] , используя длинную арифметику ( умножение длинного числа на короткое ).
Иллюстрация для восьми ладей:

В коде № 1 разбиваем вектор на ячейки по три цифры. Но, некоторые ячейки могут иметь менее чем три цифры. С учетом того, что перенос может состоять не из трех цифр, следует выводить результат так: cout << setw(3) << setfill('0') << res[i];.
В коде № 2 разбиваем строку посимвольно.

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

  • Безусловно, для использования векторов и строк нам понадобятся соответствующие  библиотеки: #include и #include .
  • Для вывода данных в коде № 1 стоит подключить библиотеку #include .

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

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

Задача

prb1488

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

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

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

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

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

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

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

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

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

Тесты

Ввод Вывод
1 a1 d1
b2
2 h8 e8
g7
3 e5 b5
d4
4 c8 f8
d7
5 h6 e6
g5

Код

Решение

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

Ссылки

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

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

e-olymp 2820. Перемещение коня

Задача с сайта e-olimp №2820Перемещение коня

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

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

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

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

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква (ah), задающая столбец и второй – цифра (18), задающая строку на шахматной доске.

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

Для каждого теста вывести одну строку следующего содержания: «To get from xx to yy takes n knight moves.» (см. пример выходных данных).

Тесты:

Пример входных данных Пример выходных данных
e2 e4 To get from e2 to e4 takes knight 2 moves.
a1 b2 To get from a1 to b2 takes knight 4 moves.
b2 c3 To get from b2 to c3 takes knight 2 moves.
a1 h8 To get from a1 to h8 takes knight 6 moves.
a1 h7 To get from a1 to h7 takes knight 5 moves.
h8 a1 To get from h8 to a1 takes knight 6 moves.
b1 c3 To get from b1 to c3 takes knight 1 moves.
f6 f6 To get from f6 to f6 takes knight 0 moves.

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

Данную задачу можно решить с помощью алгоритма поиска в ширину. Из начальной клетки мы ищем все возможные ходы пока не попадем в нужную клетку. Чтобы получить длину пути, нужно хранить длины путей до данной клетки в матрице и обновлять ее, по ходу продвижения (если новое значение меньше того, что записано в клетке — записываем его, а если больше — оставляем предыдущее). Длина в начальной клетке — 0, а длина в каждой последующей — 1.

Ссылка на засчитанное решение и код решения на ideone.

А 1041

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

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

Определяем переменные: количество слонов, длинна и ширина шахматного поля, массив клеток поля. Далее определяем булевы переменные для добавления и удаления диагоналей, расположения слонов, выхода из рекурсии. Функция «giagonal» осуществляет все операции с диагоналями. Добавляет/удаляет диагонали(параллельные главной или побочной). Она принимает булевы переменные для определения того, добавляем мы главную диагональ или побочную, собираемся мы добавлять диагональ или удалять. А также координаты начала диагоналей, координаты расположения слона.  Если клетку бьет какой-либо слон, прибавляем к ее значению 1. При этом число свободных клеток уменьшается. Если же мы удаляем диагональ, то просто уменьшаем количество бьющих данную клетку слонов (это указывается в самой клетке). Если удаленный слон был единственным, кто ее бил, увеличиваем число свободных клеток. Функция «space». Она используется как для удаления, так и для добавления диагоналей. В ней мы запоминаем последнее расположение слонов на доске и далее ищем начало прохода диагоналей. Для этого сначала мы определяем в какой части доски находится поставленный слон и исходя из этого, если оказалось, что координата по горизонтали больше координаты по вертикали, то следовательно начало первой диагонали будет в первой строке, в противном случае ее начало будет в первом столбце. Вторые координаты зависят от разности j-i. При поиске начала второй диагонали используем сумму i+j, если эта сумма меньше 8 (то есть слон находится ближе к верхнему левому углу доски, чем к правому нижнему) тогда диагональ начинается в первом столбце. Функция «find_permutation» (рекурсивно расставляет слонов). С каждой новым поставленным слоном увеличиваем переменную level, для определения в последствии момента установки последнего слона. Просматриваем клетки, если какая-то из них не под боем-ставим туда слона и запускаем функцию «space» для него. Так расставляем их, пока число слонов не достигнет 8. Если после какой-либо расстановки мы нашли правильный ответ, то используя булеву переменную isEnd выходим из рекурсии. Если после установки восьмого слона оказалось, что все поля были заполнены, то мы выводим: «Ответ найден» и печатаем доску (если булева переменная is_set — true, то есть этот элемент слон, тогда выводим 1, остальные клетки — 0). Далее выходим из всех циклов, определив переменную isEnd = true. Удаляем слонов и битые ими поля. Конец программы.

ideone.com

А1035

Задача. Указать маршрут коня. Начинающегося на одном заданном поле шахматной доски и оканчивающемся на другом. Никакое поле не должно встречаться в маршруте дважды.

Пример

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

b1

a1
b3
d2
b1
a1
h8
a1
c2
e3
g2
h4
g6
h8

 

Решение

Читаем входные данные. Преобразуем их в координаты начального и финального поля на шахматной доске. Массив chessboard  сначала заполняем -1 (не пройденные поля), затем значение в поле с начальными координатами присваиваем 0. Затем будем отмечать все доступные ходы коня до тех пор пока не изменится значение в финальном поле. Затем, если у нас не совпали начальное и финальное поле будем восстанавливать путь коня. Создаем массив в котором и будет путь коня. Первое значение которое мы заносим в массив будет наше финальное поле. Затем с этого поля будем рассматривать все возможные ходы которые пройдут по уже помеченным клеткам. Если в финальное поле можно было попасть несколькими путями одинаковой длины то нам не имеет значение каким из них возвращаться в начальное поле. Затем выводим массив пути в обратном порядке.

Код на ideone.

e-olimp 1098. Ходи ферзем!

Задача о восьми ферзях

Задача о восьми ферзях

Задача. На шахматной доске 8х8 произвольным образом расставлено ферзей, по одному на каждой вертикали, других фигур на доске нет. Ферзь может ходить на любое количество клеток как по диагонали, так и по вертикали или горизонтали, но при этом не может перепрыгивать через другие фигуры. Необходимо добиться такой позиции, в которой ни один ферзь не находится под боем любого другого, и сделать это за минимальное количество ходов.

Входные данные. В одной строке задано сначала натуральное число T (T < 6) — количество тестов. Далее через пробел задано T блоков по 8 целых чисел от 1 до 8 – номера горизонталей, на которых находится ферзь с i-той вертикали. Вертикали пронумерованы подряд.

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

Тесты

Входные данные Выходные данные Комментарий
2 1 1 1 1 1 1 1 1 2 4 6 8 3 2 7 5 71 пройден

Решение

«Поиск с возвратом» в задаче о восьми ферзях.
Алгоритм.
При решении задачи используется два массива : массив расстановок из теста и массив правильной расстановки. Первоначально массив правильных расстановок — пустой (все значения элементов массива = -1).

Для вычисления правильных расстановок вызывается рекурсивная функция line_up (параметром которого является номер столбца). Внутри функции line_up вызывается функция check (параметр — номер столбца), она проверяет горизонтальную линию и две диагонали на поля, которые бьет ферзь. Элементам массива правильных расстановок присваиваются номера горизонтальных линий (алгоритм «Поиск с возвратом»).

Как только достигается одна из возможных правильных расстановок вызывается функция calc_min_strok(). Если элемент одного массива не равен элементу другого — это ход. Функция calc_min_strok() вычисляет количество ходов для данной расстановки и решает минимальное оно или нет для данного теста.

Решение на Java:

(Что бы прошло на e-olimp нужно удалить все комментарии)

 

Ю2.25

87305Задача. На шахматной доске стоят черный король и белые ладья и слон (ладья бьет по горизонтали и вертикали, слон — по диагоналям). Проверить, есть ли угроза королю и если есть, то от кого именно. Учесть возможность защиты (например, ладья не бьет через слона).

[latex]x _{1}, y_{1}[/latex]- координаты слона.

[latex]x _{2}, y_{2}[/latex]- координаты ладьи.

[latex]x _{3}, y_{3}[/latex]- координаты короля.

Таблица:

[latex]x _{1} [/latex] [latex]y _{1} [/latex] [latex]x _{2} [/latex] [latex]y _{2} [/latex] [latex]x _{3} [/latex] [latex]y _{3} [/latex]  Предполагаемый результат  Комментарий
 1  1  2  2  4  4  Ладья перекрывает шаг от слона.  Тест пройден
 4  5  2  5  5  5  Слон перекрывает шаг от ладьи.  Тест пройден
 1  1  4  5  5  5  Короля атакует и слон и ладья.  Тест пройден
 5  1  4  5  5  5  Ладья атакует короля.  Тест пройден
 5  1  5  3  5  5  Ладья атакует короля.  Тест пройден
 3  1  4  2  5  3   Ладья перекрывает шаг от слона.  Тест пройден
 4  2  3  1  5  3  Слон объявляет шаг королю.  Тест пройден
 1  4  5  3  2  2  Короля не атакует никакая фигура.  Тест пройден

Исходный код программы:

Описание:

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

Алгоритм:

  1.  Объявляем переменные и вводим их значения.
  2. Проверка условий.
    1. Проверка правильности ввода (не совпадают  координаты фигур).
    2. Проверка условия №1.  Проверяем, может ли короля хоть кто-то атаковать. Т. е. стоят ли ладья и король на одной горизонтальной или вертикальной линии или стоит ли король на одной диагонали со слоном.
    3. Проверка условия №2. Проверяем отдельно ладью. Если какая-то координата у ладьи и короля совпадает, то проверяем, находится ли слон между ними. Вывод результата.
    4. Проверка условия №1. Проверка слона, если король и слон расположены на одной диагонали, то проверяем, находится ли ладья между ними. Вывод результата.
  3. Окончание работы.

Ссылка на Ideone.

Ю4.26

TALVEZ-NOSSO-PERSONAGEM-NA-HISTRIA1Задача: На шахматной доске находятся король и несколько ферзей другого цвета. Проверить, находится ли король под угрозой и если да, кто ему угрожает. Положение фигур задано массивом A(8,8): 0 — клетка пуста, 1 — король, 2 — ферзь. Ферзь бьет по горизонтали, вертикали и диагоналям.

0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 2 0 0 0 2 2

Король под угрозой от ферзя на клетке (2,8) (по вертикали)

Король под угрозой от ферзя на клетке (8,2) (по горизонтали)

Король под угрозой от ферзя на клетке (8,8) (по диагонали)

Решение:

Ссылка на ideone C++: http://ideone.com/h4ECiW

Ссылка на ideone Java: http://ideone.com/sIJwPA

 

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

Ю2.26

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

[latex]x_{1}[/latex] [latex]y_{1}[/latex] [latex]x_{2}[/latex] [latex]y_{2}[/latex] [latex]x_{3}[/latex] [latex]y_{3}[/latex] Результаты Комментарий
6 8 3 5 6 3 Пара ферзей 1 и 2 угрожают друг другу

Пара ферзей 1 и 3 угрожают друг другу

Пройден
1 5 6 8 7 3 Никто никому не угрожает Пройден
3 3 8 8 7 1 Пара ферзей 1 и 2 угрожают друг другу Пройден
2 8 4 7 7 4 Пара ферзей 2 и 3 угрожают друг другу Пройден

 Тесты:

Код на С

Код на Java

 

Решение:

В случае если фигуры стоят на одной вертикали или горизонтали соответствующие координаты будут равны. Таким образом, проверяя на равенство координаты, узнаем о существовании угрозы. В случае если фигуры стоят на одной диагонали можно заметить, что [latex] \left|x_{1}-x_{2 }\right|=\left|y_{1}-y_{2} \right|[/latex]. Таким образом, проверив и это условие, точно определим есть угроза или нет.

Также надо отметить тот случай, когда не существует никакой угрозы . Для этого введем счетчик [latex]k[/latex]. Если между какой-либо парой фигур есть угроза, то [latex]k[/latex] увеличивается на единицу. Если после проверки вышеупомянутых условий [latex]k[/latex] остается равным нулю, то делаем вывод, что никто никому не угрожает.

 

 

Ю2.24

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

x y x1 y1 x2 y2 x3 y3
3 6 1 1 3 7 2 5 Угроза от второй ладьи
1 2 7 8 4 6 3 6 Угрозы нет
1 2 5 4 3 7 1 2 Ошибка

Введем координаты каждой фигуры на шахматной доске от 1 до 8 (использовать отрицательные или дробные числа не имеет смысла). Проверим совпадает ли хотя бы один из координат короля с координатой хотя бы одной ладьи. Если, да то выводим соответствующее сообщение, если нет то выведем, что угрозы нет.

Код программы на Java: