В связи с тем, что у многих возникли проблемы с квалификационным раундом (особенно со второй задачей), хочу провести здесь разбор задач.
1. Double Squares
0 <= X <= 2147483647
1 <= N <= 100
Хотя реально было N=20...
Можно написать функцию, которая возвращает количество пар неотрицательных целых чисел, сумма квадратов которых равна X.
Заметим, что каждое из этих чисел не больше чем [sqrt(X)]. Тогда будем пробегать (i) от 0 до [sqrt(X)] (это будет первое число) и смотреть, является ли число sqrt(n-i*i) (это второе число) полным квадратом. Если да, то ans++.
Сложность получается O(sqrt(n)).
На самом деле достаточно быстро работает и лобовое решение, то есть такое:
i: 0..sqrt(n)
j: 0..sqrt(n)
if (i*i+j*j<=n) ans++;
2. Peg Game
В этой задаче насколько я понял основные проблемы с пониманием условия... Итак расскажу его.
У нас есть некоторая карта, по которой может скатываться шарик сверху вниз. Шарик может перемещаться только по клеткам, обозначенным точками. Если под шариком оказывается x , то шарик скатывается либо влево, либо вправо с равной вероятностью. Если слева или справа нет точки, то шарик может скатываться только в одну сторону, туда, где находится точка. Если под шариком точка, то шарик просто падает.
То, что шарик точно скатится вниз из данной позиции, обеспечивает то, что карта представлена не более чем как шахматная доска, причём возможно даже уменьшение количества точек, куда невозможно пойти.
Карта размером n x m
x.x.x.x.x
x.x.x.x
x.x.x.x.x
x.x.x.x
x.x.x.x.x
представляется как n рядов, каждый нечётный ряд имеет длинну 2*m-1, каждый чётный ряд длины 2*m-3, при этом первая позиция чётного ряда стоит под второй позицией нечётного ряда.
Рассмотрим пример (числами обозначены вероятности, что шарик окажется в данном месте):
по маске
x.x.x.x.x
x...x.x
x...x.x.x
x.x...x
x.x.x.x.x
x 1 x x x x
x 1 x x x
x 1 x x x
x 1 x x
x 0,5 x 0,5 x x x
спуск с другого места...
по маске
x.x.x.x.x
x...x.x
x...x.x.x
x.x...x
x.x.x.x.x
x x x 1 x x
x x 0,5 x 0,5 x
x 0,25 x 0,5 x0,25 x
x0,125x0,1250,50,25x
x0,0625x0,125x0.6875x0,125x
Кажется были вопросы с сэмплом 1:
5 4 0 1 2 2
по маске
x.x.x.x
x.x.x
x.x...x
x.x.x
x.x.x.x
Рисуем каждый случай падения шарика сверху...
x 1 x x x
x 1 x x
x 0,5 x 0,5 x
x0,75 x0,25 x
x0,375x 0,5 x0.125x
x x 1 x x
x 0,5 x 0,5 x
x0,25 x0,250,5 x
x0,375x0,625x
x0,1875x0,5 x0,3125x
x x x 1 x
x x 1 x
x x 1 x
x x 1 x
x x 0,5 x 0,5 x
Как видим, самое выгодное, чтобы на 0-ое свободное место пришёлся шарик, при выпуске шарика с 0-го прохода. Тогда вероятность оказаться ему в 0-ом месте последнего ряда равна 0,375.
Касательно реализации: тупо реализовать. Можно представить данный массив как такой массив (я делал так):
x.x.x.x
x.x.x
x.x.x.x
x.x.x
x.x.x.x
Ставим в одну из верхних позиций шарик (т.е. в одной из позиций он оказывается с вероятностью 1). Обрабатывать строки одну за одной сверху вниз, слева напарво, например. Вероятность попасть шарику в текущую пустую ячейку равна сумме ячейки сверху, ячейки сверху слева, поделённую на 2 и ячейке сверху справа, поделённую на 2. Если какая-то ячейка содержит препятствие, то её мы не прибавляем. Если какой то ячейки не существует, мы её тоже не считаем (это может возникнуть, когда мы стоим у края нечётной строки - когда крайний штырёк удалён, то такая ячейка не будет иметь одного верхнего левого или правого соседа (его просто нет на карте)).
Выпускаем из каждой свободной ячейки сверху шарик, и смотрим откуда самое выгодное.
3. Studious Student
Когда-то мне встречалась такая задача... где - не помню.
В данной задаче нужно просто посортить массив слов, но с таким условием: a+b<b+a вместо a<b.
Рассмотрим 4-ый пример из условия:
5 jibw ji jp bw jibw
слова jibw ji должны распологаться именно в порядке jibw ji, а не ji jibw. Правильный порядок даёт условие a+b<b+a, a<b - неправильный.
Старался понятно объяснить. Если есть вопросы - пишите, отвечу.
Comments (0)
