Матч 404, Обнаружить треугольник (RevealTriangle)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Рассмотрим треугольник цифр:

74932

1325

457

92

1

Каждая цифра, которая находится не в первом ряду, равна последней цифре суммы соседних цифр, стоящих строго сверху и сверху справа.

На вход подается массив строк questionMarkTriangle, содержащий указанный треугольник цифр. В каждой строке все цифры кроме одной заменены на символ ‘?’. Вернуть восстановленный треугольник (заменить все знаки ‘?’ на искомые цифры).

Класс: RevealTriangle

Метод: vector<string>

calcTriangle(vector<string> questionMarkTriangle)

Ограничения: questionMarkTriangle содержит от 1 до 50 элементов, i – ый элемент questionMarkTriangle (нумерация начинается с 0) содержит n – i символов ‘0’ – ‘9’ и ‘?’, где n – число элементов в questionMarkTriangle.

Вход. Массив строк questionMarkTriangle.

Выход. Восстановленный треугольник цифр.

Пример входа

questionMarkTriangle

{"4??",

"?2",

"1"}

{"???2", "??2", "?2", "2"}

{"??5?", "??9", "?4", "6"}

Пример выхода

{"457", "92", "1"}

{"0002", "002", "02", "2"}

{"7054", "759", "24", "6"}

РЕШЕНИЕ

обработка массива

Занесем таблицу цифр в символьный массив m. Занесем в ячейку pos[i] номер позиции i - ой строки, в которой находится цифра. Последняя строка содержит одно число, поэтому в ней нет символов ‘?’. Будем восстанавливать треугольник, начиная с предпоследней строки до первой (цикл по i). В первом цикле по j восстанавливаем цифры, находящиеся правее ячейки pos[i], во втором – цифры, находящиеся левее pos[i].

Рассмотрим, как восстановить цифру в ячейке m[i][j]. Изначально в ней находится ‘?’. Пусть, например, в ячейке слева m[i][j – 1] уже находится цифра (это будет иметь место при pos[i] < j). В ячейке снизу m[i + 1][j – 1] также находится цифра. Имеет место соотношение:

m[i + 1][j – 1] = (m[i][j – 1] + m[i][j]) mod 10

Откуда

m[i][j] = (m[i + 1][j – 1] – m[i][j – 1] + 10) % 10

Преобразовываем восстановленную таблицу цифр m в массив строк res, которую и возвращаем. Поскольку массив m символьный, то получить результирующие строки res[i] можно при помощи конструктора string.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

class RevealTriangle

{

public:

vector<string> calcTriangle(vector<string> questionMarkTriangle)

{

int i, j, pos[50], n = questionMarkTriangle.size();

char m[50][50];

vector<string> res(n);

for(i = 0; i < n; i++)

for(j = 0; j < questionMarkTriangle[i].size(); j++)

{

m[i][j] = questionMarkTriangle[i][j];

if (m[i][j] != '?') pos[i] = j;

}

for(i = n - 2; i >= 0; i--)

{

for(j = pos[i] + 1; j < n - i; j++)

m[i][j] = (m[i+1][j-1]-m[i][j-1] + 10) % 10 + '0';

for(j = pos[i] - 1; j >= 0; j--)

m[i][j] = (m[i+1][j]-m[i][j+1] + 10) % 10 + '0';

}

for(i = 0; i < n; i++)

res[i] = string(m[i],0,questionMarkTriangle[i].size());

return res;

}

};