Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Pascal/Delphi → Задачі типу шахової дошки
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
Всім доброго дня! Так випало що я їду на обласну олімпіаду з програмування... Вигравши районну, але не зробивши одне завдання... Так вийшло що таких завдань дуже багато на обласній олімпіаді... Допоможіть з алгоритмом... Реалізацію по алгоритму виконаю сам...
Завдання в прикріпленому фото
Завдання досить складне, я сумніваюсь, що тут викладуть алгоритм.
Такі задачі вирішуються за допомогою функцій оцінки ходу. Найпримітивнішою оцінкою для свого корабля може бути відстань до скарбу, а для ворога — відстань до лінії, яка перекриває шлях вашому кораблю. Але суша змішує всі карти і я поки що не знаю, як робити оцінку з її врахуванням.
Перша думка була - це нереально. Мапа 700х700, прорахунок маневрів проти вікінгів - там 1 секунда обмеження, точно не вийде.
Але уважніше перечитав умову - нас не просять маневрувати. Нас просять заздалегідь скласти маршрут і виходити з того, що вікінги знатимуть цей маршрут. А це вже простіше. Перед першим ходом вікінги бачать деякі клітинки. Позначимо ці клітинки нуликами. Після всіх варіантів першого ходу вікінги бачитимуть ще більше клітинок - позначимо їх одиницями і так далі. Ну а тепер просто проходимо лабіринт з урахуванням того, що n-й хід не може потрапляти на клітинку, позначену n або менше, бо вікінги туди встигли раніше за нас.
Ви пройшли по тонкій кризі — ваш алгоритм працює, але варто заборонити вікінгам пропускати хід, як маневри зразу ж починають мати сенс. А можливість пропуску ходу вікінгами у вашому розв’язанні ніяк не фігурує.
Насправді фігурує - вона позбавляє необхідності обчислювати парність ходів, це взагалі жах був би
Хм, таки да.
Перша думка була - це нереально. Мапа 700х700, прорахунок маневрів проти вікінгів - там 1 секунда обмеження, точно не вийде.
Але уважніше перечитав умову - нас не просять маневрувати. Нас просять заздалегідь скласти маршрут і виходити з того, що вікінги знатимуть цей маршрут. А це вже простіше. Перед першим ходом вікінги бачать деякі клітинки. Позначимо ці клітинки нуликами. Після всіх варіантів першого ходу вікінги бачитимуть ще більше клітинок - позначимо їх одиницями і так далі. Ну а тепер просто проходимо лабіринт з урахуванням того, що n-й хід не може потрапляти на клітинку, позначену n або менше, бо вікінги туди встигли раніше за нас.
Мені навіть страшно пробувати реалізувати ваш алгоритм програмно, а жаль 
Завдання досить складне, я сумніваюсь, що тут викладуть алгоритм.
Такі задачі вирішуються за допомогою функцій оцінки ходу. Найпримітивнішою оцінкою для свого корабля може бути відстань до скарбу, а для ворога — відстань до лінії, яка перекриває шлях вашому кораблю. Але суша змішує всі карти і я поки що не знаю, як робити оцінку з її врахуванням.
Таку задачу просто неможливо було написати на олімпіаді яка длилась 4 години... Просто навіщо таке дали незрозуміло
Якщо пару місяців себе налаштовувати на подібні задачі, вчити алгоритми і т.д., то пари годин цілком достатньо. Зрештою, це просто трохи закручений хвильовий алгоритм на два боки (для власного корабля і для вікінгів).
quez написав:Завдання досить складне, я сумніваюсь, що тут викладуть алгоритм.
Такі задачі вирішуються за допомогою функцій оцінки ходу. Найпримітивнішою оцінкою для свого корабля може бути відстань до скарбу, а для ворога — відстань до лінії, яка перекриває шлях вашому кораблю. Але суша змішує всі карти і я поки що не знаю, як робити оцінку з її врахуванням.
Таку задачу просто неможливо було написати на олімпіаді яка длилась 4 години... Просто навіщо таке дали незрозуміло
Таку задачу дуже складно вирішити правильно за чотири години. Але написати рішення, яке працює для 90% вхідних умов, відносно просто.
Але koala якось побачив, що тут не треба нічого подібного, як він це робить, я не знаю.
Якщо пару місяців себе налаштовувати на подібні задачі, вчити алгоритми і т.д., то пари годин цілком достатньо. Зрештою, це просто трохи закручений хвильовий алгоритм на два боки (для власного корабля і для вікінгів).
Я от вчу всі ті алгоритми. Досить часто буває, що прочитавши задачу я знаю який алгоритм допоможе мені її розв'язати. Тобто в загальному я знаю як рішити задачу. Але коли діло доходить до якихось дрібничок, там я роблю повно помилок. Для прикладу сьогодні - https://codeforces.com/contest/495/problem/A
Я зразу поняв, що тре порахувати к-сть цифр на які може змінитися індикатор (0 - 0,2; 3 - 3,8,9 ...) Далі тре порахувати к-сть всіх можливих чисел. Получилося щось страшне, але пів години сів знову за неї і от получився розв'язок у два рядки коду. 
P.s. Вибачте за оффтоп
Якщо пару місяців себе налаштовувати на подібні задачі, вчити алгоритми і т.д., то пари годин цілком достатньо. Зрештою, це просто трохи закручений хвильовий алгоритм на два боки (для власного корабля і для вікінгів).
Я от вчу всі ті алгоритми. Досить часто буває, що прочитавши задачу я знаю який алгоритм допоможе мені її розв'язати. Тобто в загальному я знаю як рішити задачу. Але коли діло доходить до якихось дрібничок, там я роблю повно помилок. Для прикладу сьогодні - https://codeforces.com/contest/495/problem/A
Я зразу поняв, що тре порахувати к-сть цифр на які може змінитися індикатор (0 - 0,2; 3 - 3,8,9 ...) Далі тре порахувати к-сть всіх можливих чисел. Получилося щось страшне, але пів години сів знову за неї і от получився розв'язок у два рядки коду.
P.s. Вибачте за оффтоп
З нуля не може вийти два, тільки нуль і вісім.
Задача так собі, навіть вручну розв’язується майже так само швидко, як і з допомогою програми.
З нуля не може вийти два, тільки нуль і вісім.
Вибачте, я мав на увазі що з 0 можна утворити 0 і 8, але це дві цифри. Я беру кількість таких цифр які можна утворити.
Задача так собі, навіть вручну розв’язується майже так само швидко, як і з допомогою програми.
Ну але в мою голову не може так скоро зайти, що достатнь перемножити можливі варіанти для першої цифри на всі варіанти для другої.
То все дурня. Можна бути непоганим програмістом і не вигравати на олімпіадах.
То все дурня. Можна бути непоганим програмістом і не вигравати на олімпіадах.
Але вона мені не зашкодить, хоч логічно думати навчить.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
