2 2010-07-26 15:42:56
Re: timus 1609 (2 ответов, оставленных в Problems)
Эту задачу можно сдать, нарисовав все возможные доски на листочке и для каждой найти ответ. Нужные нам замощения имеют закономерность, поэтому этот процесс не должен занять много времени. К тому же, возможно полезным окажется тот факт, что лишь для доски 10*10 ответ - 5 доминошек, а для всех остальных досок ответ 4 и меньше.
3 2010-02-13 14:35:31
Re: Задачи по теории чисел, по-моему (2 ответов, оставленных в Problems)
1) Cовершенных чисел найдено совсем немного, поэтому тут можно забить массив констант из нескольких чисел. Как видно из http://www.research.att.com/~njas/sequences/A000396 уже 9-ое совершенное число существенно превосходит 5*10^18.
2) Лишь для чисел 31, 37, 47 ответ превышает 6*10^6. Для остальных чисел можно найти ответы перебором. Для трех чисел, для которых перебор ответа не найдет, легко можно найти ответы вручную. Достаточно воспользоваться тем фактом, что если число А представимо в виде A=p1^a1*p2^a2*...*pk^ak, то A имеет ровно (a1+1)*(a2+1)*...*(ak+1) делителей. Как выше заметил KADR, числа p1, p2, ..., pk должны быть последовательными простыми числами, причем p1=2, если мы хотим добиться минимальности ответа.
4 2009-09-15 18:45:08
Re: Задача с 5-ого Открытого Кубка (10 ответов, оставленных в Problems)
Спасибо всем за идеи.
5 2009-09-11 22:52:38
Re: Задача с 5-ого Открытого Кубка (10 ответов, оставленных в Problems)
А если я конечно эту задачу понял верно, то ответ существует только для 5.
Это неправильная идея. Я первый сабмит сделал именно таким образом Итог - WA.
По поводу идеи со сферой ничего не могу сказать о правильности. Надо будет попробовать закодить, хотя там мне не все понятно.
Есть ли у кого-то еще идеи?
6 2009-09-10 20:52:54
Тема: Задача с 5-ого Открытого Кубка (10 ответов, оставленных в Problems)
В 5-ом открытом кубке на Гран-При Двух Столиц (ссылка на условия: http://acm.math.spbu.ru/~snark/files/oc … oblems.pdf) предлагалась следующая задача (Problem A на контесте):
Построить из N точек строго выпуклый 4-ехмерный многогранник, у которого любые две вершины соединены ребром, либо определить, что это невозможно. (1<=N<=10)
Кто знает как решать, или решил эту задачу, пожалуйста, поделитесь своими идеями.
7 2009-08-26 23:32:52
Re: [acm.timus.ru 1705] Зайцы-бандиты (Gangster Hares) (4 ответов, оставленных в Problems)
На самом деле существует формула, по которой можно вычислить ответ. Я нашел ответы для всех чисел от 1 до 10000, потом для всех ответов посчитал разность между корнем (целая часть) и ответом, а затем четко прослеживается закономерность.
Вот код (нахождение ответа для заданного n):
long long q=S(n); //S(x) = (int)sqrt(x), сделано из-за возможного переполнения, то есть это своя функция нахождения корня
long long plus; //разность ответа и корня
if ((q+1)*(q+1)-(q+1)<=n) plus=S((q+1)*(q+1)-n-1)+1; else
{
long long x=S(q*(q+1)-n);
if (x*(x+1)<q*(q+1)-n) plus=x+1; else
plus=x;
}
Естественно этот код можно еще сократить