e-olymp 8379. Нулі та одиниці

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

Задача

Їжачок Аліна, переглядаючи свої старі зошити знайшла в одному з них неймовірно цікавий масив з нулів. Виявилось, що Аліна з цим масивом вміє робити кілька неймовірно цікавих операцій:

  • Присвоїти елементу в позиції $x$ значення $1.$
  • Присвоїти елементу в позиції $x$ значення $0.$
  • Замінити на відрізку від $l$ до $r$ всі нулі на одиниці і навпаки.
  • Повернути масив в стан, який був після $x$-ої операції.
  • Знайти кількість одиниць на підвідрізку масиву від $l$ до $r.$

Вхідні дані

В першому рядку задано два натуральні числа $N \leqslant 10^5$ i $M \leqslant 2 \cdot 10^5,$ що позначають розмір масива і кількість операцій відповідно. В наступних $M$ рядках задано інформацію про операції.

Вихідні дані

Для кожної операції типу $5$ вивести кількість одиниць на підвідрізку від $l$ до $r.$

Тести

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

1

8 7
1 1
3 1 4
5 1 5
2 3
5 1 5
4 1
5 1 5
3
2
1

2

4 5
1 2
1 3
2 2
3 1 3
5 1 2
2

3

4 7
1 2
1 3
2 2
3 1 3
5 1 2
4 1
5 1 2
2
1

Код

Рішення

Спочатку потрібно декілька з’ясувати умову завдання, адже в ній не сказано за що відповідає перше число в кожному запиті. Це число — це номер операції, які задані в умові задачі, вони нумеруються від $1$ до $5.$ Це завдання будемо вирішувати за допомогою персистентного дерева відрізків. Зміст персистентного дерева відрізків в тому, що воно зберігає всі попередні версії самого дерева, тобто всі його стани після будь-яких модифікацій. Суть в тому, що коли ми спускаємося по дереву ми всього лише пройдемо максимум по $\log (n)$ його вершинах, що дає нам при запиті на модифікацію можливість не просто «тупо» скопіювати весь масив з $4 \cdot n$ елементів, а зберегти нову версію дерева, де зміняться лише $\log (n)$ вершин. Тобто сумарно $k \cdot \log (n)$ пам’яті замість $k \cdot n.$ Побудова персистентного дерева відрізків буде аналогічно побудові звичайного дерева відрізків за винятком того, що тепер для кожної вершини додатково доведеться в явному вигляді зберігати посилання на дочірні вершини. Додатково будемо зберігати вектор вершин, що є корінням у відповідних версіях дерева. При будові, в нього додамо єдину вершину, що є коренем отриманого дерева. Таким чином, складність побудови залишилася незмінною, а саме $O(n).$  При зміні вершини до нього будуть додані тільки ті вершини, які повинні були змінитися, і замість зміни значень старих вершин, перераховані значення будуть збережені в нові. Всі нові вершини будуть посилатися на одну вершину з дерева старої версії і на одну з щойно доданих. Тим самим, при запиті оновлення буде створено $O (\log (n))$ нових вершин, у тому числі буде створено новий корінь дерева відрізків, а вся попередня версія дерева, підвішена за старий корінь, залишиться без змін. Наприкінці потрібно зазанчити, що задача заходить на eolymp за часом лише з використанням функцій вводу/виводу scanf() та printf().

Посилання

ideone

e-olymp

Дерево відрізків на e-maxx

e-olymp 4852. Кратчайшее расстояние

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

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины $x$ до всех остальных вершин графа.

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

В первой строке содержатся два натуральных числа $n$ и $x$ $(1 \leqslant n \leqslant 1000, 1 \leqslant x \leqslant n)$ — количество вершин в графе и стартовая вершина соответственно. Далее в $n$ строках по $n$ чисел — матрица смежности графа: в $i$-ой строке на $j$-ом месте стоит «$1$», если вершины $i$ и $j$ соединены ребром, и «$0$», если ребра между ними нет. На главной диагонали матрицы стоят нули.

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

Выведите через пробел числа $d_1$, $d_2$, …, $d_n$, где $d_i$ равно $-1$, если путей между $x$ и $i$ нет, в противном случае это минимальное рaсстояние между $x$ и $i$.

Тесты

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

1

3 3

0 1 1

1 0 1

1 0 0

1 2 0

2

6 5

0 1 1 0 0 0

1 0 0 0 0 0

1 1 0 0 0 0

0 0 0 0 1 0

0 0 1 1 0 0

0 1 0 0 0 0

2 2 1 1 0 -1

3

3 1

0 0 0

0 0 1

1 1 0

0 -1 -1

Код

Решение

Данную задачу будем решать поиском в ширину. Сам граф будем хранить в двумерном массиве  graph[][], в массиве d[] будем хранить кратчайшее расстояние между заданной вершиной и $i$-ой. В очереди queue <int> q  будем хранить обрабатываемые вершины. В самом начале там будет хранится только наша исходная вершина, затем пока в очереди хранятся какие-либо вершины достаем верхнюю и смотрим ребра, выходящие из нее, если ранее вершины не были задействованными, то помещаем в конец очереди. Очередь опустеет, когда будут просмотрены все вершины, в которые можно попасть из исходной $x$. Сложность алгоритма $O(n)$.

Ссылки

ideone

e-olymp

Поиск в ширину на e-maxx

e-olymp 4844. Поиск общей подстроки

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

Задача

Дана строка [latex] A = [/latex] [latex] a_1a_2…a_n  [/latex] и строка [latex] B = [/latex] [latex] b_1b_2…b_m  [/latex]. Также дано число [latex] L [/latex].

Нужно узнать, есть ли у строк [latex] A [/latex] и [latex] B [/latex] общая подстрока длиной [latex] L [/latex].

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

В первых двух строках записаны строки [latex]A[/latex] и [latex]B[/latex], состоящие из строчных латинских букв. Эти строки непустые и имеют длину не более [latex]100000[/latex] символов. В третьей строке записано целое число [latex]L   (0 \leq L \leq 100000) [/latex] — длина общей подстроки.

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

В выходной файл выведите [latex]YES[/latex], если существует общая подстрока такой длины. В противном случае выведите [latex]NO[/latex].

Тесты

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

1

saaa

baaa

3

YES

2

raabc

taaac

3

NO

3

aaaaaaaka

akaa

3

YES

4

abcdfeg

qwertycdfeg

10

NO

Код 1

Решение 1

Суффиксный автомат

Создадим структуру struct state, которая будет хранить информацию о переходах. len — это длина строки (далее будем использовать, как длину строки в каком-то состоянии), link — это суффиксальная ссылка, список переходов будем хранить в контейнере map <char, int> next, где ключом будет выступать символ, а значением — номер состояния.. Сам суффиксный автомат будем хранить в массиве этой структуры. Заведем переменные last и  sz, отвечающие за последнее состояние и номер нового состояния соответственно.

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

В автомат будем добавлять символы поочередно, для чего нам потребуется еще одна функция sa_extend(). В начале которой будем присваивать новому состоянию соответствующий номер. А затем будем просматривать все переходы из последнего состояния по текущему символу. Таким образом переход либо будет, либо нет. Если его нет, то добавим его в текущее состояние cur и продолжим смотреть дальше, если же при этом мы дошли до состояния, на которое указывает суффиксная ссылка изначального состояния (нулевого), то суффиксную ссылку текущего состояния приравняем к нулю. Далее рассматриваем случай, когда из текущего состояния по символу переход существует, обозначим q за состояние, куда ведет переход.

Поиск наибольшей общей подстроки

Сначала для строки a  построим суффиксный автомат. Заведем две переменные, благодаря которым найдем совпадающую часть двух строк. Для этого нужна переменная, отвечающая за состояние v и переменная, отвечающая за длину совпадающей части l. Если есть переход, то переходим и увеличиваем длину на 1. Если нету, то уменьшаем длину совпадающей подстроки и переходим в новое состояние, меняя l. Цикл будет работать до тех пор, пока не найдем переход. Однако, если по суффиксным ссылкам мы дошли до состояния, в которое ведет ссылка изначальной вершины, то символ не встретился. Теперь длина наибольшей общей подстроки bestpos — это максимум из всех значений l.

Код 2

Решение 2

Стоит отметить сразу, что данный код, по сути не работает на некоторых тестах, например когда символы, которые должны входить в искомую наибольшую подстроку, стоят в начале или конце обоих строк или хотя бы одной из них. Однако, как показывает практика, тесты на e-olymp данный способ посимвольного сравнения проходит. В данном варианте решения будем использовать c-string. Сами строки объявлены так: char a[100001], b[100001];, где [latex]100001[/latex] — это максимальная длина строки, которая может быть по условию задачи, и еще [latex]+1[/latex]. Объявить можно было еще и так: char * a = new char [100001];

Ссылки

ideone (1)

ideone (2)

e-olymp (1)

e-olymp (2)

e-olymp 4557. Одинокий король

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

Задача


Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из $n$ его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) — возможные ходы короля показаны на рисунке снизу.
Определите, побывал ли король дважды на одном и том же поле за свои [latex] n [/latex] ходов.

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

В первой строке задано общее число ходов короля [latex] n [/latex] [latex](0 ≤ n ≤ 1000)[/latex]. В последующих [latex] n [/latex] строках заданы направления перемещения короля: строка под номером [latex] i + 1 [/latex] задаёт направление перемещения короля на [latex]i[/latex]-ом ходу.

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

Выведите единственное число — номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение «Ok» (без кавычек), а во второй — манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.
Напоминаем, что манхэттенское расстояние между точками с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] определяется по формуле: [latex]d = |x_2 — x_1| + |y_2 — y_1|[/latex].

Тесты

# Входные  данные Выходные данные
1 5 1 2 4 7 4 4
2 5 1 2 4 6 4 Ok 2
3 3 1 2 1 Ok 5
4 3 1 5 1 2
5 8 8 8 8 8 8 8 8 8 Ok 8

Код

Решение

За изначальное местоположение короля возьмем точку с координатами [latex](0, 0)[/latex], а все передвижения короля по шахматной доске — это изменение абсциссы и (или) ординаты данной точки. Создадим два динамических массива  x = new int [n];  и  y = new int [n]; на [latex] n [/latex] элементов каждый, для абсцисс и ординат соответственно. Они будут хранить изменения координат всех точек, в которых побывал король. При этом, так как мы считаем, что начинаем движение с начала координат начнем заполнение массивов со второго элемента. Когда массивы в цикле  for (int i = 1; i <= n; i ++);  заполнятся будем искать совпадающие точки в другом цикле, если же таких не найдется, посчитаем расстояние между конечным и начальным местоположением короля, однако так как начальное местоположение короля — это начало координат, то ограничимся лишь немного упрощенной формулой [latex]d = |x_n| + |y_n|[/latex], или же в коде это выглядит так:  abs(x[n]) + abs(y[n]);. После, не забываем удалить уже использованные массивы, чтобы освободить память.

Код 2

Решение 2

Данный способ будет отличаться тем, что в отличии от предыдущего решения мы ограничимся лишь одним массивом, содержащим попарно координаты абсцисс и ординат соответственно. Также операторы  if(); можно заменить массивами  X[]; и  Y[]; , которые на соответствующих местах уже содержат изменение абсциссы и ординаты положения короля при конкретном перемещении.

Код 3

Решение 3

Изначально создаем двумерный массив заполненый нулями. Однако будем считать изначальное положение короля в точке с координатами [latex](1001, 1001)[/latex], чтобы не было проблем с отрицательными значениями. В данном варианте кода для большей краткости и разнообразия будем использовать оператор  switch();. Если король в клетке не был, то поставим [latex]1[/latex], если же был — выводим номер хода. Высчитываем манхэттенское расстояние если король не был в одной точке дважды.

Ссылки

  • Засчитанное решение 1 на e-olymp.
  • Засчитанное решение 2 на e-olymp.
  • Засчитанное решение 3 на e-olymp.
  • Код 1 в ideone.
  • Код 2 в ideone.
  • Код 3 в ideone.

e-olymp 479. Вышивка “крестиком”

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

Задача

Валя на уроках труда училась вышивке крестиком. Но для вышивки ей нужно было приготовить макет узора, который также имел форму “крестика”, в котором количество вышитых крестиков по диагонали было равно номеру тренировочного узора. Помогите Вале приготовить нужное количество макетов.

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

Сначала кол-во макетов, потом их номера. Все номера узоров у Вали имели одну странность — всегда были нечетными и не превышали 80.

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

Макеты, в порядке, перечисленном во входном файле, разделенные пустой строкой.

Тесты

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

1

2 3 5 X X
 X
X X

X   X
 X X
  X
 X X
X   X

2

1 9 X       X
 X     X
  X   X
   X X
    X
   X X
  X   X
 X     X
X       X

Код

 

Решение

В данной задаче будем использовать потоковую обработку. Сначала считываем количество макетов [latex] n [/latex]. Затем в цикле for (int l = 0; l < n; l ++);   считываем номера узоров.  Выводить [latex] X [/latex] будем по диагоналям (справа налево и наоборот). Однако, стоит учесть, что после последнего символа [latex] X [/latex] в строке, выводить пробел не стоит. В условии задачи данный факт не фигурирует, однако, если же сделать иначе, то задача на сайте e-olymp не пройдет. Из этого вытекает, что пробелы должны располагаться исключительно до последнего крестика в строке. Для этого во внутреннем цикле ставим соответсвующее условие, чтобы при достижении последнего крестика в строке осуществлялся переход на другую строку, если это возможно. Также стоит не забыть, что между разными узорами нужно пропускать строку.

Ссылки

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

Код в ideone.

e-olymp 1452. Кролики

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

Задача

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

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

Первая строка содержит количество месяцев [latex] n [/latex] [latex] (0 ≤ n ≤ 100) [/latex], вторая — число кроликов [latex] k [/latex] [latex]  (0 ≤ k ≤ 10000) [/latex], которое съедал монстр.

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

Определить количество кроликов, которое будет находиться на планете ТТВ через [latex] n [/latex] месяцев после поселения туда первого кролика. Известно, что результат для любого теста всегда не больше [latex] 2 \cdot 10^9 [/latex].

Тесты

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

1

0 10

1

2

1 10

2

3

10 7

128

4

7 128

12

5

30 0

1073741824

6

29 29

2

7

20 20

16

8

90 90

64

Cпособ 1 (с циклом)

Код

 

Решение

Известно, что изначально на планете был один кролик. Создадим цикл, который будет высчитывать популяцию кроликов на планете через [latex] n [/latex] месяцев после прибытия. Цикл будет работать до тех пор, пока количество месяцев будет больше нуля. В нем будем высчитывать популяцию кроликов по простой формуле [latex] r = r \cdot 2 [/latex], где [latex] r [/latex] — количество кроликов. Если же количество кроликов, съедаемых монстром в начале месяца строго больше того количества, которое уже есть на планете, то от этой популяции отнимем [latex]  k [/latex]кроликов : [latex] r = r[/latex] $-$ [latex] k [/latex]. Внутри цикла также не забываем от данного количества [latex] n [/latex] месяцев отнимать по одному каждый раз.

Способ 2 (без цикла)

Код

Решение

Сам алгоритм похож на 1 способ, однако здесь мы будем использовать рекурсивную функцию, а не цикл. Функция  int f2();  будет вызывать сама себя до тех пор, пока количество месяцев [latex] n [/latex] не станет равным нулю.

Ссылки

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

1 Код в ideone.

2 Код в ideone.

e-olymp 939. Квадрат суммы

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

Задача

Найти квадрат суммы цифр двузначного натурального числа.

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

Одно натуральное двузначное число.

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

Квадрат суммы цифр заданного числа.

Тесты

#

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

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

1

23

25

2

25

49

3

36

81

4

60

36

5

99

324

Код

Решение

Разобьем двузначное натуральное число [latex] n [/latex]  на два числа, содержащих соответственно его первую цифру  ( [latex] c_1 [/latex] ) и вторую — ( [latex] c_2 [/latex] ), где  [latex] c_2 = n \mod 10[/latex], в то время как [latex] c_1 = \frac {n} {10} [/latex]. Теперь, чтобы получить квадрат суммы цифр двузначного натурального числа, сложим два эти числа и умножим еще раз на их сумму [latex] (c_2 + c_1) \cdot (c_2 + c_1) [/latex].

Ссылки

ideone

e-olymp