Re: Олімпіадна задачка
З'явилася ще одна така задача . Тут я навіть не знаю за що взятися.
Кому цікаво. Я її рішив, бо я був на тій олімпіаді, але не пам'ятаю як і не пам'ятаю чи повністю.
Хто допоможе?
Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → C++ → Олімпіадна задачка
Для відправлення відповіді ви повинні увійти або зареєструватися
З'явилася ще одна така задача . Тут я навіть не знаю за що взятися.
Кому цікаво. Я її рішив, бо я був на тій олімпіаді, але не пам'ятаю як і не пам'ятаю чи повністю.
Хто допоможе?
Я окрім перебору нічого придумати не можу.
Я не тру програміст.
Я не тру програміст.
Я тоже. Та і на олімпадіх їх взагалі нема.
перебору нічого придумати не можу.
Яка ваша умова перебору? За якими параметрами?
Я окрім перебору нічого придумати не можу.
Я не тру програміст.
При тих обмеженнях цілком можна обійтись і перебором: всього Σn² = 385 перевірок в найгіршому випадку - 1 для квадрата 10х10, 4 для квадратів 9х9 і т. д.
Можна піти знизу і почати з пошуку квадратів 2х2 з найменшою кількістю одиниць. Якщо в такому квадраті одиниць менше ніж К, то з кожного такого квадрата і клітинок, які його оточують, утворити квадрати 3х3, далі взяти до уваги лише ті, в яких одиниць найменше, повторити (для 4х4, 5х5 і до просвітлення). Такий алгоритм буде досить швидко знаходити шукане число, але от чомусь я не впевнений, що не може бути екзотичного випадку, коли найбільший квадрат будується не на основі квадрата з найменшою кількістю одиниць з попереднього кроку.
А тут і не може бути нічого, крім перебору, питання тільки в його оптимізації.
quez правильно сказав:
001111
001111
111111
111101
111000
111101
Найбільший квадрат 2х2 - в лівому верхньому кутку. Відповідь - в правому нижньому.
Я з умови тільки одного не зрозумів: куди саме Зеник переносить мішки? Якщо всередині гаража, то в
111
001
101
найбільший квадрат, що його можна звільнити - 1х1, і це теж треба враховувати.
Я з умови тільки одного не зрозумів: куди саме Зеник переносить мішки?
Ну я дав вам всю інформацію про задачу що мав.
Дякую за відповіді, трошка зрозумів
Для відправлення відповіді ви повинні увійти або зареєструватися