There is no Spoon — Episode 1

Task

The Goal

The game is played on a rectangular grid with a given size. Some cells contain power nodes. The rest of the cells are empty.

The goal is to find, when they exist, the horizontal and vertical neighbors of each node.

Rules

To do this, you must find each [latex]\left( x1, y1 \right)[/latex] coordinates containing a node, and display the [latex]\left(x2, y2\right)[/latex] coordinates of the next node to the right, and the [latex]\left(x3, y3\right)[/latex] coordinates of the next node to the bottom within the grid.

If neighbor does not exist, you must output the coordinates [latex]\left(-1, -1\right)[/latex] instead of [latex]\left(x2, y2\right)[/latex] and/or [latex]\left(x3, y3\right)[/latex].

You lose if:

  • You give an incorrect neighbor for a node.
  • You give the neighbors for an empty cell.
  • You compute the same node twice.
  • You forget to compute the neighbors of a node.

Game input

The program must first read the initialization data from standard input. Then, provide to the standard output one line per instruction.

Initialization input

Line 1: one integer width for the number of cells along the x axis.

Line 2: one integer height for the number of cells along the y axis.

Next height lines: A string line containing width characters. A dot . represents an empty cell. A zero 0 represents a cell containing a node.

[latex]0 <[/latex] width[latex]\le 30[/latex]
[latex]0 <[/latex] height[latex]\le 30[/latex]

Output for one game turn

One line per node. Six integers on each line: x1 y1 x2 y2 x3 y3 Where:

  • ( x1, y1) the coordinates of a node.
  • ( x2, y2) the coordinates the closest neighbor on the right of the node.
  • ( x3, y3) the coordinates the closest bottom neighbor.
[latex]0 \le[/latex] x1[latex]<[/latex] width
[latex]0 \le[/latex] y2[latex]<[/latex] height
[latex]-1 \le[/latex] x2, x3[latex]<[/latex] width
[latex]-1 \le[/latex] y2, y3[latex]<[/latex] height
Alloted response time to first output line [latex]\le 1[/latex]s.
Response time between two output lines [latex]\le 100[/latex]ms.

Tests

Input Output
2 2
00
0.
0 0 1 0 0 1
1 0 -1 -1 -1 -1
0 1 -1 -1 -1 -1
4 4
.0..
.000
000.
..0.
1 0 -1 -1 1 1
1 1 2 1 1 2
2 1 3 1 2 2
3 1 -1 -1 -1 -1
0 2 1 2 -1 -1
1 2 2 2 -1 -1
2 2 -1 -1 2 3
2 3 -1 -1 -1 -1

The code of the program

Solution of the task

First of all, we must pay attention, that we have to find the closest neighbor. It doesn’t mean, that if there is no neighbor on adjacent cells, then the answer will be negative, because the neighbor may be further. This leads to the fact, that the task can not be completed without memorization of the whole list of cells.

After storing every string in array, the task becomes simple: we go using the cycle through every cell, and if the cell contains a node, then we launch two cycles from it in two directions (to the right and to the bottom), and assume there are no neighbors with assigning value -1 to both variables ansX and ansY. If there will be no nodes found, the value will remain the same, otherwise variables will take values of the node coordinates. In any case, the result will be correct.

This process is optimized by usage of the following: the [latex]x[/latex] coordinate of the closest right neighbor (or the value of width) is saved in a variable x2. Whether we find a neighbor or no, we can start the further horizontal search right from the coordinate x2, because empty cells must be skipped anyway.

Links

Площадь поверхности

Задача

Найти площадь поверхности, которая является трёхмерным графиком функции [latex]f\left( x, y\right)[/latex], в пределах от [latex]a[/latex] до [latex]b[/latex] по оси [latex]x[/latex] и от [latex]c[/latex] до [latex]d[/latex] по оси [latex]y[/latex] c величиной шага [latex]h[/latex].

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

Четыре целых числа: [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], [latex]d[/latex].
Вещественное число: [latex]h[/latex].

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

Площадь поверхности [latex]S[/latex].

Тесты

 № [latex]f\left( x, y\right)[/latex] Входные данные Выходные данные
 [latex]a[/latex]  [latex]b[/latex]  [latex]c[/latex]  [latex]d[/latex]  [latex]h[/latex]  [latex]S[/latex]
 1  [latex]x+y[/latex]  -10  10  -10  10  0.001  692.82
 2  [latex]\left| x \right| +\left| y \right|[/latex]  -2  2  -2  2  0.005  27.7128
 3  [latex]1[/latex]  0  100  0  100  0.1  10000
 4  [latex]{x}^{2}+{y}^{2}[/latex]  -1  1  -1  1  0.0005  7.44626

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

Решение

Представим поверхность в виде множества геометрических фигур. Тогда её площадь будет суммой площадей этих фигур. В качестве фигур, покрывающих данную поверхность, возьмём треугольники, поскольку через любые [latex]3[/latex] точки в пространстве можно провести плоскость и только одну (а значит и треугольник). Координатную плоскость [latex]xy[/latex] условно поделим на квадраты, где сторона квадрата будет равняться заданному шагу [latex]h[/latex]. Будем рассматривать только квадраты, что лежат в заданных пределах.  Условно проведём одну из диагоналей у каждого квадрата — получим треугольники на плоскости. Поочередно будем искать координату [latex]z[/latex] вершин каждой пары треугольников, подставляя уже известные координаты [latex]x[/latex] и [latex]y[/latex] в указанную формулу. Зная координаты треугольников в пространстве, найдём площадь каждого, сумма данных площадей и будет площадью поверхности. Чтоб найти площадь треугольника, зная координаты его вершин, найдем векторное произведение его координат. Возьмем треугольник с координатами вершин  [latex]\left( x_i,y_i,z_{ii} \right) [/latex], [latex]\left( x_i, y_j, z_{ij} \right) [/latex] и [latex]\left( x_j, y_i, z_{ji} \right) [/latex], возьмём произвольные два вектора, которые образуют данный треугольник — [latex]\overrightarrow { a } =\left ( x_i-x_i, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, y_i-y_i, z_{ji}-z_{ii} \right)[/latex].
[latex]\overrightarrow { a } =\left ( 0, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, 0, z_{ji}-z_{ii} \right)[/latex].
Тогда векторное произведение [latex]\left [ \overrightarrow { a }, \overrightarrow { b } \right] =\left ( (y_i-y_j)( z_{ji}-z_{ii}), (z_{ii}-z_{ij})(z_{ji}-z_{ii} ), ( y_j-y_i)(x_j-x_i) \right)[/latex].
Поскольку длина вектора равного векторному произведения двух векторов в пространстве равна площади параллелограмма, образованного исходными векторами — найдём его длину и разделим пополам, чтоб получить площадь треугольника, образованного исходными векторами. Значит площадь каждого треугольника можно вычислить по формуле:
[latex]s =\frac { 1 }{ 2 } \sqrt{({(y_i-y_j)}^{2}{( z_{ji}-z_{ii})}^{2}+{(z_{ii}-z_{ij})}^{2}{(z_{ji}-z_{ii} )}^{2}+{( y_j-y_i)}^{2}{(x_j-x_i)}^{2})}[/latex] Тогда площадь поверхности в пределах заданных точек можно вычислить, сложив площади этих треугольников.

Модификация

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

Тесты

 № [latex]f\left( x, y\right)[/latex] [latex]z_0[/latex]  Входные данные  Выходные данные
 [latex]a[/latex]  [latex]b[/latex]  [latex]c[/latex] [latex]d[/latex]  [latex]h[/latex]  [latex]S[/latex]
 1 [latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex] [latex]1[/latex]  -1  1  -1  1  0.00011  6.28734
 2 [latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex] [latex]7y[/latex]  -1  1  -1  1  0.00011  23.0803
 3 [latex]\sqrt { 1-{ x }^{ 2 }-\frac{ { y }^{ 2 }}{ 2 } }[/latex] [latex]0[/latex]  -1  1  -2  2  0.00015  8.08214
 4 [latex]\sqrt { 2-{ x }^{ 2 }-{ y }^{ 2 } }[/latex] [latex]-1[/latex]  -2  2  -2  2  0.0005  12.5835

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

Условно отделим от функцию [latex]f\left( x, y\right)[/latex] слагаемые, что не под корнем, если такие имеются. Тогда [latex]z_0[/latex] равно части функции, что не под корнем. Для того, чтоб рассматривать площади треугольников, вершины которых выходят за область определения функции, доопределим их в [latex]z_0[/latex] по оси [latex]z[/latex]. Затем вычислим площадь треугольников, у которых как минимум одна вершина не лежит на [latex]z=z_0[/latex] .

Ссылки

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

Код на языке C++:

Код на языке Java:

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

Mif 17.14

Холодков Юрий
Холодков Юрий

Latest posts by Холодков Юрий (see all)

Задача.

Принадлежит ли точка ([latex]x[/latex];[latex] y[/latex]) фигуре на рисунке? Вариант 14. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Задача взята здесь.

Трапеция

Тесты

[latex]x[/latex] [latex] y[/latex] Ответ
-2 4 Принадлежит
4 8
Не принадлежит
-7 9
Не принадлежит
0 0
Не принадлежит
0 1
Принадлежит
4 1
Принадлежит
-7 1  Принадлежит

Код

Решение

Каждая из сторон тарпеции делит плоскость на 2 части. Сторона имеет вид [latex]y = k*x + b[/latex]. Путем подстановки были найдены коефициенты [latex] k [/latex] и [latex] b [/latex].  Точка может лежать либо ниже, либо выше, либо на стороне. Если [latex]y — k*x <= b[/latex], точка лежит на или ниже стороны. Основы трапеции представлены в виде [latex] y =1 [/latex] и [latex] y = 7 [/latex].

Ссылка на ideone.com

Mif 17.7

Станислав Коциевский
Станислав Коциевский

Latest posts by Станислав Коциевский (see all)

Задача.

Принадлежит ли точка ([latex]x[/latex];[latex]y[/latex]) фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Новый текстовый документ1

Тесты:

[latex]x[/latex] [latex]y[/latex] Результат
 -6  3 принадлежит
 0 0  не принадлежит
 2 -4  не принадлежит
 — 1 2 принадлежит
 -5 -2  принадлежит

 

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

Решение.

В данной задаче необходимо проверить подходят ли координаты точки под условия, описывающие фигуру. В этом варианте фигуру можно разбить на 2 прямоугольника. Тогда вышеуказанные условия выглядит так: [latex]-6<=x<=-1[/latex] и [latex]2<=y<=7[/latex] (это первый прямоугольник) или [latex]-6<=x<=-3[/latex] и [latex]-3<=y<=2[/latex] (соответственно, второй прямоугольник).

Здесь находится условие задачи

Ссылка на код на ideone.com

Mif 17.17

Условие :

Принадлежит ли точка [latex](x[/latex];[latex]y)[/latex] фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Рисунок :

picture

Тесты :

[latex]x[/latex] 4 -5 0 3 -2.5 1 -3 2 -1.3
[latex]y[/latex] 3 0 -5 -2 -2.5 5 3 -4 2.7
Вывод : Yes Yes Yes Yes Yes No No No Yes

Решение :

Во [latex]II[/latex], [latex]III[/latex] и [latex]IV[/latex] координатных четвертях данная фигура удовлетворяет неравенству [latex]|x| + |y| \leq 5[/latex], а в [latex]IV[/latex] — неравенству [latex]x^2 + y^2 \leq 25[/latex]. Программа должна проверять, подходят ли числа [latex]x[/latex] и [latex]y[/latex] соответствующему неравенству (в зависимости от координатной четверти, в которой они находятся).

Код :

Рабочая версия кода на Ideone.