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а

Задача: Получить квадратную матрицу порядка [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

Задача

Комплексная матрица [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б

Задача.  Дана квадратная матрица порядка 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а

Задача:

Дана действительная квадратная матрица порядка 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б

Задача

Таблица футбольного чемпионата задана квадратной матрицей порядка [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) на саму программу.

А397б

Задача: Дана действительная квадратная матрица порядка [latex]n[/latex]. В строках с отрицательным элементом на главной диагонали найти наибольший из всех элементов.

Тесты:

n matrix results the biggest element in line
4
-1 3 4 5
2 3 6 7
1 4 -2 7
2 3 4 2
5
7
5
-1 2 3 4 5
6 7 8 9 10
2 4 -5 7 8
11 -1 0 5 9
1 8 -33 2 -1

 

5
8
8
0 error: wrong value of n
3
0 1 3
-2 -5 -1
-4 -9 -4
-1
-4

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

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

Ссылка:https://ideone.com/kCDer9

План программы:

  1. Назначение макросов
  2. Назначение рабочих переменных
  3. Проверка ввода порядка n
  4. Проверка ввода матрицы
  5. Печать введённой матрицы для отладки
  6. Вывод результата, содержит номер строки, где необходимо было искать наибольший элемент

Программе задаётся квадратная матрица порядка [latex]n[/latex]. На тех строках, где на главную диагональ попадает отрицательный элемент, программа отыскивает наибольший элемент в строке и выводит его.

Для поиска наибольшего значения в строке используется макрос X_INIT. Он используется в качестве начального значения максимума. Этим наименьшим значением является взятый с отрицательным знаком макрос DBL_MAX из библиотеки float.h , обозначающий наибольшее значение.

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

А394а

Задача:  Дана целочисленная квадратная матрица порядка [latex]n[/latex]. Найти номера строк, все элементы которых — нули.

[latex]n[/latex] [latex]M[/latex] [latex]v[/latex] Комментарий
4
0 0 0 0
0 -290 56 48
0 0 0 0
1 2 3 4
1 3
3
0 0 0
0 0 0
0 0 0
1 2 3
3
1 2 3
4 5 6
7 8 9
Таких строк нет.

C++:

Java:

Пусть дана квадратная матрица [latex]M[/latex], количество строк и столбцов — [latex]n[/latex].

Заводим дополнительную переменную [latex]k[/latex]. При вводе элементов матрицы, проверяем, равны ли они нулю. Если элемент равен нулю, прибавляем к значению [latex]k[/latex] единицу. При первом ненулевом элементе переходим к другой строке. Если после прочтения строки [latex]k=n[/latex], то все элементы строки были нулевыми (перед прочтением каждой новой строки в [latex]k[/latex] записывается ноль). Записываем номер строки в заранее созданный вектор [latex]v[/latex]. Выводим элементы вектора, увеличивая их на единицу, чтобы получилась правильная нумерация строк.

Задача на Ideone:
C++
Java

A412г

Задача:

Даны две целочисленные квадратные матрицы порядка 6. Найти последовательность из нулей и единиц  [latex]b_{1} , … , b_{6}[/latex] такую, что [latex]b_{i} = 1[/latex], когда:

г) количество отрицательных и неотрицательных элементов [latex] i [/latex]- строки первой матрицы совпадает соответственно с количеством отрицательных и неотрицательных элементов [latex] i[/latex]-строки второй матрицы.

 

  Матрица [latex]A[/latex]

    Матрица [latex]B[/latex]

     Ожидаемый      результат

 Комментарий

   1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
                  1 1 1 1 1 1          Тест пройден
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
                    0 0 0 0 0 0          Тест пройден
 0 2 2 3 4 4
1 3 3 4 5 5
2 4 4 5 6 6
3 5 5 6 7 7
4 6 6 7 8 8
5 7 7 8 9 9
0 2 2 3 4 4
-1 3 1 4 3 5
-2 4 0 5 2 6
-3 5 -1 6 1 7
-4 6 -2 7 0 8
-5 7 -3 8 -1 9
                    1 0 0 0 0 0          Тест пройден
0 2 2 3 4 4
1 3 3 -4 5 5
2 4 -4 5 6 6
3 -5 5 6 7 -7
4 6 -6 -7 8 8
5 -7 7 -8 9 -9
0 2 2 3 4 4
-1 3 1 4 3 5
-2 4 0 5 2 6
-3 5 -1 6 1 7
-4 6 -2 7 0 8
-5 7 -3 8 -1 9
                   1 1 1 1 1 1          Тест пройден

Исходный код:

Код на Java

 

Описание:

Для решения данной задачи я решил ввести два счетчика, которые считают количество отрицательных чисел. Потом мы сравниваем счетчики каждого массива. Если в соответствующих строках данных массивов равное число отрицательных элементов, то и равное число неотрицательных.  В таком случае мы должны напечатать «1», в противном случае «0».

 Алгоритм:

  1. Создаем функцию для ввода данных.
    1. Создаем первый цикл для перебора строк.
    2. Создаем вложенный цикл для перебора каждого элемента массива и функцию ввода данных.
  2. Создаем главную функцию.
    1. Создаем цикл, перебирающий строки массивов.
    2. Создаем два счетчика.
    3. Создаем первый вложенный цикл, для перебора каждого элемента второго массива.
      • В случае обнаружения отрицательных элементов, увеличиваем счетчик.
    4. Создаем первый вложенный цикл, для перебора каждого элемента второго массива.
      • В случае обнаружения отрицательных элементов, увеличиваем счетчик.
    5. Объявляем условие вывода данных. Так как условие находится внутри главного цикла, то будет выведено по одному значению, которое характеризует каждую строку.
  3. Создаем функцию для печати результата.
    1. Один цикл для перебора каждого элемента одномерного массива.
  4. В функции «int main ()»:
    1. Вводим значения элементов первого массива.
    2. Вводим значения элементов второго массива.
    3. Применяем главную функцию к данным массивам.
    4. Печатаем результат.
    5. Окончание работы программы.

Ссылка на Ideone.

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

Рабочий образец.