1

Тема: Задачі типу шахової дошки

Всім доброго дня! Так випало що я їду на обласну олімпіаду з програмування... Вигравши районну, але не зробивши одне завдання... Так вийшло що таких завдань дуже багато на обласній олімпіаді... Допоможіть з алгоритмом... Реалізацію по алгоритму виконаю сам...
Завдання в прикріпленому фото

Post's attachments

1.png 5.79 mb, 195 downloads since 2014-12-23 

Найбільш роздута проблема, зрештою стає вашою найтупішою помилкою!!

2

Re: Задачі типу шахової дошки

Завдання досить складне, я сумніваюсь, що тут викладуть алгоритм.

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

МАКЕ ЦКЯАІИЕ БЯЕАТ АБАІИ
Подякували: Program_man1

3

Re: Задачі типу шахової дошки

Перша думка була - це нереально. Мапа 700х700, прорахунок маневрів проти вікінгів - там 1 секунда обмеження, точно не вийде.
Але уважніше перечитав умову - нас не просять маневрувати. Нас просять заздалегідь скласти маршрут і виходити з того, що вікінги знатимуть цей маршрут. А це вже простіше. Перед першим ходом вікінги бачать деякі клітинки. Позначимо ці клітинки нуликами. Після всіх варіантів першого ходу вікінги бачитимуть ще більше клітинок - позначимо їх одиницями і так далі. Ну а тепер просто проходимо лабіринт з урахуванням того, що n-й хід не може потрапляти на клітинку, позначену n або менше, бо вікінги туди встигли раніше за нас.

Подякували: quez, Joker, Program_man3

4

Re: Задачі типу шахової дошки

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

МАКЕ ЦКЯАІИЕ БЯЕАТ АБАІИ

5

Re: Задачі типу шахової дошки

Насправді фігурує - вона позбавляє необхідності обчислювати парність ходів, це взагалі жах був би :)

Подякували: quez, Joker2

6

Re: Задачі типу шахової дошки

koala написав:

Насправді фігурує - вона позбавляє необхідності обчислювати парність ходів, це взагалі жах був би :)

Хм, таки да.

МАКЕ ЦКЯАІИЕ БЯЕАТ АБАІИ

7

Re: Задачі типу шахової дошки

Перша думка була - це нереально. Мапа 700х700, прорахунок маневрів проти вікінгів - там 1 секунда обмеження, точно не вийде.
Але уважніше перечитав умову - нас не просять маневрувати. Нас просять заздалегідь скласти маршрут і виходити з того, що вікінги знатимуть цей маршрут. А це вже простіше. Перед першим ходом вікінги бачать деякі клітинки. Позначимо ці клітинки нуликами. Після всіх варіантів першого ходу вікінги бачитимуть ще більше клітинок - позначимо їх одиницями і так далі. Ну а тепер просто проходимо лабіринт з урахуванням того, що n-й хід не може потрапляти на клітинку, позначену n або менше, бо вікінги туди встигли раніше за нас.

Мені навіть страшно пробувати реалізувати ваш алгоритм програмно, а жаль :(

8

Re: Задачі типу шахової дошки

quez написав:

Завдання досить складне, я сумніваюсь, що тут викладуть алгоритм.

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

Таку задачу просто неможливо було написати на олімпіаді яка длилась 4 години... Просто навіщо таке дали незрозуміло

Найбільш роздута проблема, зрештою стає вашою найтупішою помилкою!!

9

Re: Задачі типу шахової дошки

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

10

Re: Задачі типу шахової дошки

Program_man написав:
quez написав:

Завдання досить складне, я сумніваюсь, що тут викладуть алгоритм.

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

Таку задачу просто неможливо було написати на олімпіаді яка длилась 4 години... Просто навіщо таке дали незрозуміло

Таку задачу дуже складно вирішити правильно за чотири години. Але написати рішення, яке працює для 90% вхідних умов, відносно просто.

Але koala якось побачив, що тут не треба нічого подібного, як він це робить, я не знаю.

МАКЕ ЦКЯАІИЕ БЯЕАТ АБАІИ

11 Востаннє редагувалося Joker (24.12.2014 23:29:44)

Re: Задачі типу шахової дошки

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

Я от вчу всі ті алгоритми. Досить часто буває, що прочитавши задачу я знаю який алгоритм допоможе мені її розв'язати. Тобто в загальному я знаю як рішити задачу. Але коли діло доходить до якихось дрібничок, там я роблю повно помилок. Для прикладу сьогодні - http://codeforces.ru/contest/495/problem/A

Я зразу поняв, що тре порахувати к-сть цифр на які може змінитися індикатор (0 - 0,2; 3 - 3,8,9  ...) Далі тре порахувати к-сть всіх можливих чисел. Получилося щось страшне, але пів години сів знову за неї і от получився розв'язок у два рядки коду. :) :(

P.s. Вибачте за оффтоп

12

Re: Задачі типу шахової дошки

Joker написав:

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

Я от вчу всі ті алгоритми. Досить часто буває, що прочитавши задачу я знаю який алгоритм допоможе мені її розв'язати. Тобто в загальному я знаю як рішити задачу. Але коли діло доходить до якихось дрібничок, там я роблю повно помилок. Для прикладу сьогодні - http://codeforces.ru/contest/495/problem/A

Я зразу поняв, що тре порахувати к-сть цифр на які може змінитися індикатор (0 - 0,2; 3 - 3,8,9  ...) Далі тре порахувати к-сть всіх можливих чисел. Получилося щось страшне, але пів години сів знову за неї і от получився розв'язок у два рядки коду. :) :(

P.s. Вибачте за оффтоп

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

МАКЕ ЦКЯАІИЕ БЯЕАТ АБАІИ

13 Востаннє редагувалося Joker (24.12.2014 23:53:51)

Re: Задачі типу шахової дошки

З нуля не може вийти два, тільки нуль і вісім.

Вибачте, я мав на увазі що з 0 можна утворити 0 і 8, але це дві цифри. Я беру кількість таких цифр які можна утворити.

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

Ну але в мою голову не може так скоро зайти, що достатнь перемножити можливі варіанти для першої цифри на всі варіанти для другої.

14

Re: Задачі типу шахової дошки

То все дурня. Можна бути непоганим програмістом і не вигравати на олімпіадах.

15

Re: Задачі типу шахової дошки

То все дурня. Можна бути непоганим програмістом і не вигравати на олімпіадах.

Але вона мені не зашкодить, хоч логічно думати навчить.