Обратная польская запись

 

Алгоритм:

Пока строка содержит символы для чтения, читаем очередной символ. Далее рассматриваются варианты:
1) Если символ не является символом функции или скобкой, добавляем его к выходной строке.
2)

  1. Если встретили символ функции, помещаем его в стек.
  2. Если встретили символ функции и при этом стек не пустой, выталкиваем в выходную строку все символы функции, пока не встретим символ, имеющий больший приоритет или открывающую скобку.
  3. Если символ является закрывающей скобкой:
    Выталкиваем элементы из стека в выходную строку, пока верхним элементом стека не станет открывающая скобка. Если после этого на вершине стека находится символ функции, выталкиваем его в выходную строку.
  4. Если символ является открывающей скобкой, помещаем его в стек.

Код на Ideone.

e-olymp 4050. Забавная игра

Ссылка на задачу.

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

В одной стране есть несколько аэропортов, между некоторыми аэропортами есть рейсы. Можно перелететь из любого аэропорта в любой другой, возможно, с несколькими пересадками. Для каждой пары аэропортов существует только одна последовательность рейсов, соединяющая эти аэропорты.

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

Напишите программу, которая по начальному списку полётов и номеру аэропорта, в котором террористы начинают игру, определяет, кто выигрывает, если террористы играют идеально (каждый выбирает лучший ход).

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

Первая строка содержит два целых числа: n и k, разделённые пробелом. Здесь n — количество аэропортов (n1000), а k — номер аэропорта, являющегося начальной точкой игры (1kn). Следующая n−1 строка содержит пары целых чисел, разделённых пробелами. Это номера аэропортов, соединённых рейсом. Все рейсы двусторонние и упомянуты только один раз. Каждый аэропорт соединён рейсами не более, чем с 20 другими.

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

Если игрок, начинающий игру, выигрывает, программа должна написать «First player wins flying to airport L«, где L— номер аэропорта, в который игрок должен вылететь из текущего. Если таких аэропортов несколько, программа должна выбрать вариант с меньшим номером аэропорта. Если начинающий игрок проигрывает, программа должна написать «First player loses«.

Определяем массив аэропортов, булев массив пройденных аэропортов уровень вложенности функции dfs(), переменную запоминающую вторую вершину, булевы переменные для определения победителя, отсортированных вершин. В функции мы отмечаем первую вершину как пройденную переходим на следующий уровень. Сортируем все возможные варианты перехода, выбираем наименьший подходящий нам. Далее определяем переменную, которая считает вершины, в которые можно пойти из данной. В цикле проходим все вершины, пока проходим считаем количество детей.
Если оно равно нулю то это тупик.
И мы посмотрим кто бы выиграл если бы бандиты дошли до этого аэропорта.Если level нечетный, то мы ищем правильный ход первого, иначе второго террориста. Если уровень равен 1, то мы уже выходим. Выводим ответ. Иначе, если level не равен 1, то мы еще не дошли до конца и возвращаем выше, кто выигрывает в данном узле.
При этом каждый бандит ищет ветку где бы он победил.
Определяем количество детей. Если мы не в тупике, то но увеличивается на 1. Далее, если ходит второй террорист, то он выбирает ветку, в котором выиграет он. Если мы попали в тупик, выводим кто выиграл в зависимости от четности пройденного пути.
В main() считываем количество аэропортов и номер первого , записываем в вектора смежные аэропорты для каждого и запоминаем первую вершину. Запускаем dfs().

А 1041

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

Предполагается, что используется обычная шахматная доска размером 8х8, а слоны могут бить по
обоим частичным диагоналям на пересечении которых они находятся. Если на той же диагонали находится ещё один слон, то он перекрывает линию боя. Для данной задачи этот факт не имеет значения, поскольку требуется, чтобы каждую клетку бил хотя бы один слон. Перекрытые клетки диагонали будут находиться под боем того слона, который перекрывает линию боя.

Определяем переменные: количество слонов, длинна и ширина шахматного поля, массив клеток поля. Далее определяем булевы переменные для добавления и удаления диагоналей, расположения слонов, выхода из рекурсии. Функция «giagonal» осуществляет все операции с диагоналями. Добавляет/удаляет диагонали(параллельные главной или побочной). Она принимает булевы переменные для определения того, добавляем мы главную диагональ или побочную, собираемся мы добавлять диагональ или удалять. А также координаты начала диагоналей, координаты расположения слона.  Если клетку бьет какой-либо слон, прибавляем к ее значению 1. При этом число свободных клеток уменьшается. Если же мы удаляем диагональ, то просто уменьшаем количество бьющих данную клетку слонов (это указывается в самой клетке). Если удаленный слон был единственным, кто ее бил, увеличиваем число свободных клеток. Функция «space». Она используется как для удаления, так и для добавления диагоналей. В ней мы запоминаем последнее расположение слонов на доске и далее ищем начало прохода диагоналей. Для этого сначала мы определяем в какой части доски находится поставленный слон и исходя из этого, если оказалось, что координата по горизонтали больше координаты по вертикали, то следовательно начало первой диагонали будет в первой строке, в противном случае ее начало будет в первом столбце. Вторые координаты зависят от разности j-i. При поиске начала второй диагонали используем сумму i+j, если эта сумма меньше 8 (то есть слон находится ближе к верхнему левому углу доски, чем к правому нижнему) тогда диагональ начинается в первом столбце. Функция «find_permutation» (рекурсивно расставляет слонов). С каждой новым поставленным слоном увеличиваем переменную level, для определения в последствии момента установки последнего слона. Просматриваем клетки, если какая-то из них не под боем-ставим туда слона и запускаем функцию «space» для него. Так расставляем их, пока число слонов не достигнет 8. Если после какой-либо расстановки мы нашли правильный ответ, то используя булеву переменную isEnd выходим из рекурсии. Если после установки восьмого слона оказалось, что все поля были заполнены, то мы выводим: «Ответ найден» и печатаем доску (если булева переменная is_set — true, то есть этот элемент слон, тогда выводим 1, остальные клетки — 0). Далее выходим из всех циклов, определив переменную isEnd = true. Удаляем слонов и битые ими поля. Конец программы.

ideone.com

e-olymp 4. Две окружности

Две окружности

Ссылка на засчитанное решение.

Определить количество точек пересечения двух окружностей.
Входные данные

6 чисел x1, y1, r1, x2, y2, r2, где x1, y1, x2, y2 — координаты центров окружностей, а r1, r2 – их радиусы. Все числа — действительные, не превышают по модулю 1000000000, заданы не более чем с 3-мя знаками после запятой.

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

Количество точек пересечения. Если точек пересечения бесконечно много, то вывести -1.

Считываем данные, далее если координаты центров и длины радиусов совпадают печатаем: «-1». Затем рассматриваем варианты, когда окружности имеют одну, две общих точки либо не имеют ни одной.

Код на Java:

Код Ideone

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

e-olymp 974. Флойд-1

974. Флойд-1

Ссылка на засчитанное решение.

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

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

В первой строке записано количество вершин графа n (1n100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

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

Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.

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

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

e-olymp 625. Расстояние между вершинами

Задача с сайта e-olimp № 625.

Ссылка на засчитанное решение.

РАССТОЯНИЕ МЕЖДУ ВЕРШИНАМИ

Дан неориентированный взвешенный граф. Найти вес минимального пути между двумя вершинами.

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

Первая строка входного файла содержит натуральные числа N, M, S и F (N5000, M100000, 1S, FN, SF) — количество вершин и ребер графа а также номера вершин, длину пути между которыми требуется найти.

Следующие M строк содержат по три натуральных числа bi, ei и wi — номера концов i-ого ребра и его вес соответственно (1bi, eiN, 0wi100000).

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

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

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

После считывания входных данных создаем три массива. Массив вершин входящих в кратчайший путь, а также два массива для преобразования считанной матрицы в матрицу смежности  вершин графа. Далее с помощью алгоритма Дейкстра находим кратчайшее расстояние до каждой вершины и одновременно записываем в  массив [latex]h\left [ n \right ][/latex] вершины, через которые проходит кратчайший путь. Затем выводим расстояние до вершины [latex]f[/latex] если путь к ней существует, иначе печатаем: «-1». Далее выводим кратчайший маршрут между вершинами [latex]s[/latex] и [latex]f[/latex].