Re: Дуже потрібна допомога по задачі,вже четвертий день граюсь з нею
А такі дані:
6 1;2;4;3 3;2;4;5 3;4;4;7 1;6;4;7 3;4;6;5 5;4;8;5
Чотири.
Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Дуже потрібна допомога по задачі,вже четвертий день граюсь з нею
Для відправлення відповіді ви повинні увійти або зареєструватися
А такі дані:
6 1;2;4;3 3;2;4;5 3;4;4;7 1;6;4;7 3;4;6;5 5;4;8;5
Чотири.
yooll написав:А такі дані:
6 1;2;4;3 3;2;4;5 3;4;4;7 1;6;4;7 3;4;6;5 5;4;8;5
Чотири.
А має бути три.
Тут є три точки, в кожній з яких перетинається по 2 листи. Якщо в них забити, то всі листи охопляться.
Bartash написав:yooll написав:А такі дані:
6 1;2;4;3 3;2;4;5 3;4;4;7 1;6;4;7 3;4;6;5 5;4;8;5
Чотири.
А має бути три.
Тут є три точки, в кожній з яких перетинається по 2 листи. Якщо в них забити, то всі листи охопляться.
Точно, маєте рацію. Прогалина у підході.
Хоча за інших умов це було нормально (справа):
Є нова ідея, прочитавши уважно умову, можна зробити такі висновки:
1. Беремо черговий прямокутник, і знаходимо координати його середини. (Оскільки N менше 21, питання про швидкодію і обробку довгих чисел знімається)
2. Беремо слід. прямокутник, і находимо його середину.
3. Порівнюємо координати середин, якщо збігаються - +1 цвях, а якщо ні, то +2 цвяха. Профіт, не?)
Тут є незначна двозначність: "в середині" може означати як точку, так і область. Втім, речення в дужках все розставляє по місцях:
(цвяхи, що проходять через границі аркушу, не прибивають його)
Тобто будь-яка позиція, крім границі аркушу, знаходиться всередині, мова йде не про геометричний центр. Отже, ваш розв'язок не працює.
"Аркуш вважається прибитим, якщо в середині нього проходить хоча б один цвях"
Можливо середина - центр прямокутника?
Тоді як ви поясните фразу в дужках? Що вона уточнює?
Ось. Тестовий файл через пробіли, циклів поки що не шукає. Алгоритм - той, що я вище писав, розтягнутий на коментарі.
Для відправлення відповіді ви повинні увійти або зареєструватися