Ю2.27 Шашечный эндшпиль

Задача из сборника задач по программированию Юркина А.Г. 2002 г.
Условие задачи:
В шашечном эндшпиле остались белая дамка и две черных пешки, позиции которых известны. Ход белых. Сможет ли дамка срубить одну или сразу обе пешки?

Входные данные:
-[latex]lady[/latex]-позиция дамки;
-[latex]pawn1[/latex]-позиция первой пешки;
-[latex]pawn2[/latex]-позиция второй пешки;

Тесты:

[latex]lady[/latex] [latex]pawn1[/latex] [latex]pawn2[/latex] Выходные данные
a1 b2 f6 Дамка срубит две пешки
c3 a1 b2 Дамка срубит ничего
d4 b6 f2 Дамка срубит одну пешку

Решение задачи:
Для описания позиций шашек использовалась структура [latex]position[/latex] с указанием на буквенную строку и числовой столбец шашечной доски. Задача разбивается на 4 главных подзадачи, основанные на таких 4 условиях:
пешки не находятся на границе шашечного поля;
первая пешка находится на границе шашечного поля;
вторая пешка находится на границе шашечного поля;
обе пешки находятся на границе шашечного поля;
В свою очередь данные подзадачи разбиваются еще на несколько условий, что подробно изложены в комментариях кода. На выходе программа предоставляет информацию о том, какое количество пешек срубила дамка относительно заданных позиций.

Условие задачи(стр.31)
Код задачи на с++

КМ259(б). Квартеты из клеток

Антон Куперман
Антон Куперман

Latest posts by Антон Куперман (see all)

Задача

Назовем квартетом четверку клеток на клетчатой бумаге, центры которых лежат в вершинах прямоугольника со сторонами, параллельными линиям сетки. Какое наибольшее число квартетов, не имеющих общих клеток, можно разместить в прямоугольнике [latex]m\times n[/latex] клеток?

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

[latex]m[/latex],[latex]n[/latex]

Вывод

[latex]x[/latex]-кол-во квартетов.

Тесты

m n x
8 6 12
16 7 24
17 8 29,75
15 11 37

Код

Решение

Если [latex]m[/latex] и [latex]n[/latex] четные, то в прямоугольнике [latex]m\times n[/latex] можно разместить [latex]m/n[latex] квартетов. Если [latex]m[/latex] четное, а [latex]n[/latex] нечетное (и наоборот), то квартетов — [latex]m(n-1)/4[/latex]. И наконец если [latex]m[/latex] и [latex]n[/latex] — нечетные, то формула будет выглядеть так: [latex]m(n-1)-2/4[/latex].

КМ.72

Лена Бригарь
Лена Бригарь

Latest posts by Лена Бригарь (see all)

Задача из журнала «Квант» №72

Условие:
Пусть p — произвольное вещественное число. Найдите все такие x, что сумма кубических корней из чисел 1 – x и 1 + x равна p.

Тесты:

Входные данные Выходные данные
1 0.6 No solutions
2 1.4 x1 = -0.997217
x2 = 0.997217
3 2 x=0
4 1.79 x1 = -0.814516
x2 = 0.814516

Код

Решение:
Рассмотрев условие, приходим к такому уравнению [latex] \sqrt[3]{\left(1+x \right)}+\sqrt[3]{\left(1-x \right)}=p [/latex] , где p — параметр, который будет задаваться на входе.Ответы для р будут существовать на промежутке [latex] \left[\sqrt[3]{2}; 2\right] [/latex] . Если р не входит в промежуток, то выводим «нет решений». Если р=2, то оба корня совпадут, по этому выводим один «х=0». Для остальных случаев ответом будет два корня.

Ссылки:
Решение на ideone http://ideone.com/A8DXC9
Условие http://www.kvant.info/zkm_1971.htm
Решение wolfram http://www.wolframalpha.com/input/?i=(1%2Bx)%5E(1%2F3)+%2B+(1-x)%5E(1%2F3)+%3D+p

Mif 9. Пересечение отрезков

Задача

Пересекаются ли отрезки. Для двух отрезков [latex]AB[/latex] и [latex]CD[/latex], заданных целочисленными координатами вершин на плоскости, определить имеют ли они общие точки.

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

Координаты концов отрезка[latex]AB[/latex] и [latex]CD[/latex].

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

Пересекаются ли отрезки.

Тесты

Входные данные Выходные данные
[latex]x1[/latex] [latex]y1[/latex] [latex]x2[/latex] [latex]y2[/latex] [latex]x3[/latex] [latex]y3[/latex] [latex]x4[/latex] [latex]y4[/latex]
1 0 2 1 1 0 2 0 Отрезки пересекаются
-1 1 2 -2 0 -2 1 3 Отрезки пересекаются
1 1 2 2 2 2 1 1 Отрезки пересекаются
-1 1 -1 2 1 1 2 2 Отрезки не пересекаются
-2 -1 -2 3 0 -1 0 3 Отрезки не пересекаются
-2 0 0 2 0 -2 1 1 Отрезки не пересекаются

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

Решение

Пусть концы отрезков имеют координаты [latex](x1,y1),[/latex] [latex](x2,y2),[/latex] [latex](x3,y3),[/latex] и [latex](x4,y4),[/latex]. По имеющимся точкам выведем параметрические уравнения обоих отрезков: [latex]0\leq u \leq 1:[/latex] $$\begin{cases}x=ux1+(1−u)x2; \newline y=uy1+(1−u)y2\end{cases};$$ и [latex] 0\leq v \leq 1:[/latex] $$\begin{cases}x=vx3+(1−v)x4 \newline y=vy3+(1−v)y4\end{cases}$$
В точке пересечения [latex]x[/latex] и [latex]y[/latex] должны совпадать. Значит выходит система двух линейных уравнений, которую нужно решить относительно [latex]u[/latex] и [latex]v:[/latex] $$\begin{cases}ux1+(1−u)x2=vx3+(1−v)x4 \newline uy1+(1−u)y2=vy3+(1−v)y4\end{cases}$$
Найдем определитель: [latex]denominator=(y4-y3)\cdot(x1-x2)-(x4-x3)\cdot(y1-y2).[/latex] Если он равен [latex]0[/latex], то прямые содержащие отрезки параллельны или совпадают. В этом случае проверим лежит ли вершина одного отрезка на другом, если она лежит, то отрезки пересекаются, иначе не пересекаются.
Если не [latex]0[/latex], то найдем решение по правилу Крамера:
$$\begin{cases}Ua=\frac{(x4-x2)\cdot(y4-y3)-(x4-x3)\cdot(y4-y2)}{denominator} \newline Ub=\frac{(x1−x2)\cdot(y4−y2)−(x4−x2)\cdot(y1−y2)}{denominator}\end{cases}$$
Если [latex]0\leq Ua \leq 1[/latex] и [latex]0\leq Ub \leq 1[/latex], то отрезки пресекаются, иначе отрезки не пересекаются.

Ссылки

Ideone

A60г

Алла Марокко
Алла Марокко

Latest posts by Алла Марокко (see all)

Задача:
Пусть [latex]D[/latex] — заштрихованная часть плоскости и пусть u определяется по [latex]x[/latex] и [latex]y[/latex] следующим образом: [latex] u=\begin{cases}x^{2}-1, ; \text{ if } (x,y)\in D \\\sqrt{\left| x-1 \right| } ; \text{ another case }\end{cases}[/latex] (запись [latex](x,y)\in D[/latex] означает, что точка с координатами [latex]x, y[/latex] принадлежит [latex]D[/latex]).

Даны действительные числа [latex]x[/latex] и [latex]y.[/latex] Определить [latex]u.[/latex]

a60%d0%b3
Тесты:

Вход Выход
[latex]x[/latex] [latex]y[/latex] [latex]u[/latex]
1 0.3 0.3 0.836660
2 1 1 0.000000
3 2 2 1.000000
4 0 0 -1.000000

Код:

Решение:
Для решения задачи проверим не принадлежит ли выбранная точка полуплоскости [latex] y<0 [/latex].Затем следует проверить не лежит ли выбранная точка вне полукруга, радиус которого равен 1 . Следующим действием нужно проверить не находиться ли точка в вырезанной четвертине маленького круга, радиус которого равен 0.3 .
Ссылка:
Онлайн компилятор ideone .

KM2. Радиус окружностей, удовлетворяющих условию

Задача

Дана сфера радиуса [latex]1[/latex]. На ней расположены равные окружности [latex]\gamma_0[/latex], [latex]\gamma_1[/latex], [latex]\ldots[/latex], [latex]\gamma_n[/latex] радиуса [latex]r \left(n \ge 3\right)[/latex]. Окружность [latex]\gamma_0[/latex] касается всех окружностей [latex]\gamma_1[/latex], [latex]\ldots[/latex], [latex]\gamma_n[/latex]; кроме того, касаются друг друга окружности [latex]\gamma_1[/latex] и [latex]\gamma_2[/latex]; [latex]\gamma_2[/latex] и [latex]\gamma_3[/latex]; [latex]\ldots[/latex]; [latex]\gamma_n[/latex] и [latex]\gamma_1[/latex].
При каких [latex]n[/latex] это возможно? Вычислить соответствующий радиус [latex]r[/latex].

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

Количество окружностей [latex]n[/latex].

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

Радиус окружностей [latex]r[/latex].

Тесты

Входные данные ([latex]n[/latex]) Выходные данные ([latex]r[/latex])
3 0.816497
4 0.707107
5 0.525731
6 Solution does not exist.

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

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

Каждой окружности на сфере можно сопоставить её «центр на сфере» — конец радиуса сферы, проходящего через центр окружности (никогда не лежащий на сфере). Эту точку мы будем называть «центром» окружности в кавычках, подчёркивающих, что это не «обычный» центр (рис. 2, а).

Заметим для точности, что такого определённого «центра» нет у окружностей больших кругов сферы. Но окружности, о которых идёт речь в условии задачи, заведомо не могут иметь радиус [latex]1[/latex], потому что окружности двух больших кругов не могут друг друга касаться, — они всегда пересекают друг друга в двух диаметрально противоположных точках сферы.

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

Пусть [latex]A_0[/latex], [latex]A_1[/latex], [latex]A_2[/latex], [latex]\ldots[/latex], [latex]A_n[/latex] — «центры» окружностей [latex]\gamma_0[/latex], [latex]\gamma_1[/latex], [latex]\ldots[/latex], [latex]\gamma_n[/latex], о которых идёт речь в условии задачи. Тогда [latex]A_0 A_1=A_0 A_2=\ldots=A_0 A_n=A_1 A_2=A_2 A_3=\ldots=A_n A_1=2r[/latex], другими словами, [latex]A_0 A_1 A_2 \ldots A_n[/latex] — правильная [latex]n[/latex]-угольная пирамида с вершиной [latex]A_0[/latex], у которой все боковые грани — равносторонние треугольники со сторонами равными [latex]2r[/latex]. Итак, достаточно построить пирамиду, для которой выполнены эти условия, тогда точки [latex]A_0[/latex], [latex]A_1[/latex], [latex]\ldots[/latex], [latex]A_n[/latex] будут определять окружности радиуса [latex]r[/latex], с «центрами» [latex]A_0[/latex], [latex]A_1[/latex], [latex]\ldots[/latex], [latex]A_n[/latex], которые, очевидно, удовлетворяют условию задачи.

Поскольку сумма плоских углов выпуклого [latex]n[/latex]-гранного угла с вершиной [latex]A_0[/latex] меньше [latex]360^\circ[/latex]:
[latex]n\cdot60^\circ=[/latex]∠[latex]A_1 A_0 A_2+[/latex]∠[latex]A_2 A_0 A_3+\ldots+[/latex]∠[latex]A_n A_0 A_1<360^\circ[/latex], то [latex]n<6[/latex]. Для [latex]n=3[/latex], [latex]4[/latex] и [latex]5[/latex] нетрудно построить нужные пирамиды.

Пусть [latex]O[/latex] — центр сферы. Высота пирамиды [latex]h[/latex] и длина её рёбер [latex]2r[/latex] находятся из следующих соображений: радиус [latex]K A_1[/latex] основания пирамиды — катет [latex]\bigtriangleup A_0 K A_1[/latex] и боковая сторона [latex]\bigtriangleup A_1 K A_2[/latex], где ∠[latex]A_1 K A_2=2 \pi / n[/latex] (рис. 3, а , б),
[latex]\sqrt{4 r^2-h^2 \sin \frac{\pi}{n}}=r[/latex]

Из [latex]\bigtriangleup A_0 O A_1[/latex] имеем [latex]r=\frac{h}{2r}[/latex].

Отсюда [latex]h=2 r^2[/latex], [latex]r=\sqrt{1-\frac{1}{4 \sin^2 \frac{\pi}{n}}}[/latex]

Таким образом,
при [latex]n=3[/latex]: [latex]r=\sqrt{\frac{2}{3}}[/latex] [latex]\left( \sin \frac{\pi}{3}=\frac{\sqrt{3}}{2} \right)[/latex]
при [latex]n=4[/latex]: [latex]r=\sqrt{\frac{1}{2}}[/latex] [latex]\left( \sin \frac{\pi}{4}=\frac{\sqrt{2}}{2} \right)[/latex]
при [latex]n=5[/latex]: [latex]r=\sqrt{\frac{1-\sqrt{5}}{2}}[/latex]
(формулу [latex]\sin \frac{\pi}{5}=\frac{\sqrt{10-2 \sqrt{5}}}{4}[/latex] можно вывести из рисунка 4, с помощью которого строятся правильный десятиугольник и правильный пятиугольник).

Рисунки, использованные в решении

Рисунок 2:

Рисунок 3:

Рисунок 4:

Научно-популярный журнал «Квант», 1970 год, №7, страницы 51-53

Итоги:
Выведенная во время решения формула [latex]r=\sqrt{1-\frac{1}{4 \sin^2 \frac{\pi}{n}}}[/latex] справедлива только при [latex]n=3[/latex], [latex]4[/latex], [latex]5[/latex]. В случае, если задать значения больше этих, то выражение под корнем примет отрицательное значение, а в рамках данной задачи это будет говорить об отсутствии решения. Значения же меньше будут недопустимы, что было указано в условии.
Таким образом, программа выведет сообщение об отсутствии решения, если заданные значения [latex]n[/latex] отличны от вышеупомянутых. Если же условия будут соблюдаться, то задача выведет соответствующее значение радиуса.

Ссылки