Форум администраторов игровых серверов

Форум администраторов игровых серверов (https://forum.zone-game.info/TT.php)
-   Программирование / Programming (https://forum.zone-game.info/forumdisplay.php?f=98)
-   -   Задача на логику (https://forum.zone-game.info/showthread.php?t=35347)

Clown 30.05.2014 11:58

Задача на логику
 
Всем привет!
Собственно, снова понадобилась помощь дружного коллектива :)
На носу всеми любимой летней сессии задали задания на UVA, которые обязательно нужно решить . Сказано - сделано. Практически все задачи были сделаны (язык программирования характерный - С++ или Java), а вот одно задание - хоть убей, не пойму.
Нужна помощь с алгоритмом, если кто поможет - добра и счастье тебе, друг:) . А вообще - всем того же ;)

http://uva.onlinejudge.org/index.php...m&problem=3937 Сама задача.

UPD:
Нашел код на сишке, но не могу понять алгоритма, может кто понял и объяснит, так же был бы крайне благодарен... По сути, мне важен именно алгоритм решения, ибо написать могу и сам .
https://github.com/marioyc/Online-Ju...0-%20Stars.cpp

C Уважением.

Добавлено через 2 часа 49 минут
Ну хоть предположения:(

flopix 30.05.2014 14:51

Re: Задача на логику
 
Для скорейшего понимания написали бы суть задания на русском, а то на английском ро ссылке тяжело вникать.

Clown 30.05.2014 16:15

Re: Задача на логику
 
"Фернандо получил компас на день рождения, и теперь его хобби - рисовать звёзды. Сначала он делает N отметок на окружности, разделяя её на N равных дуг, потом соединяет каждую точку с каждой К-той точкой, и так до тех пор, пока не вернётся к первой точке2"
"В зависимости от значения К, Фернандо может достичь\не достичь всех точек на окружности; когда это случается - звезда называется завершённой. Например, когда N=8, возможные звёзды показаны на фигуре ниже. Звёзды а и с - завершённые, б и д - напротив, нет.
В зависимости от значения N, есть вероятность нарисования всеразличных звёзд, Фернандо попросил тебя написать программу, которая при заданном значении N определяет количество возможных законченных звёзд, которые он может нарисовать."
"Ввод:
Ввод содержит несколько тестовых вариантов. Каждый тестовый вариант содержит одну линию (строку), включающую в себя число типа integer, =диапазон для N даётся=, указывая число дуг, на которые окружность была поделена.
Вывод:
Для каждого тестового варианта твоя программа должна вывести одну строку (линию), содержащую одну же линию с числом типа integer (=дословно: одну линию содержащуюю один инт=), показывая количество законченных звёзд, которые могут быть нарисованы.

flopix 30.05.2014 18:16

Re: Задача на логику
 
k - это количество пропускаемых точек, при построение очередного отрезка, k = 0 .. N-1


Одним из признаков, что звезда получилась является:

1. построение звезды закончилось в той же точке где и началось
2. количество отрезков равно количеству точек на окружности

Но это не достаточное условие, нужно как то исключить попадание в одни и те же точки, надо подумать как.

И кстати пример по вашей ссылке вряд ли является корректным решением этой задачи так как N по условию может быть очень большим числом и задан лимит в 2 секунды на работу программы.
Но могу ошибаться, там основной цикл идет от 2 до корень из N.

Clown 30.05.2014 18:29

Re: Задача на логику
 
Цитата:

Сообщение от flopix (Сообщение 364986)
k - это количество пропускаемых точек, при построение очередного отрезка, k = 0 .. N-1


Одним из признаков, что звезда получилась является:

1. построение звезды закончилось в той же точке где и началось
2. количество отрезков равно количеству точек на окружности

Но это не достаточное условие, нужно как то исключить попадание в одни и те же точки, надо подумать как.

И кстати пример по вашей ссылке вряд ли является корректным решением этой задачи так как N по условию может быть очень большим числом и задан лимит в 2 секунды на работу программы.
Но могу ошибаться, там основной цикл идет от 2 до корень из N.

Я , честно говоря, не очень понял алгоритм по которому реализован тот пример. Можете объяснить, если разобрали? Вообще - данное решение (по той ссылке) - верное. Тестировал - выполнение ~ за 1,5-1,7 s на все тесты. Не пойму сей логики кода, хотя пропускал пошагово выполнение. (Сам код то элементарен, а вот алгоритм - извольте, хотя, вероятно, больше здесь "не в тыкаю" я).

flopix 30.05.2014 18:30

Re: Задача на логику
 
Пример глдянул только мельком, так не интересно :)


Добавлю еще условие 3.

3. если мы попали в исходную точку раньше времени (количество отрезков звезды < N) значит звезда не получилась.

Думаю этого достаточно, теперь думаем как это решить быстро и элегантно.

Clown 30.05.2014 18:34

Re: Задача на логику
 
Цитата:

Сообщение от flopix (Сообщение 364991)
Пример глдянул только мельком, так не интересно :)


Добавлю еще условие 3.

3. если мы попали в исходную точку раньше времени (количество отрезков звезды < N) значит звезда не получилась.

Думаю этого достаточно, теперь думаем как это решить быстро и элегантно.

Да, уже заметил и плюсанул в репу, огромное Вам спасибо! теперь хоть алгоритм решения стал понятен и , в принципе, если не выплывет никаких подводных камней - можно спокойно реализовать. Но на счет примера - актуально. Не в плане того, что мне хотелось бы его взять (это я и так бы мог сделать не прося помощи), а в плане, что интересно само решение, которое нет смысла пропускать и опускать на будущее, ведь плохо то, что я не понял его:Olen':. Так что разобраться было бы не лишним, что, к сожалению, у меня не очень хорошо получается на данный момент, разве что понял, что мы доходим до первой точки , а вот дальше.

flopix 30.05.2014 18:47

Re: Задача на логику
 
А как там пошагово запустить код на исполнение? Нужно регаться?

Clown 30.05.2014 18:49

Re: Задача на логику
 
Цитата:

Сообщение от flopix (Сообщение 364994)
А как там пошагово запустить код на исполнение? Нужно регаться?

Не, не, не, юзаю Visual Studio. Можно с Вами как-то связаться? Думаю, так бы было удобнее. А как итог я приложу сюда и попрошу закрыть тему, вдруг, кому-то тоже понадобится.

flopix 30.05.2014 18:51

Re: Задача на логику
 
Да я не эксперт в алгоритмах. Возможно я вам совсем не оптимальный вариант решения предложил. Погодите разберусь в примере кода.


Текущее время: 15:27. Часовой пояс GMT +3.

Powered by vBulletin® Version 3.8.6
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot