В связи с тем, что у многих возникли проблемы с квалификационным раундом (особенно со второй задачей), хочу провести здесь разбор задач.
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 - неправильный.
Старался понятно объяснить. Если есть вопросы - пишите, отвечу.
ps. и да, ни в коем случае не std:string!!!
Во второй, можно 1.0 поставить снизу, и динамику делать снизу вверх.
А потом выбрать максимум из первой строки.
Да, так и делал, но что-то у них там с чекером не так...вывел 6 знаков после запятой, не приняли...
в первой нужно количество неупорядоченных пар, поэтому оба решения надо поправить, например, так:
будем пробегать (i) от 0 до [sqrt(X)] (это будет первое число) и смотреть, является ли число (n-i*i) (это второе число) полным квадратом, не превосходящим i*i.и вот так:
i: 0..sqrt(n)
j: i..sqrt(n)
if (i*i+j*j<=n) ans++;
Я рассказал общую идею решений. Я решал этот вопрос делением на 2 полученного ответа.
Эм.. нет. На тесте 2 у меня всё правильно :)
Вот мой код:
int n,t,x;
cin>>n;
for (int i=0;i<n;i++){
cin>>x;
int ans=0;
int s=(int)(sqrt((double)x)+EPS);
if (s*s>x) s--;
for (int j=0;j<=s;j++){
int ss=x-j*j,sss=(int)floor(sqrt((double)ss)+EPS);
if (sss*sss==ss){
ans++;
}
}
ans=(ans+1)/2;
cout<<ans<<endl;
}
Но вообще, подход к разбору у вас примерно такой же, какой у организаторов подход к контесту :)
Кстати, посты можно редактировать, в отличие от комментариев ;) .
Edit: Ой, да, и комментарии тоже можно ж уже.
i: 0..sqrt(n)
j: 0..sqrt(n)
if (i*i+j*j<=n) ans++;
Ну ведь да же.
Ну я таже не писал как мы инициализируем ans. А ещё я перепутал n и x.
Мне кажется то, что я привёл - это не код, а объяснение, ведь если бы я стал писать тоже самое словами вы бы не сказали что это код, тем не менее такое объяснение расползлось бы на много-много баковок.
Почему все так придираются по написанному разбору? Говорят, что не указано то и то.
По-моему не было задано ни одного вопроса касательно идеи - значит либо человеку и так не интересно узнать решение, либо всё понятно. Вопросов вида "я тоже придерживался этих идей, но у меня всё-равно получились не правильные ответы" тоже не было задано, значит видимо опять же либо не интересно, либо это и так не требуется, то есть это всем понятно.
Так для кого же тогда нужно писать тонкости реализации, которые, имхо, даже начинающий прогер сам в состоянии увидеть? Для тех, кто и так решил эти задачи?
Если уж на то пошло, по поводу разборов двух других задач вот что:
2.
Картинки хорошие и понятные, но.
"Вероятность попасть шарику в текущую пустую ячейку равна сумме ячейки сверху, ячейки сверху слева, поделённую на 2 и ячейке сверху справа, поделённую на 2."
Это же неверно, разве нет? Если ячейка сверху слева или ячейка сверху справа — крайняя, то её надо учесть, не деля на 2. В картинках так и сделано.
По самой задаче — ещё мне интересно, какую позицию надо выбирать, если получилась одинаковая максимальная вероятность при вбрасывании из двух различных позиций. Условие по этому поводу уже не посмотреть (в лучших традициях)...
3.
Разбор понятен, но можно сделать его лучше. А именно: возникает вопрос, почему это работает. Такое решение — это полезный приём, причём он в разы полезнее, когда понимаешь, почему он работает. Тогда резко возрастают шансы применить его правильно в следующей задаче — вместо того, чтобы написать с мыслью “вероятно, это и здесь работает” и потом, пока задача не проверится, отвлекаться, гадая, действительно ли это так.
По первой промолчу, своё мнение высказал не раз.
2. А это что тогда?
Если слева или справа нет точки, то шарик может скатываться только в одну сторону, туда, где находится точка.
Ну уж извините, что не выложил условия. Никогда не видел, чтобы условия выкладывались в разбор. Там чётко сказано, что вывести любой ответ.
(то, что условия посмотреть нельзя, очевидно, не ваша вина, а организаторов контеста, это была не придирка :))
В разборе есть несколько частей: условие, разбор одного примера, разбор другого примера, часть о реализации. Ты считаешь, что в части о реализации не нужно учитывать детали условия? Я считаю, что нужно — алгоритм изложен словами достаточно чётко, чтобы это сделать. Хотя бы упомянуть, что в этом месте нужно доделать.
Во-первых, потому, что в готовой работающей программе эти детали должны быть учтены, а часть о реализации ближе всего к готовой программе.
Во-вторых, потому, что, читая разбор на четыре страницы, можно к четвёртой странице успеть забыть детали первой.
В-третьих, потому, что удобно было бы, если бы разбор можно было читать по частям. Если интересна реализация, читать только про реализацию; если нужно понять на сэмплах — читать разбор примеров, и так далее. И хорошо бы каждая часть по отдельности несла всю нужную информацию.
"По самой задаче" — это не претензия к разбору, а вопрос в ответ на "Если есть вопросы - пишите, отвечу." в конце поста. Ну я уже разобрался.
Такое впечаление что это писал работник фэйсбука...
Квалификационный раунд, анонсированный официально Хабром завершился успешно
Результаты раунда говорят о 5846 игроках, прошедших в первый онлайн тур.
Участникам квалификационного раунда предлагалось 3 задачи, для прохождения достаточно было правильного решения любой из них.