Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 0 до \(M\) включительно. На костяшках полного набора домино обозначены все возможные различные пары чисел, например, если M равно 3, то полный набор содержит 10 костяшек: (0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).
Из костяшек можно выкладывать цепочки, соединяя пары костяшек короткими сторонами, если количества точек на соседних с местом соединения половинках костяшек равны.
Некоторые костяшки были удалены из полного набора. Требуется определить, какое минимальное количество цепочек нужно выложить из оставшихся в наборе костяшек, чтобы каждая из них принадлежала ровно одной цепочке.
Напишите программу, которая по информации о наборе домино должна ответить, какое минимальное количество цепочек нужно выложить.
В первой строке входного файла содержится одно целое число \(M\) (0≤\(M\)≤100), которое соответствует максимально возможному количеству точек на половинке костяшки. Во второй строке записано одно целое число \(N\), равное количеству костяшек, удаленных из полного набора. Каждая \(і\)-я из последующих \(N\) строк содержит по два числа \(A_i\) и \(B_і\). Это количества точек на половинках \(i\)-й удалённой костяшки.
Единственная строка выходного файла должна содержать одно целое число \(L\) – минимальное количество цепочек.
7 2 7 5 3 4
2
Ограничение по времени: 0.2 секунды
На планете Олимпия рабочие строят новую дамбу. Часть плоскости, на которой проводятся строительные работы, имеет вид прямоугольника размером 1 x \(L\) метров, на котором введены координаты, как показано на рисунке.
Для поднятия ландшафта используют специально разработанные магические импульсаторы. Если магический импульсатор силой \(H\) поставить в точку с \(X\)-координатой \(p\), то в каждой точке \(q\) отрезка [\(p\)–\(H\);\(p\)] на оси \(X\) рельеф поднимается на \(q\)–\(p\)+\(H\) метров по всей его ширине (то есть для произвольного \(Z\) от 0 до 1), а в каждой точке \(q\) отрезка [\(p\);\(p\)+\(H\)] рельеф поднимается на \(H\)+\(p\)–\(q\) метров по всей его ширине, в остальных точках ландшафт остается неизменным (см. рисунок).
Во время строительства рабочие время от времени интересуются объёмом части дамбы, находящейся над некоторым прямоугольником.
Напишите программу, которая поможет рабочим в их расчётах.
В первой строке входного файла содержатся два целых числа: N – количество операций, которые будут выполнять рабочие (1≤\(N\)≤100000), и \(L\) – длина прямоугольника (1≤\(L\)≤100000).
В следующих \(N\) строках содержатся описания операций: первое число строки – номер операции, где „1” означает, что рабочие собираются поставить магический импульсатор, „2” – рабочие хотят узнать некоторый объём. Если операция имеет код „1”, то далее идут два целых числа \(p\) и \(H\) (0≤\(p\)≤\(L\); 1≤\(H\)≤\(L\)), то есть импульсатор силой \(H\) ставят в позицию p (на оси \(X\)). Если операция имеет код „2”, то далее идут два целых числа \(A\) и \(B\) (0≤\(A\)<\(B\)≤\(L\)); это означает, что рабочие хотят узнать объём части дамбы, которая находится над прямоугольником от \(A\) до \(B\) по оси \(X\), и от 0 до 1 по оси \(Z\).
Создайте выходной файл, в котором для каждой операции, указанной во входном файле, выведите строку со следующей информацией.
Если операция есть „1”, то выведите число „-1” без кавычек. Если операция есть „2”, то выведите число округленное вниз до ближайшего целого, равное объёму части дамбы, которая находится над прямоугольником от \(A\) до \(B\) по оси \(X\), и от 0 до 1 по оси \(Z\), как показано на рисунке.
2 13 1 7 5 2 5 9
-1 16
По заданному натуральному числу N необходимо вычислить количество натуральных чисел, которые есть делителями N! (факториала числа N).
Например, при N=4, N!=4·3·2·1=24. Это число имеет следующие делители: 1, 2, 3, 4, 6, 8, 12, 24. Таким образом, искомое количество составляет 8.
Напишите программу, которая по натуральному N, находит количество делителей его факториала.
Формат входных данных
Единственная строка входного файла содержит одно целое число N (1≤N≤45).
Формат выходных данных
Единственная строка выходного файла должна содержать одно целое число –найденное количество делителей числа N!
4
8
В стране Олимпия очень развита живопись. Картиной считается любой прямоугольник, который состоит из черных и белых единичных квадратов. Художник Олимпус решил радикально улучшить свои картины. Для этого он планирует к белому и черному цветам добавить еще и серый оттенок. По его задумке, граница между каждыми черным и белым квадратом должна содержать серую линию, чтобы образовался эффект плавного перехода.
Однако, перед началом работы, он обнаружил, что серая краска очень дорого стоит. Чтобы сэкономить деньги художник решил оценить, не выгоднее ли сначала перекрасить некоторые белые квадраты в черные, а черные в белые для того, чтобы минимизировать расходы на краску.
Напишите программу, которая по информации о существующей картине определяет минимальную сумму денег, которые понадобятся на ее улучшение.
Формат входных данных
Первая строка входного файла содержит пять натуральных чисел N, M, w, b, g. 1≤N, M≤70 – высота и ширина картины, 1≤w,b,g≤1000 – цена рисования одного белого единичного квадрата, черного единичного квадрата и серой линии единичной длины, соответственно. Далее следует N строк, каждая из которых состоит из M литер. Литера B соответствует черному квадрату, а W – белому.
Формат выходных данных
Единственная строка выходного файла должна содержать одно целое число, которое есть минимальной суммой затрат на улучшение картины.
3 2 10 12 1 BW WB BW
7
Петрик и Василько — настоящие друзья, поэтому они постоянно задают друг другу всевозможные интересные задачи. Однако Василько всегда с легкостью решает задачи своего друга, поэтому Петрик решил придумать по-настоящему сложную задачу. И вот что у него получилось. Будем называть число b подчислом числа a , если из числа a можно вычеркнуть некоторые цифры так, что цифры, которые остались, образуют число b . Задано n -цифровое число x . Обозначим как x k наибольшее k -цифровое подчисло числа x . Необходимо ответить на m запросов. Каждый запрос состоит из двух цифр - k и l . Ответом на запрос является l -я цифра числа x k . На этот раз задача действительно заставила Василько задуматься. А сможете ли вы решить ее быстрее его?
В первой строке входного файла содержится целое число x длины n ( 1 ≤ n ≤ 100 000 ). Во второй строке содержится число m ( 1 ≤ m ≤ 50 000 ). В следующих m строках содержится по два числа k i , l i ( 1 ≤ k i ≤ n , 1 ≤ l i ≤ k i ) — параметры i -го запроса.
Выходной файл должен содержать одну строку длины m , i -й символ которого является ответом на i -й запрос.
31415926 7 2 2 3 1 1 1 4 3 5 2 8 2 7 3
6992511