Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 2 задач <---
Источники --> Личные олимпиады --> Индивидуальная олимпиада по информатике и программированию (ИОИП)
    Заключительный этап 2009(4 задач)
    Заключительный этап 2010(4 задач)
    Заключительный этап 2012(4 задач)
    Заключительный этап 2013(5 задач)
    Заключительный этап 2015(5 задач)
Страница: 1 Отображать по:
#111114
Волшебные грибы
  
Темы: [Хеш]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

На планете Руук существует Большая Корпорация Маленьких Фей. Одним из видов деятельности, которым испокон веков занимаются ее сотрудницы, является посадка грядок с волшебными грибами. Каждый день, начиная с самого первого дня существования этой корпорации, феи создают одну новую грядку грибов. После этого с новой грядки два дня можно собирать споры, которыми размножаются эти грибы, а потом грядка будет поставлять уже только сам продукт — грибы.

Таким образом, если обозначить количество грибов, посаженных на грядке, созданной в день номер i, как ci, то оно будет считаться по формуле ci = ci - 1 + ci - 2. Так, в первый и второй дни было посажено по одному грибу, в третий — два, в четвертый — три, в пятый — пять и так далее.

Волшебные грибы являются самыми ценными сувенирами, которые путешественник может привезти с планеты Руук. Поэтому первым, что делает любой приезжий, становится поиск грядки с волшебными грибами. Однако, в последнее время все чаще стали появляться сообщения о поддельных волшебных грибах. Тщательное расследование показало, что это является следствием действий Маленькой Корпорации Больших Фей, которая сажает грядки с грибами, внешне не отличимыми, но далеко не такими ценными, как волшебные. Причем, создавая очередную грядку, эти феи сажают туда такое количество грибов, какое их соперницы никогда не сажали и не смогут посадить.

Казалось бы, после выяснения этого факта отличать волшебные грядки от поддельных стало просто. Но обе корпорации существуют достаточно давно, количество грядок и грибов на них давно превысило все разумные пределы. Вас попросили написать программу, по количеству грибов на грядке сообщающую, является ли эта грядка волшебной.

Входные данные

Первая строка входного файла содержит одно число N (1 ≤ N ≤ 1000000) — количество исследуемых грядок. Следующие n строк содержат по одному целому числу ai — количества грибов на исследуемых грядках. Размер входного файла не превышает 1 Мб.

Выходные данные

Для каждого числа, данного во входном файле, выведите «Yes», если грядка с таким количеством грибов является волшебной, и «No» — если не является. Ответы разделяйте переводами строк.

Примечание

Решения, работающие для чисел, не превышающих 263 - 1, будут оцениваться из 30 баллов.

Решения, также работающие для входных данных, не превышающих 15 килобайт, будут оцениваться из еще 30 баллов.

Примеры
Входные данные
8
1
2
3
4
5
6
7
8
Выходные данные
Yes
Yes
Yes
No
Yes
No
No
Yes
#111582
Гарри Поттер и Зал Пророчеств
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Отряд Дамблдора готовится к полёту в Отдел Тайн Министерства Магии. Так как на их пути за Пророчеством могут встретиться слуги Волан-де-Морта, Гарри с Невиллом решили потренироваться в дуэльных боях.

Они решили провести \(n\) раундов дуэли, а после каждого раунда выпивать восстанавливающее зелье, чтобы не тратить лишних сил. Всего у ребят \(2n\) зелий. После каждого раунда дуэли они выбирают два наиболее близких по мощности восстанавливающих зелья. Из нескольких таких пар они выбирают ту, у которой сумма мощностей наибольшая. Затем Невилл выпивает более мощное зелье из пары, а Гарри - менее мощное.

Помогите Гарри с Невиллом определить, какие зелья и в каком порядке выпьет каждый из них.

Формат входного файла

Первая строка входного файла содержит одно целое число \(n\) (\(1 \le n \le 100\,000\)) - количество раундов дуэли. Во второй строке входного файла содержится \(2n\) целых чисел \(a_1, a_2, \ldots, a_{2n}\) (\(1\le a_i \le 10^9\)), где \(a_i\) - мощность \(i\)-го восстанавливающего зелья.

Формат выходного файла

В первой строке выведите \(n\) чисел - мощности зелий, которые выпьет Невилл. Во второй строке выведите \(n\) чисел - мощности зелий, которые выпьет Гарри. Зелья надо выводить в том порядке, в котором Невилл и Гарри должны их выпивать.

Примеры
Входные данные
1
3 6
Выходные данные
6
3
Входные данные
2
11 43 56 22
Выходные данные
22 56
11 43
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест