Добрый день.
Сегодня пройдёт ещё один раунд по правилам codeforces. Автором сегодняшнего контеста являюсь я. Раунд помогали готовить Артём Рахов и Мария Белова. Большое спасибо им и всем борцам фронта codeforces!
Желаю всем удачи и весёлых хаков!
P.S: В связи с проблемами работы сервера раунд признан нерейтинговым. Приносим извинения всем участникам. Подробности в теме по этой ссылке.
Этот контест только для первого дивизиона?
В чём смысл такого контеста?
Если честно, я точно не знаю=)
Вполне возможно он для обоих дивизионов. Надо будет спросить Артёма. Извиняюсь за своё незнание...
почему только для 1 ?
в списке зарегистрированых много людей с 2-див, вывод: етот контест для всех :)
Думаю вы правы.
Сейчас заредактирую пост, пока толпа недовольных с факелами не собралась=)
Может, на всякий случай, задачи в pdf выложить?
Может быть, коли сервер не справляется с разщовым наплывом, чуть поменять правила: или выкладывать задач за 10-15 мин. до начала отсчета, или штраф начислять начинать не с первой минуты, а с11-ой или м 16-ой. Суть не изменится, зато "низкий старт" ровно в 19:00 будет уже не столь актуален, наименее нервные и наиболее уверенные в себе задерждатся на минутку-другую - глядишь, и сервер выдюжит.
Indeed, I don't seem to appear on the registration list, but I must have been registered or that pop-up wouldn't have appeared, right?
And I see a typo on the Score Table on the problems screen. "Successfull" and "Unsuccessfull" should each have only one "l" at the end.
Consider a single building: either you destroy it with some probability p, and you still have to destroy k-1 building, or you don´t destroy it(with a probability 1-p) and you still have to destroy k buildings. You can implement it using memoization for an O( n*k ) solution( with R fixed). That's why you see people talking about binary search + dp: you do bsearch over R.
cannot submit the code
cannot challange others
cannot watch the standing
only i can do ... goto bed at once ...
Just to init an array with length 260 or more.
One more thing,
in problem B, if i use printf("%lld\n",ans) it gives me wrong answer but accepts when i use cout<<ans.
Why?
With one test case per file cin/cout would be a better option :D.
The great problem was that "%lld" did not work properly on the server (GCC). I was not aware of this problem (on my computer it works well). This difference caused a lot of hacks in B. Sorry for that...
Though even is "%lld" worked properly the number of int64 hacks would be huge=(
вероятность одного - 2/3, другого - 1/4.
Какова вероятность, что хотя бы одного событие произойдёт?
Ответ: 1 - (1/3 * 3/4)
Доказательство: вероятность того, что оба события не произойдут равна 1/3 * 3/4.
У меня и у товарища Shtrix времена сдачи всех трех задач совпадают с точностью до минуты. И мы были в одной комнате. Прикольно)
I use Greedy + Binary Search, but it seems DP + Binary Search.
and test 10 for problem D please,thanks
okay....enough talk of server being busy...
can anyone point me my mistake for Problem B:
#include<vector>
#include<map>
#include<string>
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main()
{
map<char,long long > c;
unsigned long long int ans;
long long int j;
string s;
cin>>s;
j=0;
while(s[j]!='\0')
{
// if((s[i]<='z'&& s[i]>='a')||(s[i]>='0' && s[i]<='9'))
c[s[j]]++;
j++;
}
ans=0;
for(map<char,long long int>::iterator i = c.begin();i!=c.end();i++)
{
//printf("%d ",c[i]);
ans+=(*i).second*(*i).second;
}
printf("%llu",ans);
scanf("%*d");
return 0;
}
UPD: это не ошибка вывода 64-битных чисел. изменение printf("%lld") на cout или printf("%I64d") дает все тот же wrong тест 4.
http://codeforces.me/contest/50/standings/2
253 Prabhu
задача A
338 / 00:56
00:44:02 Неправильный ответ на претест 2 [претесты]
00:56:30 Полное решение [финальные тесты]
01:30:27 Неправильный ответ на претест 1 [претесты]
UPD: А, торможу... Тогда странно, что синим цветом выделяет.
Я просто заметил, что почему-то посылку выделило синим в таблице.
Видимо проблема в
<span class="cell-accepted">338</span> (у Prabhu)
<span class="cell-passed-system-test">336</span> (у пользователя ниже)
Т.е. неверно определён класс ячейки у тех, кто посылал решения, после посланного верного, которые не прошли претесты.
UPD: либо тут что-то более хитрое...
P.S In WinGW you must use %I64d for long long and double instead of long double.
По D использовал 60 итераций бинпоиска, а для AC надо было использовать 62!
Что видно по куче хаков по задаче Б и прочем. Все никак не заставлю себя вообще нигде не жадничать)
I thought about octagon at the contest and used 8 points.
First of all let's prove, that if the root is not integer, it's unique (that is, it can appear only once):
Let x = -b + sqrt(d). In case x is also a root of another equation, there exists such u and v, that x = -u + sqrt(v). Then b - u = sqrt(d) - sqrt(v). That means, that difference between two square roots is integer, however one can prove that it is only possible when d and v are full squares, which isn't true (according to our assumption).
Now if x is not integer, then let's check if it can be root of some equation.
Since all roots are negative, for given x, we try to find negative y that
x+y >= -n
x*y <= m
Apparently such y can be 1 for odd x and 2 for even x.
Howerver, If you would started the description like.
"Vasja is playing a game. In this game he has to drop..."
It would be much more appropriate.
В задаче С по ходу выпуклая оболочка не нужна. Там ответ
( maxx - minx + maxy - miny ) * 2 - ( maxx + maxy - maxs ) - ( mins - minx - miny ) - ( maxx - miny - maxd ) - ( mind - minx + maxy )
Где maxx, maxy, minx, miny - максимальные и минимальные координаты соответственно, а maxs, mins, maxd, mind - максимальные и минимальные сумма и разность координат соответственно. Все максимальные надо потом увеличить на единицу, а минимальные уменьшить.
Там еще все сокращается и ответ получается maxs + maxd - mins - mind.
в худшем случае можно обойти 8-угольником
Но на контесте я написал вот такую формулу (с abs), чтоб не париться
2*(ymax-ymin+xmax-xmin+2)-(abs(dmin-xmin+ymax)+abs(dmax-xmax+ymin)+abs(smin-xmin-ymin)+abs(smax-xmax-ymax))
//#include is important to solve this problem be carfull to this]