e-olimp 5074. Степени вершин по спискам ребер

Задача:

Неориентированный граф задан списком ребер.

Найдите степени всех вершин графа.

Технические условия:

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

Входной файл содержит числа [latex]n[/latex]  [latex] (1 \leq n \leq 100) [/latex] — число вершин в графе и

[latex]m[/latex]  [latex](1 \leq m \leq \frac{n(n-1)}{2})[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

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

Выведите в выходной файл [latex]n[/latex] чисел — степени вершин графа.

Результат на C++

Результат на Java

Код на C++:

Код на Java:

 

Описание:

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

AA1

Задача:

В заданной строке заменить подряд идущие пробелы на один пробел.

Примечание:

Будем называть строку правильной, если она не содержит подряд идущих пробелов.

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

 Исходная строка  Оптимистичное ожидание Комментарий
Gagarin               became an                     international celebrity, and was                                              awarded many                     medals and titles, including                       Hero of the                        Soviet Union. Gagarin became an international celebrity, and was awarded many medals and titles, including Hero of the Soviet Union.  Пройден.
 Leonardo                             was, and                             is,                                         renowned                               primarily                         as a                             painter. Leonardo was, and is, renowned primarily as a painter.  Пройден.

Код на С++

Код на Java

 

Пояснение:

Вариант удаления пробелов с помощью [latex]erase()[/latex] является самым очевидным. Но у него больше недостатков, чем достоинств. Данный метод имеет линейную асимптотику, в худшем случае он выполнил бы [latex]n — 1[/latex] ( в дальнейшем [latex]»n»[/latex] — это длина строки ) сдвиг в индексах строки.

Другой способ — создание новой строки и добавление туда только нужных нам символов. Единственная проблема — новая строка, т. е. в худшем случае у нас появится строка равная данной или же на один символ меньше (если была добавлена проверка на правильность строки).

Второй способ мне нравится больше (просто потому, что он работает), но выделять новую строку очень не хочется. Оказалось, что можно обойтись и без неё. В качестве новой я использовал исходную. Для этого ввел два «указателя» на позиции элементов. Первый пробегает всю строку в цикле, второй же указывает на элемент, этой строки, в который будет положено новое значение. Таким образом, полученная последовательность символов (от нулевой, до [latex]j[/latex] — той не включительно) будет правильной строкой. Осталось удалить элементы на полуинтервале от [latex]j[/latex] до [latex]n[/latex].

 

e-olimp 6130. Дек неограниченного размера.

Задача:

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

push_front

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

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

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

pop_back

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

front

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

back

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

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

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

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

Результат на C++

Результат на Java

Код на C++:

Код на Java:

 

Пояснение:

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

Трудности возникли тогда, когда количество элементов в деке сравнялось с вместимостью базового массива. В таком случае необходимо величить вместимость дека. Сделать это можно следующим образом. Нужно создать новый массив, перенести в него элементы старого массива, а после присвоить указателю на старый массив указатель на новый. После увеличения вместимости дека возник вопрос: Куда указывают указатели? Мы их не меняли, а значит они имеют прежние значения, что уже не актуально. Так как первый элемент в новом массиве находится на нулевой позиции, меняем значение указателя на первый элемент (front_) на нуль. Указатель на последний элемент (back_) теперь должен иметь значение равное, уменьшенному на единицу, количеству элементов. Осталось только изменить значение вместимости (capacity), у меня вместимость увеличивается вдвое.

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

 

 

 

e-olimp 4004. Есть ли цикл?

Задача:

  Дан ориентированный граф. Требуется определить, есть ли в нём цикл.

Технические условия:

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

В первой строке вводится натуральное число [latex]N ( N \leq 50)[/latex] — количество вершин. Далее в [latex]N[/latex] строках следуют по [latex]N[/latex] чисел, каждое из которых — «0» или «1«. [latex]j [/latex] -е число в [latex]i[/latex] -й строке равно «1» тогда и только тогда, когда существует ребро, идущее из [latex]i[/latex] -й вершины в [latex]j[/latex]-ю. Гарантируется, что на диагонали матрицы будут стоять нули.

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

Выведите «0«, если в заданном графе цикла нет, и «1«, если он есть.

Результат на С++

Результат на Java

Код на С++:

Код на Java:

 

Пояснение:

Циклом в графе называется цепь, в которой первая и последняя вершина совпадает. Значит, если проходя по вершинам графа в лексикографическом порядке, в какой — то момент я попаду в вершину в которую вошел, но еще не вышел, то это будет означать, что я нашёл цикл.

Если б мне по условию давался связный ориентированный граф, то достаточно было бы запустить поиск (поиск в глубину) из произвольной вершины и, по идее, мы бы обошли весь граф. Так как о связности графа ничего сказано не было, пришлось запускать поиск из каждой вершины.

A159

Задача:

Даны натуральное число n, действительные числа [latex]a_{1}, …, a_{n}[/latex] [latex]\left( n\geq 3\right)[/latex] .

Получить [latex]b_{1}, …, b_{n-2}[/latex], где [latex]b_{i} = a_{i + 1} + a_{i + 2}[/latex], [latex]i=1, 2 , … , n-2[/latex].

Таблица:

[latex]a_{1}, …, a_{n}[/latex] [latex]b_{1}, …, b_{n-2}[/latex] Комментарий
1 2 3 4 5 6 7 5 7 9 11 13 Пройден
1.235 2.457 2.543 4.457  4.543 6.457 6.543 5 7 9 11 13 Пройден
 9 -12 17 -10 19 -8 21 5 7 9 11 13 Пройден
-21 26 -21 28 -19 30 -17 22 -15 24 -13 26 5 7 9 11 13 5 7 9 11 13 Пройден
21 -26 21 -28 19 -30 17 -22 15 -24 13 -26 -5 -7 -9 -11 -13 -5 -7 -9 -11 -13 Пройден

Исходный код:

Работать будет и такая версия:

Код на Java

 

 Описание:

Для выполнения условия задачи необходимо пропустить первый элемент первой последовательности и начать суммирование второго и третьего элементов (далее третьего и четвертого, четвертого и пятого и т. д.). Для этого я ввел переменную, в которой будет храниться первый элемент вводимой последовательности (более он использоваться не будет). Далее создаем цикл, в котором будем одновременно вводить значения элементов первой последовательности и выводить элементы результирующей последовательности.

Алгоритм:

  1. Объявление необходимых переменных.
  2. Отдельно ввод первого и второго элемента первой последовательности.
  3. Создание цикла для ввода данных.
    1. Печать суммы второго и третьего элемента первой последовательности (первый элемент результирующей последовательности).
    2. Обеспечение сдвига суммируемых элементов (со второго и третьего на третий и четвертый и т. д.)
  4. Окончание работы программы после завершения цикла.

Ссылка на Ideone.

 

 

 

 

 

A412г

Задача:

Даны две целочисленные квадратные матрицы порядка 6. Найти последовательность из нулей и единиц  [latex]b_{1} , … , b_{6}[/latex] такую, что [latex]b_{i} = 1[/latex], когда:

г) количество отрицательных и неотрицательных элементов [latex] i [/latex]- строки первой матрицы совпадает соответственно с количеством отрицательных и неотрицательных элементов [latex] i[/latex]-строки второй матрицы.

 

  Матрица [latex]A[/latex]

    Матрица [latex]B[/latex]

     Ожидаемый      результат

 Комментарий

   1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
                  1 1 1 1 1 1          Тест пройден
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
                    0 0 0 0 0 0          Тест пройден
 0 2 2 3 4 4
1 3 3 4 5 5
2 4 4 5 6 6
3 5 5 6 7 7
4 6 6 7 8 8
5 7 7 8 9 9
0 2 2 3 4 4
-1 3 1 4 3 5
-2 4 0 5 2 6
-3 5 -1 6 1 7
-4 6 -2 7 0 8
-5 7 -3 8 -1 9
                    1 0 0 0 0 0          Тест пройден
0 2 2 3 4 4
1 3 3 -4 5 5
2 4 -4 5 6 6
3 -5 5 6 7 -7
4 6 -6 -7 8 8
5 -7 7 -8 9 -9
0 2 2 3 4 4
-1 3 1 4 3 5
-2 4 0 5 2 6
-3 5 -1 6 1 7
-4 6 -2 7 0 8
-5 7 -3 8 -1 9
                   1 1 1 1 1 1          Тест пройден

Исходный код:

Код на Java

 

Описание:

Для решения данной задачи я решил ввести два счетчика, которые считают количество отрицательных чисел. Потом мы сравниваем счетчики каждого массива. Если в соответствующих строках данных массивов равное число отрицательных элементов, то и равное число неотрицательных.  В таком случае мы должны напечатать «1», в противном случае «0».

 Алгоритм:

  1. Создаем функцию для ввода данных.
    1. Создаем первый цикл для перебора строк.
    2. Создаем вложенный цикл для перебора каждого элемента массива и функцию ввода данных.
  2. Создаем главную функцию.
    1. Создаем цикл, перебирающий строки массивов.
    2. Создаем два счетчика.
    3. Создаем первый вложенный цикл, для перебора каждого элемента второго массива.
      • В случае обнаружения отрицательных элементов, увеличиваем счетчик.
    4. Создаем первый вложенный цикл, для перебора каждого элемента второго массива.
      • В случае обнаружения отрицательных элементов, увеличиваем счетчик.
    5. Объявляем условие вывода данных. Так как условие находится внутри главного цикла, то будет выведено по одному значению, которое характеризует каждую строку.
  3. Создаем функцию для печати результата.
    1. Один цикл для перебора каждого элемента одномерного массива.
  4. В функции «int main ()»:
    1. Вводим значения элементов первого массива.
    2. Вводим значения элементов второго массива.
    3. Применяем главную функцию к данным массивам.
    4. Печатаем результат.
    5. Окончание работы программы.

Ссылка на Ideone.

 Функция пересчета отрицательных элементов в заданной строке заданного массива.

Рабочий образец.