Андрей работает в секретной химической лаборатории, в которой производят опасную кислоту с удивительными свойствами. У Андрея есть n бесконечно больших резервуаров, расположенных в один ряд. Изначально в каждом резервуаре находится некоторое количество кислоты. Начальство Андрея требует, чтобы во всех резервуарах содержался одинаковый объем кислоты. К сожалению, разливающий аппарат несовершенен. За одну операцию он способен разлить по одному литру кислоты в каждый из первых k (1 ≤ k ≤ n) резервуаров. Обратите внимание, что для разных операций k могут быть разными. Поскольку кислота очень дорогая, Андрею не разрешается выливать кислоту из резервуаров. Андрей просит вас узнать, можно ли уравнять объемы кислоты в резервуарах, и, если это возможно, то посчитать минимальное количество операций, которое потребуется, чтобы этого достичь.
Первая строка содержит число n ( 1 ≤ n ≤ 100000 ) — количество резервуаров. Во второй строке содержатся n целых чисел a i ( 1 ≤ ai ≤ 10^9 ), где ai означает исходный объём кислоты в i -м резервуаре в литрах.
Если объемы кислоты в резервуарах можно уравнять, выведите минимальное количество операций, необходимых для этого. Если это невозможно, выведите «-1».
| Ввод | Вывод |
|---|---|
| 2 | 1 |
| 1 2 |
| Ввод | Вывод |
|---|---|
| 5 | 4 |
| 1 1 5 5 5 |
| Ввод | Вывод |
|---|---|
| 3 | -1 |
| 3 2 1 |
В первом примере достаточно одной операции с k, равным 1. Тогда в обоих резервуарах окажется по 2 литра. Во втором примере достаточно четырех операций с k, равным 2. Тогда во всех резервуарах окажется по 5 литров. В третьем примере объемы уравнять невозможно.
В самолете n рядов и по три кресла слева и справа в каждом ряду. Крайние кресла (A и F) находятся у окна, центральные (C и D) – у прохода. На регистрацию приходят группы из одного, двух или трех пассажиров. Они желают сидеть рядом, то есть на одном ряду и на одной стороне: левой или правой. Например, группа из двух пассажиров может сесть на кресла B и C, но не может сесть на кресла C и D, потому что они разделены проходом, а также не может сесть на кресла A и C, потому что тогда они окажутся не рядом. Кроме того, один из пассажиров каждой группы очень требовательный – он хочет сесть либо у окна, либо у прохода. Конечно же, каждая группа из пассажиров хочет занять места в ряду с как можно меньшим номером, ведь тогда они скорее выйдут из самолета после посадки. Для каждой группы пассажиров определите, есть ли места в самолете, подходящие для них.
Первая строка содержит число n ( 1 ≤ n ≤ 100 ) – количество рядов в самолете. Далее в n строках вводится изначальная рассадка в самолете по рядам (от первого до n-го), где символами . (точка) обозначены свободные места, символами # (решетка) обозначены занятые места, а символами _ (нижнее подчеркивание) обозначен проход между креслами C и D каждого ряда.
Следующая строка содержит число m ( 1 ≤ m ≤ 100 ) – количество групп пассажиров. Далее в m строках содержатся описания групп пассажиров. Формат описания такой: num side position , где num – количество пассажиров (число 1, 2 или 3), side – желаемая сторона самолета (строка left или right), position – желаемое место требовательного пассажира (строка aisle или window).
Если группа может сесть на места, удовлетворяющие ее требованиям, то выведите строку Passengers can take seats: и список их мест в формате row letter, упорядоченный по возрастанию буквы места. Затем выведите в n строках получившуюся рассадку в самолете, в формате, описанном выше, причем места, занятые текущей группой пассажиров, должны быть обозначены символом X. Если группа не может найти места, удовлетворяющие ее требованиям, то выведите строку Cannot fulfill passengers requirements. Ответ сравнивается с правильным посимвольно, поэтому ваше решение не должно выводить никаких лишних символов, в том числе лишних переводов строк или пробельных символов в концах строк. В конце каждой строки (включая последнюю) должен быть выведен символ перевода строки.
| Ввод | Вывод |
|---|---|
| 4 | Passengers can take seats: 1B 1C |
| ..._.#. | .XX_.#. |
| .##_... | .##_... |
| .#._.## | .#._.## |
| ..._... | ..._... |
| 7 | Passengers can take seats: 2D 2E 2F |
| 2 left aisle | .##_.#. |
| 3 right window | .##_XXX |
| 2 left window | .#._.## |
| 3 left aisle | ..._... |
| 1 right window | Passengers can take seats: 4A 4B |
| 2 right window | .##_.#. |
| 1 right window | .##_### |
| .#._.## | |
| XX._... | |
| Cannot fulfill passengers requirements | |
| Passengers can take seats: 1F | |
| .##_.#X | |
| .##_### | |
| .#._.## | |
| ##._... | |
| Passengers can take seats: 4E 4F | |
| .##_.## | |
| .##_### | |
| .#._.## | |
| ##._.XX | |
| Cannot fulfill passengers requirements |
Рассмотрим целочисленный массив a длины n. Назовём расстоянием от индекса i до множества индексов S величину dist(i,S) = ∑(j∈S)|ai−aj|.
Зафиксируем целое число k. Рассмотрим функцию f(i) = min dist(i,S), где минимум берётся по множествам S размера k, не содержащим индекс i.
Определите значение f(i) для всех i от 1 до n.
В первой строке заданы два целых числа n и k (2≤n≤300000, 1≤k<n), описанные в условии.
Во второй строке содержится n целых чисел ai (1≤ai≤10^9) — элементы массива a.
Выведите n целых чисел: значения f(i) для i=1,i=2,…,i=n.
| Ввод | Вывод |
|---|---|
| 4 2 | 3 2 2 3 |
| 1 2 3 4 |
| Ввод | Вывод |
|---|---|
| 5 3 | 4 2 8 4 2 |
| 3 2 5 1 2 |
| Ввод | Вывод |
|---|---|
| 6 2 | 3 2 3 3 2 3 |
| 3 2 1 101 102 103 |
Рассмотрим первый пример.
При i=1 оптмиальное S — это {2,3}; dist(1,{2,3})=|1−2|+|1−3|=3.
При i=2 оптмиальное S — это {1,3}; dist(2,{1,3})=|2−1|+|2−3|=2.
При i=3 оптмиальное S — это {2,4}; dist(3,{2,4})=|3−2|+|3−4|=2.
При i=4 оптмиальное S — это {2,3}; dist(4,{2,3})=|4−2|+|4−3|=3.
Разработчик Василий торопился на встречу с коллегами, поэтому быстро написал программу. Код получился неидеальным. Помогите Василию исправить ошибки в коде:
module.exports = function (participants, sports) {
/**
* Подобно оператору new создает экземпляр объекта,
* используя функцию-конструктор и параметры для нее
*/
function constructFrom (fnConstructor, params) {
const res = {};
fnConstructor.bind(res).call(params);
Object.setPrototypeOf(res, fnConstructor);
return res;
}
/**
* Создает пары вида [’вид спорта’, ’имя участника’],
* где первому виду спорта соответствует последний участник
*/
function assignParicipants () {
const participants = this.participants;
const sports = this.sports;
const orderIndexes = [];
let i = sports.length;
while (i--) {
orderIndexes.push(function() {
return i;
});
}
return orderIndexes.map(
(getSportIndex, i) => [sports[i], participants[getSportIndex()]]
);
}
function Contest (participants, sports) {
this.participants = participants;
this.sports = sports;
}
Contest.prototype.assignParicipants = assignParicipants;
const contest = constructFrom(Contest, participants, sports);
return contest.assignParicipants();
}
И отправить исправленный вариант в качестве решения.
На вход подается список участников participants и список видов спорта sports. Оба списка одинаковой длины.
| Ввод | Вывод |
|---|---|
| { | [["football","Kate"],["hockey","Mary"]] |
| "participants": ["Mary", "Kate"], | |
| "sports": ["football", "hockey"] | |
| } |
Магнитная буря здорово потрепала файлы Бальтазара. Раньше он хранил в своей папке разные файлы и поддиректории, но теперь там настоящая неразбериха.
Бальтазар был минималистом, поэтому всегда все файлы называл file и использовал собственную асинхронную файловую систему, которая базировалась на объекте Folder c двумя методами:
type File = string | Folder | {} | null | undefined;
type Folder = {
// Получить по индексу файл или папку
read(index: number, callback: (file: File) => void): void;
// Получить количество элементов в директории
size(callback: (size: number) => void): void;
}
Часть файлов осталась без повреждений, часть — потеряна навсегда, потому что превратилась в null или {}, а еще часть повреждена и, кажется, может быть восстановлена. Понять, что файл поврежден очень просто — часть букв в названии продублировались. Помогите Бальтазару найти все такие файлы и сложите их в массив для дальнейшего анализа. Массив надо отсортировать лексиграфически.
Объект с определенной структурой:
Folder([
’file’,
’ffffile’,
Folder([
’file’,
]),
Folder([
’fiiile’,
]),
Folder([
{},
null,
’file’,
’ffiillee’,
’ffiillee’,
]),
Folder([
Folder([
’filllle’,
’file’,
null,
]),
{},
Folder([]),
]),
]);
Массив строк, отсортированный в лексикографическом порядке:
[
’ffffile’,
’ffiillee’,
’ffiillee’,
’fiiile’,
’filllle’,
]
Задачу требуется решить на JavaScript (ES2017) и оформить решение по шаблону:
module.exports = async function(input) {
// ...
return result;
}
Песочницу для решения можно загрузить по ссылке: Скачать условие задачи
В поисках сокровищ известный археолог попал в огромную сеть двумерных пещер. Он вспомнил, что в университете как раз делал дипломную работу по этой местности: руками подсчитывал количество сталактитов, сталагмитов и сталагнатов и записывал всё это в рабочую тетрадь. Да, ошибиться легко. Приходилось проверять себя несколько раз. Теперь же у него с собой есть портативный сканер местности, который переводит всё в матрицу из 0 и 1. Только вот незадача, там нет возможности узнать количество объектов на карте. Для знаменитого археолога нет непреодолимых препятствий, а проверить свои студенческие расчеты очень хочется.
Нужно реализовать метод scan, который принимает на вход карту – матрицу NxM, состоящую только из 1 (каменная порода) и 0 (пустое пространство). Матрица – это 2D карта пещеры, вид сбоку, аля платформер.
Пример карты:
[
[1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 1, 0, 1, 0, 1, 0, 0, 0],
[0, 1, 0, 1, 0, 0, 0, 1, 1]
]
Метод экспортировать таким образом:
module.exports = { scan };
Проверяться будет результат вывода:
scan([...массив с картой...]);
Метод scan возвращает объект с количеством каждого типа образования {ceil: 0, floor: 0, both: 0}
- Если образование свисает с потолка и не касается пола – ceil
- Если образование растет от пола и не касается потолка – floor
- Если образование свисает с потолка и при этом еще и касается пола – both
Результат вывода на примере карты выше: {ceil: 2, floor: 2, both: 1}
У одного образования может быть несколько точек касания.
Пример 1:
[
[1, 0, 1],
[1, 1, 1],
[0, 0, 0]
]
Результат: {ceil: 1, floor: 0, both: 0}
Пример 2:
[
[1, 0, 1],
[1, 1, 1],
[0, 0, 1]
]
Результат: {ceil: 0, floor: 0, both: 1}
Считаем, что по диагонали образования не пересекаются:
[
[1, 0, 1],
[0, 1, 0],
]
Результат: {ceil: 2, floor: 1, both: 0}
Дан массив a длины 3 из целых чисел. Определим операцию изменения массива: выбирается два различных индекса i и j (1≤i,j≤3, i≠j), после чего a[i] становится равным a[i]−a[j].
Пример операции: дан массив [1,−3,2], выбрали i=2,j=1, получили массив [1,−3−1,2] = [1,−4,2].
Определим для массива a медиану m как значение, расположенное на позиции 2 при сортировке элементов массива a.
К примеру, медианой массива a = [1,−3,2] является m = 1, так как в сортированном массиве [−3, 1, 2] именно 1 стоит на позиции 2.
Назовём медианным индексом такой индекс i, что ai = m.
Обратите внимание, что медианный индекс необязательно единственный: в массиве a = [3, 0, 3] медиана m = 3, а медианными индексами являются i1 = 1 (a1 = m) и i2 = 3 (a3 = m).
Для каждого индекса i массива a выясните, может ли он стать медианным, если можно сделать не более одной операции изменения массива (можно не делать операций вовсе).
В единственной строке даны 3 целых числа ai (−10^9 ≤ ai ≤ 10^9), разделенные пробелами.
Для каждого индекса i (1 ≤ i ≤ 3) выведите в отдельной строке ответ: YES, если после не более, чем одной операции изменения массива i может стать медианным индексом; NO — иначе.
| Ввод | Вывод |
|---|---|
| 2 6 5 | YES |
| YES | |
| YES |
| Ввод | Вывод |
|---|---|
| 0 -3 1 | YES |
| NO | |
| YES |
В первом тесте a = [2,6,5]. Если сделать операцию изменения i = 2, j = 3, то получится массив [2, 1, 5], медиана будет равна 2, а значит i = 1 будет являться медианным индексом.
Если сделать операцию изменения i = 2, j = 1, то получится массив [2, 4, 5], медиана будет равна 4, а значит i = 2 будет являться медианным индексом.
Если не делать никаких операций изменения, то медианой массива [2, 6, 5] будет 5, а значит i = 3 будет являться медианным индексом. Аналогично i = 3 будет медианным индексом после операции изменения i = 3, j = 1.
Во втором тесте единственной операцией изменения, делающей индекс i = 2 медианным, является операция i = 2, j = 2, но такая операция не является корректной, так как индексы i и j должны быть различны.
Яндекс запускает новый бизнес-юнит – Яндекс.Бар. При разработке меню появилась необходимость рисовать слоистые коктейли. Для поддержания концепции IT-бара было принято решение рисовать коктейли, используя ASCII-арт. Вам необходимо считать форму стакана и список ингредиентов слоистого коктейля, заполнить стакан ингредиентами в нужном порядке и распечатать результат.
Описание стакана – это символьное поле из n строк по m символов в каждой. Поле состоит из символов . (точек), \ (обратных слешей), / (прямых слешей), | (вертикальных черт), _ (нижних подчеркиваний) и пробелов.
Дно стакана расположено на последней n-й строке и состоит из символов _ (нижних подчеркиваний), расположенных слитно.
Слева и справа от дна нарисованы грани стакана. Грань – это «ломаная» из символов \ (обратных слешей), / (прямых слешей), | (вертикальных черт). Каждая грань состоит из ровно n символов, начинается в последней n-й строке и заканчивается в первой. Для любой пары соседних строк i и i+1 символы грани расположены в одном или соседних столбцах. Грани не пересекаются и не касаются друг друга ни по стороне, ни по углу. В частности из этого следует, что в любой строке, кроме последней n-й, есть пустое место, обозначаемое пробелами.
Фон изображения стакана состоит из символов . (точек), расположенных слева от левой грани стакана и справа от правой.
Первая строка содержит два числа n и m (2≤n≤100, 3≤m≤100), которые обозначают размеры поля – изображения стакана. Следующие n строк по m символов в каждой содержат описание стакана в формате, указанном выше.
Следующая строка содержит число k (0≤k≤min(n−1,89)) – количество ингредиентов коктейля.
Следующие k строк содержат описания ингредиентов, по одному в каждой строке. Описание имеет вид namei counti symboli.
namei – это название i-го ингредиента (строка из строчных латинских букв длиной не менее 1 и не более 10).
counti – это количество слоев i-го ингредиента.
symboli – это символ, которым i-й ингредиент должен быть представлен в изображении (любой символ с ASCII кодом больше 32 и меньше 127, кроме тех, которые используются в описании изображения стакана).
Гарантируется, что сумма всех counti не превосходит высоты стакана, то есть n−1. Также гарантируется что все символы symboli уникальны.
В n строках по m символов в каждой выведите описание стакана в указанном выше формате.
Ввод
8 15
\ /
.| |.
.| |.
..\ /..
...| |...
...| |...
....\ /....
.....\___/.....
2
gin 2 %
tonic 4 *
Вывод
\ /
.|***********|.
.|***********|.
..\*********/..
...|*******|...
...|%%%%%%%|...
....\%%%%%/....
.....\___/.....
Ввод
10 23
.........\ /.........
........./ \.........
......../ \........
......./ \.......
....../ \......
...../ \.....
..../ \....
.../ \...
../ \..
./___________________\.
1
acid 5 X
Вывод
.........\ /.........
........./ \.........
......../ \........
......./ \.......
....../XXXXXXXXX\......
...../XXXXXXXXXXX\.....
..../XXXXXXXXXXXXX\....
.../XXXXXXXXXXXXXXX\...
../XXXXXXXXXXXXXXXXX\..
./___________________\.
Ввод
16 28
...| |...
...| |...
...| |...
...| |...
...| |...
...| |...
....| |....
....| |....
....| |....
....| |....
....| |....
.....| |.....
.....| |.....
.....| |.....
.....| |.....
......|______________|......
4
kahlua 4 k
baileys 5 b
cointreau 3 c
fire 1 !
Вывод
...| |...
...| |...
...|!!!!!!!!!!!!!!!!!!!!|...
...|cccccccccccccccccccc|...
...|cccccccccccccccccccc|...
...|cccccccccccccccccccc|...
....|bbbbbbbbbbbbbbbbbb|....
....|bbbbbbbbbbbbbbbbbb|....
....|bbbbbbbbbbbbbbbbbb|....
....|bbbbbbbbbbbbbbbbbb|....
....|bbbbbbbbbbbbbbbbbb|....
.....|kkkkkkkkkkkkkkkk|.....
.....|kkkkkkkkkkkkkkkk|.....
.....|kkkkkkkkkkkkkkkk|.....
.....|kkkkkkkkkkkkkkkk|.....
......|______________|......
В первом примере из условия ингредиент gin наливается в седьмую и шестую строки изображения стакана, а ингредиент tonic в пятую, четвертую, третью и вторую.
В не очень далёкой галактике на планете Икс-Бомбикс тоже проводится чемпионат мира по футболу. На этой планете солнечные лучи в течение всего дня падают ровно вертикально вниз.
Возле главного стадиона расположена сторожевая башня, состоящая из n плит, расположенных друг над другом так, что их левые края прикреплены к общей колонне. Длина i-й плиты равна ai.
Занимать пост на сторожевой башне стадиона вызвались m добровольцев - охранников. j-й доброволец имеет ширину плеч bj, а высота любого из них меньше, чем расстояние между соседними плитами.
С башни открывается отличный вид на стадион, поэтому очень много добровольцев хотят на неё попасть. В то же время из-за техники безопасности при распределении охранников по плитам башни должны выполняться следующие условия:
- Охранник будет стоять на плите боком, поэтому ширина плеч охранника не должна превышать длины плиты.
- Охранник должен быть расположен на плите полностью - по краям плиты стоят защитные ограждения (чтобы с неё нельзя было упасть).
- Охранник должен полностью находиться под солнечными лучами (если он будет в тени хотя бы частью тела, то за время матча замерзнет).
- На одной плите может быть не более одного охранника (два добровольца не поделят место под солнцем).
Изучите графическое представление первого теста ниже в примечании для лучшего понимания задачи.
Вам необходимо расположить максимальное число добровольцев по плитам с выполнением описанных условий. Скорее, матч начнётся с минуты на минуту, а добровольцы так и не знают, кого возьмут охранять главный стадион галактики и кто сможет насладиться крутым видом на игру!
Первая строка входных данных содержит два числа n и m (1≤n,m≤2×10^5) — количество плит, находящееся в башне, и количество добровольцев соответвенно.
Вторая строка входных данных содержит n натуральных чисел ai (1≤ai≤10^18) — длина i-й плиты в порядке снизу вверх.
Третья строка входных данных содержит m натуральных чисел bj(1≤bj≤10^18) — ширина плеч j-го добровольца.
В единственной строке выведите максимальное число добровольцев-охранников, которых можно расположить на плитах, с учетом описанных условий.
| Ввод | Вывод |
|---|---|
| 5 3 | 3 |
| 7 3 4 2 2 | |
| 3 2 1 |
| Ввод | Вывод |
|---|---|
| 2 1 | 0 |
| 2 10 | |
| 11 |
| Ввод | Вывод |
|---|---|
| 5 4 | 3 |
| 100 98 96 40 30 | |
| 2 4 60 3 |
В первом тесте из условия есть 3 светлых участка:
- 5-ю (самую верхнюю) плиту солнце освещает полностью, поэтому на ней находится солнечный участок размера 2;
- 4-я плита - так же размера 2, поэтому она полностью закрыта 5-й.
- 3-я плита имеет общий размер 4, поэтому солнечный участок на ней имеет размер 2 (над остальной частью плиты нависают плиты 5 и 4);
- 2-я плита имеет размер 3 и полностью закрыта от солнца плитой 3.
- 1-я плита имеет общий размер 7, поэтому солнечный участок на ней имеет размер 3 (остальную часть закрывает 3-я плита). Соответственно, доброволец с шириной плеч 3 займет место на солнечном участке 1-й плиты, а добровольцы с шириной плеч 1 и 2 могут встать на плиты 3 и 5 в любом порядке.
