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

А694а

Сабиров Ильдар
Сабиров Ильдар

Latest posts by Сабиров Ильдар (see all)

Задача: Получить квадратную матрицу порядка [latex]n[/latex] [latex]\begin{pmatrix}1 &0 &\cdots & 0 \\ 0 & 1 &\cdots &0 \\ \cdots &\cdots &\cdots \cdots & \cdots \\ 0 & 0 & \cdots & 1\end{pmatrix}[/latex]

Тесты:

n Матрица
3 1 0 0

0 1 0

0 0 1

4 1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

6 1 0 0 0 0 0

0 1 0 0 0 0

0 0 1 0 0 0

0 0 0 1 0 0

0 0 0 0 1 0

0 0 0 0 0 1

Ход работы:
1. С помощью цикла заполняем главную диагональ единицами.

2. Приравниваем элементы не равные единице к нулю.

3. Вывод массива.

Ссылка на код

А714

Ковальський Олександр Дмитрович
Ковальський Олександр Дмитрович

Latest posts by Ковальський Олександр Дмитрович (see all)

Задача

Комплексная матрица [latex]Z[/latex] представляется парой [latex]X[/latex], [latex]Y[/latex] действительных матриц так, что [latex]Z=X+iY[/latex]. Даны действительные квадратные матрицы [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] и [latex]D[/latex] порядка [latex]m[/latex]. Найти произведение двух комплексных матриц [latex]A+iB[/latex] и [latex]C+iD[/latex], т. е. найти действительные квадратные матрицы [latex]X[/latex] и [latex]Y[/latex] порядка [latex]m[/latex] такие, что [latex]X+iY=(A+iB)(C+iD)[/latex].

Пример

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

9 5 4 8 5 2 6 1 3

1 4 6 5 3 1 9 8 7

4 2 8 3 9 5 1 2 7

5 6 7 4 1 9 3 8 2

X:

16 13 70

9 24 39

-68 -91 -75

 

Y:

99 141 186

96 108 167

110 165 218

 

 

Решение

 

 

 

 

[latex]X+iY=(A+iB)(C+iD)=(AC-BD)+i(AD+BC)[/latex], т. е. [latex]X=AC-BD[/latex], [latex]Y=AD+BC[/latex].

Код на ideone.

А702б

Кваша Дар`я Михайлівна
Кваша Дар`я Михайлівна

Latest posts by Кваша Дар`я Михайлівна (see all)

Задача.  Дана квадратная матрица порядка n. Получить вектор  Ab, где b-вектор, элементы которого вычисляются по формулам:

[latex]b_{i}=\begin{cases}\frac{1}{i^{2}+2} & \text{, if i mod 2=0} \\ \frac{1}{i} & \text{, other case } \end{cases}[/latex]

i=(1,…,n).

Тесты:

Вход Выход Комментарий
4
1 2 1 1
1 3 6 9
1 2 1 1
1 6 3 18
1.72222 4 1.72222 4 Пройден
3
0 0 0
1 1 1
2 2 2
0 1.5 3 Пройден
4
1 2 2 9
3 4 1 18
1 1 1 1
0 0 0 0
2.5 5 1.55556 0 Пройден
Решение:

Согласно условию находим вектор b. По формуле [latex]Ab_{i}=\sum_{j=1}^{n}A_{ij}b_{j}[/latex], i=(0,…,n) находим произведение матрицы на вектор.

С работой программы можно ознакомится здесь.

А397а

Чежеумова Анна
Чежеумова Анна

Latest posts by Чежеумова Анна (see all)

Задача:

Дана действительная квадратная матрица порядка 10. В строках строках с отрицательным элементом на главной диагонали найти сумму всех элементов.

Тесты:

 

 Матрица  Сумма элементов строки Комментарий
-1 1 1 1 1 1 1 1 1 1

2 -2 2 2 2 2 2 2 2 2

3 3 3 3 3 3 3 3 3 3

4 4 4 4 4 4 4 4 4 4

5 5 5 5 -5 5 5 5 5 5

6 6 6 6 6 -6 6 6 6 6

7 7 7 7 7 7 7 7 7 7

8 8 8 8 8 8 8 8 8 8

9 9 9 9 9 9 9 9 -9 9

10 10 10 10 10 10 10 10 10 -10

 8

16

0

0

40

48

0

0

72

80

 Пройден
 -1 -2 -3 0 9 8 7 6 5 4

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

1 2 3 4 5 6 7 8 9 0

5 3 -4 -7 8 9 0 3 3 8

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

0 2 3 7 5 9 6 2 5 7

-3 -6 -2 0 8 5 -1 -6 -8 1

7 8 3 6 7 8 6 3 -5 -8

3 6 2 5 2 2 5 2 7 3

-3 -5 -7 -5 -3 -7 -2 -9 -5 -8

 33

0

0

28

-45

0

-12

0

0

-54

 Пройден
 -8 -9 -9 -6 -6 -6 -5 -5 -4 -3

6 9 8 5 3 2 4 8 5 3

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

1 2 3 4 5 6 4 5 6 0

-5 -5 -6 -6 -4 -4 -9 -9 -7 -7

3 5 7 1 9 3 4 0 5 7

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

3 5 6 2 7 1 9 8 6 4

-3 -4 -2 -1 -3 -7 -3 -8 -6 -2

9 2 3 7 1 6 4 8 3 8

 -61

0

-52

0

-62

0

-48

0

-39

0

 Пройден

Работу программы можно посмотреть тут.

Решение:

1. Вводим квадратную матрицу порядка 10.

2. Через условный оператор проверяем, является ли элемент главной диагонали отрицательным.

3. Если элемент главной диагонали отрицательный, то считаем сумму элементов строки. Для остальных стрк выводим [latex]0[/latex].

А413б

Бровко Ілля
Бровко Ілля

Latest posts by Бровко Ілля (see all)

Задача

Таблица футбольного чемпионата задана квадратной матрицей порядка [latex]n[/latex], в которой все элементы, принадлежащие главной диагонали, равны нулю, а каждый элемент, не принадлежащий главной диагонали, равен  [latex]2[/latex],  [latex]1[/latex]  или  [latex]0[/latex] (числу очков, набранных в игре:  [latex]2[/latex]- выигрыш,  [latex]1[/latex]- ничья,   [latex]0[/latex]- проигрыш).

б) Определить номера команд, прошедших чемпионат без поражений.

Количество команд. Турнирная таблица.

Номера команд, прошедшие турнир без поражений.

Комментарий.
4
0 2 0 1
0 0 1 2
2 1 0 1
1 0 1 0
3 Пройдено.
4
0 1 2 2
1 0 2 2
0 0 0 1
0 0 1 0
1 2 Пройдено.
3
0 2 0
0 0 2
2 0 0
Ни одна из команд не прошла турнир без поражений. Пройдено.
4
0 2 1 1
0 0 1 2
1 1 0 2
1 2 2 0
1 3 4 Пройдено.

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

Для начала вводим двумерный массив. Далее, в циклах, проверяем на наличие у команды поражения: для не диагональных элементов ([latex]i\neq j[/latex]), если команда хотя бы один раз проиграла, цикл обрывается и команда в дальнейшей проверке не участвует.

Если ни одна команда не прошла турнир без поражений, то для этого заводим счетчик [latex]k[/latex]. Если [latex]k>0[/latex], то хотя бы одна команда прошла турнир без поражений. Если [latex]k=0[/latex], то ни одна из команд не прошла без поражений.

Ниже представлен сам код (C++).

Код на Java:

 

Также, вы можете воспользоваться ссылкой (C++)/ссылкой (Java) на саму программу.