Задача А(cAPS lOCK)
В задаче делаем все что просят в условии, если есть хоть одна строчная буква не считая первую, то оставляем все как есть, иначе меняем все буквы на противоположные. Что-бы поменять значение регистра, нужно в случае большой буквы прибавить к коду 32, иначе отнять 32.Задача B(Противоположности притягиваются )
Посчитаем кол-во каждого числа, пускай кол-во числа i - B[i] тогда ответом будем сумма B[i]*B[-i], i=1..10 + B[0]*(B[0]-1)/2.Задача C(Весь мир театр )
Перебираем сколько мы будем брать мальчиков(пуская будет х) , считаем сколько нужно девочек на оставшиеся места(пускай будет у), если оба параметра удовлетворяют входные данные то к ответу добавим C(N,x)*C(M,y), где C(n,k) - кол-во способов выбора k элементов из n. В данной задаче лучше считать с помощью треугольника паскаля используя свойство: C(n,k) = C(n-1,k-1) + C(n-1,k), C(n,0) = 1. Так-же важно не забыть что если не проверять границы , то-есть допускать M<y, то возможны переполнения или еще какие-то тупые баги.Задача D(Метро)
Найдем цикл (например обходом в глубину, Ссылка, еще нужно не забыть что граф неориентированный, и ходить в предка нельзя). Добавим эти вершины в очередь, и пометим расстояние до них как 0, потом запустим обычный волновой алгоритм и получим ответ.
Задача E(Еще одна задача о ферзях)
Посчитаем для каждого ферзя, угрожает-ли он кому-то в каждом направлении. Как это сделать: Ответы по горизонтали: сортим по X, идем слева на право, если уже встречалась раньше, вершина с таким Y, то ответ для ферзя +1, ну и еще нужно пометить что такой У уже встретился. Аналогично сделаем с проходом с права на лева.
Для ответов по горизонтали, все так-же, просто меняем местами X и Y во всех местах.
Остались диагонали: каждая диагональ может относиться к двум видам, первый однозначно задается как X+Y, второй как X-Y, то есть снова сортируем все по X, делаем два прохода, слева на право и наоборот, только в данном случае считаем встречались/нет не X, а значение диагонали.
Задача F(Подарок маме)
Определим где есть и где нету звезд, если она есть то в ячейке матрицы будет 1, иначе 0. Посчитаем частичные суммы таких прямоугольников. Дальше зафиксируем левую и правую границы прямоугольника, а дальше будет идти с двумя указателями, смещать первый вниз и двигать второй вниз пока между ними кол-во звезд больше-равно К. Кол-во звезд в прямоугольнике можно посчитать через частичные суммы: пускай координаты прямоугольника будут (x1,y1,x2,y2), а частичные суммы для позиции (i,j) будут лежать ячейке a[i,j], тогда ответом будет a[x2-1,y2-1]-a[x2-1,y1]-a[x1,y2-1]+a[x1,y1], так-как границы мы не можем включать в ответ. Теперь допустим в какой-то момент левая граница равна l(l = 0, если еще даже взяв все не получим сумму в К), то к ответу нужно прибавить это-же l, то-есть все не меньшие прямоугольники.
В задаче C я считал все через BigInteger, считаю свое решение ужасным и предпочел бы сказать, что оно не мое, но на контесте ничего более доходчивого не пришло на ум. А что должно было придти - открываем Википедию и читаем: "В общем случае число, показывающее, сколькими способами можно выбрать k элементов из множества, содержащего n различных элементов, стоит на пересечении k-й диагонали и n-й строки треугольника Паскаля." Вот и все дела, собственно.
А в D, не знаю, как надо было, но я искал цикл алгоритмом окрашиваний вершин, как он точно называется не знаю, но суть в этом. Жаль, не успел сдать, какая-то непонятная ошибка атаковала код, из-за чего он выдавал неверный ответ..
По поводу цикла и биномиальных коэффициентов можно прочитать на все известном e-maxx.ru/algo.
'a' ^ 32 => 'A''A' ^ 32 => 'a'cApS
p-строчная - строку оставляем.
Насчет задачи D и нахождения цикла... собственно искал методом, который указан в разборе и получалось, что цикл 1 - 3.
Реализация
Здесь приведена реализация для случая ориентированного графа.
"Дальше зафиксируем левую и правую границы прямоугольника, а дальше будет идти с двумя указателями, смещать первый вниз и двигать второй вниз пока между ними кол-во звезд больше-равно К." - можно немного поподробнее, заранее спасибо.
Можно сделать также как и с левой/правой границей - перебрать все верхние/нижние границы, т.е. получится полный перебор прямоугольников, что будет работать, но не уложится в TL... Будем оптимизировать наш brute force:
1. Можно заметить, что если мы нашли удовлетворяющий условию прямоугольник, то все большие тоже нам подойдут. Потому нет смысла проходить самый вложенный цикл всегда до конца — если нашли прямоугольник с количеством звёзд >=k, то количество оставшихся итераций можно просто прибавить, не выполняя их. Это не повлияет на ответ.
2. Можно заметить, что нет смысла проходить самый вложенный цикл с самого начала. В качестве стартового значения счетчика цикла можно использовать значение с предыдущей итерации. Очевидно, что все меньшие значения дадут прямоугольники, которые не удовлетворяют условию, т.к. мы уже проверили прямоугольник их содержащий.
Т.о. мы получили решение типа «два указателя», что и описано у ув. Sereja.