Привет всем из солнечного Петрозаводска!
Сегодня я и мой брат sdya подготовили для вас несколько интересных задач. Из-за плотного графика на петрозаводских сборах, особенно из-за рафтинга и просмотра аниме ночами напролет, у нас было немного времени на написание длинных условий задач. Так что наслаждайтесь короткими условиями и изобретайте легенды на ваше усмотрение :)
P.S. Удачного всем и во всех смыслах контеста!
Используйте несколько календарей. :-)
У меня пропала кнопка отмены регистрации. Зарегистрировался на сегодняшний раунд и только потом вспомнил что на это время назначены важные дела.
Просто когда участвую не нравится что половина комнаты забила, не хочу быть одним из таких участников.
The "lock" icon disappeared.
Для каждого x находить все делители. смотреть когда каждый делитель появлялся последний раз. Если попадает в диапазон , то +1 к ответу, потом обновить для делителя время когда на него что-то делилось в последовательности.
Из первых четырёх задач дольше всего думал над B, которую и написал последней. Есть решение проще, чем для каждого делителя построить список чисел, его содержащих, и потом разбираться с каждым делителем в отдельности?
И почему я это придумывал минут двадцать реального времени?)
Wrong comment
http://www.codechef.com/SEPT11/problems/SHORT
For the case 18 4.
Why is 6 not a solution, it does not divide any of 14,15,16,17 . Or did I miss something miniscule.
Thanks.
Usually authors write special program - checker, that checks your answer, using input and jury output for this test. Moreover, sometimes checker program can be much more difficult then solution.
UPD вопрос снят
Думать дальше мне было лень, но это уже походило на что-то выполнимое по времени, поэтому я запустил это на своём компе, и минут через 10-15 получил ответы для всех возможных тестов, ведь их не так и много.
очевидно что нас в текущий момент интересует только последний и предпоследний столбец.
Я хранил две маски: то, с каких клеток не будут двигаться и те которые еще не ушли с клеток, хотя клетка должна быть свободна. И переходы (i,m1,m2) - (i+1,m3,m4) m4 определяется по m1,m2,m3. Не особо оптимизил по времени, вышло: O(n*2^(3*n)) если чуть-чуть переписать, то будет: O(n*3^n*2^n).
Ну и небольшой комментарий к решениям: N <= 6, так как мы можем спокойно повернуть поле, если это не выполняется.
Самое лучшее что можно написать это наверное: O(N*M*2^(2*N)) N<=M.
Did I miss something or it is a mistake in author's solution?
OOOX
XOOO
OOXO
X - spots, where all the spiders ends up, you can reach an X from any square.
(1,3)
(2,1)
(3,4)
(4,2)
(numbering starts from1 )
Thanks Seyaua and sdya for problems :)
Для перехода перебирал двоичную маску где останутся пауки. Сложность O(N*(3^M)*(2^M))(N>=M).
Any one else didn't see the n.m<=40 constraint in C DIV-1?
1.first rotate the grid such that smaller side remains at top, which is of length <= 6. (sqrt(40)).
2.then try all possible subsets (2^6).
3.any particular state is given by settled spiders in curr. row and prev row. and the curr row number.
4.Easy if you have solved similar problems previously.
Быстрее можно, если, например, предпросчитать результаты функций, аналогичных операциям битовым AND, XOR и тд. для небольших чисел. И для работы с большими числами разбивать на меньшие делением на степени тройки.
the timer should be started as a problem is opened or at least when someone enters the contest area!
But seriously, I don't get what isn't fair - that's the rules of this competition. It's like arriving late to a rock star concert and complaining afterwards that he started before you arrive. The advantages and disadvantages of particular format (CodeForces/ACM/TopCoder/IOI etc.) is another topic.
Sorry if I misunderstood your post.
для m=1: ans = k^n
для m=2: нужно посчитать кол-во способов покрасить первый столбец в Т цветов и второй в Т цветов(причем использовать все Т цветов нужно), и для каждого Т их перемножить.
для m>2: у нас первый и последний столбец должны содержать одни и те-же цвета, а посередине цвета которые использовались по краям, но не обязательно все.
Получил ВА на претесте 4, видел что не у одного меня такой ответ на него выдавало. ЧТо не правильно?
Если покрасить доску 2x2 следующим образом:
12
23
то условие выполняется, хотя множества цветов слева и справа не совпадают.
122
223
Честно говоря, отсутствие возможности запустить код на сервере довольно сильно помешало (использовать то, что за WA1 баллы не снимаются, на контесте я не догадался :)). У меня локально работало примерно 7 секунд, а во всех задачах разница по сравнению с серверами CF была как минимум вдвое. Но не в этой...
Простите за глупый вопрос, но в див.2 в задаче А, как можно было коротко поменять все буквы скажем на нижнего регистра? Просто я не понял как такое организовать и написал цикл с кучей ифов и вещей а-ля 'A'='a'
как вариант можно использовать такое условие, когда проходитесь по строке.
if (s[i]>='A' && s[i]<='Z')
s[i]=s[i]-'A'+'a';
а так есть ещё встроенные функции. например в с++ функция tolower(s[i]);
It's always priceless to see these kind of comments.
?detaR tI sI