e-olimp 5077. Полуполный граф

Задача: Полуполный граф

Решение

ссылка на ideone, засчитанное решение на e-olymp

Решение на Java

ссылка на ideone, засчитанное решение на e-olymp

Идея решения

Считаем что граф неорентированный и проверяем, не полный ли наш граф. Если полный — выводим «YES», иначе «NO».

e-olimp 553. Рекурсия

Задача: Рекурсия

Решение

ссылка на ideone, засчитанное решение на e-olimp

Идея решения

Можно заметить, что каждая процедура — это вершина ориентированного графа. Чтобы узнать, является ли процедура потенциально рекурсивной, нужно было запустить из неё поиск в глубину и узнать, сможем ли мы прийти к ней вновь.

Было решено использовать map<string,set<string>> как структуру для описания графа: каждая вершина — это строка и у каждой вершины есть множество вершин (строк), смежных с ней.
А еще задача имеет классификацию — поиск в глубину, что как бы намекает.

Стек, дек и очередь неограниченного размера

Задачи: Стек, Очередь и Дек

Решение:

Код для задачи на неограниченный стек:

Код для задачи на неограниченную очередь:

Код для задачи на неограниченный дек:

Засчитанные решения на сайте e-olimp: Стек, Очередь и Дек.

Идея решения: Каждый элемент в структуре должен хранить информацию о предыдущем и последующем. Для этого была организована структура Node. Для дека и очереди она одинаково реализована, а для стека можно было хранить только предыдущий элемент. Во всех 3х задачах была реализована требуемая структура данных.

Однако в каждой задаче требовалось возможность использования всей оперативной памяти под структуру. В моем решении каждый элемент занимает втрое больше памяти (я подозреваю) чем обычный int, а значит всю оперативную память под числа я использовать не смогу. Тогда можно использовать заранее созданный массив достаточно большого размера, чтобы занять всю выделенную память в 256 мб. Но это не будет считаться «неограниченным» размером. А если использовать ту же структуру с Node, но вместо одного элемента хранить массив? Тогда информацию о следующем и предыдущем массиве нужно так-же хранить, как и с отдельными элементами. Вроде бы меньше памяти будет тратится на хранение дополнительной информации, НО никто не может точно сказать, какого размера массивы должны быть. Если они будут слишком маленькие — большой выгоды такой способ не принесет. Если они будут слишком большими, то есть шанс, что мы не покроем большой кусок памяти, что тоже не очень хорошо.

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

Поэтому я реализовал всё без массивов (хотя вариант с маленькими массивами имеет место быть).

AA21

Задача. В строке сосчитать количество всех открывающих (квадратных, круглых и фигурных) и закрывающих скобок. Если открывающих скобок на одну больше, добавить закрывающую круглую скобку в конец, а если открывающих скобок на одну меньше, то удалить последнюю закрывающую.

Тесты:

Ввод Результат Комментарий
./main «({){«  «({){« Пройдено
./main «({}){«  «({}){)» Пройдено
./main «)]}]([[«  «)]}([[« Пройдено

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

Идея решения:
Сосчитать кол-во открывающих и закрывающих скобок в одну переменную. Если текущий символ — открывающая скобка, то прибавить к переменной единицу, если закрывающая скобка, то отнять единицу. Совершать проверку переменной на равенство 1 (если на одну открывающую скобку больше) или -1 (если на одну открывающую скобку меньше).

Скриншот:
AA21

А407

Задача:
Даны натуральные числа n и m, действительное число r, действительная матрица размера nxm. Получить значение [latex]{b}_{1}{r}^{n-1}+{b}_{2}{r}^{n-2}+\dots+{b}_{n}[/latex], где [latex]{b}_{k}[/latex] — первый по порядку положительный элемент в k-й строке матрицы [latex](k=1,\dots,n)[/latex]; если в k-строке нет положительных элементов, то [latex]{b}_{k}=0.5[/latex].

Тесты:

nxm r Матрица Результат Комментарий
2х2 2.5 [latex]\begin{pmatrix} -1 & 1 \\ 1 & 0 \end{pmatrix}[/latex]  3.5 Пройдено
 3×4  3.14 [latex]\begin{pmatrix}5.7 & 6.7 & -7.7 & 0.9\\-3.0 & 2.3 & -5.0 & -2.4\\6.7 & 3.5 & 0.0 & 4.4\end{pmatrix}[/latex]  70.1 Пройдено
 2×4  2.71 [latex]\begin{pmatrix}-9.0 &-8.8 &-7.3 & 7.5\\-6.3 &-9.7 & 6.8 &-0.5\end{pmatrix}[/latex]  27.1 Пройдено

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

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

Идея решения:
Считать n, m как целочисленные переменные. После этого считать r как переменную типа double. Следующим считать массив nxm созданный благодаря генератору матриц из случайных чисел заданного размера. Завести переменную [latex]sum = 0[/latex] для хранения результата. Проверять построчно каждый столбик на наличие положительного числа и прибавить первое положительное число в строке, умноженное на [latex]{r}^{n-i-1}[/latex], к результаты. В случает отсутствия положительного элемента в строке,  брать 0.5. В конце вывести результат.

А165б

Задача:
Даны действительные числа [latex]{a}_{1},{a}_{2},\dots[/latex] . Известно, что [latex]{a}_{1}>0[/latex] и что среди [latex]{a}_{2},{a}_{3},\dots[/latex] есть хотя бы одно отрицательное число. Пусть [latex]{a}_{1},\dots,{a}_{n}[/latex] – члены данной последовательности, предшествующие первому отрицательному члену (n заранее неизвестно). Получить:
б) [latex]{a}_{1}{a}_{2}\dots{a}_{n}[/latex];

Тесты:

Последовательность [latex]{a}_{1}{a}_{2}\dots{a}_{n}[/latex] Комментарий
1 2 3 4 -1 2 24 Пройден
0.5 0.4 0.3 0.2 0.1 -0.1 -0.2 -0.3 0.0012 Пройден
1.5 -1 50 1.5 Пройден
1 2 3 4 3 2 1 0 -1 0 Пройден

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

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

Идея решения:
Считывать числа с потока ввода. Если считанное число отрицательное, остановится и вывести накопленное произведение на экран. Иначе умножить произведение на очередное число.

Ю11.12

Задача:
Интерполяционный многочлен Лагранжа. Значения функции [latex]y=f\left(x\right)[/latex] заданы таблично в массиве [latex]Y\left(x\right)[/latex] при соответствующих значениях аргумента в упорядоченном массиве [latex]X\left(x\right)[/latex]. Найти значение функции в произвольной точке [latex]x[/latex] по формуле Лагранжа:
[latex]y={L}_{n}\left(x\right)=\sum _{i=1}^{n}{{y}_{i}\prod _{\underset{j\neq i}{j=1}}^{n}{\frac{x-{x}_{j}}{{x}_{i}-{x}_{j}}}}[/latex]

Вводимые значения:

X: -1 0 1 2
Y: 1 2 3 -1

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

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

 

Идея решения:
Использование отдельной функции, которой надо передать 3 параметра: значение аргумента, массив исходных значений аргумента и массив исходных значений функции при соответствующих аргументах. Эта функция возвращает значение многочлена Лагранжа при подстановки вместо [latex]x[/latex] конкретного значения.

В функции был использован внешний цикл for для вычисления суммы в формуле и внутренний цикл for для вычисления произведения [latex]\prod _{\underset{j\neq i}{j=1}}^{n}{\frac{x-{x}_{j}}{{x}_{i}-{x}_{j}}}[/latex].

В программе мы разбиваем отрезок [-3, 3] на 101 отдельную точку и вычисляем значение полинома Лагранжа для каждой из этих точек. Выводим на экран.

График:ГрафикПолиномаЛагранжа

Комментарии: Точки выбраны специально. Мне просто захотелось увидеть, как выглядит график функции, которую мы разбирали на паре (кстати по той же самой теме =) ). График сделан в xls. Векторы выбраны по причине ограниченности массива.

Skynet: the Virus

Skynet


SKYNET FINALE — LEVEL 1


Вирус

Los Angeles 2029 — Resistance HQ — Review of facts:

В минувшую субботу, сотни отважных бойцов рисковали своей жизнью, чтобы уничтожить Skynet. СТОП

Используя зараженных мото-терминаторов, им удалось привить смертельный вирус к Skynet. СТОП

Проблема: Skynet борется. СТОП

Джон, ещё раз,  нам нужна ваша помощь. СТОП


Задача:

У нас в распоряжении целый граф узлов. Некоторые из них названы шлюзами. Шлюзы надо защищать от злобного Skynet агента, который способен передвигаться по связям между узлами. Способ защиты очень прост: каждый ход можно навсегда заблокировать одну связь, тем самым, через некоторое количество ходов, полностью закрыть шлюз от нежелательных гостей.

Первичная инициализация:

Первая строка: 3 целых числа N L E

  • N — Количество узлов, включая шлюзы
  • L — Количество связей
  • E — Количество шлюзов

Следующие L строк: по два числа на строку (N1, N2), означающие, что между узлами с индексами N1 и N2 присутствует связь.
Следующие E строк: по одному числу на строку, означающие индексы шлюзов.

Инициализация за каждый игровой тик:

Одно число — индекс связи, на которой находится Skynet агент.

Вывод за каждый игровой тик:

Одна строка в которой присутствует два числа C1 и C2. C1 и C2 — это индексы двух узлов, между которыми мы хотим заблокировать переход. Если между ними нет связи, возникает ошибка. В конце строки обязательно должен стоить символ перехода на новую строку.

Программа:

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

Переходы между узлами занесены в двумерный массив N1, далее этот массив был своеобразно отсортирован (для удобства). В игровом цикле объявляем булевую переменную AgentIsNear — агент вблизи шлюза.

Первый цикл: Проверяем каждую клетку вокруг каждого шлюза на присутствие там агента. И если он таки там есть, блокируем переход, меняем первую переменную (отвечающую за шлюз) в массиве переходов (N1) на -1 (значение, которое никогда не встретится), изменяем AgentIsNear на true и прерываем цикл.

Второй цикл: так как агент гуляет где-то далеко, то мы блокируем любой свободный проход любого шлюза.

Второй цикл выполняется только тогда, когда за весь первый цикл условие внутри него ни разу не стало истинным.

Программа проходит все тесты на MEDIUM и, что удивительно, половину тестов на HARD! Взято с CodinGame

 

Ю3.39

Задача: Численно убедиться в справедливости равенства [latex]\frac{1}{4}\ln{\frac{1+x}{1-x}}+\frac{1}{2}\arctan{x}=\quad x+\frac{{x}^{5}}{5}+\dots+\frac{{x}^{4n+1}}{4n+1}+\dots[/latex], для чего для заданного значения аргумента [latex]x[/latex] вычислить левую его часть и разложение, стоящее в правой части, с заданной погрешностью [latex]e[/latex]. Испытать разложение на сходимость при разных значениях аргумента, оценить скорость сходимости, для чего вывести число итераций [latex]n[/latex] слагаемых, необходимых, для достижения заданной точности. Интервал для этой задачи: [latex]-1<x<1[/latex].

Ввод Вывод
[latex]x[/latex] Погрешность Output Комментарий
-0.99 1e-4 148 Пройден
0.99 1e-4 148 Пройден
0.99 1e-14 685 Пройден
0.7 1e-10 14 Пройден
-0.3 1e-13 6 Пройден
0.001 1e-13 1 Пройден

Идея решения: Используем цикл for, в условие которого ставим проверку на превышение погрешности суммы. Левую часть выражения вычисляем и записываем в переменную [latex]curr[/latex]. Сумму (то что стоит в правой части выражения) объявим как [latex]sum[/latex], и инициализируем значением [latex]x[/latex] (Это делается для того, чтобы во время работы цикла не вычислялось одно лишнее слагаемое).

Каждую итерацию цикла инкрементируем счетчик [latex]count[/latex]. Переменную [latex]y[/latex], которая соответствует i-тому слагаемому суммы, увеличивают до значения следующего слагаемого и прибавляют к сумме. Далее проверяем разность частичной суммы и заданного значения [latex]curr[/latex]. Если эта разность будет удовлетворять нашей точности, то число [latex]count[/latex] и будет количеством слагаемых в правой части.

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

Ideone

Ю3.17

Задача: Сколько сомножителей надо взять в произведении: [latex]\prod_{k=1}^{\infty}{(1+\frac{{(-1)}^{k}}{2k+1})}=\frac{\sqrt{2}}{2}[/latex], чтобы равенство выполнялось до шестой значащей цифры, то есть с погрешностью не более [latex]{10}^{-6}[/latex]

Идея решения: Используем цикл for, в качестве [latex]k[/latex] в формуле используем переменную [latex]count[/latex] в программе. Переменную, которая будет соответствовать произведению, назовем [latex]mul[/latex] (сокращенно от multiplication) и присвоим ей значение 1 как нейтральный элемент для операции умножения. Каждую итерацию цикла проверяем разность [latex]mul-curr[/latex], где [latex]curr=\frac{\sqrt{2}}{2}[/latex], на превышение погрешности [latex]{10}^{-6}[/latex].

Если разность больше точности, умножаем [latex]mul[/latex] на выражение под знаком произведения и увеличиваем [latex]count[/latex] на единицу.

Если разность меньше точности, число [latex]count[/latex] и будет количеством сомножителей в произведении.

Число сомножителей оказалось достаточно большим — 88390. Ideone

А34б

Задача: Даны действительные числа [latex]x,y,z[/latex] Вычислить:
[latex]\min\left(x,y,z\right)[/latex]
[latex]\max\left(x,y,z\right)[/latex]

Ввод Вывод
[latex]x[/latex] [latex]y[/latex] [latex]z[/latex] Output Комментарий
0 0 0 Max — 0
Min — 0
Пройден
1 2 3 Max — 3
Min — 1
Пройден
3 2 1 Max — 3
Min — 1
Пройден
10.1 10.01 10.001 Max — 10.1
Min — 10.001
Пройден
12345.12345 12345.123445 12345.12346 Max — 12345.123456
Min — 12345.123445
Пройден
0.001 0.0009 0.00099 Max — 0.001
Min — 0.0009
Пройден

Идея решение: Сохранить в переменную [latex]\min[/latex] и [latex]\max[/latex] числа, соответствующие минимальному и максимальному из данного набора, полученных путем (довольно сложных) вычислений с применением вложенных в тернарные операции тернарных операций.

 

Ю2.13

Задача: Проверить, лежит ли окружность [latex]{(x-{a}_{1})}^{2}+{(y-{b}_{1})}^{2}={r}_{1}^{2}[/latex] целиком внутри окружности [latex]{(x-{a}_{2})}^{2}+{(y-{b}_{2})}^{2}={r}_{2}^{2}[/latex] или наоборот.

Тестирование:

Ввод Вывод
[latex]a_{1}[/latex] [latex]b_{1}[/latex] [latex]r_{1}[/latex] [latex]a_{2}[/latex] [latex]b_{2}[/latex] [latex]r_{2}[/latex]  Печать Комментарий
 0  0  0  0  0  0  2 в 1  Пройден
 0  0  3  0  0  1  2 в 1  Пройден
 0  0  2  0  0  5  1 в 2  Пройден
 1  1  3  3  1  1  2 в 1  Пройден
 2  2  3  6  2  4  ——  Пройден
 24  27  51  96  48  20  ——  Пройден

Код:

Идея решение: Расстояние между центрами окружностей [latex]({a}_{1};{b}_{1})[/latex] и [latex]({a}_{2};{b}_{2})[/latex] должно быть меньше, чем модуль разности их радиусов [latex]\left|{r}_{1}-{r}_{2}\right|[/latex]. Это условие необходимо и достаточно для того, чтобы одна из окружностей была вложена в другую.

Ю1.5

Задача: в такси одновременно сели три пассажира. Когда вышел первый пассажир, на счетчике было [latex]p_{1}[/latex] рублей; когда вышел второй — [latex]p_{2}[/latex] рублей. Сколько должен был заплатить каждый пассажир, если по окончании поездки счетчик показал [latex]p_{3}[/latex] рублей? Плата за посадку составляет [latex]p_{0}[/latex] рублей.

Ввод Вывод
 [latex]p_{0}[/latex]  [latex]p_{1}[/latex]  [latex]p_{2}[/latex]  [latex]p_{3}[/latex] [latex]op_{1}[/latex]  [latex]op_{2}[/latex] [latex]op_{3}[/latex] Комментарий
 0  0  0  0  0.00  0.00  0.00  Пройден
 6  1  2  3  2.33  2.83  3.83  Пройден
 7  2 5  16  3.00  4.50  15.50  Пройден
 1  1  1  1  0,67  0,67  0,67  Пройден
 150  1138  2590  5788  429.33  1155.33  4353.33  Пройден
 3  0  0  6  1.00  1.00  7.00  Пройден

[latex]p_{0}[/latex],  [latex]p_{1}[/latex],  [latex]p_{2}[/latex],  [latex]p_{3}[/latex] — целые числа, хоть и определены как double, всё равно это целые числа. У таксиста просто такой счетчик.

Идея решение: Первый участок проехали трое и расходы делятся на троих ([latex]\frac { { p }_{ 1 } }{ 3 }[/latex]). Второй участок – двое, значит за него двое платят поровну ([latex]\frac{{p}_{2}-{p}_{1}}{2}[/latex]). Последний участок проехал один, ему за него и платить ([latex]{p}_{3}-{p}_{2}[/latex]). Оплатой за поездку для каждого является сумма стоимости каждого пути до его остановки.