Задача на логику
Всем привет!
Собственно, снова понадобилась помощь дружного коллектива :) На носу всеми любимой летней сессии задали задания на UVA, которые обязательно нужно решить . Сказано - сделано. Практически все задачи были сделаны (язык программирования характерный - С++ или Java), а вот одно задание - хоть убей, не пойму. Нужна помощь с алгоритмом, если кто поможет - добра и счастье тебе, друг:) . А вообще - всем того же ;) http://uva.onlinejudge.org/index.php...m&problem=3937 Сама задача. UPD: Нашел код на сишке, но не могу понять алгоритма, может кто понял и объяснит, так же был бы крайне благодарен... По сути, мне важен именно алгоритм решения, ибо написать могу и сам . https://github.com/marioyc/Online-Ju...0-%20Stars.cpp C Уважением. Добавлено через 2 часа 49 минут Ну хоть предположения:( |
Re: Задача на логику
Для скорейшего понимания написали бы суть задания на русском, а то на английском ро ссылке тяжело вникать.
|
Re: Задача на логику
"Фернандо получил компас на день рождения, и теперь его хобби - рисовать звёзды. Сначала он делает N отметок на окружности, разделяя её на N равных дуг, потом соединяет каждую точку с каждой К-той точкой, и так до тех пор, пока не вернётся к первой точке2"
"В зависимости от значения К, Фернандо может достичь\не достичь всех точек на окружности; когда это случается - звезда называется завершённой. Например, когда N=8, возможные звёзды показаны на фигуре ниже. Звёзды а и с - завершённые, б и д - напротив, нет. В зависимости от значения N, есть вероятность нарисования всеразличных звёзд, Фернандо попросил тебя написать программу, которая при заданном значении N определяет количество возможных законченных звёзд, которые он может нарисовать." "Ввод: Ввод содержит несколько тестовых вариантов. Каждый тестовый вариант содержит одну линию (строку), включающую в себя число типа integer, =диапазон для N даётся=, указывая число дуг, на которые окружность была поделена. Вывод: Для каждого тестового варианта твоя программа должна вывести одну строку (линию), содержащую одну же линию с числом типа integer (=дословно: одну линию содержащуюю один инт=), показывая количество законченных звёзд, которые могут быть нарисованы. |
Re: Задача на логику
k - это количество пропускаемых точек, при построение очередного отрезка, k = 0 .. N-1
Одним из признаков, что звезда получилась является: 1. построение звезды закончилось в той же точке где и началось 2. количество отрезков равно количеству точек на окружности Но это не достаточное условие, нужно как то исключить попадание в одни и те же точки, надо подумать как. И кстати пример по вашей ссылке вряд ли является корректным решением этой задачи так как N по условию может быть очень большим числом и задан лимит в 2 секунды на работу программы. Но могу ошибаться, там основной цикл идет от 2 до корень из N. |
Re: Задача на логику
Цитата:
|
Re: Задача на логику
Пример глдянул только мельком, так не интересно :)
Добавлю еще условие 3. 3. если мы попали в исходную точку раньше времени (количество отрезков звезды < N) значит звезда не получилась. Думаю этого достаточно, теперь думаем как это решить быстро и элегантно. |
Re: Задача на логику
Цитата:
|
Re: Задача на логику
А как там пошагово запустить код на исполнение? Нужно регаться?
|
Re: Задача на логику
Цитата:
|
Re: Задача на логику
Да я не эксперт в алгоритмах. Возможно я вам совсем не оптимальный вариант решения предложил. Погодите разберусь в примере кода.
|
Re: Задача на логику
На самом деле, еще очень актуально.
|
Re: Задача на логику
Как работает код в примере из первого поста разобраться пока не могу :(
Попробуйте погуглить методику решения. Там вроде как бы и просто, но почему считается именно так мне непонятно. |
Re: Задача на логику
Актуально.
|
Re: Задача на логику
Clown, не пытайтесь придумать алгоритм для этой задачи. Всё что вам нужно - это найти зависимости между переменными и составить уравнение. К сожалению я сейчас не могу помочь вам с решением, возможно в один из ближайших дней на следующей неделе. Я более чем уверен, что для любого вашего алгоритма найдется такое N, которое провалит тест по времени выполнения. Начните с определения того, что Фернандо считает звездой.
Составьте примерный вход - выход для идеально правильной программы, хотя бы для первых нескольких значений. Найдите принцип, по которому изменяется выходное значение, слепите формулу, и задача решена самым оптимальным образом. Upd: В промежутке 1 < k < N/2 вам нужно найти числа, которые не являются делителями N, узнать их кол-во, и прибавить 1. Это и будет ответом. Пример: Делители числа N=8 попадающие в заданный промежуток это 1, 2, 4, 8. т.е. делителями не являются 3, 5, 6, 7. в промежуток попадает только число k=3, прибавляем единицу (т.к. 1 - это делитель любого числа, и для него звезда всегда будет строиться) получаем выходной ответ: 2 Делители числа N=9 это 1, 3, 9. делителями не являются 2, 4, 5, 6, 7, 8. В промежуток(1 < k < N/2) попадают 2 и 4. прибавляем к кол-ву этих чисел 1, получаем ответ:3 Делители числа N=10 это 1, 2, 5, 10. не делят 3, 4, 6, 7, 8, в промежуток попадают 3 и 4, кол-во = 2, прибавляем 1, ответ:3 итд... Промежуток 1 < k < N/2 снизу ограничивает 1, из которого звезда получится в любом случае. сверху ограничивает максимально разумный диапазон (дальше звезды начнут повторяться, только в другую сторону, например для N = 9 звезды будут при k1=3, k2=4, k3=5=(9-4), звезда аналогичная той, что будет при k2=4, и k4=6=(9-3) - звезда аналогичная звезде при k1. http://codeforces.ru/blog/entry/651?locale=ru |
Re: Задача на логику
По времени не провалит там каждый проход число N делится на 2 и больше.
Звезда С как раз подходит. Достаточное условие чтобы Фернандо считал фигуру звездой - это построить кривую через все точки по заданным правилам. Пошагово прошел по коду из примера. Например при N = 8 происходит следующее: ans = 1; i = 2; aux = 1; 1 проход: N = N / i = 4; aux = aux * i = 1 * 2 = 2; 2 проход: N = N / i = 2; aux = aux * i = 2 * 2 = 4; 3 проход: N = N / i = 1; aux = aux * i = 4 * 2 = 8; ans = ans * (aux - aux/i) = 1 * (8 - 8/2) = 4; ans = (ans + 1)/2 = (4 + 1)/2 = 5/2 = 2;//целочисленное округление ответ - 2 Каждый проход мы как бы делим окружность пополам и постепенно получаем фигуры с рисунка D, B, A. http://uva.onlinejudge.org/external/124/p12493.png Но как на основании этого делается вывод, что можно построить именно 2 разные звезды при k = 1 (звезда A) и k = 3 (звезда C) я не пойму. Но работает правильно. |
Текущее время: 19:47. Часовой пояс GMT +3. |
Powered by vBulletin® Version 3.8.6
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot