Задачі Асорті

Задача А
Після екзамену n магістрів зайшли до ресторану відзначити цю непересічну подію. Директор ресторану запропону­вав їм і надалі відвідувати саме цей ресторан цього дня щороку, причому кожного разу сідати за той самий КРУГЛИЙ стіл іншим способом. Директор пообіцяв, що, після того як усі способи посад­ки за стіл будуть вичерпані, їх годуватимуть у ресторані безкош­товно. Коли настане цей день?

Формат входных данных

Натуральне число n≤1000

Формат результата

Рядок з цілим числом, яке містить точну відповідь.

Примеры

Входные данные	Результат работы
3	6

Розв’язання.

Необхідно обчислити кількість способів сісти за круглий стіл, тобто N! (факторіал). Особливістю задачі є умова накладена на N, яка означає потребу у використанні довгої арифметики. Зокрема в програмі використовується алгоритм множення довгого числа на коротке. Опис алгоритму можна подивитись на сайті.

Під час використання алгоритму з вказаного сайту потрібно видозмінити умову в циклі та уточнення найстаршого розряду в числі, яке є результатом добутку.

Для прискорення обчислень можна використовувати основу 10000, але потрібно написати функцію, яка правильно буде доповнювати «0» розряди, які менші за 10000.

Задача В

Написати програму для знаходження кількості N-розрядних чисел, що володіють наступними властивостями: - складаються лише з цифр 1, 2 та 3; - не містять підряд двох однакових цифр 1 та 3; - містять цифру 2 або групу з цифр 2 лише тоді, коли в записі числа зліва знаходиться цифра 1, а справа – цифра 3. Наприклад, при N=4 це будуть числа: 1313, 3131, 1231, 1223, 3123.

Формат входных данных

Єдиний рядок вхідного файлу містить натуральне число N (1≤N≤500).

Формат результата

Єдиний рядок вихідного файлу повинен містити одне натуральне число – відповідь.

Примеры

Входные данные	Результат работы
4	5

Розв’язання.

Задача розв’язується по аналогії з задачею на послідовність з 0 та 1, які не повторюються (та різні варіації цієї задачі) через динамічне програмування. Хороший опис методу можна знайти на сайті.

особливістю задачі є великі вхідні дані, які вимагають використання довгої арифметики, зокрема, додавання довгих чисел. Для прискорення обчислень варто використати основу числення 10000 та правильно записати функцію виведення розрядів, які менші 10000.

Задача С

Нехай n - довільне натуральне число, а послідовність i1, i2, ... , in містить усі натуральні числа від 1 до n включно. Порушенням порядку у такій послідовності називають систему таких двох нерівностей, що справджуються: j менше k та ij більше ik. Якщо послідовність зростає, то кількість порушень порядку дорівнює 0. Якщо послідовність спадає, то така кількість дорівнює n(n - 1)/2. В усіх інших випадках ця кількість розташована між вказаними величинами. Завдання Встановіть парність кількості порушень порядку послідовності.

Формат входных данных

У першому рядку вхідного файлу вказано кількість послідовностей m. Кожний з наступних m рядків містить натуральне число n і послідовність різних натуральних чисел від 1 до n включно: i1, i2, ... , in при 2 ≤ т ≤ 100, 2 ≤ n ≤ 1 048 576. У 50 % тестів n ≤ 4096.

Формат результата

Єдиний рядок вихідного файлу має містити число в шістнадцятковій системі числення, яке відповідає двійковому числу яке утворене з m символів - нулів або одиниць - без пропусків: k-й символ рядка - це залишок від ділення на 2 кількості порушень порядку k-ї послідовності, заданої (k + 1)-м рядком вхідного файлу.

Примеры

Входные данные	Результат работы
5 3 1 2 3 3 2 3 1 3 1 3 2 4 2 3 4 1 4 3 4 1 2	6

Розв’язання.

Задача зводиться до розкладання перестановки чисел від 1 до N на цикли та обчислення параметру цих циклів:

парність чи непарність. Добуток цих парметрів визначає парність всієї перестановки.

Формулу та пояснення можна знайти в Інтернеті в документі Егор Ясинский Перестановки: все что вы хотели знать, но боялись спросить.

Ще одна особливість задачі – переведення з 2ої в 16-ву систему числення: про це можна почитати на сайті:

ru.wikihow.com/переводить-из-двоичной-системы-в-шестнадцатеричную

Задача D

Відсортуйте N заданих чисел у неспадаючому порядку.

Формат входных данных

Задано число N (1 ≤ N ≤ 100000), а потім в одному чи декількох рядках N цілих чисел з діапазону від -100 до 100.

Формат результата

Виведіть у стовпчик N чисел у неспадаючому порядку.

Примеры

Входные данные	Результат работы
5 3 1 2 4 2	1 2 2 3 4

Розв’язання.

Задача зводиться до сортування масиву буд-яким алгоритмом сортування, наприклад, швидким сортуванням

Задача Е

За заданим числом N виведіть усі перестановки чисел від 1 до N у лексикографічному порядку.

Формат входных данных

Задано одне число N (0 менше N менше 10).

Формат результата

Необхідно вивести усі перестановки чисел від 1 до N у лексикографічному порядку. Перестановки виводяться по одній у рядку, числа у перестановці виводяться без пропусків.

Примеры

Входные данные	Результат работы
3	123 132 213 231 312 321

Розв’язання.

Необхідно створити функціюгенератор перестановок. Інформацію про її створення можна знайти в документі

http://shujkova.ru/sites/default/files/lec6.pdf

Задача F

Під час досліджень, присвячених появі життя на планеті Олімпія, вченими було зроблено декілька сенсаційних відкриттів: 1. Усі живі організми планети походять від однієї бактерії Bitozoria Programulis. 2. Еволюція проходила крок за кроком (за припущенням вчених – під час змін клімату на планеті). 3. На кожному кроці еволюції з кожного виду утворювалися рівно два підвиди, а попередній вид зникав. 4. Якщо вважати появу бактерії Bitozoria Programulis першим кроком еволюції, то нині існуючі живі організми знаходяться на N-му кроці. Щоб не вигадувати назви під час досліджень, вчені пронумерували всі види організмів, що будь-коли існували на планеті. Для цього вони намалювали дерево еволюції із коренем Bitozoria Programulis, яка отримала номер 1. Далі нумерували види кожного кроку еволюції зліва направо. Таким чином безпосередні підвиди Bitozoria Programulis отримали номери 2 та 3. Наступними були занумеровані види третього кроку еволюції – підвиди виду 2 отримали номери 4 та 5, а виду 3 – номери 6 та 7, і т.д. Завдання Напишіть програму EVO, яка за номерами двох видів обчислить номер виду їх найближчого спільного предка у дереві еволюції.

Формат входных данных

Перший рядок вхідного файлу EVO.DAT містить ціле число N (1≤N≤100) – кількість етапів еволюції, що відбулися на планеті Олімпія до теперішнього часу. Другий та третій рядки файлу містять по одному натуральному числу, що представляють номери видів, для яких потрібно знайти номер їх найближчого спільного предка.

Формат результата

Єдиний рядок вихідного файлу EVO.SOL має містити натуральне число – номер найближчого предка для двох видів.

Примеры

Входные данные	Результат работы
4 15 12	3
18 233016 233008	14563

Розв’язання.

Умову цієї задачі також можна знайти на E-Olimp: https://www.e-olymp.com/ru/problems/223

Особливість цієї задачі в тому, що, не зважаючи на назву, тут не потрібно використовувати алгоритм пошуку спільного предка, бо не задано граф явно. Варто звернути увагу, що номери вершин пов’язані з степенем числа 2 та перебрати можливі варіанти.

Алгоритм:

якщо А та В однакові і дорівнюють 1, то вивести 0,  return

якщо А та В однакові і не дорівнюють 1, то вивести А (чи В)  ,  return //так зроблені тести

якщо А!=В то

                якщо А/2==В/2, то іиісти, наприклад, А/2 ,  return

                обчислити, що є більшим та меншим з А та В: ma, mі

                поки ma>mі   зменшувати, тобто ma /= mі

                якщо ma== mі, то вивести відповідь ma ,  return

                інакше

                               якщо mі!=1 то зменшити mі /2

                               поки(ma!= mі)

зменшити ma /2

зменшити mі /2

вивести ma

 Увага: якщо відповідь знайдена , тоді подільших обчислень непотрібно робити і програма зупиняється.

Особливістю цієї задачі є використання довгої арифметики, в якій потрібно реалізувати операції <, ==, !=, > та ділення довгого на коротке (ціла частина від ділення). Також потрібно написати функцію, яка прочитає дані як текстові та конвертує в в вектор (представлення довгого числа, наприклад. з основою числення 10000). Про довгу арифметику можна подивитись на сайті http://cppalgo.blogspot.com/2010/05/blog-post.html

Задача G

Турбаза мала для ночівлі N місць, з’єднаних стежками. Туристів можна вести в одну сторону. Довжина стежки – одноденний перехід. Пройти і перевірити всі M-денні маршрути, які починаються на базі K.

Формат входных данных

В першому рядку задано N,M,K. В наступних N рядках матриця суміжності.

Формат результата

Одне число, яке визначає кількість маршрутів.

Примеры

Входные данные	Результат работы
6 3 1 0 1 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0	7

Розв’язання.

Задача з теми графи: піднесення матриці суміжності до степеня M та обчислення суми в рядку К.

Прочитати про алгоритм можна на сайті: http://e-maxx.ru/algo/fixed_length_paths

Задача H

Зада́ча комівояже́ра (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP; нім. Problem des Handlungsreisenden) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів.

Формат входных данных

Перший рядок N. Граф задається матрицею суміжності.

Формат результата

Довжина шляху.

Примеры

Входные данные	Результат работы в файле output.txt
3 0 1 2 1 0 3 2 3 0	6

Розв’язання.

Класична задача на пошук гамільтонового циклу. Невеликі вхідні дані дозволяють застосувати метод динамічного програмування по масці (використовується робота з бітами). Прочитати та ознайомитись з методом можна на сайті: https://brestprog.neocities.org/lections/bitmasks.html

Задача І

Король країни Аріїв завоював N міст на території сусідніх держав. Тепер йому необхідно створити систему збирання мита з завойованих територій. Він хоче збудувати таку систему шляхів між цими містами, щоб до будь-якого міста можна було дістатися (можливо, через інші міста) зі столиці, але у воєнному стані на транспорт виділяється дуже незначна частина фінансів, тому сумарна вартість побудованих шляхів сполучення між містами має бути мінімальною.

Формат входных данных

Перший рядок вхідного файлу містить натуральне число N (1≤N≤100) – кількість міст у країні, а також цілі числа X та Y – координати столиці. Наступні N рядків містять через проміжок координати Xi , Yi завойованих міст. Значення координат по модулю менші 50000.

Формат результата

Єдиний рядок має містити дійсне число з трьома знаками після коми – сумарну вартість побудованих доріг. Вважайте, що вартість одиниці довжини дороги дорівнює одній умовній одиниці.

Примеры

Входные данные	Результат работы в файле output.txt
6  0 0  1  1 -1  1  0  2  1 -1 -1 -1  0 -2	8.485

Розв’язання.

Задача схожа на задачу https://acmp.ru/index.asp?main=task&id_task=142 (мінімальний каркас). Особливість задачі в тому, що тут не потрібно будувати остовне дерево алгоритмами Пріма або Краскала. Використовується наступний алгоритм:

1) на основі координат міст обчислити попарно відстані між ними та створити список ребер.

2) вибрати зі списку ребер найкоротше

3) поки не всі вершини включені до дерева:

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

4) обчислити та вивести суму довжин вибраних ребер.

Прочитати та ознайомитись з методом можна на сайті: https://www.youtube.com/watch?v=CXOvOg_kbTM

Задача J

Нехай є n міст, пронумерованих числами від 1 до n. Для кожної пари міст із номерами і, j у таблиці a[і][j] зберігається ціле число - ціна прямого авіаквитка з міста i у місто j. Вважається, що рейси існують між будь-якими містами, a[і,і] = 0 при всіх і, a[і][j] може відрізнятися від a[j,і]. Найменшою вартістю проїзду з і в j вважається мінімально можлива сума цін квитків для маршрутів (у тому числі з пересадженнями), що ведуть з і в j. (Вона не перевершує a[і][j], але може бути менше).

Формат входных данных

N - кількість міст, a - старт, b - фініш. Матриця суміжності.

Формат результата

Найкоротша відстань.

Примеры

Входные данные	Результат работы
3 1 2 0 37 56 37 0 99 56 99 0	37

Розв’язання.

Необхідно знайти найкоротші відстані у графі, при цьому передбачається що від’ємних циклів не має. Алгоритм Флойда.  http://urban-sanjoo.narod.ru/floyd.html

Зададча K

У школі вирішили організувати змагання спортивного орієнтування. В парку, де мало відбутися змагання, відмітили N контрольних пунктів, які потрібно пройти. Організатори журі вирішили обгородити територію. Але з метою економії коштів потрібно визначити спосіб побудови огорожі мінімальної довжини і площі, яка б охопила всі контрольні точки. Необхідно за заданими координатами точок обчислити площу території і довжину огорожі.

Формат входных данных

Вхідні дані: В першому рядку вхідного файлу записано N - кількість контрольних точок, в наступних рядках координати - (хi, уi), і=1,2,...,N. Всі числа цілі та знаходяться в межах від -1000 до 1000.

Формат результата

Вихідні дані: Містить два рядки з дійсними числами з точністю два знаки після коми, які відповідають площі території і довжині огорожі.

Примеры

Входные данные	Результат работы
3 0 0 0 3 4 0	6.00 12.00

Розв’язання.

Задача зводиться до наступного алгоритму:

1) знайти праву нижню точку для побудови оболонки багатокутника,

2) обчислити опуклу оболонку, наприклад алгоритмом Джарвіса,

3) обчислити периметр багатокутника,

4) обчислити площу багатокутника.

Для виконання обчислень слід скористатись формулами векторного добутку, обчислення відстані між точками на площині (заданими координатами), периметр та площу опуклого багатокутника (на основі добутку векторів).

Прочитати про формули та їх реалізацію можна в документі:

http://informatics.mccme.ru/file.php/22/part3.pdf

Задача L

Просте

За введеним натуральним числом N вивести кількість простих чисел з діапазону [1;N].

Формат входных данных

Натуральне число N (1≤N≤10000000)

Формат результата

Рядок з числом, яке відповідає кількості простих чисел.

Примеры

Входные данные	Результат работы
10	4

Розв’язання.

Задача зводиться до решета Ератосфена: http://e-maxx.ru/algo/eratosthenes_sieve