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:

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