Задача на логику - Страница 2 - Форум администраторов игровых серверов
Форум администраторов игровых серверов StormWall - Защита от DDos атак
Регистрация Мнения Справка Пользователи Календарь Все разделы прочитаны
Вернуться   Форум администраторов игровых серверов > Полезное / Common > Программирование / Programming

Программирование / Programming
Ищете помощи в написании программы, есть сложность в выполнении задания (в институте и т.д.), пожалуйста, спросите у нас в данном форуме и мы обязательно вам поможем.

Ответ
Опции темы
Непрочитано 30.05.2014, 19:50   #11
Аватар для Clown
Пользователь

Автор темы (Топик Стартер) Re: Задача на логику

На самом деле, еще очень актуально.
__________________
// GPRS удалил подпись пользователя
Clown вне форума Ответить с цитированием
Непрочитано 31.05.2014, 02:21   #12
Пользователь

По умолчанию Re: Задача на логику

Как работает код в примере из первого поста разобраться пока не могу
Попробуйте погуглить методику решения. Там вроде как бы и просто, но почему считается именно так мне непонятно.
flopix вне форума Ответить с цитированием
Непрочитано 31.05.2014, 18:07   #13
Аватар для Clown
Пользователь

Автор темы (Топик Стартер) Re: Задача на логику

Актуально.
__________________
// GPRS удалил подпись пользователя
Clown вне форума Ответить с цитированием
Непрочитано 31.05.2014, 20:07   #14

По умолчанию 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

Последний раз редактировалось Camelion; 31.05.2014 в 20:36.
Camelion вне форума Отправить сообщение для Camelion с помощью ICQ Ответить с цитированием
Сказали спасибо:
Непрочитано 31.05.2014, 20:19   #15
Пользователь

По умолчанию 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.



Но как на основании этого делается вывод, что можно построить именно 2 разные звезды при k = 1 (звезда A) и k = 3 (звезда C) я не пойму. Но работает правильно.

Последний раз редактировалось flopix; 31.05.2014 в 23:05.
flopix вне форума Ответить с цитированием
Сказали спасибо:
Ответ


Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
 
Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вот такая вот задача Asmodiel Курилка / Yak floor 5 12.01.2013 15:52
Задача на VBA Nowell Программирование / Programming 2 10.06.2010 09:24


© 2007–2024 «Форум администраторов игровых серверов»
Защита сайта от DDoS атак — StormWall
Работает на Булке неизвестной версии с переводом от zCarot
Текущее время: 22:11. Часовой пояс GMT +3.

Вверх