Пусть N человек бегут вниз по эскалатору, причем i -ый пробегает одну ступеньку за t i секунд. По технике безопасности бега по эскалатору, на эскалаторе запрещены "обгоны", то есть если A в процессе бега догнал человека B , который бежит с более низкой скоростью, то далее, до конца эскалатора, человек A бежит со скоростью человека B . Однако ступени эскалатора таковы, что на них может помещаться несколько человек одновременно. Ваша задача написать программу, которая рассчитает, когда закончит свой бег по эскалатору каждый бегущий человек.
В первой строке записано число N ( 1 ≤ N ≤ 10 5 ). В следующих N строках перечислены пары чисел t i , w i ( 1 ≤ t i , w i ≤ 10 6 )- время пробега одной ступени и количество ступеней до конца эскалатора. Гарантируется что изначально всем людям осталось бежать различное количество ступеней.
В i -ой строке выведите время в секундах, через которое i -ый человек сойдет с эскалатора
3 2 10 3 11 1 12
20 33 33
Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:
Дана последовательность команд для автомата. Требуется выполнить эти команды в указанной последовательности, и для каждой команды запроса ближайших белых соседей указать результат ее выполнения.
начала вводятся размеры поля N и M ( 1 ≤ N ≤ 20 , 1 ≤ M ≤ 50000 ), затем количество команд K ( 1 ≤ K ≤ 10 5 ), а затем сами команды. Команды записаны по одной в строке в следующем формате:
На каждый запрос Neighbors требуется вывести сначала количество ближайших белых соседей (или 0 , если ни с одной из сторон белых клеток не осталось), а затем их координаты (соседей можно перечислять в произвольном порядке). Если запросов Neighbors нет, ничего выводить не надо.
5 5 10 Neighbors 3 1 Color 4 1 Color 2 4 Color 4 5 Color 2 2 Neighbors 5 4 Neighbors 5 5 Neighbors 2 4 Color 3 5 Neighbors 3 5
3 2 1 4 1 3 2 3 4 4 5 3 5 5 2 3 5 5 4 4 1 4 3 4 2 3 2 5 3 2 5 5 5 3 4
Феоктист Всеволодович — преподаватель физкультуры старой закалки, глубоко убеждённый, что в начале каждого урока школьников необходимо построить по росту. Для этого он сначала просит школьников построиться самостоятельно, после чего последовательно меняет местами произвольную пару стоящих рядом учеников, пока шеренга не примет желанный вид.
Всего на урок пришло \(N\) детей, изначально построившихся таким образом, что рост стоящего на позиции \(i\) равен \(h_i\) (используется нумерация c \(1\)). Можно считать, что все числа \(h_i\) различны и лежат в диапазоне от 1 до \(N\). Шеренга считается упорядоченной, если на первой позиции стоит школьник ростом один, на второй позиции стоит школьник ростом два и так далее.
Феоктист Всеволодович получает большое удовольствие от процесса упорядочивания школьников, поэтому он всегда выбирает наиболее длинную последовательность обменов. С другой стороны, он не хочет чтобы ученики догадались о том, что он умышленно затягивает построение, поэтому никогда не делает заведомо бессмысленных обменов. А именно, преподаватель никогда не меняет местами школьников на позициях \(i\) и \(j\), если \(h_i < h_j\) . Очевидно, что данное ограничение делает процесс сортировки шеренги по росту конечным.
Староста Саша очень любит играть в волейбол и прекрасно понимает, что чем дольше преподаватель будет расставлять всех по местам, тем меньше времени останется для игры. Ученики уже построились некоторым образом, а Феоктист Всеволодович вышел поговорить по телефону, так что Саша может успеть поменять местами ровно двух школьников, необязательно стоящих рядом в шеренге. Разумеется, он хочет сделать это таким образом, чтобы преподаватель как можно быстрее закончил упорядочивать шеренгу (Саша давно уже раскусил, как именно действует Феоктист Всеволодович). С информатикой у старосты всегда были определённые проблемы, поэтому ему требуется ваша помощь.
В первой строке ввода содержится единственное число N — количество школьников на уроке (\(1 \le N \le 1 000 000\)).
Во второй строке записано \(N\) различных целых чисел \(h_i\) (\(1 \le h_i \le N\)). \(i\)-е число соответствует росту школьника стоящего на \(i\)-й позиции
Выведите два числа — номера позиций школьников, которым необходимо поменяться местами, чтобы минимизировать количество действий преподавателя. Если таких пар несколько, то выведите любую из них. Если никому меняться местами не нужно, выведите -1 -1
В первом примере из условия после Сашиной перестановки, получится последовательность {2, 1, 3, 5, 4}, и тренер сможет сделать всего два обмена, перед тем как последовательность станет упорядоченной (например, он может поменять местами 1-го и 2-го школьника, а затем 4-го и 5-го). Если Саша поменяет местами двух других школьников, тренер затем сможет сделать три или более обменов.
Тесты к этой задаче состоят из одиннадцати групп. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
5 2 4 3 5 1
2 5
4 1 2 3 4
-1 -1
10 2 3 7 1 5 10 4 6 9 8
3 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
Дан трёхмерный массив. Найдите сумму на параллелепипеде со сторонами, паралельными осям координат.
В первой строке даны три числа: 1 ≤ N , M , K ≤ 100 . В следующих N × M строках даны по K чисел - | a ijk | < 10 9 . Далее в отдельной строке даётся одно число Q ≤ 10 9 - количество запросов. В следующих Q строках даются запросы: каждый запрос имеет вид x 1 y 1 z 1 x 2 y 2 z 2 - две противоположные границы параллелепипеда, сумму которого необходимо подсчитать. 1 ≤ x 1 ≤ x 2 ≤ N 1 ≤ y 1 ≤ y 2 ≤ M 1 ≤ z 1 ≤ z 2 ≤ K
Для каждого запроса выведите одно число в отдельной строке - ответ на этот самый запрос
3 3 3 2 3 5 1 2 3 4 5 7 1 6 6 9 6 6 8 6 6 4 3 3 2 3 3 5 3 3 1 2 1 2 3 3 3
54