AL1

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

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

Условие задачи

Вводится последовательность, состоящая из [latex]N[/latex] пар символов [latex](a_i, b_i)[/latex]. Каждая пара определяет порядок предшествования символов, например, пара [latex](b, c)[/latex] означает, что символ [latex]b[/latex] предшествует символу [latex]c[/latex]. Из порядка [latex](b, c)[/latex] и [latex](c, a)[/latex] следует порядок [latex](b, a)[/latex]. Необходимо определить, является ли введенная последовательность:

а) полной, т.е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку [latex]A_{1},A_{2}, \cdots ,A_{s}[/latex] в порядке предшествования;

б) противоречивой, т.е. для некоторых символов [latex]x,y[/latex] можно получить одновременно порядок как [latex](x, y)[/latex] так и [latex](y, x)[/latex];

Тесты

Входные данные Результат
4
a b
b c
c d
b d
полный порядок
3
2 a
8 c
c b
порядок неполный
3
2 a
8 c
a 8
полный порядок
4
2 a
8 c
c 2
a c
Порядок противоречив
10
a 5
5 4
b 3
3 4
5 3
b 5
a b
4 *
* 0
4 0
полный порядок

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

Решение

Общая идея решения

Эта часть решения взята отсюда

Пусть при записи этих [latex]N[/latex] пар встретилось всего [latex]K[/latex] различных символов, которые образуют множество [latex]X[/latex].

Идея решения задачи состоит в последовательном присвоении каждому символу [latex]s[/latex] из [latex]X[/latex] номера, который определяет количество [latex]P(s)[/latex] элементов, предшествующих ему, с учетом свойства транзитивности (из [latex](c, b)[/latex] и [latex](b, a)[/latex] следует [latex](c, a)[/latex]). Это осуществляется следующим образом:

Первоначально предполагается, что каждому символу не предшествует ни один символ, т.е. [latex]P(s)=0[/latex] для любого [latex]s[/latex].

При просмотре очередной пары [latex](x, y)[/latex] символу y присваивается большее из значений [latex]P(x)+1, P(y)[/latex].

Очевидно, что при первом просмотре всех пар из входной последовательности определятся все упорядоченные цепочки длины 2, т.е. состоящие из 2 элементов. Поэтому номера некоторых элементов будут как минимум 1. При каждом из следующих просмотров входной строки возможно несколько вариантов.

  1. Не произошло изменения ни одного из номеров символов. Если при этом номера символов различны и лежат в пределах от 0 до [latex]K-1[/latex], то эта нумерация определяет полный порядок. Иначе порядок неполный.
  2. Номер некоторого символа превысил [latex]K-1[/latex]. Это произошло потому, что рост номеров неограничен, т.е. осуществляется циклически. Следовательно порядок противоречив.

Легко понять, что число просмотров не превысит [latex]N[/latex].

Некоторые аспекты реализации

Нам необходимо будет несколько раз просматривать все пары, поэтому их не получится обрабатывать поточно. Будем хранить их в отдельном двумерном массиве.

Воспользуемся тем фактом, что символы воспринимаются компьютером, как числа. Заведем для номеров символов в последовательности массив chars на 256 элементов, поскольку тип данных char может принимать значения от 0 до 255. Это позволит обращаться к элементу массива, соответствующий какому-то символу напрямую, а не используя ассоциативный массив.  Это дает выигрыш в скорости, хотя и с некоторым увеличением расхода памяти.

Изначально каждый элемент массива chars пусть будет равен -1. Затем, пройдя все пары, присвоим каждому символу номер 0 в этом массиве. Таким образом, мы в дальнейшем сможем определить, что символ входит в нашу последовательность, поскольку его номер неотрицательный.

Если при очередном просмотре входной строки не произошло изменений, отсортируем массив номеров и проверим каждый ли предыдущий неотрицательный меньше следующего на 1.

ссылка на код на ideone

ссылка на условие задачи

Лабиринт

Маша Лукьянова
Маша Лукьянова

Latest posts by Маша Лукьянова (see all)

Условие:

           Имя входного файла:                стандартный поток ввода
           Имя выходного файла:             стандартный поток вывода
           Ограничение по времени:      2 second
           Ограничение по памяти:        64 мегабайт
Задан лабиринт [latex] N \times N [/latex], некоторые клетки которого могут быть заняты. Дан путь робота длины [latex] k [/latex] по этому лабиринту без указания его начального положения. Известно, что робот до начала движения стоит в одной из свободных клеток. Необходимо определить наименьшее количество передвижений по пути, после которого можно точно определить, где находится робот.

Формат входного файла:

Первая строка входного файла содержит два целых числа через пробел $$ N (1 \leq  N \leq  100) $$ и $$k  (0 \leq  k \leq  10^{5}) $$. В следующих [latex] N [/latex] строках задана карта лабиринта как совокупность 0 и 1 без пробелов: 1 – занятая клетка, 0 – свободная. В последней строке дана последовательность из $$ k  (0 \leq  k \leq  10^{5} ) $$ символов. Символы задают движение робота по лабиринту: символ [latex] U [/latex] — вверх, [latex] D [/latex] — вниз, [latex] R [/latex] —вправо, [latex] L [/latex] — влево. Других символов в строке передвижений нет, все символы в верхнем регистре латиницы.

Формат выходного файла:

В единственной строке выходного файла выведите единственное целое число не меньше нуля — наименьшее количество передвижений по пути, после которого можно точно определить местоположение робота. Если ответ не существует, либо входные данные некорректны, выведите -1.

Тесты:

Входные данные Выходные данные
1
 2 0
 11
 01
 0
2
 2 0
 11
 11
 -1
3
2 1
11
01
R
 -1
4
3 3
000
010
000
RDU
2
5 5 5
00010
10001
00100
10100
01101
RDUUU
4

Решение:

Если попробовать решить эту задачу «в лоб», то решение не будет удовлетворять пределу по времени, так как в худшем случае, нам надо перебрать $$ 10^{4} $$ возможных начальных позиций и совершить из них  $$ 10^{5} $$  ходов, что в результате дает  $$ 10^{9} $$ операций.

Решение «в лоб»:

  • Заведем список позиций в лабиринте, которым соответствуют элементы матрицы, в которые может попасть робот. В изначальном состоянии, без просмотра пути передвижения робота, это будут все позиции в лабиринте, где значение равно $$ 0 $$. После чего, проходя путь робота по шагам, будем для всех позиций в списке проверять:
    • Если мы вышли за границу матрицы, или в клетке, в которую мы собираемся перейти стоит $$ 1 $$, тогда удаляем эту позицию, поскольку она для нас недостижима.
    • Иначе ничего не делаем.
  • Если количество текущих вариантов пути стало равным $$ 1 $$, то мы запоминаем количество ходов при которой была достигнута данная ситуация.
  • Так будем делать до тех пор, пока робот закончил свой путь.
  • Если после всех проделанных нами операций остался один вариант полностью пройденного пути, тогда ответ найден. А именно это будет ход, после которого у нас кол-во удовлетворяющих позиций стало равным $$ 1 $$. В любом другом случае ответ нельзя определить однозначно.

Другая идея состоит в том, чтобы построить карту «переходов», в которой будет храниться номер хода, на котором робот впервые попал в эту клетку и ее координаты. Эта карта играет роль некоторого шаблона полного пути робота и «накладывая» его на каждый элемент матрицы в качестве начальной позиции, мы проверяем мог ли данный элемент матрицы служить «пунктом отправления» робота. Если такой элемент есть и он единственен, значит, можно однозначно определить начальное положение робота, но для того чтобы определить минимальное количество требуемых ходов-нужно последовательно удалять последние ходы из карты, «накладывая» изменившийся шаблон на каждый элемент, до тех пор, пока количество элементов удовлетворяющих шаблону не возрастет. Что значит, что мы получим номер решающего хода после которого судьба робота решится однозначно, значит ответом будет предыдущий ход. Стоит отметить, что если в карте останется всего лишь один элемент (соответствующий первому ходу), то расположение робота определялось однозначно первым ходом.

Submission.

 

e-olymp 1060. Линии

Задача взята с сайта e-olymp.com.

Условие задачи

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

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

В первой строке находится число [latex]n \left (2\leq n\leq 40 \right )[/latex], в каждой из следующих [latex]n[/latex] строк — по [latex]n[/latex] символов. Символом точки обозначена свободная клетка, латинской заглавной [latex]O[/latex] — шарик, [latex]@[/latex] — исходное положение шарика, который должен двигаться, латинской заглавной [latex]X[/latex] — конечное положение шарика.

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

В первой строке выводится [latex]Y[/latex], если движение возможно, или [latex]N[/latex], если нет. Если движение возможно далее следует [latex]n[/latex] строк по [latex]n[/latex] символов — как и на вводе, но [latex]X[/latex], а также все точки на пути заменяются плюсами.

Тесты

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

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

ideone.com

Засчитанное решение на e-olymp.com.

Решение

Для решения данной задачи можно использовать волновой алгоритм.  Считывая исходный массив с лабиринтом находим индексы начального и конечного положения шарика. Затем, начиная с начальной позиции проверяем проходимы ли соседние с ней клетки . Если клетка проходима и не была посещена ранее, помещаем ее в очередь и присваиваем соответствующей клетке массива, в котором хранится путь, значение на единицу большее, чем в начальной клетке. Так каждая помеченная клетка становится начальной, порождая шаги в соседние клетки, пока очередь не опустеет.

Затем, если клетка с конечным положением шарика достижима, необходимо восстановить кратчайший путь. Двигаясь от конечной позиции в начальную, на каждом шаге выбираем клетку значение которой на единицу меньше текущего положения, при этом символы в соответствующих клетках исходного лабиринта заменяем на символ [latex]+.[/latex]

А406

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

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

Задача

С помощью [latex]x_{ij}, i=1,2; j=1,\ldots,n.[/latex] — действительной матрицы на плоскости задано n точек так, что [latex]x_{1j}, x_{2j}[/latex] — координаты [latex]j[/latex] — точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n Матрица [latex]x_{ij}, i=1,2.[/latex] Длина наибольшего отрезка  Комментарий
3  

2 8 4

9 1 5

10 Пройдено
4  

6 14 2 1

9 3 8 0

13.3417 Пройдено
5  

1 8 4 3 7

2 9 5 0 11

11.7047 Пройдено

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

Ход решения:

  1. Вводим матрицу построчно (не очень удобно).
  2. Находим длину наибольшего отрезка.
    С помощью вложенных циклов мы находим длины всех отрезков по формуле
    [latex] AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}). [/latex]
  3. По алгоритму нахождения максимума находим длину наибольшего отрезка.
  4. Выводим матрицу.
  5. Выводим длину наибольшего отрезка.
    Ссылка на код

А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. Вывод массива.

Ссылка на код

А705

Кібакова Надія Олександрівна
Кібакова Надія Олександрівна

Latest posts by Кібакова Надія Олександрівна (see all)

Задача:
Даны квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex]. Получить матрицу [latex]A(B-E)+C[/latex], где [latex]E[/latex] — единичная матрица порядка [latex]n[/latex], а элементы матрицы [latex]C[/latex] вычисляются по формуле:[latex]C_{ij}=\frac{1}{i+j}\;\;\;\;(i,j=1,2,\ldots,n)[/latex].

Тесты
К сожалению я не разместила здесь тесты к задаче.

Решение
Реализуем хранение матрицы в виде двумерного массива. Операции сложения и вычитания матриц выполняются поэлементно. Умножение требует наличия у левого сомножителя такого же числа столбцов, как и число строк у правого сомножителя. Поэлементно умножаем каждую строку первой матрицы на каждый столбец второй накапливая сумму значений в элементах результирующей матрицы.

Код C++

Код C++ на Ideone: A705

Код Java

Код Java на Ideone: A705

Тесты:

№ теста Размерность матрицы n Матрица A Матрица В Ответ
1 2 3 4
2 1
2 1
9 0
  39.50  -0.67

11.33  1.25

2 4 5 5 5 5
0 0 8 7
2 3 4 7
8 6 1 2
5 7 3 4
9 8 3 4
2 3 4 5
6 6 6 6
  105.50  115.33  75.25  90.20

58.33  66.25  66.20  75.17

85.25  89.20  69.17  75.14

100.20  113.17  57.14  71.12

3 3 0 0 0

0 0 0

0 0 0

1 0 0

0 1 0

0 0 1

 0.5 0.33 0.25

0.33 0.25 0.20

0.25 0.20 0.17