21

Re: Олімпіадна задачка

З'явилася ще одна така задача . Тут я навіть не знаю за що взятися.
Кому цікаво. Я її рішив, бо я був на тій олімпіаді, але не пам'ятаю як :) і не пам'ятаю чи повністю.
Хто допоможе?
https://cloclo18.cloud.сайт-злодій/weblink/thumb/xw1/da59e687b709/%D0%9A%D0%BE%D0%BD%D0%BA%D1%83%D1%80%D1%81%20%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D1%82%D1%96%D0%B2.tif?x-email=havdyak_misha1998%40mail.ru

22

Re: Олімпіадна задачка

Я окрім перебору нічого придумати не можу.
Я не тру програміст.

23

Re: Олімпіадна задачка

Я не тру програміст.

Я тоже. Та і на олімпадіх їх взагалі нема.

перебору нічого придумати не можу.

Яка ваша умова перебору? За якими параметрами?

24 Востаннє редагувалося quez (08.09.2014 18:52:18)

Re: Олімпіадна задачка

Singularity написав:

Я окрім перебору нічого придумати не можу.
Я не тру програміст.

При тих обмеженнях цілком можна обійтись і перебором: всього Σn² = 385 перевірок в найгіршому випадку - 1 для квадрата 10х10, 4 для квадратів 9х9 і т. д.

Можна піти знизу і почати з пошуку квадратів 2х2 з найменшою кількістю одиниць. Якщо в такому квадраті одиниць менше ніж К, то з кожного такого квадрата і клітинок, які його оточують, утворити квадрати 3х3, далі взяти до уваги лише ті, в яких одиниць найменше, повторити (для 4х4, 5х5 і до просвітлення). Такий алгоритм буде досить швидко знаходити шукане число, але от чомусь я не впевнений, що не може бути екзотичного випадку, коли найбільший квадрат будується не на основі квадрата з найменшою кількістю одиниць з попереднього кроку.

Подякували: Joker1

25

Re: Олімпіадна задачка

А тут і не може бути нічого, крім перебору, питання тільки в його оптимізації.
quez правильно сказав:
001111
001111
111111
111101
111000
111101
Найбільший квадрат 2х2 - в лівому верхньому кутку. Відповідь - в правому нижньому.

Я з умови тільки одного не зрозумів: куди саме Зеник переносить мішки? Якщо всередині гаража, то в
111
001
101
найбільший квадрат, що його можна звільнити - 1х1, і це теж треба враховувати.

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

26

Re: Олімпіадна задачка

Я з умови тільки одного не зрозумів: куди саме Зеник переносить мішки?

Ну я дав вам всю інформацію про задачу що мав.

Дякую за відповіді, трошка зрозумів