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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 13.11.2006, 20:03
незарегистрированный

 
Сообщений: n/a

1430 timus
http://acm.timus.ru/problem.aspx?space=1&num=1430
Вот такая задача.

Как я понимаю нам надо найти, такие X и Y, что
X in [0..(n div a)];
Y in [0..(n div b)];

и

max{X*A + Y*B} <= N

Но как это сделать быстро? Или предложите идею для решения задачи.
tnx.
  #2  
Старый 21.12.2006, 21:25
necro

 
Сообщений: n/a

ghm
имхо здесь чтото связанно с расширенным алгоритмом евклида на сайте густокашина вродебы есть подобная задача с разбором
  #3  
Старый 22.12.2006, 19:54
Новичок

Отправить личное сообщение для it4.kp Посмотреть профиль Найти все сообщения от it4.kp
 
Регистрация: 23.09.2006
Адрес: Архангельск
Сообщений: 22

Можно решать так:

1. Если (N div A) <= 100000, то перебрать все варианты для X.
2. Иначе если (N div B) <= 100000, то перебрать все варианты для Y.
3. Иначе:
Во-первых, заметим, что A и B довольно небольшие (<=20000).
Пусть максимум, который мы можем получить, равен M, тогда
очевидно, что 0 <= N-M < B. Теперь если перебирать по возрастанию
X от 0 до 20000, то мы получим все возможные остатки N-M. В самом
деле всего их 20000, а если на каком-то шаге мы получим остаток,
который уже был, то дальше все зациклится и ничего нового мы
уже не получим. Т.е. все, что необходимо перебрать X от 0 до 20000.

Вообще в пунктах 1 и 2 можно взять не 100000 а sqrt(N). Тогда и в
пункте 3 придется перебирать от 0 до sqrt(N).

Таким образом, алгоритм имеет сложность O(sqrt(N)).
  #4  
Старый 26.12.2006, 02:02
незарегистрированный

 
Сообщений: n/a

Сообщение от it4.kp Посмотреть сообщение
Можно решать так:

1. Если (N div A) <= 100000, то перебрать все варианты для X.
2. Иначе если (N div B) <= 100000, то перебрать все варианты для Y.
3. Иначе:
Во-первых, заметим, что A и B довольно небольшие (<=20000).
Пусть максимум, который мы можем получить, равен M, тогда
очевидно, что 0 <= N-M < B. Теперь если перебирать по возрастанию
X от 0 до 20000, то мы получим все возможные остатки N-M. В самом
деле всего их 20000, а если на каком-то шаге мы получим остаток,
который уже был, то дальше все зациклится и ничего нового мы
уже не получим. Т.е. все, что необходимо перебрать X от 0 до 20000.

Вообще в пунктах 1 и 2 можно взять не 100000 а sqrt(N). Тогда и в
пункте 3 придется перебирать от 0 до sqrt(N).

Таким образом, алгоритм имеет сложность O(sqrt(N)).
Я решаю подобным образом, но у меня WA 16. Может кто-нибудь знает в чем дело?
  #5  
Старый 28.12.2006, 15:25
Новичок

Отправить личное сообщение для it4.kp Посмотреть профиль Найти все сообщения от it4.kp
 
Регистрация: 23.09.2006
Адрес: Архангельск
Сообщений: 22

может у тебя где-нибудь переполняется целый тип?
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Timus 1463 sawe Задачи 3 25.08.2009 01:01
Timus 1003 Parity незарегистрированный Задачи 6 03.05.2008 09:05
Timus 1090 незарегистрированный Задачи 4 27.02.2008 01:21
Timus Top Coders: Third Challenge Dmitry Kovalioff Участие 6 12.01.2007 14:44
Timus, 1142 xbit Задачи 3 30.12.2006 18:13