Темы
Информатика(2656 задач)
--->
228 задач
<---
Учительница по программированию задала Вовочке задачу — отсортировать массив из N различных чисел по возрастанию.
Вовочка поступает так: он просматривает массив чисел слева направо, и, если замечает два элемента, стоящих рядом, таких, что правый меньше левого, он меняет их местами. Так он поступает, пока массив не будет отсортирован.
Но Вовочка — очень ленивый ученик. В какой-то момент ему надоело сортировать числа, и он решил посчитать, сколько ещё описанных выше обменов нужно сделать. Помогите ему.
В первой строке входных данных находится натуральное число N (1 ≤ N ≤ 1 500). Во второй строке через пробел вводится N различных целых чисел, каждое из которых не меньше 1 и не больше 10 000.
Выведите одно число — искомое количество обменов.
5
1 2 3 5 4
1
3
3 2 1
3
От некоторых школ в командной олимпиаде по информатике участвует очень много команд. Учитель одной из таких школ раздал для регистрации своим командам номера: 1, 2, 3 и т. д. Для того чтобы проверить, все ли команды зарегистрировались, учитель выписал из таблицы регистрации только номера команд своей школы, но в том порядке, в котором команды регистрировались.
После нелёгких подсчётов оказалось, что зарегистрировались все. Но в процессе решения этой задачи учитель сформулировал следующую: сколькими способами можно выбрать стоящие подряд в этом списке K номеров команд, чтобы они образовывали некоторую перестановку чисел от 1 до K? Например, если от школы участвуют всего три команды, то при порядке регистрации 3 1 2 таких способов будет три (для K = 1, 2, 3), а при регистрации в порядке 2 3 1 — всего два (для K = 1 и K = 3).
В первой строке входных данных находится одно число N (1 ≤ N ≤ 200) — количество команд, участвующих в олимпиаде от этой школы. Во второй строке находятся N натуральных чисел от 1 до N в том порядке, в котором команды регистрировались на олимпиаду.
Гарантируется, что каждое число встречается в этой строке ровно один раз.
Выведите одно число, обозначающее число способов выбрать из списка несколько стоящих подряд команд, удовлетворяющих условию задачи.
3
2 3 1
2
Джонни работает в министерстве финансов одной небольшой страны. На этот раз он решил очень тщательно распланировать бюджет. Для этого ему первым делом необходимо выяснить, сколько же будет выходных дней в каждом интересующем его году (без учёта праздников, которые и в этой стране то и дело переносят).
Так как Джонни смотрит в будущее, то его интересуют лишь года, которые ещё не наступили. Но он верит в успехи биоинформатики, касающиеся увеличения продолжительности жизни, и хочет рассчитать всё заранее, поэтому его интересуют и очень отдалённые даты. При этом, Джонни уже вычислил для интересующего его года, какой день недели приходится на первое января этого года.
В единственной строке входных данных содержатся два целых числа: год Y, который интересует Джонни, (2013 ≤ Y ≤ 2100) и номер дня недели D, на который приходится первое января этого года (1 ≤ D ≤ 7). D = 1 означает понедельник, D = 2 — вторник и т. д.
В единственной строке выведите количество выходных дней в соответствующем году.
2013 2
104
Напомним, что в неделе семь дней, выходными считаются суббота и воскресенье. В невисокосных годах 365 дней, в високосных — 366. Год называется високосным, если он делится на 400, или если он делится на 4, но не делится на 100.
Город N, в отличие от города M, расположен на склоне одного холма. Чистоту улиц этого города обеспечивает единственная поливальная машина. Бензин нынче дорог, поэтому движение муниципального транспорта «в гору» признано слишком расточительным.
Карта города представляет собой прямоугольник, разбитый на H × W клеток, где H и W — высота и ширина карты в клетках соответственно. Часть клеток заняты зданиями, остальные соответствуют улицам и площадям, которые и требуется помыть.
Поливальная машина начинает свой путь в одной из клеток самого верхнего ряда, не занятой зданиями. Она может полить асфальт в текущей клетке и переместиться в любую из двух соседних клеток этого же ряда, не занятых зданиями. Объехать здания, не поднимаясь при этом в гору, невозможно. Поливальная машина также может переместиться в соседнюю по вертикали свободную клетку из нижнего ряда.
Помогите узнать экономному муниципалитету, какое максимальное количество свободных клеток поливальная машина сможет помыть, не поднимаясь при этом в гору?
Учтите, что структура города такова, что в каждом ряду свободные клетки образуют один непрерывный отрезок.
В первой строке входного файла находятся натуральные числа H и W — высота и ширина карты города (1 ≤ W ≤ 300, 1 ≤ H ≤ 300).
Каждая из следующих H строк содержит W символов ‘#’ и ‘.’, означающих, соответственно, клетки со зданиями и без.
Выведите единственное натуральное число — максимальную площадь, которую может обработать поливалка.
8 8 ###...## #...#### ##.##### ##..#### ......## ####...# #...#### #.....##
18
На Международной олимпиаде по информатике некоторые участники, конечно же, получают удовольствие именно от решения предложенных задач, но большинство — от полученных в новой стране впечатлений. Впечатления принято запечатлевать на фотоаппарат. Участник T решил подойти к процессу съёмок с научной (по его мнению) точки зрения. Он желает заснять сразу два интересных объекта, местоположение каждого из которых на земле мы будем описывать с помощью отрезка. T выбирает точку для съёмок так, чтобы площадь двух треугольников, образованных концами соответствующих отрезков и выбранной точкой была одинаковой. Треугольники при этом должны быть невырожденными.
Помогите T с выбором такой точки. Возможность заснять сразу два объекта при этом анализировать не нужно, мы лишь действуем в рамках модели, сформулированной T. Задача упрощается тем, что каждый из отрезков, описывающих объекты, оказался параллельным одной из осей координат (возможно, каждый своей).
В первой строке входного файла находятся 4 целых числа x1, y1, x2, y2, характеризующие координаты концов первого отрезка. Во второй строке — x3, y3, x4, y4, описывающие второй отрезок. Все координаты по модулю не превосходят 1000. Каждый отрезок параллелен одной из осей координат. То есть гарантируется, что у каждого отрезка или координаты x его концов или координаты y концов совпадают. Также гарантируется, что отрезки невырождены, и что они не имеют общих внутренних точек и могут касаться только своими концами.
Если точку, удовлетворяющую условию задачи, и координаты которой по абсолютной величине не превосходят 5000 найти можно, то в первой строке выведите слово «YES». В этом случае во второй строке выведите координаты найденной точки. Если таких точек несколько, то выведите любую из них. Координаты могут оказаться вещественными, и их следует выводить с как можно бóльшим числом знаков после десятичной точки. Разница соответствующих площадей должна быть не больше 10 - 3. Площадь каждого треугольника должна быть не меньше 0.1.
Если искомую точку найти невозможно, или координаты любой такой точки по модулю превышают 5000, то выведите только слово «NO».
0 0 0 4
5 2 5 3
YES
1.00000000000000 0.0000000000000000
1 0 3 0
1 0 1 1
YES
3.00000000000 1.000000000000000