Розбір Вадима Волошина: Серед усіх координат потрібно знайти максимальний X, максимальний Y, мінімальний X, мінімальний Y.
Потім по формулі S = (maxX-minX)·(maxY-minY) обчислити площу.
Але необхідно обійти пастку пов'язану з типом. Щоб задача пройшла на 100% потрібно щоб змінні для координат та результату були типу Int64.
Поки що лише ідея: задача може бути розв'язана методами динамічного програмування.
Поки що лише ідеї: Задача розв'язується на основі так званої основної теореми арифметики про єдиність подання довільного натурального числа у розкладі на прості множники. Зробити це можна:
1-й спосіб: з використанням методів динамічного програмування;2-й спосіб: рекурсивним пошуком по двійковому дереву.
Поки що лише ідея: запустимо алгортм Флойда - причому двічі.
Після зчитування заданого числа, утворимо нове число без першої цифри. Оскільки за умовою наше число складається як мінімум з 2-х розрядів ми маємо право виконати подібну операцію. Приймемо це нове число за максимальне.
Далі у циклі починаючи з 2-ї цифри ліворуч і до останньої правої цифри будемо по черзі викидувати з заданого числа чергову цифру і порівнювати отримане таким чином число з максимальним. Якщо на якомусь етапі утворене число більше за максимальне, то приймаємо його за максимальне.
Складність алгоритму становить O(N), де N - кількість цифр у числі.
При реалізації описаного алгоритму зручніше всього працювати не з числом і його цифрами, а операціями для роботи з рядками, враховуючи той факт, що множина цифр у пам'яті комп'ютера є лексикографічно упорядкованою.
Задачу можна розв'язувати різними способами. Перший спосіб - це зчитати усі елементи масиву, їх відсортувати і порахувати кількість унікальних елементів утвореного масиву. Складність такого алгоритму становить 2·O(N)+O(N·logN), де O(N·logN) йде на виконання швидкого сортування, а 2·O(N) - безпосередньо на зчитування даних та підрахунок.
Проте існує більш швидкий спосіб розв'язання цієї задачі, складність якого становить O(N). Використовуючи операції роботи з множинами, можна порахувати кількість унікальних елементів відразу ж на етапі зчитування даних.
Дана задача є яскравою демонстрацією відомих слів Ніклуса Вірта: "Програма = алгоритм + структура даних", які стали назвою його всесвітньо відомого підручника з програмування і який рекомендується прочитати кожному, хто мріє стати справжнім програмістом.
Запишемо члени заданої послідовності у табличку, яка буде містити номер члена послідовності, його десяткове значення та подання у двійковій системі числення:
| N члена | Значення | Двійкове подання |
| 1 | 3 | 11 |
| 2 | 5 | 101 |
| 3 | 6 | 110 |
| 4 | 9 | 1001 |
| 5 | 10 | 1010 |
| 6 | 12 | 1100 |
| 7 | 17 | 10001 |
| 8 | 18 | 10010 |
| 9 | 20 | 10100 |
| 10 | 24 | 11000 |
| 11 | 33 | 100001 |
Зрозуміло, що повний перебор усіх десяткових чисел підряд та їх переведення у двійкову систему числення не є ефективним, тому опишемо алгоритм, який дещо схожий на алгоритм лексикографічної генерації перестановок і який дає можливість генерувати потрібні числа одне за одним.
Спочатку лівий доданок рівний 2 (21), а правий - 1 (20).
Якщо другий (правий) доданок рівно у 2 рази менший за перший, то перший (лівий) доданок збільшуємо вдвічі, а правий встановлюємо рівним 1 (20), у противному випадку удвічі збільшуємо правий доданок. На кожному кроці лічильник кількості кроків виконання алгоритму буде рівним номеру елемента шуканої послідовності.
Складність описаного алгоритму становить O(N).
Нижче наведено вигляд описаного алгоритму на шкільній алгоритмічній мові. У програмній реалізації алгоритму слід врахувати, що відповідь поміщається у 64-бітний беззнаковий цілочисельний тип, що дозволяє обійтись без довгої арифметики.
...x :=1;
L := 2; R := 1;
поки x < n
пц
якщо 2*R = L
то
R := 1;
L := 2*L;
інакше R := 2*R;
x := x+1;
кц
answ := L+R;
...
Поки що лише ідея: Запустимо хвилю, причому двічі: перший раз будемо шукати від старту усі мішки з золотом, а потім від усіх мішків - вихід. Серед знайдених значень найменше і буде відповіддю до задачі.
Немає коментарів:
Дописати коментар