Задача А(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, то-есть все не меньшие прямоугольники.
Comments (0)
