algoprog.kz

Ограничения в этой задаче $N \le 10^{2000}$.

Пусть длина $N$ равна n.

Для длины $k$, количество палиндромов будет $10^[k/2]$, где $[x]$ = округленное значение $x$.

Надо сложить все значения для $k = 1..n-1$.

Теперь рассмотрим палиндромы длины n. Будем считать количество палиндромов так:

если $N = abc...xyz$, то прибавляем к ответу:

$(a-1)$99 ... 9 (до середины, так как это палиндром)

$a$$(b - 1)$99 ... *9 (так же до середины)

... И так далее.

Cложность будет примерно $O(n^2)$.

Задача решается перебором. Перебираем три точки и проверяем на условие прямоугольности.

Проверять на прямоугольность надо аккуратно. Так как времени хватает почти в притык. Известно, что вычисления из под корня работают долго, так-что по возможности желательно их не делать. Известно, что у прямоугольного треугольника гипотенуза $h = \sqrt{a^2 + b^2}$.

Так-как нам известны координаты трех точек на плоскости $(x_1, y_1), (x_2, y_2), (x_3, y_3)$, то посчитать длинны сторон треуголника (x, y, z) не сложно.

• $x = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
• $y = \sqrt{(x_1 - x_3)^2 + (y_1 - y_3)^2}$
• $z = \sqrt{(x_2 - x_3)^2 + (y_2 - y_3)^2}$

Понятно, что если рассматриваемый треугольник является прямоуголным, то должно выполняться одно из условий:

• $x^2 = y^2 + z^2$
• $y^2 = x^2 + z^2$
• $z^2 = y^2 + x^2$

Для вычисления x мы берем выражение $(x_1 - x_2)^2 + (y_1 - y_2)^2$ под корнем, а потом при сравнениии опять берем квадрат. Очевидно, что это лишнее и тут можно сократить вычисления из под корня вычисляя только:

• $x' = (x_1 - x_2)^2 + (y_1 - y_2)^2 = \sqrt{x}$
• $y' = (x_1 - x_3)^2 + (y_1 - y_3)^2 = \sqrt{y}$
• $z' = (x_2 - x_3)^2 + (y_2 - y_3)^2 = \sqrt{z}$

и проверять условия так:

• $x' = y' + z'$
• $y' = x' + z'$
• $z' = y' + x'$

если одно из условий выполняется, то треугольник прямоугольный и мы определили какая сторона у наc гипотенуза, а какие катеты. Предположим у нас выполнилось первое условие. Дальше надо еще проверить площадь треуголника $A = \frac{a*b}{2}$.

Мы уже посчитали $y' = a^2$ и $z' = b^2$, тогда А можно считать так $A = \frac{\sqrt{y'} * \sqrt{z'}}{2}$, но лучше так $A = \sqrt{\frac{y' * z'}{4}}$. Если и это условие $A_1 \le A \le A_2$ выполняется, то увеличиваем счетчик на один. Когда перебор завершится, то выписываем что насчитали.

А вообще можно посчитать площадь в квадрате $A^2 = \frac{y' * z'}{4}$ и сравнивать $A_1^2 \le A^2 \le A_2^2$. Но тут надо аккуратнее так-как может быть большим. $A^2 > 2^{31}$

Если учесть что ограничения довольно маленькие тогда задача решается простым перебором.
Только нужно учесть один момент который в условии упомянут не явно. Сказано что "Мэр хочет знать сколько гречки он получит в следующем году".
Так что задача сводится к тому чтобы вычислить наибольший прямоугольник состоящих только из единиц и добавить количество двоек на поле.

В переборочной реализации с 6-ю вложенными циклами, при правильном определении границ на наибольшем тесте достаточно сделать 488410000 операций.

Но конечно можно использовать динамические алгоритмы которые смогут сделать это за более короткое процессорное время.

Мое решение просто перебирает верхний-левый, и правый-нижний угол поля. После дополнительные два цикла пробегают по выбранному полю и проверяют является ли оно пшеничным и максимальным.

Вот собственно и все, сложив площадь максимального пшеничного поля и сколько гречки было в прошлом году будет ответ.

ЗЫ: возможно и не очень элегантное решение, но задача подразумевалась как халявная :)

...

.

Нам дано что числа меньше 10^9, из этого можно вывести что максимальный делитель
это корень из 10^9.

Еще хорошее условие это что отрезки будут меньше 100000, так что можно перебрать
каждое число и проверить на простоту. Но если это делать в лоб то также это будет
очень долго.

Первое решетом найти все простые числа от 1 до корня из 10^9(примерно 32000).
А в дальнейшем проверять каждое число на простоту, путем деления на простые числа,
которые, меньше корня этого числа.

При самом большом тесте как раз вписывается в 2 секунды. :)

Во входных данных мы имеем 12 чисел, некоторые из которых могут совпадать. Несложно понять, что в правильной коробке не может быть более 3х наборов различных размеров (это понятно так же из рассуждений в Решении №1). Пронумеруем всевозможные наборы размеров. Мы это можем делать сразу при чтении входных данных. В некоторой переменной C будем хранить количество различных размеров, а в массиве F[X] будет номер размера X или 0, если такого размера нет. Так же используем 2х-мерный массив G[i][j], где будет находиться количество плиток с номерами размеров i и j, для простоты, чтобы каждый раз не вращать плитки следует сделать так, чтобы G[i][j]=G[j][i]. Определить значение C и заполнить вышеописанные массивы возможно в одном цикле, сразу при чтении данных.

Теперь для определения возможности построения коробки достаточно знать ранее вычисленные значения C и G. Здесь нужно рассмотреть все случаи, которые могут быть в зависимости от количества разных размеров C:

C=1. Это означает, что все размеры одинаковые, т.е. все плитки представляют из себя равные квадраты и мы можем построить из них коробку в форме куба. Заметим так же, что в этом случае определено только G[1][1], которое равно 12 (это даже можно не проверять).

C=2. В этом случае для возможности построения коробки мы должны иметь 2 одинаковых квадратных плитки и 4 одинаковых прямоугольных, для чего достаточно проверить что G[1][2]=4. Заметим, что при этом либо G[1][1]=2 либо G[2][2]=2 (один из размеров дает две плитки, а другой 0). Но последнее условие можно не проверять, т.к. оно вытекает само из того, что C=2, а G[1][2]=4.

C=3. Здесь мы имеем случай, когда все размеры (высота, ширина и длина) различны. Тут для возможности построения коробки необходимо убедиться в том, что при этом получаются ровно по 2 одинаковых плитки для всевозможных G[i][j], 1 <= i,j <= 3. Иначе говоря, должно получаться G[1][2]=G[1][3]=G[2][3]=2.

C>3. При таком варианте, как уже говорилось ранее, мы не можем в любом случае построить коробку.

Можно решить задачу за O( Cat(n)*n ) , где Cat(n) - число правильных скобочных последовательностей, n -- длина последовательности. Рассмотрим построение скобочной последовательности. Заметим, что любой префикс правильной скобочной последовательности характерихуется тремя числами : кол-во открывающихся скобок в этом префиксе -- обозначим currentOpen, кол-во закрывающихся скобок в префиксе -- currentClose, кол-во открывающихся скобок, которые еще нужно добавить -- needOpen. Научимся переходить в новые состояния. 1)Понятно, что если needOpen > 0, мы можем поставить на текущую позицию '(' и решить задачу для следущей позиции с новыми параметрами(currentOpen + 1, currentClose, needOpen - 1). 2)В любом префиксе правильной скобочной последовательности кол-во закрывающихся не превосходит кол-ва открывающихся. Воспользуемся этим фактом. Если ( currentOpen > currentClose ) на текущую позицию ставим ')' и переходим в новое состояние ( currentOpen, currentClose + 1, needOpen ). Генерируя состояния в таком порядке мы соблюдаем лексикографический порядок.

как было сказано, из-за того, что b>1, мы будем перебирать все числа для а с 2..sqrt(n), а дальше для проверки можно воспользоваться процедурой logn(a,n) uses math; var i,j,k,l,m,n:longint; q:int64; a,b:array[1..1000] of longint; begin assign(input,'power.in'); reset(input); assign(output,'power.out'); rewrite(output); readln(n); i:=2; k:=0; while (ii<=n) do begin l:=round(logn(i,n)); q:=round(exp(lln(i))); if (q=n) then begin inc(k); a[k]:=i; b[k]:=l; end; i:=i+1; end; writeln(k); for i:=1 to k do writeln(a[i],' ',b[i]); close(input); close(output); end.

Все последовательности хоть правильные хоть нет =2^(2n). Так что можно смело писать перебор и проверять последовательность правильная или нет.

Любая коробка определяется 3мя размерами: высотой, шириной и длиной. Пусть это значения A, B и C соответственно. В силу того, что все эти значения равноправны (коробку можно вращать), то мы можем полагать, что A <= B <= C. Так же ясно, что для того, чтобы построить коробку нужно иметь набор из трех пар плиток. Плитки в каждой паре идентичны и представляют собой плитки, не имеющие общих граней (противоположные). Причем должна быть возможность стыковать плитки из разных пар друг с другом.

Формализуем вышеописанную идею. Размеры каждой из коробок отсортируем по возрастанию, т.е. будем всегда считать например, что высота меньше либо равна ширине. После чего получившиеся наборы плиток мы можем отсортировать сначала по высоте, а затем (при равных высотах) по ширине. Таким образом, мы должны получить следующую последовательность:

1. AB
2. AB
3. AC
4. AC
5. BC
6. BC

Отсортировав плитки остается лишь проверить на равенство элементов в 3х четверках. Например, если в a[i].h хранится высота, а в a[i].w соответственно длина i-й коробки, то следует проверить на равенство следующие элементы: a[1].h=a[2].h=a[3].h=a[4].h и a[1].w=a[2].w=a[5].h=a[6].h и a[3].w=a[4].w=a[5].w=a[6].w . Такое решение не является самым оптимальным как по времени выполнения, так и по объему кода программы, но тем неменее оно более понятно. Разбор с сайта acmp.ru