Вторая индивидуальная олимпида neerc

13 лет назад, # ^ |

-8

С токенами тут абсолютов штук 15 будет :)

→ Ответить

Joshik

13 лет назад, # ^ |

Ближайшая серьезная олимпиада, к которой все готовятся - региональная и на ней нет токенов.

Ближе к РОИ они появятся и в интернет-олимпиадах.

→ Ответить

dalex

13 лет назад, # ^ |

Что такое токены?

→ Ответить

yahooo

13 лет назад, # ^ |

вроде это когда можно смотреть свой балл по задаче.... или я ошибаюсь

→ Ответить

tunyash

13 лет назад, # |

← Rev. 2 →

Только меня не система не пускает?
УПД: теперь всё ок.

→ Ответить

yahooo

13 лет назад, # ^ |

меня пускает, я через web

→ Ответить

d_i	13 лет назад, # \| 0 Как решается последняя задача Наименьшее общее кратное? → Ответить

13 лет назад, # |

← Rev. 2 →

Кто как делал Д?
У меня упадет по времени когда много разных множителей в факторизации.

ПС. Я делал ДП по маскам + метод включения/выключения. Вышло О(3^p*K^2), где p - кол-во различных простых множителей в числе N.

→ Ответить

tunyash

13 лет назад, # ^ |

← Rev. 2 →

Я тоже делал дп по маскам, но за divs*k^2*2^p, где divs - число делителей n. p - то же, что и у вас. dp[divisor][mask][count]. divisor - номер текущего делителя. mask - маска покрытых классов эквивалентности простых множителей. Покрытым класс называется тогда, когда мы включили в набор число, в разложение которого данное простое число входит в той же степени, что и в n. count - количество чисел в наборе. Считается число способов добиться состояния mask-count использовав первые divisor делителей. Тогда ответом будет dp[divs][2^p-1][k]. Переходы простые - мы можем добавить текущий множитель несколько раз.

→ Ответить

agul	13 лет назад, # \| 0 Как решать D? → Ответить

unrated

13 лет назад, # |

Как решать С??

→ Ответить

oldoldold

13 лет назад, # ^ |

Что то наподобие решета эратосфена. Вся фишка в маленьком N.
http://ideone.com/2oJMO

→ Ответить

agul

13 лет назад, # ^ |

Отсортируем все a_i.

Затем запустим "решето эратосфена" на этих числах:

1) заполним массив чисел единичками

2) идем от 1 до k: если это число a_i в массиве все еще единичка, то запустим просеивание (как в решете). всем числам, кратным данному a_i присвоим 0.

3) посчитаем количество единичек в массиве - это и будет ответом.

→ Ответить

pavel.savchenkov

13 лет назад, # ^ |

А я впопыхах ничего проще метода включений-исключений не придумал и радостно сдал его на 25 баллов)

→ Ответить

Timus

13 лет назад, # ^ |

← Rev. 2 →

Неожиданно, но зашло решение за О(n*sqrt(n)). Просто идем от 1 до n, смотрим на делители числа, если хоть один делитель есть в нашем наборе, прибавляем к ответу, идем дальше.

→ Ответить

Creed

13 лет назад, # ^ |

Т.к. N маленькое то можно хранить булевский массив и вычеркивать числа влоб. Почему это быстро? Потому что вычеркивая все числа кратные a[i] мы потратим N / a[i] действий и понятно что худшим вариантом будет когда a[i] достаточно маленькие. Но если избавиться от повторяющихся a[i] (понятно по каким соображениям), то самым худшим вариантом будет последовательность рода N / 2, N / 3 ... N / K. Как известно такая последовательность сходится к N ln N, что вполне удовлетворяет =)

→ Ответить

agul	13 лет назад, # \| 0 Условие в задаче А - ужас, ничего почти непонятно. Наверное, поэтому у многих 64 за нее. → Ответить

d_i	13 лет назад, # ^ \| 0 А где вы смотрите результаты? → Ответить

13 лет назад, # ^ |

Может потому-что ответ на влазит в инт?

→ Ответить

agul	13 лет назад, # ^ \| +1 Блииин... → Ответить

13 лет назад, # |

D была бы интереснее с N = 10^18 :)

→ Ответить

agul	13 лет назад, # ^ \| 0 как ее вообще решать? → Ответить

13 лет назад, # ^ |

Научимся считать f(i, j) - количество разных наборов из i чисел, при том, что можно выбирать числа в набор из j различных. Это считается простой дп-шкой. Теперь заметим, что в наборах могут быть только делители числа N. Еще заметим, что их будет немного(меньше 10000) и то что количество различных простых делителей числа невелико (для N<=10^12) максимум 11. Надо просто найти степени всех простых делителей N. Потом можно за 2^11 делать включения-исключения по простым делителям. Код тут.

→ Ответить

pva701

13 лет назад, # ^ |

я бы не сказал, что она была неинтересна

→ Ответить

13 лет назад, # ^ |

Для N ≤ 10¹⁸ все решалось бы также, только нужно было бы уметь факторизовать быстро.

→ Ответить

13 лет назад, # ^ |

Быстро факторизовать не требуется, достаточно только знать степени с которыми простые входят в число.

→ Ответить

13 лет назад, # ^ |

Да, ты прав :) Я не подумал о том, что степени-то мы можем узнать до 10¹⁸. Действительно интересней.

→ Ответить

13 лет назад, # ^ |

Также можно было сделать k ≤ 10⁵, но подумал, что и так непросто будет для многих:)

→ Ответить

13 лет назад, # ^ |

Для меня К ,и так, оказалась большой преградой.

→ Ответить

13 лет назад, # ^ |

Нияз, у тебя нету доступа что-бы посмотреть по каким причинам у меня упала задача С?

→ Ответить

13 лет назад, # ^ |

Нет

→ Ответить

agul	13 лет назад, # \| 0 Результаты уже доступны в PCMS2. → Ответить

nerd	13 лет назад, # ^ \| 0 Можете ссылку на PCMS2 дать?! → Ответить

agul	13 лет назад, # ^ \| ← Rev. 2 → 0 http://neerc.ifmo.ru/trains/ - раздел "Софт". → Ответить