e-olymp 4481. В стране невыученных уроков

Задача

Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа [latex]l[/latex] и [latex]r[/latex], и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от [latex]l[/latex] до [latex]r[/latex] включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие.

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

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

Первая строка содержит количество элементов [latex]n[/latex] [latex](1\leq n\leq 10^5)[/latex] в массиве. Во второй строке находится [latex]n[/latex] чисел – элементы [latex]a_i[/latex] [latex](1\leq a_i\leq 10^9)[/latex] массива. В третьей строке находится количество запросов [latex]m[/latex] [latex](1\leq m\leq 10^5)[/latex]. Далее в [latex]m[/latex] строках находятся по три числа [latex]q[/latex], [latex]l[/latex], [latex]r[/latex] [latex](1\leq l\leq r\leq n)[/latex]. Если [latex]q=1[/latex], требуется посчитать НОД элементов на промежутке [latex][l,r][/latex], если [latex]q=2[/latex], то надо заменить элемент в позиции [latex]l[/latex] на число [latex]r[/latex].

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

Для каждого запроса с номером [latex]l[/latex] в отдельной строке выведите ответ на запрос.

Тесты

Входные данные: Выходные данные:
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 5
2
2
5
1

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

Алгоритм решения

Данная задача решена с помощью структуры данных «дерево отрезков». В каждой вершине дерева храним НОД всех чисел на соответствующем отрезке массива. Функции, отвечающие за построение самого дерева отрезков, нахождение  НОД на отрезке и запрос на модификацию элемента являются рекурсивными.  Дерево строим следующим образом: листьями данного дерева будут сами элементы исходного массива, а значения элементов, находящихся на уровень выше, будут представлять собой НОД двух соседних листов. Таким же образом считаем значения вершин следующего уровня и т.д. Чтобы найти НОД на заданном отрезке рассматриваем случаи расположения данного отрезка. Он может полностью принадлежать одному потомку, а может быть разбит между правым и левым потомками. В первом случае функцию запускаем от одного потомка и получаем требуемое, во втором случае функцию запускаем от двух потомков и находим от полученных результатов НОД. При выполнении запроса на модификацию запускаем функцию от корня, спускаемся до требуемого элемента, изменяем его, и поднимаемся обратно к корню, модифицируя значения вершин, для которых данный элемент является подотрезком.

В самой задаче, в зависимости от требуемого, в цикле находим НОД на заданном отрезке или выполняем модификацию элемента.

Для получения подробной информации о структуре данных «Дерево отрезков» можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

e-olymp 1455. Цикл

Задача

Дан граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.

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

Первая строка содержит количество вершин графа n (1n100). В следующих n строках находится по n чисел — матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.

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

В первой строке выведите «YES«, если цикл существует, или «NO» в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковыми первую и последнюю) и в третьей строке — вершины, входящие в этот цикл в порядке обхода. Если циклов несколько — выведите любой.

Тесты

Входные данные Выходные данные:
2
0 -1
-1 0
YES
3
1 2 1
4
0 2 0 9
2 0 6 0
0 6 0 -3
9 0 -3 0
YES
3
3 4 3
3
0 2 3
2 0 1
3 1 0
NO

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

Алгоритм решения:

Для решения данной задачи задействован алгоритм Беллмана-Форда, который позволяет проверить наличие или отсутствие цикла отрицательного веса в графе, а при его наличии — найти один из таких циклов. Создадим вектор, который будет содержать в себе элементы матрицы смежности графа. По определению смежных вершин графа, учитывая условие задачи (если ребра нет, соответствующее значение равно [latex]100000[/latex]), заполним этот вектор. Далее будем использовать алгоритм Беллмана-Форда. Если алгоритм даст отрицательный ответ на вопрос задачи, то выводим NO. Если цикл все-таки существует, то выводим YES. В вектор записываем вершины, входящие в цикл отрицательного веса. Далее выводим их количество, а затем и сами вершины в порядке обхода.

Для получения подробной информации об алгоритме Беллмана-Форда можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

e-olymp 6127. Очередь неограниченного размера

Задача

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

push n

Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из очереди первый элемент. Программа должна вывести его значение.

front

Программа должна вывести значение первого элемента, не удаляя его из очереди.

size

Программа должна вывести количество элементов в очереди.

clear

Программа должна очистить очередь и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Размер очереди должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций front и popпрограмма должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция frontилиpop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error.

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример выходных данных.

Тесты 

Входные данные Выходные данные:
1 push 1
front
exit
ok
1
bye
2 size
push 1
size
push 2
size
push 3
size
exit
0
ok
1
ok
2
ok
3
bye

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

Алгоритм решения:

Каждый элемент (узел) очереди состоит из информационной части (его значение) и адресной. В адресную часть первого элемента записываем адрес следующего элемента и т.д., тем самым мы создаем порядок следования элементов в очереди, связывая их между собой. При добавлении или удалении элемента мы соответственно изменяем размер очереди, который изначально равен нулю, а также меняем позиции указателей на начало и конец очереди. В условии задачи сказано, что если во входных данных встречается операция front или  pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error. Поэтому создаем исключительную ситуацию для проверки наличия в очереди хотя бы одного элемента.

Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

 

 

 

A304

Задача
Даны действительные числа [latex]a_{1},a_{2},\cdots[/latex] (читать до конца входного потока). Переставить члены последовательности так, чтобы сначала расположились все ее неотрицательные члены, а потом  — все отрицательные. Порядок как среди неотрицательных членов, так и среди отрицательных должен быть сохранен прежним.
Код программы
Тесты

Test № Input Output
1 -23 45 17 -78 0 34 45 17 0 34 -23 -78
2 -56 -56.34 0.2 56 9 0.2 56 9 -56 -56.34
3  -1 3 2 1 0 -3 -2 3 2 1 0 -1 -3 -2
4 -0.333 -1 0 1 0 -2 0 2 0 1 0 0 2 -0.333 -1 -2
5 9 -9 0 -96 -11 27 -13 9 0 27 -9 -96 -11 -13

Алгоритм решения

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

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

 

A279

Задача

Даны действительные числа [latex]a_{1},[/latex] … [latex], a_{n},[/latex] [latex]b_{1},[/latex] … [latex], b_{n}[/latex]. Вычислить [latex](a_{1} + b_{n})(a_{2} + b_{n-1})[/latex] … [latex](a_{n} + b_{1})[/latex].
Тесты
Test № Input Output
1  1 2 3 4 5 6  343
2  1 1 1 1  4
3  0.5 0.1 0.07 -4 7 13  -376.691
4  0 0 0 0 0 0 0 0  0
5  0.4 0.3 2 -1 0.7 0.6  1

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

Алгоритм  решения

 Считываем все действительные числа до конца входного потока и записываем их в один вектор c. Далее работаем по такому алгоритму: складываем первый элемент вектора с последним, а полученный результат умножаем на переменную result, значение которой изначально равно единице, т.к, единица  — нейтральный элемент при умножении. Далее складываем второй элемент вектора с предпоследним, а полученный результат снова умножаем на переменную result и т.д. Так делаем до тех пор, пока не дойдем но середины вектора  c. Затем выводим полученное значение переменной  result.

MLoops 11

Задача

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел n > 0 (количество столбцов) и m > 0(количество строк).
Замечание 1. В некоторых задачах появляется дополнительный параметр k < n.
Замечание 2. Многоточие означает продолжение последовательности.                            Совет. Если закономерность разгадать не получается, попробуйте воспользоваться Онлайн-энциклопедией целочисленных последовательностей.

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

Три числа: количество столбцов и строк, параметр [latex]k[/latex].

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

Код программы:
Решение:

Для построения данной таблицы нужно найти закономерность чередования символов в таблице. Решение данной задачи можно осуществить с помощью двух циклов. Первый отвечает за строки, а второй — за столбцы. Пусть нумерация строк и столбцов начинается с нуля. Тогда, если номер строчки нацело делится на [latex](k+1)[/latex], то рассматриваем столбцы этой строчки. Если номер столбца нацело делится на [latex](k+1)[/latex], то записываем «+», иначе «-«. Если номер строки не делится нацело на [latex](k+1)[/latex], а номер столбца в этой строке — делится, то записываем «|». Если номер строки и столбца не делятся нацело на [latex](k+1)[/latex], то создаем переменную, с помощью которой будем заполнять таблицу цифрами. Так как, каждый столбик и каждая строка имеют свой номер, то с помощью нахождения суммы остатка от деления строки и столбца на [latex](k+1)[/latex] будем находит значение элемента, стоящего на пересечении [latex]i- [/latex]ой строки и [latex]i-[/latex]ого столбца, но этого не достаточно, в таблице есть перестановка, чтобы ее реализовать отнимаем от суммы единицу, делая этим сдвиг вправо. Также от полученного результата нужно найти остаток от деления на параметр [latex]k[/latex] для того, чтобы выполнялась правильная последовательность символов. Если результат вычисления переменной равен нулю, то записываем значение параметра [latex]k[/latex], иначе — результат вычисления переменной.

Тесты:

m n k

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

5 5 10  
 14 13  5  
 9  7  5  
 17  30 7  

 

 

Код программы на ideone.com