May 27th, 2012

Интересно, это они…

Интересно, это они специально в фейсбуке кнопку Share в своем мобильном клиенте не делают? Это ж core feature для соцети, типа их же лайка (он есть). Походу не разобрался, как видеть все посты, которые я лайкнул. Такого списка нет в интерфейсе?


Появится пара часов…

Появится пара часов свободных. Сегодня бы сумку куда-нибудь бросить на несколько часов, чтобы плечо не отдавила. В Питере реально найти в центре какое-то подобие камеры хранения?


Уже полчаса идет олимпиада…

Уже полчаса идет олимпиада по программированию RussianCodeCup 2012. За первые полчаса пришло 462 сданных решения, первую задачу сделал первым Егор Куликов за 2:08, третью задачу сделал первым Капун Евгений на 16-й минуте, на 18-й минуте пришла вторая задача от Максима Иванова.


Задача №1 из Russian Code Cup.…

Задача №1 из Russian Code Cup. Первое правильное решение сдано за 2:08 с момента открытия задачи на сайте.



«Вопреки известной поговорке «спички детям не игрушка», один мальчик очень любит играть со спичками. Но он не балуется ими, не разжигает огонь, а решает различные головоломки. Например, он умеет приравнивать число девять к числу одиннадцать, переложив только одну спичку.



Недавно родители этого мальчика подарили ему несколько наборов, каждый из которых состоит из двенадцати спичек. Мальчик начал собирать из них различные геометрические фигуры. Он уже собрал много различных фигур, но теперь ему стало интересно: из каких наборов возможно склеить каркас параллелепипеда при помощи двенадцати спичек из набора и клея? Ломать спички нельзя и ни одна из спичек не должна выступать за каркас.



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



Входные данные содержат не более тысячи строк, каждая из которых содержит в себе описание набора спичек — двенадцать целых положительных чисел не превышающих 109. Ввод заканчивается строкой, состоящей из двенадцати нулей, — этот запрос обрабатывать не нужно.



Для каждого набора спичек выведите «yes», если из него возможно склеить каркас параллелепипеда, и «no» в обратном случае.



К примеру, при входных данных

1 1 1 1 2 2 2 2 3 3 3 3

1 1 1 1 2 2 2 2 3 3 3 4

0 0 0 0 0 0 0 0 0 0 0 0



вывод должен быть такой:

yes

no

»


Задача №2, посложнее:…

Задача №2, посложнее: «Перестройка». Первое правильное решение засабмичена Максимом Ивановым на 18-й минуте раунда. Вот она:



«В некоторой стране было ровно n городов и m дорог между ними. При этом в этой стране дорожная система была устроена следующим образом:



* между любыми двумя городами не больше одной дороги;

* никакая дорога не соединяет город с самим собой.



После смены власти новое правительство решило провести ряд реформ, среди которых есть реформа, затрагивающая дорожную систему страны. Эта реформа состоит из двух пунктов:



* разрушить одну из существующих дорог;

* построить новую дорогу, которой раньше не было, не ведущую из города в

него же.



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



Теперь правительство задумалось о том, сколько существует способов провести реформу. Помогите ему.



Первая строка содержит два целых числа n и m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000). Следующие m строк содержат два числа ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — номера городов, которые соединяет i-я дорога.



Выведите одно целое число — количество способов провести реформу.



Например, при следующих входных данных

4 4

1 2

2 3

1 3

3 4



должно выводиться

8

»


Задача №3, тоже посложнее,…

Задача №3, тоже посложнее, «Война». Решена правильно Капуном Евгением на 16-й минуте.



«На одну маленькую нефтеносную страну было совершено нападение высокотехнологичной армии другой враждебной страны. Для защиты была мобилизована армия, состоящая из n солдат. Перед началом решающего боя все n солдат выстроились в шеренгу перед генералом. Он всегда считал, что все солдаты в его войске одинакового роста, однако это оказалось не так. Генерал понял, что такая армия малоэффективна, и решил разбить ее на подразделения. Под подразделениями генерал подразумевал непустые группы солдат, стоящих друг за другом в шеренге. Также генерал решил ввести понятие "мощность подразделения", которое определялось как:



* количество солдат в подразделении, если в шеренге они стоят в порядке невозрастания или неубывания их роста;

* 0 в противном случае.



Также генерал решил, что мощность армии равна произведению мощностей всех подразделений.



Генерал хочет найти такое разбиение армии на подразделения, чтобы мощность всей армии была максимальна. Помогите ему решить эту задачу.



Первая строка содержит целое число n (1 ≤ n ≤ 50000)— количество солдат. В следующей строке содержится n целых чисел ai (0 ≤ ai ≤ 109) — рост i-го солдата.



В первой строке выведете число k — количество подразделений, на которое генералу следует раздить шеренгу. Во второй строке следует вывести k чисел bi — номер в шеренге самого правого солдата в i-м подразделении. Числа надо вывести в порядке возрастания. Если существует несколько разбиений, то можно вывести любое разбиение.



Например, при следующих входных данных

5

1 2 3 5 4



нужно выводить

2

3 5

»


Хотя бы одну задачу Russian Code…

Хотя бы одну задачу Russian Code Cup сдали 553 человека (за 51 минуту турнира). Уже есть решение четырех задач от Епифанова Владислава. Принимают участие не меньше полутра тысяч человек.


Задача №5, Джавайское…

Задача №5, Джавайское оружие. Первым решил Кирилл Веденский на 24-й минуте. Вот ее задача:



«С древности у каждого джавая был набор из трех видов оружия: лазерный меч, лазерная сабля и лазерный ножик для намазывания масла на хлеб (вдруг джавай проголодается).



Но так как это оружие джавайское, а не простое, на длины входящих в набор предметов накладывались следующие ограничения:



* Длина ножика — d1, длина сабли — d2, длина меча — d3 должны быть простыми числами;

* d1 ≤ d2 ≤ d3;

* (d1 + d2)^2 − 1 делится на d3;

* (d2 + d3)^2 − 1 делится на d1;

* (d3 + d1)^2 − 1 делится на d2.



Компания “Dart Generics Industries” продает любой набор джавайского оружия по его номеру в лексикографическом порядке. А именно, упорядочим все джавайские наборы по неубыванию d1, при равном d1 по неубыванию d2, а при равных d1 и d2 по возрастанию d3 и пронумеруем их в этом порядке от 1 до бесконечности. Тогда по заданному k можно купить k-й набор в этом порядке.



Джавай Anykey хочет купить k-й набор. Подскажите ему размеры его оружия.



Первая строка содержит одно целое число k (1 ≤ k ≤ 60000).



Нужно вывести три упорядоченных по неубыванию размера оружий, входящих в k-й комлект.



К примеру, при входных данных

1



нужно выводить

2 2 3

»


Задача №5, "Этикетка".…

Задача №5, "Этикетка". Только что ее решил Епифанов Кирилл, тем самым взяв первое место в квалификации (решил все задачи быстрее остальных). Вот ее постановка:



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



Проблема заключалась в том, что эта цивилизация не пользовалась знаком переноса. Как только строка заканчивалась, чтение просто продолжалось со следующей строки. При расшифровке книг это не доставляло никаких неудобств, однако у этикетки есть существенное отличие от книги — этикетка наклеивалась на бутылку так, что получался цельный цилиндр, на котором по кругу был написан текст. При чтении текста следовало начать читать первую строку от места склейки, после достижения места склейки перейти на вторую строку, после этого на третью и так далее. Но ученым пока не удается определить место, где этикетка была склеена! Так что вместо текста пока имеется только набор строк одинаковой длины k, состоящих из букв и символов «.», которые использовались этой цивилизацией вместо пробелов.



К счастью, кроме самой этикетки имеется словарь, в котором перечислены все возможные слова, которые использовались этой цивилизацией. Теперь по этим данным вам необходимо определить, сколько существует вариантов местонахождения склейки. Более формально, вам необходимо определить, сколько существует неотрицательных значений t < k таких, что конкатенация всех данных вам строк, циклически сдвинутых влево на t символов, представляет собой набор слов из словаря, разделенных одним или несколькими символами «.». Кроме этого, вам необходимо также вывести все эти значения t.



Входные данные имеют следующий формат.



Первая строка содержит одно целое число m (1 ≤ m ≤ 2000) — количество слов в словаре. Следующие m строк содержат слова из словаря. Все слова различны, состоят только из строчных букв латинского алфавита, длина каждого слова не превышает 2000 символов.



Следующая строка содержит одно целое число n (1 ≤ n ≤ 2000) — количество строк, написанных на этикетке. Следующие n строк содержат слова строки, написанные на этикетке. Все эти строки состоят только из строчных букв латинского алфавита и символов «.». Длина всех строк одинакова и не превышает 2000 символов. Гарантируется, что в каждой строке содержится хотя бы один символ «.».



Выводить нужно в таком формате: В первой строке - одно целое число — количество значений t. В следующей строке - сами эти значения, разделенные пробелами и упорядоченные по возрастанию.



Например, при входных данных

2

uu

u

5

.uu..uu

.uu...u

...uu.u

.u.u.uu

uuu.uu.



нужно выводить

2

1 2

»


Не понимаю, почему при том,…

Не понимаю, почему при том, что абсолютно во всех ресторанах кормят в кредит по доверию анонимных людей, заправки в России до сих пор (кроме ВР) ре уют денег вперед. Ну уедет один, не заплатив - видео и заяву ментам, плюс копейка к цене за литр и проблем нет.