1. Положил: С монет (1C-0x)
2. Вытащил - Х монет. (стало 1С-1X)
3. Положил C монет. (стало 2С-1X)
4. Положил С-X монет. (стало 3C-2х)
5. Положил 2С-Х монет (стало 5С-3х)
6. Положил 3с-2х монет. ( стало 8С - 5Х монет)
7. Положил 5С-3х монет. ( стало 13С - 8Х монет)
Очевидно что коэффициенты у чисел равны числам фибоначчи:
Число монет в год N равно F(x) Положил - F(x-1) Взял.
Таким образом, тебе надо решить уравнение AX - BY = Z, в котором A и B известны, и при этом Y < X, а также известно что значения - целочисленные.
Дальше, я думаю, сможешь посчитать сам.
2. Вытащил - Х монет. (стало 1С-1X)
3. Положил C монет. (стало 2С-1X)
4. Положил С-X монет. (стало 3C-2х)
5. Положил 2С-Х монет (стало 5С-3х)
6. Положил 3с-2х монет. ( стало 8С - 5Х монет)
7. Положил 5С-3х монет. ( стало 13С - 8Х монет)
Очевидно что коэффициенты у чисел равны числам фибоначчи:
Число монет в год N равно F(x) Положил - F(x-1) Взял.
Таким образом, тебе надо решить уравнение AX - BY = Z, в котором A и B известны, и при этом Y < X, а также известно что значения - целочисленные.
Дальше, я думаю, сможешь посчитать сам.
Спасибо
Если решений несколько, нужны все или любое? А так-то легко.
Пусть в первый год положили N монет, а во второй год вытащили m монет.
В год X в сундуке Y=(N-m + (X-2)N) монет.
m = N(X-1) - Y ≤ N
Пусть m≥1. Тогда берёшь любое натуральное N из промежутка от (Y+1)/(X-1) до Y/(X-2) и по нему считаешь m. Если m может быть равно нулю, то промежуток надо брать от Y/(X-1) до Y/(X-2)
Пусть в первый год положили N монет, а во второй год вытащили m монет.
В год X в сундуке Y=(N-m + (X-2)N) монет.
m = N(X-1) - Y ≤ N
Пусть m≥1. Тогда берёшь любое натуральное N из промежутка от (Y+1)/(X-1) до Y/(X-2) и по нему считаешь m. Если m может быть равно нулю, то промежуток надо брать от Y/(X-1) до Y/(X-2)
Гарантируют что решение одно
Хотя я неправильно условие понял, забудь.
>Начиная с третьего года, он добавлял столько монет, сколько было в сундуке два года назад.
Сколько было после того как он забрал монеты, или столько, сколько он положил в первый год?
Сколько было после того как он забрал монеты, или столько, сколько он положил в первый год?
это считается элементарным; вся суть задачи в поиске этих самых коэффициентов. циклом по времени не проходит. возможно бинарный поиск
Дан массив n целых положительных (>0) чисел и число k <= n. Нужно разбить массив на k (возможно пустых) частей так, чтобы минимизировать максимальную сумму внутри частей.
Например:
4 2 -1 5, k = 2
Видим, что оптимальное разбиение это 4 + 2 - 1 и 5, т.е. max(5, 5) = 5, в остальных случаях максимум больше.
Найти минимальную максимальную сумму, само разбиение находить не надо.
Время: O(kn)
Память: O(k + n)
задачка с собеседования в американский яндекс
Например:
4 2 -1 5, k = 2
Видим, что оптимальное разбиение это 4 + 2 - 1 и 5, т.е. max(5, 5) = 5, в остальных случаях максимум больше.
Найти минимальную максимальную сумму, само разбиение находить не надо.
Время: O(kn)
Память: O(k + n)
задачка с собеседования в американский яндекс
> Дан массив n целых положительных (>0) чисел
> 4 2 -1 5
Вот обосрался с примером. Если числа отрицательные, то только O(k * n^2)
Вот правильный пример:
4 2 1 5, k = 2
4 + 2 и 1 + 5, ответ 6.
Это оффициальный тред? Тут теперь спрашивать помощь по решению олимпиадных задач?
Бин поиск по ответу + жадность. Ответ надо искать в промежутке от 1 до суммы всех чисел. Выбрав какую-то сумму s идем по последовательности и в текущую подпоследовательность пихаем столько элементов, сколько можем.
Только тут время n log(sum a_i), что меньше o(nk) для маленьких k. Ща еще подумаю.
Кстати в наукаче есть тред про Computer Science. Говорят и с олимпиадными задачами к ним можно. Поэтому если в этот тред будут заходить только полтора умеющих решать задачки анона, то можно к ним перекатиться.
>для больших k
вот это ты хотел сказать.
Оригинально. Я просто через SMAWK решил т.к. матрица получается строго монотонная.
Дан массив uint64_t, найти непрерывный подмассив с максимальным xor-ом. Т.е. подмассив l1, l2, ... lk такой, что l1 ^ l2 ^ ... lk максимально.
> Оригинально
На самом деле бин поиск по ответу - это стандартный асмовский прием, я его десятки раз писал. А про SWAMK первый раз слышу.
> SMAWK
фикс
Лол, оп, задача в твоём посте очень простая, решил буквально за 3 минуты полным перебором, думал словлю таймлимит, но нихуя. Вот как я рассуждал. Во первых, сразу бери листочек и ручку и начинай придумывать примеры, я вот взял числа 6 и 30 и сразу увидел, что снизу вверх можно собрать уравнение, а потом перебором найти коэффициенты. Вот код, если интересно. http://pastebin.com/sRYe7kUz
Гарантируют, что оно ЕСТЬ. Учись читать условия.
На checkio похожая задача есть, только там количество групп ограничено 2мя. И минимальной должна быть разница между суммами в них.
Ну SMAWK это тоже в некотором смысле "олимпиадный приём".
Есть матрица nxn с таким свойством. Если a[r1][c1] >= a[r1][c2], то для всех r > r1 a[r][c1] >= a[r][c2]
Найти в данной матрице минимальный элемент в каждой строчке за O(n)
Это и есть SMAWK
Дерево отрезков?
То есть нужно модифицировать "Поиск подотрезка с максимальной суммой" вот в этой статье
http://e-maxx.ru/algo/segment_tree
Ну а для тупых есть вариант с trie. Запихиваем все частичные xor-ы в trie, а после этого нам нужно для каждого частичного xor-а найти такой частичный xor, который бы при xor-е дал максимальный результат, т.е. в trie стараемся идти в 0 когда в исходном числе 1 и в 1, когда в исходном числе 0.
Блядь, какое-то торжество олимпидодаунов, и их ещё не обоссали? Что ж! Я буду первым! Открывайте рот пошире, чтобы не пропустить ни капли!
Чет никто не вбрасывает. Тогда я вброшу такую задачу с опенкапа недавнего. Это обобщение загадки о волке, козе и капусте на случай, когда животных много.
Ой, картинки не те.
Кстати можно где-нибудь получить сертификат что я мастер алгоритмов? Как к нему готовиться?
только начал
только начал
И нахуя это нужно?
Что значит нужно?
Для чего вы это решаете? В каких проектах будете применять?
Для развлечения, очевидно.
По крайней мере, я этим занимаюсь для развлечения. Возможно кто-то решает олимпиады, потому что хочет профессионально заниматься алгоритмами или чем-то подобным.
ЧО ЗА ГРАФЫ ТАКИЕ?
@
КРУЖКИ РИСУЕШЬ ЧТО ЛИ?
@
РАСКРАСКИ? КАКИЕ РАСКРАСКИ?
@
БЛЯ У МЕНЯ У ПЛЕМЯННИКА ТОЖИ РАСКРАСКИ ЕСТЬ))0
@
А ТЕБЕ-ТО 20 ЛЕТ, КАКИЕ РАСКРАСКИ, ТЫ ЧО ЕПТ))0
@
А ДЕВУШКУ СВОЮ ТЫ ГРАФАМИ БУДЕШЬ ЗАЩИЩАТЬ?)))0
Но ведь всё это - говно без задач. Учили бы лучше принципы построения грамотной архитектуры и всё такое.
Это учит мыслить out of the box. Современная архитектура, кстати, уже подгнивает. Индустрии требуется языки шестого поколения, потому что предыдущие уже не справляются с нагрузкой комплексностью.
Изобретать же новые инструменты будут не дрочители паттернов, а те кто смогут выйти за пределы текущей парадигмы.
Ты просто быдло. Я не знаю как объяснить. Ты музыку слушаешь? Тебе музыка как-то поможет деньги заработать, если ты не профессиональный музыкант?
Но я - профессиональный музыкант.
Ну ладно. Тогда я профессиональный математик, занимаюсь теорией графов, в своей команде по acm отвечаю за всякие графы и деревья.
А я Иван, сосу кукан))
Тогда тебе можно решать задачи про волка, козу и капусту.
Спасибо.
Даунята не в курсе, что на собеседовании в любую нормальную компанию сейчас дают решать олимпиадные задачи, и спрашивают про математику и алгоритмы.
Энтри левел. Дано n (очень большое) и m, найдите n-е число Фибоначчи по модулю m.
А m какое? За какое время надо решить?
Можно использовать формулу Бине (с корнями из 5) и быстрое возведение в степень. Если m и n взаимно простые, то по теореме Эклера можно найти обратный элемент. Время работы O(log n + log m).
m влазит в инт, ну как минимум линейное от номера числа.
>теореме Эклера
Какой обратный элемент, что ты несёшь? Быстрое возведение в степень по модулю, ты хотел сказать?
Ну в формуле Бине надо в конце делить на 2^n. А чтобы поделить на 2^n в кольце вычетов по модулю m, нужно найти обратный элемент, нельзя просто делить. А его проще всего найти по теореме Эклера (но если n и m не взаимно простые, то не получится).
Наверное, более простой вариант, последовательно вычислять числа по модулю m, пока пары чисел не начнут повторяться. Дальше просто находим период. Назовем его T. Ответ - это число с номером n mod T. Пары чисел начнут повторяться через O(m^2) вычисленных чисел, потому что есть m^2 / 2 различных пар элементов в Z_m. У меня есть подозрение, что они раньше начнут повторяться, но я хз как доказать.
> но если n и m не взаимно простые, то не получится
Фикс: 2^n и m не взаимно простые естественно. То есть m должно быть хотя бы нечетным.
Ок, с периодом Пизано закатит.
http://ideone.com/0TGSWI а как же вариант через матрицы, который за O(log(n)) работает через школьную арифметику..
Ебать, оказывается это еще и назвали в честь кого-то, хотя этот результат придумывается за 5 минут любым асмщиком.
Бляяя, точно, чет не подумал.
Пожалуй, продолжу. Задачка из facebook задавал индус
Кузнечик находится в (0, 0). После этого он делает n шагов. Шаг это - (+1, 0), (-1, 0), (0, +1) или (0, -1).
Рассмотрим множество всех его возможных путей. Их 4^n. Будем считать два пути различными, если множество посещённых координат различается.
Сколько всего уникальных путей у кузнечика, если он делает n шагов?
Нужно быстрее чем за O(n) и без преподсчёта.
Кузнечик находится в (0, 0). После этого он делает n шагов. Шаг это - (+1, 0), (-1, 0), (0, +1) или (0, -1).
Рассмотрим множество всех его возможных путей. Их 4^n. Будем считать два пути различными, если множество посещённых координат различается.
Сколько всего уникальных путей у кузнечика, если он делает n шагов?
Нужно быстрее чем за O(n) и без преподсчёта.
Чет хуй знает пока что. Я спать пойду.
4 * 3 ^ (n - 1)
Или не. Наверное сумма этой хуйни от 1 до n, считать что n ^ 0 = 1.
За каждый шаг вариативность пути возрастает на 4 клетки.
Значит: n^4
Некоторые пути одинаковые по определению "различных путей". Например влево - влево - враво - влево и влево - вправо - влево - влево.
Какая-нибудь формула из комбинаторики не подходит?
Я так подумал, это тоже не правильно. Нужно на каждом шаге (от 1 до n) высчитать количество путей которые не пересекаются сами с собой, и проссумировать.
Ох блядь, там еще нужно учесть пути соприкасающиеся с началом. Вот же индус.
>Будем считать два пути различными, если множество посещённых координат различается.
Хуйня кокая-то.
для n=2 путей 16 но уникальных только 12, ибо путь (1 -1 1) образует подмножество пути (1 1 1). И так 4 раза.
Т.е наверно нужно учитывать только самы длинные пути, ибо у них самы сильные множества.
Я уже понел, но чет никак не соображу формулу.
для n=3 у меня получилось 9*4 разных путей.
Лол, походу задача сводится к поику площади прямоугольника с вершинами {n,n}{n,-n}{-n,n}{-n,-n}.
Ну сами посудите: любая крайняя клетка(принадлежит периметру) может быть достигнута за n шагов, любая внутреняя клетка не является уникальным путем, ибо ее координаты точно войдут в путь до края или станут конечными в путе-цикле(путь с повторами шаг - вперед шаг назад).
цыфры вроде сходятся.
Кароч формула: (4n) + 4 sum(1, n - 1)
Ну сами посудите: любая крайняя клетка(принадлежит периметру) может быть достигнута за n шагов, любая внутреняя клетка не является уникальным путем, ибо ее координаты точно войдут в путь до края или станут конечными в путе-цикле(путь с повторами шаг - вперед шаг назад).
цыфры вроде сходятся.
Кароч формула: (4n) + 4 sum(1, n - 1)
Вершины же по нулевой оси?
->
И, кстати, в одну точку можно добраться разными путями без циклов. Например, вверх-вправо и вправо-вверх — точка одна, а путей уже 2.
И, кстати, в одну точку можно добраться разными путями без циклов. Например, вверх-вправо и вправо-вверх — точка одна, а путей уже 2.
по фразе "Нужно быстрее чем за O(n) и без преподсчёта." наверное можно понять что формулы там нихуя нет и надо писать алгоритм.
>для n=2 путей 16 но уникальных только 12, ибо путь (1 -1 1) образует подмножество пути (1 1 1).
какие из слов "множества посещенных координат" тебе непонятны?
Че может подскажешь? Как-то вообще идей нет
Нужно думать out of the box.
Нужен учебник олимпиадным задачам. Не алгоритмам, а именно задачам.
Я сегодня уже думал out of the box, когда твою мамку на секс разводил. Уже лимит думанья out of the box превышен.
Поясните за функцию эйлера. Как этот код и формула связаны? В формуле от 1 отнимают единицу деленную на простое число что меньше единицы и это перемножают с другими результатами которые меньше единицы. Получается какое-то маленькое число которое умножают на n. И при чём тут этот код?
Скобочки начни раскрывать слева.
Функция эйлера - это количество чисел меньше n, взаимно простых с n. Несложно доказать, что она мультиплакитивна. А какой-то арифметической формулы для нее нет. Код который ты привел вычисляет функцию Эйлера перебором. А что это за формулы - хуй знает.
А нет, падажжи, я понял. В той формуле сверху пэ это простые делители, а альфа - их кратность. Но один хуй в коде вычисляется не по этой формуле.
Во первых, там нихуя не полный перебор, а перебор с учётом формулы. Во вторых, того что она мультипликативна достаточно для вывода формул выше.
Следи за рукой:
n(1-1/p1)...(1-1/pk) = (n - n/p1)(1-1/p2)...(1 - 1/pk) и так далее последовательным раскрытие скобок. Код делает то же самое - находит простой делитель n и раскрывает для этого делителя его скобку, а само n делит пока оно не станет взаимно просто с этим делителем.
Ну дак че, как решать?
Как без массива решать? С решение в лоб меньше половины тестов проходит.
это скрин с какого сайта?
dl.gsu.by Ссылка не дам т.к. нужна регистрация она без инвайтов, но всё равно всем лень и так проще.
Помогите.
Пожалуйста.
Где же все знатоки? Может там какой-то известный алгоритм из ДП, а я его не знаю?
Ну хуй знает. Можно такой тупой алгоритм: рассмотрим каждую строчку. Возьмём наш прямоугольник RxC и будем двигать его слева направо и считать количество деревьев в нём. Для каждого отдельно взятого прямоугольника линия будет иметь вид / --- \ (то есть, три фазы- рост, константность, падение). Заметим, что скорость роста - константна, падения - тоже. Теперь у нас задача - есть 100 таких линий, нужно их сложить, а потом найти точку минимума.
Вот так примерно выглядит линия для одного прямоугольника:
0 0 0 10 20 30 30 30 30 30 30 30 20 10 0 0 0
Представим, что это - линия, имеющая в x=0 значение 0, в x =1 значение 0, в x=2 значение 0, потом между x=2 и x=3 она идёт вверх с производной 10, в x=3 достигает значения 10, в x=4 - значения 20, итд. Теперь возьмём производную от этой линии. она будет представлять из себя 3 отрезка - со значением 10 на отрезке [2, 5], со значением 0 на отрезке [5, 11] и со значением -10 на [11, 14]
Нас интересуют точки, где производная либо меняет знак с - на +, либо равна 0 (ну, будем считать, что меняет знак с - на + включает переход из 0 в положительное значение). То есть изначально интересные точки - [2, 5, 11, 14]. В точке 2 производная набирает 10 очков, в точке 5 их теряет, в точке 11 теряет ещё 10 очков, а в точке 14 набирает 10 очков. (очки - скорость роста).
Значит, таких линий всего может быть 100. Пройдёмся сканлайном по их интересным точкам,и найдём минимальное значение количества деревьев. Проглядеть минимум мы не могли так как он находится только в интересных точках. Сканлайн нужен, чтобы мы могли, зная значение производной, предсказать сколько же будет деревьев в следующей интересной точке.
Итого на строчку уходит 400 log(400) на сортировку интересных точек + 400 на проход по ним + 400 на заполнение массива перед сортировкой.
Получаем 400 (log(400) + 2) 10^5 = 4000 10^5 = 4 10^8.
Ну хуй знает.
И тут возникает идея - нам по сути можно перенести идею с производными на двумерное пространство.
Тогда нужно всего-лишь понять, какое множество точек для парка является интересным. Нарисуй в 3D как оно будет выглядеть - я вижу, что сверху, слева, внизу, справа это будут тупо плоскости наклонные, (как раскрытая коробка), а вот по углам контур интересных точек я не могу представить. нужна бумага уже.
Тогда идея такая - у каждого парка будет 10^5 20 интересных точек. Каждую из них можно проверить за 100 (тупо пересекаем со всеми парками и смотрим сколько деревьев), получается 10^5 20 100 = 2 * 10^8.
Мб как-то можно сократить множество проверяемых парков какими-нибудь тупыми корзинками по координатам.
Хотя, 100 миллионов это слишком дохуя для OJ, есть подозрение, что тут нужно что-то более хитровыебанное, либо тебе повезёт и на их тестах оно пройдёт. Хотелось бы увидеть правильное решение, ну ты попробуй, вдруг прокатит.
Кажись, придумал решение, которое влезает всегда в TL.
Забудь про вторую идею с коробкой. Итак, для каждой строчки у нас есть набор интересных точек, их не более 400. Объединим интересные точки всех строчек. Их опять будет 400. Бинго! То есть мы можем из 10^5 столбцов оставить 400.
Теперь проведём такой же финт, но со строчками. Теперь у нас матрица 400 на 400.
После этого нам только нужно быстро уметь находить количество деревьев в данной точке. Просто для каждого прямоугольника проставляем правильное значение производной для каждой интересной точки - 400, а потом сканлайн за 400.
Получается, каждую строчку мы пробегаем за 800, строчек 400 - ответ за 320,000. Должно влезать в любой таймлимит теперь.
Забудь про вторую идею с коробкой. Итак, для каждой строчки у нас есть набор интересных точек, их не более 400. Объединим интересные точки всех строчек. Их опять будет 400. Бинго! То есть мы можем из 10^5 столбцов оставить 400.
Теперь проведём такой же финт, но со строчками. Теперь у нас матрица 400 на 400.
После этого нам только нужно быстро уметь находить количество деревьев в данной точке. Просто для каждого прямоугольника проставляем правильное значение производной для каждой интересной точки - 400, а потом сканлайн за 400.
Получается, каждую строчку мы пробегаем за 800, строчек 400 - ответ за 320,000. Должно влезать в любой таймлимит теперь.
Не понял как это сделать. Что из верхнего описания ты выкинул, а что оставил?
Оставил подсчёт количества деревьев через производные. Выкинул перебор ненужных 10^5 строчек, оставив только 400.
Вот код на питоне
http://ideone.com/b17P6I
По крайней мере на вариантах до 100 ответ совпадает с тупым перебором.
Ого даже код написал. Спасибо. Щас сам попробую.
Пацаны, кто-то следил за полуфиналом? Вот standings:
http://neerc.ifmo.ru/information/standings.html
А как понять, кто прошел в финал?
http://neerc.ifmo.ru/information/standings.html
А как понять, кто прошел в финал?
Пусть A = {1, 2, ..., n}. Найти максимальное по мощности A' ⊂ A такое, что A' не содержит x и y таких, что x = 2y.
Забыл еще:
Если максимальных по мощности подмножеств несколько, вывести любое из них.
Время полиномиальное.
Ну давай подумаем в двоичной системе.
Если есть число XXXX, то нельзя чтобы было число XXXX0, при этом XXXX00 можно.
То есть для любого числа XXX мы выводим XXX XXX00 XXX0000, удваивая число нулей на конце. при этом начинать с XXX0 не имеет смысла так как, если начать с XXX, мы получим больше чисел - раньше вылезем за N.
Значит, алгоритм такой: для каждого нечётного числа выводим x, x 4, x 16, x * 64, ...
Так как каждое число мы просмотрим максимум один раз, сложность O(n)
http://ideone.com/BWwyTO
Да, я так же решил.
Дано дерево, у каждого ребра некоторый вес. Поступают запросы
1) Изменить вес ребра между u и v
2) Найти максимальное ребро на кратчайшем пути между вершинами u и v.
Давайте представим, что про HLD мы не знаем.
1) Изменить вес ребра между u и v
2) Найти максимальное ребро на кратчайшем пути между вершинами u и v.
Давайте представим, что про HLD мы не знаем.
Есть какой-нибудь учебник по олимпиадным задачам?
бамп
Билли Бонс положил в сундук некоторое количество золотых монет. На второй год он вынул из сундука сколько-то монет. Начиная с третьего года, он добавлял столько монет, сколько было в сундуке два года назад.
Требуется написать программу, которая определит, сколько монет было в сундуке в первый и во второй года, если в X-м году там оказалось ровно Y монет.
Входные данные
Входной файл содержит натуральные числа X и Y (3 ≤ X≤20, 1≤Y≤32767).
Выходные данные
В выходной файл выведите через пробел количество монет в первый и второй года. Гарантируется, что решение задачи всегда существует.
Как ее решить?В душе не чаю.