Разбираем реальные задачи для кандидатов в Яндекс

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.
Хабр, это снова я, Алексей Рак (фото не мое). В прошлом году, помимо основной работы, мне довелось стать одним из автором задач для кандидатов в Яндекс. Сегодня наша команда впервые за долгое время публикует на Хабре реальные задачи для разработчиков, которые устраиваются в компанию. Эти задачи использовались до февраля 2020 года при отборе на стажировку для бэкендеров. Решения проверял компьютер. Сейчас кандидатам достаются похожие задания.

Разборы и код сознательно спрятаны в спойлеры. Если вы интересуетесь стажировкой или готовитесь к собеседованиям в большие IT-компании, попробуйте решить одну или несколько задач, прежде чем смотреть разбор. Код представлен на Python, C++ и Java.

Авторы и мои коллеги: задача A — Павел Дорошкевич, B и F — Егор Чунаев, E — Андрей Халявин, C и D — я.

A. День рождения Васи
　Решение и код

B. Закрытый ключ
　Решение и код

C. Программист на пляже
　Решение и код

D. Перемещение чанков
　Решение и код

E. Разделение графа
　Решение и код

F. Поиск
　Решение и код

A. День рождения Васи

Ограничение по времени на тест 3 с
Ограничение по памяти на тест 256 МБ
Ввод стандартный ввод
Вывод стандартный вывод
Вася и его друзья очень любят вкусно поесть. На свой день рождения каждый обязан удивить других, приготовив новые вкусные и полезные блюда.

Сегодня у Васи день рождения, и он позвал своих друзей отведать n своих самых лучших блюд. Название каждого из них состоит из строчных букв английского алфавита, цифр и знака подчеркивания.

Для приготовления блюда с номером i требуется zi ингредиентов. Для каждого ингредиента известно его название, требуемое количество для одной порции блюда, а также единица измерения, в которой это количество задано. Помимо этого, Васе известно, что i-й кулинарный шедевр захотят попробовать ci друзей.

Используются следующие единицы измерения:

  • g, kg — граммы и килограммы соответственно;
  • l, ml — литры и миллилитры соответственно;
  • cnt, tens — одна штука и десять штук соответственно.

В одном килограмме 1000 грамм и в одном литре 1000 миллилитров. Делать перевод из одной единицы измерения в другую можно тогда и только тогда, когда они одновременно обозначают или массу, или объем, или количество.

У Васи есть два справочника ингредиентов. В первом для каждого ингредиента указано его количество в упаковке и цена за упаковку. Во втором справочнике для каждого ингредиента указано содержание белков, жиров, углеводов и энергетическая ценность некоторого количества данного ингредиента.

Васе нужно приготовить все блюда, при этом не купить ничего лишнего. Для этого ему нужно определить, какие ингредиенты и в каком количестве необходимо приобрести в магазине.

Так как друзья именинника очень следят за питанием, то они, перед тем как попробовать Васины блюда, захотят узнать всё: как Вася готовил блюда, их энергетическую ценность и содержание белков, жиров и углеводов. Васе нужно подготовить эту информацию.

Необходимо помочь имениннику подсчитать, сколько требуется потратить денег на покупку продуктов в магазине, какие ингредиенты и в каком количестве нужно купить, а также для каждого блюда посчитать содержание белков, жиров, углеводов и энергетическую ценность, если его съесть полностью.

Входные данные


Первая строка содержит целое число n (1 ⩽ n ⩽ 1000) — количество блюд, которое решил приготовить Вася.

Затем следует описание n блюд. В первой строке содержатся строка di и целые числа сi, zi (1 ⩽ сi, zi ⩽ 100) — название блюда, количество друзей, желающих отведать данное блюдо, и количество ингредиентов необходимых для приготовления. Название блюда состоит из строчных букв английского алфавита, цифр и знака подчеркивания. Его длина не превосходит 20 символов.

В следующих zi строках содержатся описания ингредиентов. В строке с номером j содержатся строка si, j — название ингредиента, целое число ai, j (1 ⩽ ai, j ⩽ 1000) — требуемое количество ингредиента и строка ui, j — название единицы измерения количества. Название ингредиента состоит из строчных букв английского алфавита, цифр и знака подчеркивания. Длина строки не превосходит 20 символов.

Следующая строка содержит целое число k (1 ⩽ k ⩽ 1000) — количество ингредиентов в каталоге цен.

В каждой из следующих k строк содержатся четыре значения ti pi ai ui, описывающих ингредиент.

  • ti — название ингредиента, состоящее из строчных букв английского алфавита, цифр и знака подчеркивания. Длина строки не превосходит 20 символов;
  • pi — стоимость ингредиента, заданная целым числом (1 ⩽ pi ⩽ 1000);
  • ai — количество ингредиента в упаковке в единицах, заданное целым числом (1 ⩽ ai ⩽ 1000);
  • ui — единица измерения количества (l, ml, g, kg, cnt или tens).

Следующая строка содержит число m (1 ⩽ m ⩽ 1000) — количество ингредиентов в каталоге еды.

Далее расположены m строк, в каждой из которых содержатся семь значений ti ai ui pri fi chi fvi, описывающих ингредиент.

  • ti — название ингредиента, состоящее из строчных букв английского алфавита, цифр и знака подчеркивания. Длина строки не превосходит 20 символов;
  • ai — количество ингредиента, для которого указаны характеристики ингредиента, заданное целым числом (1 ⩽ ai ⩽ 1000);
  • ui — единица измерения (l, ml, g, kg, cnt или tens);
  • pri fi chi fvi — содержание белков, жиров, углеводов и энергетическая ценность ингредиента соответственно, заданные вещественными числами с не более чем шестью знаками после запятой (0 ⩽ pri, fi, chi ⩽ 1000, 0 ⩽ fvi ⩽ 10 000).

Гарантируется, что:

  • в каталогах перечислены все ингредиенты, необходимые для приготовления блюд;
  • не существует двух блюд с одинаковым названием;
  • не существует двух ингредиентов в одном каталоге с одинаковым названием;
  • не существует двух ингредиентов в одном блюде с одинаковым названием;
  • для любых двух упоминаний ингредиента единицы измерения, в которых заданы его количества, можно перевести друг в друга.

Выходные данные


Первая строка должна содержать одно целое число: сумма, которую нужно потратить Васе на подготовку к празднику.

Далее должны следовать k строк, в каждой из которых через пробел указано название ингредиента и целое число — количество упаковок, которое необходимо купить. Ингредиенты, выведенные в этих k строках, должны соответствовать ингредиентам, описанным в первом справочнике.

В следующих n строках через пробел должны быть указаны название блюда и его характеристики, описанные четырьмя вещественными числами: белки, жиры, углеводы и энергетическая ценность.

Ингредиенты и блюда разрешается выводить в любом порядке.

Ваш ответ будет считаться правильным, если все целые числа совпадают с соответствующими числами в ответе жюри, а для всех вещественных чисел в ответе их абсолютная или относительная погрешность не превосходит 10-3. Более формально, пусть вещественное число в вашем ответе равно A, а соответствующее число в ответе жюри равно B. Тогда число A будет считаться корректным, если $\frac{|A - B|}{max(1,B)}⩽10^{-3}$.

Пример

Входные данные Выходные данные
2
sandwich 7 3
butter 10 g
toasted_bread 2 cnt
sausage 30 g
omelet 9 4
egg 4 cnt
milk 120 ml
salt 1 g
sausage 50 g
7
egg 61 1 tens
milk 58 1 l
sausage 100 480 g
butter 120 180 g
cream 100 350 g
salt 14 1000 g
toasted_bread 40 20 cnt
8
egg 1 cnt 13 12 1 16.4
milk 1 l 3 4.5 4.7 60
chocolate 90 g 6.8 36.3 47.1 546
salt 1 kg 0 0 0 0
strawberry 100 g 0.4 0.1 7 35
sausage 100 g 10 18 1.5 210
toasted_bread 5 cnt 7.3 1.6 52.3 248
butter 100 g 0.8 72.5 1.3 661		 734
egg 4
milk 2
sausage 2
butter 1
cream 0
salt 1
toasted_bread 1
sandwich 6.00 13.29 21.50 228.3
omelet 57.360 57.540 5.314 177.800

Примечание


В первом примере Васе необходимо приготовить 7 бутербродов и 9 омлетов.

Для приготовления всех первых блюд необходимо 10 ⋅ 7 грамм масла, 2 1 7 кусочков хлеба и 30 ⋅ 7 грамм колбасы. В каждом из бутерброде будет содержаться $0.8 ⋅ \frac {10}{100} + 7.3 ⋅ \frac {2}{5} + 10 ⋅ \frac {30}{100} =6$ грамм белков, $72.5 ⋅ \frac {10}{100} + 1.6 ⋅ \frac {2}{5} + 18 ⋅ \frac {30}{100} =13.29$ грамм жиров и $1.3 ⋅ \frac {10}{100} + 52.3 ⋅ \frac {2}{5} + 1.5 ⋅ \frac {30}{100} =21.5$ грамм углеводов. Энергетическаая ценность составит $661 ⋅ \frac {10}{100} + 248 ⋅ \frac {2}{5} + 210 ⋅ \frac {30}{100} =228.3 ккал$.

Для приготовления всех вторых блюд необходимо 4 ⋅ 9 = 36 яиц, 120 ⋅ 9 = 1080 миллилитров молока, 9 грамм соли, 50 ⋅ 9 = 450 грамм колбасы. В каждом омлете будет содержаться $13 ⋅ 4+ 3 ⋅ \frac {120}{1000} + 10 ⋅ \frac {50}{100} =57.36$ грамм белков, $12 ⋅ 4+ 4.5 ⋅ \frac {120}{1000} + 18 ⋅ \frac {50}{100} =57,54 жиров$ и $1 ⋅ 4+ 4.7 ⋅ \frac {120}{1000} + 1.5 ⋅ \frac {50}{100} =5.314$ углеводов. Энергетическая ценность составит $16 ⋅ 4+ 60 ⋅ \frac {120}{1000} + 210 ⋅ \frac {50}{100} =177.8$ ккал.

Всего необходимо 70 грамм масла, 36 яиц, 1080 литров молока, 9 грамм соли, 210 + 450 = 660 грамм колбасы и 14 кусочков тостового хлеба.

Таким образом, в магазине нужно купить одну упаковку масла, 4 десятка яиц, 2 упаковки колбасы и молока, по одной упаковке соли и тостового хлеба, заплатив 120 + 61 ⋅ 4 + 100 ⋅ 2 + 58 ⋅ 2 + 14 + 40 = 734 рубля.

Решение
Итак, в задаче даны описания n блюд dishes, справочник с описанием цен prices для каждого из k ингредиентов, а также каталог catalog, где содержится описание количества белков, жиров и углеводов для m ингредиентов.

Для решения задачи нужно:

1. Определить, сколько требуется потратить денег на продукты, и указать минимальное количество каждого из них.
2. Вывести суммарное количество белков, жиров, углеводов и энергетическую ценность для каждого блюда.

Эти подзадачи можно решать независимо.

Опишем алгоритм для первой подзадачи. Нам нужны блюда dishes и справочник с описанием цен prices.

1. Заведем хэш-таблицу inredients, где ключ — название ингредиента, а значение — количество (в единицах измерения).
2. Для каждого блюда перебираем набор его ингредиентов.
3. Зная требуемое количество блюд и ингредиентов в блюде, добавляем в ingredients по ключу с названием ингредиента эту информацию.
4. Когда все блюда обработаны, для каждого ингредиента суммарное количество по всем блюдам делим на указанное количество в справочнике цен prices с округлением вверх.
5. Зная суммарное необходимое количество ингредиентов, легко найти итоговую сумму. Стоит иметь в виду, что для хранения суммарного количества денег 32-битного типа недостаточно.
6. Выводим сначала общее количество денег, а затем k строк с названием ингредиента и его количества.

Стоит обратить внимание, что если какой-то из ингредиентов не был использован ни разу, его все равно нужно вывести и указать число 0.

Опишем последовательность действий для второй подзадачи. Нам нужны блюда dishes и каталог с описанием ингредиентов catalog:

1. Для каждого блюда перебираем его набор ингредиентов.
2. Берем из каталога информацию об ингредиенте, умножаем на его количество в блюде и делим на количество, указанное в каталоге.
3. Прибавляем к ответу.
4. После обработки всех ингредиентов блюда выводим на экран.

Также стоит обратить особое внимание на работу с переводом величин. Так как единицы измерения в пределах одной группы кратны 10 ил 1000, можно использовать тип Decimal или целые числа. При использовании целых чисел стоит заранее умножить величины в описании блюд на 1000, так как при конвертации из граммов в килограммы и из миллилитров в литры необходимо деление. Так как перевод величин необходимо выполнять в нескольких местах, лучше всего вынести данную логику в функцию или класс.

Тип данных float плохо подходит для хранения количества ингредиента, так как имеет точность всего лишь в 6-7 десятичных знаков и требует обрабатывать ошибки округления. Точности типа данных double достаточно для выполнения операций и вывода результатов. Его можно использовать, если корректно делать округление.

Асимптотическая сложность алгоритма при использовании хэш-таблиц для каталога и справочника: $O(\sum_{i=1}^{n}z_i)$, где zi — количество ингредиентов в i-м блюде.

Код на Python
import collections
import math
import typing
from decimal import Decimal


class Amount(object):
    def __init__(self, count: Decimal, unit: str):
        self.count = count
        self.unit = unit

    def convert_to(self, unit: str):
        multipliers_dict = {
            'g': 1,
            'kg': 1000,
            'ml': 1,
            'l': 1000,
            'cnt': 1,
            'tens': 10
        }
        assert self.is_compatible(self.unit, unit)

        return Amount(self.count * multipliers_dict[self.unit] / multipliers_dict[unit], unit)

    @staticmethod
    def is_compatible(unit1, unit2):
        unit_classes = [
            ('g', 'kg'),
            ('ml', 'l'),
            ('cnt', 'tens')
        ]

        for unit_class in unit_classes:
            if unit1 in unit_class:
                return unit2 in unit_class
        return False


class FoodInfo(object):
    def __init__(self, proteins: Decimal = Decimal(0), fats: Decimal = Decimal(0), carbohydrates: Decimal = Decimal(0), food_value: Decimal = Decimal(0)):
        self.proteins = proteins
        self.fats = fats
        self.carbohydrates = carbohydrates
        self.food_value = food_value

    def __mul__(self, other: Decimal):
        assert isinstance(other, Decimal)

        return FoodInfo(self.proteins * other, self.fats * other, self.carbohydrates * other, self.food_value * other)

    def __add__(self, other):
        assert isinstance(other, FoodInfo)

        return FoodInfo(
            self.proteins + other.proteins,
            self.fats + other.fats,
            self.carbohydrates + other.carbohydrates,
            self.food_value + other.food_value
        )


class AmountFoodInfo(object):
    def __init__(self, amount, food_info):
        self.amount = amount
        self.food_info = food_info


class Ingredient(object):
    def __init__(self, name: str, amount: Amount):
        self.name = name
        self.amount = amount


class CatalogIngredientInfo(object):
    def __init__(self, name: str, price: int, amount: Amount):
        self.name = name
        self.price = price
        self.amount = amount


class Dish(object):
    def __init__(self, name: str, count: int, ingredients: typing.List[Ingredient]):
        self.name = name
        self.count = count
        self.ingredients = ingredients


def read_dishes():
    dish_count = int(input())

    dishes = []
    for _ in range(dish_count):
        dish_name, dish_count, ingredient_count = input().split(' ')
        ingredient_count = int(ingredient_count)

        ingredients = []
        for _ in range(ingredient_count):
            ingredient_name, amount, unit = input().split(' ')
            ingredients.append(Ingredient(name=ingredient_name, amount=Amount(Decimal(amount), unit)))

        dishes.append(Dish(name=dish_name, ingredients=ingredients, count=int(dish_count)))

    return dishes


def read_catalog():
    ingredient_count = int(input())

    catalog = {}
    for _ in range(ingredient_count):
        name, price, amount, unit = input().split(' ')
        catalog[name] = CatalogIngredientInfo(
            name=name,
            price=int(price),
            amount=Amount(Decimal(amount), unit)
        )

    return catalog


def read_food_info():
    info_count = int(input())

    food_info = {}
    for _ in range(info_count):
        name, amount, unit, proteins, fats, carbohydrates, food_value = input().split(' ')
        food_info[name] = AmountFoodInfo(
            amount=Amount(
                count=Decimal(amount),
                unit=unit
            ),
            food_info=FoodInfo(
                proteins=Decimal(proteins),
                fats=Decimal(fats),
                carbohydrates=Decimal(carbohydrates),
                food_value=Decimal(food_value)
            )
        )

    return food_info


def main():
    dishes = read_dishes()
    catalog = read_catalog()
    food_info = read_food_info()

    need_ingredients = collections.defaultdict(Decimal)
    need_ingredients_count = collections.defaultdict(int)
    dish_info = collections.defaultdict(FoodInfo)
    for dish in dishes:
        for ingredient in dish.ingredients:
            converted_amount = ingredient.amount.convert_to(catalog[ingredient.name].amount.unit)
            converted_food_info_amount = food_info[ingredient.name].amount.convert_to(catalog[ingredient.name].amount.unit)
            need_ingredients[ingredient.name] += converted_amount.count * dish.count
            dish_info[dish.name] += food_info[ingredient.name].food_info * (converted_amount.count / converted_food_info_amount.count)

    total_price = Decimal(0)
    for ingredient_name, need_ingredient in need_ingredients.items():
        need_count = need_ingredient // catalog[ingredient_name].amount.count
        if need_count * catalog[ingredient_name].amount.count < need_ingredient:
            need_count += 1

        need_ingredients_count[ingredient_name] = need_count
        total_price += catalog[ingredient_name].price * need_count

    print(total_price)
    for name in catalog.keys():
        print(name, need_ingredients_count[name])

    for name, info in dish_info.items():
        print(name, info.proteins, info.fats, info.carbohydrates, info.food_value)


if __name__ == '__main__':
    main()

Код на C++
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>
#include <unordered_map>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int ll;
typedef long double ld;

const int INF = 1000 * 1000 * 1000 + 21;
const ll LLINF = (1ll << 60) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 10 * 1000 + 227;
const int MAX_LEN = 35;

struct ig_info {
    ll cost = 0;
    ll cnt = 0;
    ll buy_cnt = 0;
    ll eg_cnt = 0;
    ld arr[4] = {0.0, 0.0, 0.0, 0.0};
};

struct rs {
    string name;
    ll mult = 0;
    vector<pair<string, ll>> igs;
    ld arr[4] = {0.0, 0.0, 0.0, 0.0};
};

int n, k, m;
char buf[MAX_LEN];
char buf_cnt[MAX_LEN];
rs arr[MAX_N];
unordered_map<string, ig_info> info;

ll get_cnt() {
    ll cnt;
    scanf("%lld %s", &cnt, buf_cnt);
    if (!strcmp(buf_cnt, "kg") || !strcmp(buf_cnt, "l")) {
        return 1000 * cnt;
    }
    if (!strcmp(buf_cnt, "tens")) {
        return 10 * cnt;
    }
    return cnt;
}

int main() {
#ifdef CH_EGOR
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#else
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int sz;
        scanf("%s%lld%d", buf, &arr[i].mult, &sz);
        arr[i].name = buf;
        arr[i].igs.resize(sz);
        for (int j = 0; j < sz; ++j) {
            scanf("%s", buf);
            arr[i].igs[j].first = buf;
            arr[i].igs[j].second = get_cnt();
        }
    }

    scanf("%d", &k);
    for (int i = 0; i < k; ++i) {
        ll cost;
        scanf("%s%lld", buf, &cost);
        ig_info& cur_info = info[buf];
        cur_info.cost = cost;
        cur_info.cnt = get_cnt();
    }

    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        scanf("%s", buf);
        ig_info& cur_info = info[buf];
        cur_info.eg_cnt = get_cnt();
        for (int j = 0; j < 4; ++j) {
            double x;
            scanf("%lf", &x);
            cur_info.arr[j] = x;
        }
        if (cur_info.cnt == 0) {
            info.erase(buf);
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < (int)arr[i].igs.size(); ++j) {
            ig_info& cur_info = info[arr[i].igs[j].first];
            cur_info.buy_cnt += arr[i].mult * arr[i].igs[j].second;
            for (int k = 0; k < 4; ++k) {
                arr[i].arr[k] += ((double)arr[i].igs[j].second / (double)cur_info.eg_cnt) * cur_info.arr[k];
            }
        }
    }

    ll ans = 0;
    for (auto& cur_info : info) {
        cur_info.second.buy_cnt = (cur_info.second.buy_cnt + cur_info.second.cnt - 1) / cur_info.second.cnt;
        ans += cur_info.second.buy_cnt * cur_info.second.cost;
    }

    printf("%lld\n", ans);

    for (const auto& cur_info : info) {
        printf("%s %lld\n", cur_info.first.c_str(), cur_info.second.buy_cnt);
    }

    for (int i = 0; i < n; ++i) {
        printf("%s ", arr[i].name.c_str());
        for (int j = 0; j < 4; ++j) {
            printf("%.20lf%c", (double)arr[i].arr[j], " \n"[j == 3]);
        }
    }

    return 0;
}

Код на Java
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.HashMap;
import java.io.IOException;
import java.util.Map.Entry;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ch_egor
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        Recipes solver = new Recipes();
        solver.solve(1, in, out);
        out.close();
    }

    static class Recipes {
        static final int CNT_ENERGY = 4;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();

            Recipes.Recipe[] recipes = new Recipes.Recipe[n];
            for (int i = 0; i < n; ++i) {
                recipes[i] = new Recipes.Recipe();
                recipes[i].name = in.nextString();
                recipes[i].mult = in.nextLong();

                int ingredientsSize = in.nextInt();
                recipes[i].ingredients = new Recipes.Ingredient[ingredientsSize];
                for (int j = 0; j < recipes[i].ingredients.length; ++j) {
                    recipes[i].ingredients[j] = new Recipes.Ingredient();
                    recipes[i].ingredients[j].name = in.nextString();
                    recipes[i].ingredients[j].cnt = readCnt(in);
                }
            }

            int k = in.nextInt();
            HashMap<String, Recipes.IngredientBuyInfo> ingredientBuyInfo = new HashMap<>();
            for (int i = 0; i < k; ++i) {
                String name = in.nextString();

                Recipes.IngredientBuyInfo curBuyInfo = new Recipes.IngredientBuyInfo();
                curBuyInfo.cost = in.nextLong();
                curBuyInfo.cnt = readCnt(in);

                ingredientBuyInfo.put(name, curBuyInfo);
            }

            int m = in.nextInt();
            HashMap<String, Recipes.IngredientEnergyInfo> ingredientEnergyInfo = new HashMap<>();
            for (int i = 0; i < m; ++i) {
                String name = in.nextString();

                Recipes.IngredientEnergyInfo curEnergyInfo = new Recipes.IngredientEnergyInfo();
                curEnergyInfo.cnt = readCnt(in);
                for (int j = 0; j < CNT_ENERGY; ++j) {
                    curEnergyInfo.energyArr[j] = in.nextDouble();
                }

                ingredientEnergyInfo.put(name, curEnergyInfo);
            }

            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < recipes[i].ingredients.length; ++j) {
                    Recipes.IngredientBuyInfo curBuyInfo = ingredientBuyInfo.get(recipes[i].ingredients[j].name);
                    curBuyInfo.buyCnt += recipes[i].mult * recipes[i].ingredients[j].cnt;

                    Recipes.IngredientEnergyInfo curEnergyInfo = ingredientEnergyInfo.get(recipes[i].ingredients[j].name);
                    for (int p = 0; p < CNT_ENERGY; ++p) {
                        recipes[i].energyArr[p] += ((double) recipes[i].ingredients[j].cnt / (double) curEnergyInfo.cnt) * curEnergyInfo.energyArr[p];
                    }
                }
            }

            long totalCost = 0;
            for (HashMap.Entry<String, Recipes.IngredientBuyInfo> entry : ingredientBuyInfo.entrySet()) {
                totalCost += entry.getValue().cost * ((entry.getValue().buyCnt + entry.getValue().cnt - 1) / entry.getValue().cnt);
            }

            out.println(totalCost);

            for (HashMap.Entry<String, Recipes.IngredientBuyInfo> entry : ingredientBuyInfo.entrySet()) {
                out.println(entry.getKey() + " " + ((entry.getValue().buyCnt + entry.getValue().cnt - 1) / entry.getValue().cnt));
            }

            for (int i = 0; i < n; ++i) {
                out.print(recipes[i].name + " ");
                for (int j = 0; j < CNT_ENERGY; ++j) {
                    out.print(String.format("%.20f", recipes[i].energyArr[j]) + (j == CNT_ENERGY - 1 ? "\n" : " "));
                }
            }
        }

        private long readCnt(InputReader in) {
            int cnt = in.nextInt();
            String type = in.nextString();
            if (type.compareTo("kg") == 0 || type.compareTo("l") == 0) {
                return 1000 * cnt;
            }
            if (type.compareTo("tens") == 0) {
                return 10 * cnt;
            }
            return cnt;
        }

        static class Ingredient {
            String name;
            long cnt;

        }

        static class IngredientBuyInfo {
            long cost;
            long cnt;
            long buyCnt;

        }

        static class IngredientEnergyInfo {
            long cnt;
            double[] energyArr;

            IngredientEnergyInfo() {
                energyArr = new double[CNT_ENERGY];
                for (int i = 0; i < CNT_ENERGY; ++i) {
                    energyArr[i] = 0.0;
                }
            }

        }

        static class Recipe {
            String name;
            long mult;
            Recipes.Ingredient[] ingredients;
            double[] energyArr;

            Recipe() {
                energyArr = new double[CNT_ENERGY];
                for (int i = 0; i < CNT_ENERGY; ++i) {
                    energyArr[i] = 0.0;
                }
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new UnknownError();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new UnknownError();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new UnknownError();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c)) {
                    res.appendCodePoint(c);
                }
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, nextInt());
                }
                if (c < '0' || c > '9') {
                    throw new UnknownError();
                }
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E') {
                        return res * Math.pow(10, nextInt());
                    }
                    if (c < '0' || c > '9') {
                        throw new UnknownError();
                    }
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

        public void println(long i) {
            writer.println(i);
        }

    }
}

B. Закрытый ключ

Ограничение по времени на тест 2 с
Ограничение по памяти на тест 256 МБ
Ввод стандартный ввод
Вывод стандартный вывод

Во всех крупных IT-компаниях немалое внимание уделяется вопросам информационной безопасности, и Яндекс  — не исключение.


Дима и Егор разрабатывают новый сервис YD (Yandex Dorogi) и в данный момент проводят аудит его безопасности. Для шифрования пользовательских данных в YD используется алгоритм шифрования с открытым ключом YS (Yandex Shifrovatel).


Схема работы YS такова: для каждого сервиса генерируется закрытый ключ ($p, q$), где $p$ и $q$ — натуральные числа. По закрытому ключу ($p, q$) генерируется открытый ключ (НОД($p, q$), НОК($p, q$)), который доступен всем пользователям. Если злоумышленник сможет по открытому ключу получить закрытый ключ, то он получит доступ ко всем данным YD и принесет сервису непоправимый вред. Конечно же, Егор и Дима не могут этого допустить, поэтому они хотят сделать так, чтобы злоумышленнику пришлось перебрать очень много вариантов открытого ключа, прежде чем он сможет его угадать.


Дима уже сгенерировал закрытый ключ для YD и получил на его основе открытый ключ ($x, y$). Егору сразу же стало интересно, сколько вариантов закрытого ключа придется перебрать злоумышленнику для взлома YD в худшем случае, иными словами, сколько существует закрытых ключей ($p, q$) таких, что открытым ключом для них является ($x, y$). К сожалению, у Егора есть много других задач, очень важных для запуска YD, поэтому он просит вас вычислить это количество за него.


Входные данные


В первой строке содержатся два целых числа $x$ и $y$ ($1 \leq x \leq y \leq 10^{12}$) — описание открытого ключа.


Выходные данные


Выведите одно целое число — количество закрытых ключей, для которых данный ключ является открытым.


Примеры


Входные данные

5 10
Выходные данные
2
Входные данные
10 11
Выходные данные
0
Входные данные
527 9486
Выходные данные
4

Примечание


В первом примере существует два закрытых ключа, для которых ($5, 10$) является открытым ключом: ($5, 10$) и ($10, 5$).


Во втором примере Дима ошибся, потому что ни один закрытый ключ не порождает открытый ключ ($10, 11$).


В третьем примере подходящими закрытыми ключами являются ($527, 9486$), ($1054, 4743$), ($4743, 1054$), ($9486, 527$).


НОД (наибольшим общим делителем) двух натуральных чисел $p$ и $q$ называется наибольшее число $k$ такое, что $p$ делится на $k$ и $q$ делится на $k$. Например, НОД($6, 15$) равен $3$, а НОД($16, 8$) равен $8$.


НОК (наименьшим общим кратным) двух натуральных чисел $p$ и $q$ называется наименьшее число $k$ такое, что $k$ делится на $p$ и $k$ делится на $q$. Например, НОК($2, 3$) равен $6$, а НОК($10, 20$) равен 20.


Решение и код

Если $y$ не делится на $x$, то ответ, очевидно, равен нулю.


Иначе рассмотрим какую-то пару $p$, $q$, что $gcd(p, q) = x$, а $lcm(p, q) = y$. С каждой такой парой можно сопоставить два числа $p' = \frac{p}{x}$ и $q' = \frac{q}{x}$ такие, что $gcd(p', q') = 1$, а $lcm(p', q') = \frac{y}{x}$.


Иными словами, задачу можно свести к задаче нахождения количества пар взаимно простых чисел $p'$, $q'$ таких, что их $lcm$ равен $\frac{y}{x}$.


Далее будем предполагать что $x = 1$, если это не так, то сводим исходную задачу к задаче $x' = 1$, $y' = \frac{y}{x}$.


Первый вариант решения

Решение за $O(factor(y) + number\_of\_divisors(y) \cdot \log{(y}))$.


Зафиксируем $p'$, тогда ему в пару может подойти только $q' = \frac{y'}{p'}$, поскольку $y' = lcm(p', q') = \frac{p' \cdot q'}{gcd(p', q')} = \frac{p' \cdot q'}{1} = p' \cdot q'$. Единственное, что надо проверить, это равенство $gcd(p', \frac{y'}{p'}) = 1$, это можно сделать алгоритмом Евклида за $O(\log{(y')})$.


Под факторизацией подразумевается любой способ нахождения делителей. С учетом достаточно маленьких ограничений их можно найти просто проверкой всех целых чисел от $1$ до $\sqrt{y'}$, что имеет сложность $O(\sqrt{y'})$. Известно, что количество делителей точно не превосходит $2 \cdot \sqrt{y'}$, так что проверку, что $gcd(p', \frac{y'}{p'}) = 1$, нужно выполнить не более $2 \cdot \sqrt{y'}$ раз, что имеет сложность $O(\sqrt{y'}\log{y'})$.


Получаем решение за $O(\sqrt{y} \log{(y)})$.


Код на С++
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int ll;
typedef long double ld;

const int INF = 1000 * 1000 * 1000 + 21;
const ll LLINF = (1ll << 60) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

ll x, y;

int main() {
#ifdef CH_EGOR
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#else
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif

    scanf("%lld%lld", &x, &y);

    if (y % x != 0) {
        return 0 * printf("0\n");
    }

    y /= x;

    ll ans = 0;
    for (ll i = 1; i * i <= y; ++i) {
        if (y % i == 0) {
            if (gcd(i, y / i) == 1) {
                ans += 1 + (i * i != y);
            }
        }
    }

    printf("%lld\n", ans);

    return 0;
}

Второй вариант решения

Решение за $O(factor(y))$.


Рассмотрим простое число $z$, на которое делится $y'$. Если $lcm(p', q') = y'$, то либо $p'$, либо $q'$ должно делится на $z^{\alpha}$, где $\alpha$ — максимальная степень, с которой $z$ входит в $y'$. Чтобы выполнялось $gcd(p', q') = 1$, одно из этих чисел не должно делиться на $z$.


Иными словами, для каждого простого числа, на которое делится $y'$, мы выбираем, пойдет оно в $p'$ или в $q'$. Тогда ответ на задачу равен $2^{number\_of\_distinct\_prime\_divisors(y')}$.

Код на Python
x, y = map(int, input().split())

if y % x != 0:
    print(0)
else:
    y //= x

    i = 2
    ans = 0
    while i * i <= y:
        if y % i == 0:
            ans += 1
            while y % i == 0:
                y //= i
        i += 1

    if y != 1:
        ans += 1

    print(2 ** ans)

Код на C++
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int ll;
typedef long double ld;

const int INF = 1000 * 1000 * 1000 + 21;
const ll LLINF = (1ll << 60) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

ll x, y;

int main() {
#ifdef CH_EGOR
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#else
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif

    scanf("%lld%lld", &x, &y);

    if (y % x != 0) {
        return 0 * printf("0\n");
    }

    y /= x;

    ll ans = 0;
    for (ll i = 2; i * i <= y; ++i) {
        if (y % i == 0) {
            ++ans;
            while (y % i == 0) {
                y /= i;
            }
        }
    }
    ans += (y != 1);

    printf("%lld\n", (1ll << ans));

    return 0;
}

Код на Java
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ch_egor
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        GcdAndLcm solver = new GcdAndLcm();
        solver.solve(1, in, out);
        out.close();
    }

    static class GcdAndLcm {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            long x = in.nextLong();
            long y = in.nextLong();

            if (y % x != 0) {
                out.println(0);
                return;
            }
            y /= x;

            long ans = 0;
            for (long i = 2; i * i <= y; ++i) {
                if (y % i == 0) {
                    ++ans;
                    while (y % i == 0) {
                        y /= i;
                    }
                }
            }
            if (y != 1) {
                ++ans;
            }

            out.println(1L << ans);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new UnknownError();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new UnknownError();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(long i) {
            writer.println(i);
        }

        public void println(int i) {
            writer.println(i);
        }

    }
}

C. Программист на пляже

Ограничение по времени на тест 2 с
Ограничение по памяти на тест 256 МБ
Ввод стандартный ввод
Вывод стандартный вывод

Однажды программист Алексей из Яндекса взял отпуск и уехал отдыхать на море. В один из дней он пошел на пляж, причем пошел туда не один. Возможно, он пошел туда с мамой, возможно, с бабушкой, а, возможно, с другом или подругой. Важно, что пошел он туда не один.


На пляже программист Алексей обнаружил, что осталось всего $n$ ($2 \leq n \leq 10^6$) свободных лежаков. Но среди всего этого множества лежаков программисту Алексею нужно было всего лишь 2: для него самого и для того (или той), с кем он пришел. Так как программист Алексей очень любил порядок, то он хотел, чтобы лежаки были как можно более похожи друг на друга. Похожесть лежаков можно вычислить следующим образом:


  • Каждому лежаку каким-то образом по его внешним признакам назначается некоторое число $a_i$ ($1 \leq i \leq n$, $0 \leq a_i \leq 10^9$).
  • Затем непохожесть двух лежаков вычисляется как XOR (побитовое исключающее ИЛИ) чисел назначенных этим лежакам. Чем значение непохожести меньше, тем более похожи лежаки.

Помогите программисту Алексею понять, какого минимального значения непохожести лежаков он может достичь, сравнив попарно все свободные лежаки.


Входные данные


В первой строке задано число $T$ ($1 \leq T \leq 1000$) – количество тестов. Каждый тест состоит из двух строк.


В первой строке каждого теста задано число $n$ ($2 \leq n \leq 10^6$) – количество лежаков.


Во второй строке каждого теста заданы $n$ чисел $a_i$ ($1 \leq i \leq n$, $0 \leq a_i \leq 10^9$) – значения, которые были поставлены лежакам в соответствие по внешним признакам.


Сумма $n$ по всем тестам не превосходит $10^6$.


Выходные данные


Для каждого теста выведите по одной строке, в которой должно быть единственное число – минимальное значение непохожести.


Примеры


Входные данные

1
5
1 2 4 8 16
Выходные данные
3
Входные данные
2
2
2 4
4
2 4 6 8
Выходные данные
6
2

Примечание


В первом примере Алексей выберет лежаки со значениями 1 и 2.


В первой части второго примера Алексей может взять только лежаки со значениями 2 и 4. Во второй части он выберет лежаки со значениями 4 и 6.


Решение

Зададим все числа в их двоичном представлении, дополнив ведущими нулями так, чтобы их длины были одинаковы. Далее построим на этих значениях бор, где первое от корня ребро задается старшим разрядом: спускаясь вглубь дерева, вы переходите от старших разрядов к младшим.


Далее найдем все самые отдаленные от корня вершины, которые содержат ровно 2 числа. Каждой такой вершине поставим в соответствие число $z$, равное XOR между числами, которое содержит эта вершина. Тогда ответ на задачу – это минимум всех чисел $z$.


Покажем, что это и правда ответ на задачу. Зададим расстояние от всех выбранных вершин до ближайших листьев числом $k$ – оно также указывает на самый старший разряд, в котором числа отличаются (если $k=0$, то числа равны). Тогда XOR между числами, принадлежащими разным сыновьям некоторой вершины, лежащей на расстоянии $x$ от листьев, будет лежать в отрезке $[2^{x-1}, 2^x - 1]$ (для $x = 0$ ответ $0$, ибо числа полностью совпадают, для $x=1$ ответ $1$, ибо числа отличаются только в последнем разряде, для $x=2$ ответ либо 2, либо 3 и т. д.). Если же ответ задачи достигается не на выбранных нами числах, то по построению получается, что они отличаются в каком-то разряде, старше $k$. В таком случае числа будут отличаются хотя бы на $2^k$. Получаем противоречие, ибо существует попарный XOR меньше.


На самом деле, задачу можно решить без помощи бора, просто отсортировав все числа и взяв попарный XOR между соседними после сортировки числами. Ведь все числа, которые попадали в самые глубокие вершины, содержащие ровно 2 числа, являются также соседними числами после сортировки. Это действительно так, поскольку по построению бора ни одно другое число не может иметь значение из отрезка $[a, b]$, где $a$ и $b$ – числа из некоторой выбранной нами вершины.


Код на Python
import sys


def read_int():
    return int(sys.stdin.readline())
    

def read_ints():
    return list(map(int, sys.stdin.readline().split()))
    
    
def main():
    t = read_int()
    for _ in range(t):
        n = read_int()
        a = sorted(read_ints())
        r = a[0] ^ a[1]
        for i in range(1, n):
            r = min(r, a[i-1] ^ a[i])
            
        print(r)
        
        
if __name__ == '__main__':
    main()

Код на C++
#include <algorithm>
#include <cstdint>
#include <cstdio>

using namespace std;

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    int* v = (int*) malloc(sizeof(int) * n);
    for (int i = 0; i < n; ++i) {
      scanf("%d", &v[i]);
    }
    sort(v, v + n);
    int ans = INT32_MAX;
    for (int i = 1; i < n; ++i) {
      ans = min(ans, v[i] ^ v[i - 1]);
    }
    printf("%d\n", ans);
  }
  return 0;
}

Код на Java
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.lang.Math;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        PairwiseXor solver = new PairwiseXor();
        int n = in.nextInt();
        for (int i = 1; i <= n; ++i) {
            solver.solve(n, in, out);
        }
        out.close();
    }
    
    static class PairwiseXor {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = in.nextInt();
            }
            Arrays.sort(a);
            int answer = 2000000000;
            for (int i = 1; i < n; ++i) {
                answer = Math.min(answer, a[i - 1] ^ a[i]);
            }
            out.println(answer);
        }
    }
 
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
 
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
    }
}

D. Перемещение чанков

Ограничение по времени на тест 1 с
Ограничение по памяти на тест 256 МБ
Ввод стандартный ввод
Вывод стандартный вывод

Хранение данных в распределенном хранилище является крайне сложной задачей, однако инженеры Яндекса успешно с ней справляются.


Один из кластеров хранилища состоит из $m$ серверов, на которых хранятся данные, разбитые на $n$ чанков. Для дефрагментации кластера и возможности отключения старых серверов чанки периодически приходится перемещать между серверами. Перемещение чанков по одному неэффективно, поэтому они перемещают группами. Запрос на перемещение описывается четырьмя числами $a, b, l, r$ и обозначает заказ на перемещение всех чанков с номерами от $l$ до $r$ включительно с сервера с номером $a$ на сервер с номером $b$. После перемещения соотвествующие чанки с сервера с номером $a$ стираются. Таким образом, каждый чанк находится всегда ровно на одном сервере.


При построении распределенных систем очень важно избегать возможности конфликта изменений на кластере. Перед выполнением каждого из запросов необходимо убедиться, что все чанки, участвующие в запросе, находятся на ожидаемом сервере. Иными словами, перед выполнением запроса, описываемого параметрами $a, b, l, r$, необходимо убедиться, что все чанки с номерами от $l$ до $r$ включительно расположены на сервере с номером $a$. В случае, если это неверно, запрос на перемещение чанков отменяется и система переходит к обработке следующего запроса. Если же это верно, то запрос осуществляется и все чанки от $l$ до $r$ включительно перемещаются с сервера $a$ на сервер $b$.


По заданному начальному состоянию кластера и списку запросов перемещения чанков определите, какие запросы будут выполнены.


Входные данные


В первой строке заданы три целых числа $n, m$ и $q$ ($1 \leq n, q \leq 100\,000, 2 \leq m \leq 100\,000$) — количество чанков на кластере, количество серверов, на которых располагаются чанки, и количество запросов, соответственно.


Во второй строке содержатся $n$ чисел $p_i$ ($1 \leq p_i \leq m$), $i$-е из которых обозначает номер сервера, где изначально располагается чанк с номером $i$.


В следующих $q$ строках содержатся описания запросов перемещения чанков в хронологическом порядке.


Каждый запрос описывается четверкой чисел $a_i, b_i, l_i, r_i$ ($1 \leq a_i, b_i \leq m, a_i \neq b_i, 1 \leq l_i \leq r_i \leq n$) и обозначает заказ на перемещение чанков с номерами с $l_i$ по $r_i$ (включительно) с сервера $a_i$ на сервер $b_i$.


Выходные данные


Выведите $q$ строк. В строке с номером $i$ выведите $1$, если запрос с номером $i$ будет выполнен, и $0$, если нет.


Примеры


Входные данные

1 2 1
1
1 2 1 1
Выходные данные
1
Входные данные
1 2 1
1
2 1 1 1
Выходные данные
0
Входные данные
5 5 6
1 2 3 4 5
1 2 1 1
2 3 1 3
4 2 4 4
2 5 1 4
3 2 2 3
3 2 3 3
Выходные данные
1
0
1
0
0
1

Примечание


Рассмотрим третий пример. Изначально расположение чанков на серверах описывается массивом $[1, 2, 3, 4, 5]$.


В первом запросе требуется переместить чанк с номером $1$ с сервера $1$ на сервер $2$. Чанк с номером $1$ находится на сервере $1$, поэтому перемещение будет произведено. После выполнения запроса расположение чанков на серверах описывается массивом $[2, 2, 3, 4, 5]$.


Во втором запросе требуется переместить чанки $1, 2$ и $3$ с сервера $2$ на сервер $3$. Чанк $3$ расположен не на сервере $2$, а на сервере $3$, поэтому операция не будет выполнена. Расположение чанков на серверах останется прежним.


В третьем запросе требуется переместить чанк $4$ с сервера $4$ на сервер $2$. Чанк $4$ находится на сервере $4$, поэтому перемещение будет произведено. После выполнения запроса расположение чанков на серверах будет описываться массивом $[2, 2, 3, 2, 5]$.


В четвертом запросе требуется переместить чанки $1, 2, 3$ и $4$ с сервера $2$ на сервер $5$. Так как чанк $3$ расположен на сервере $3$, а не на сервере $2$, запрос не будет выполнен и расположение чанков останется прежним.


В пятом запросе требуется переместить чанки $2$ и $3$ с сервера $3$ на сервер $2$, но чанк $2$ расположен на сервере $2$, поэтому запрос не будет выполнен и расположение чанков останется прежним.


В шестом запросе требуется переместить чанк $3$ с сервера $3$ на сервер $2$. Чанк с номером $3$ находится на сервере $3$, поэтому перемещение будет произведено и расположение чанков станет описываться массивом $[2, 2, 2, 2, 5]$.


Решение и код
Первый способ

Можно хранить для каждого сервера по одному декартову дереву, содержащему все находящиеся на нем чанки. Для этого при поступлении запроса нужно достать из декартова дерева, соответствующего вершине $a$, все чанки от $l$ до $r$. Это можно сделать за 2 операции Split и одну операцию Merge, то есть за $O(\log n)$. Далее нужно проверить количество чанков, которые удалось достать из этого сервера. Если их в точности $r - l + 1$, то валидация пройдена и нужно вывести $1$, если же нет, то ответ $0$. Количество чанков можно проверить за $O(1)$.

Далее в зависимости от ответа вырезанные чанки нужно вернуть либо обратно на сервер $a$, либо на сервер $b$. Это делается с помощью одной операции Split и двух операций Merge, то есть за сложность $O(\log n)$. Итоговая сложность $O(q \log n)$. Решение можно немного модифицировать и совершать меньше операций в случае ответа $0$, но асимптотически сложность это не улучшит.

Код на Python
import sys
import random

INF = 10**9 + 21

random.seed(227)


class Node(object):
    def __init__(self, x, value):
        self.x = x
        self.value = value
        self.y = random.randint(1, 10**9)

        self.l = None
        self.r = None

def merge(t1, t2):
    if t1 is None:
        return t2
    if t2 is None:
        return t1

    if t1.y < t2.y:
        t1.r = merge(t1.r, t2)
        return t1
    else:
        t2.l = merge(t1, t2.l)
        return t2

def split(t, x):
    if t is None:
        return None, None

    if t.x < x:
        t1, t2 = split(t.r, x)
        t.r = t1
        return t, t2
    else:
        t1, t2 = split(t.l, x)
        t.l = t2
        return t1, t

def add(t, nd):
    if t is None:
        return nd

    if nd.y < t.y:
        nd.l, nd.r = split(t, nd.x)
        return nd

    root = t;

    p = None
    last_l = False
    while t is not None and t.y < nd.y:
        p = t
        if t.x < nd.x:
            last_l = False
            t = t.r
        else:
            last_l = True
            t = t.l

    if last_l:
        p.l = nd
    else:
        p.r = nd

    nd.l, nd.r = split(t, nd.x)

    return root

def remove(t, x):
    if t.x == x:
        return merge(t.l, t.r)

    root = t

    p = None
    last_l = False
    while t is not None and t.x != x:
        p = t
        if t.x < x:
            last_l = False
            t = t.r
        else:
            last_l = True
            t = t.l

    if last_l:
        p.l = merge(t.l, t.r)
    else:
        p.r = merge(t.l, t.r)

    return root

def get_up(t, x):
    cur = None
    while t is not None:
        if t.x >= x and (cur is None or cur.x > t.x):
            cur = t

        if t.x >= x:
            t = t.l
        else:
            t = t.r

    return cur

def get_down(t, x):
    cur = None
    while t is not None:
        if t.x <= x and (cur is None or cur.x < t.x):
            cur = t

        if t.x >= x:
            t = t.l
        else:
            t = t.r

    return cur

def main():
    n, m, q = map(int, sys.stdin.readline().split())
    arr = list(map(int, sys.stdin.readline().split()))

    tree = None

    tree = add(tree, Node(0, INF))
    tree = add(tree, Node(n + 1, INF))

    for i in range(n):
        if i == n - 1 or arr[i] != arr[i + 1]:
            tree = add(tree, Node(i + 1, arr[i]))

    ans = ["0" for i in range(q)]
    for i in range(q):
        a, b, l, r = map(int, sys.stdin.readline().split())

        ptr1 = get_up(tree, l)
        ptr2 = get_up(tree, r)

        if ptr1 is ptr2 and ptr1.value == a:
            pr = get_down(tree, l - 1)
            if pr.x + 1 != l:
                tree = add(tree, Node(l - 1, a))

            if pr.x + 1 == l and pr.value == b:
                tree = remove(tree, pr.x)

            need_add = True
            if r == ptr1.x:
                nx = get_up(tree, r + 1)
                if nx.value == b:
                    need_add = False
                tree = remove(tree, r)

            if need_add:
                tree = add(tree, Node(r, b))

            ans[i] = "1"

    sys.stdout.write("\n".join(ans) + "\n")

main()

Второй способ

Также можно воспользоваться двумя деревьями отрезков c отложенным изменением: на минимум и максимум. Каждое из деревьев отрезков содержит номера серверов, на которых находится каждый из чанков. При поступлении запроса нужно проверить, что и минимум, и максимум на отрезке $[l, r]$ равны $a$ – в таком случае ответ $1$, иначе ответ $0$. Если ответ $1$, то нужно отложенно изменить все значения на этом отрезке на $b$. Итоговая сложность решения такая же: $O(q \log n)$.

Код на C++
#include <iostream>
#include <vector>

using namespace std;

vector<int> min_t;
vector<int> max_t;
vector<int> u;
int p;

inline void update(int i) {
  if (u[i]) {
    int l = i << 1;
    int r = l ^ 1;
    min_t[l] = u[i];
    min_t[r] = u[i];
    max_t[l] = u[i];
    max_t[r] = u[i];
    u[l] = u[i];
    u[r] = u[i];
    u[i] = 0;
  }
}

pair<int, int> get(int i, int l, int r, int ll, int rr) {
  if (r <= ll || rr <= l) {
    return make_pair(INT32_MAX, -1);
  }
  if (ll <= l && r <= rr) {
    return make_pair(min_t[i], max_t[i]);
  }
  update(i);
  int m = (l + r) >> 1;
  auto a = get(i << 1, l, m, ll, rr);
  auto b = get((i << 1) ^ 1, m, r, ll, rr);
  return make_pair(min(a.first, b.first), max(a.second, b.second));
}

void set(int i, int l, int r, int ll, int rr, int v) {
  if (r <= ll || rr <= l) {
    return;
  }
  if (ll <= l && r <= rr) {
    min_t[i] = v;
    max_t[i] = v;
    u[i] = v;
    return;
  }
  update(i);
  int m = (l + r) >> 1;
  int a = i << 1;
  int b = (i << 1) ^ 1;
  set(a, l, m, ll, rr, v);
  set(b, m, r, ll, rr, v);
  min_t[i] = min(min_t[a], min_t[b]);
  max_t[i] = max(max_t[a], max_t[b]);
}

int main() {
  ios_base::sync_with_stdio(false);
  int n, m, q;
  cin >> n >> m >> q;
  p = 1;
  while (p < n) {
    p <<= 1;
  }
  min_t.resize(p << 1);
  max_t.resize(p << 1);
  u.resize(p << 1);
  for (int i = 0; i < n; ++i) {
    cin >> min_t[i + p];
    max_t[i + p] = min_t[i + p];
  }
  for (int i = p - 1; i > 0; --i) {
    min_t[i] = min(min_t[i << 1], min_t[(i << 1) ^ 1]);
    max_t[i] = max(max_t[i << 1], max_t[(i << 1) ^ 1]);
  }
  while (q--) {
    int a, b, l, r;
    cin >> a >> b >> l >> r;
    auto t = get(1, 0, p, --l, r);
    if (t.first == a && t.second == a) {
      set(1, 0, p, l, r, b);
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
  }
  return 0;
}

Код на Python
MAX = 1000000000

n, m, q = map(int, input().split())
v = list(map(int, input().split()))

p = 1
while p < n:
    p *= 2

min_t = [0] * (p * 2)
max_t = [0] * (p * 2)
u = [0] * (p * 2)
min_t[p:p+n] = v
max_t[p:p+n] = v
for i in range(p - 1, 0, -1):
    min_t[i] = min(min_t[2 * i], min_t[2 * i + 1]);
    max_t[i] = max(max_t[2 * i], max_t[2 * i + 1]);

def update(i):
    if u[i] != 0 and i < p:
        a = i * 2
        b = a + 1
        min_t[a] = u[i]
        min_t[b] = u[i]
        max_t[a] = u[i]
        max_t[b] = u[i]
        u[a] = u[i]
        u[b] = u[i]
        u[i] = 0

def get(i, l, r, ll, rr):
    if rr <= l or r <= ll:
        return MAX, -1
    if ll <= l and r <= rr:
        return min_t[i], max_t[i]
    update(i)
    m = (l + r) / 2
    a, b = get(i * 2, l, m, ll, rr);
    c, d = get(i * 2 + 1, m, r, ll, rr);
    return min(a, c), max(b, d)

def set(i, l, r, ll, rr, v):
    if rr <= l or r <= ll:
        return
    if ll <= l and r <= rr:
        min_t[i] = max_t[i] = u[i] = v
        return
    update(i)
    m = (l + r) / 2
    set(i * 2, l, m, ll, rr, v)
    set(i * 2 + 1, m, r, ll, rr, v)
    min_t[i] = min(min_t[i * 2], min_t[i * 2 + 1])
    max_t[i] = max(max_t[i * 2], max_t[i * 2 + 1])

while q > 0:
    q -= 1
    a, b, l, r = map(int, input().split())
    l -= 1
    c, d = get(1, 0, p, l, r)
    if a == c == d:
        print(1)
        set(1, 0, p, l, r, b)
    else:
        print(0)

E. Разделение графа

Ограничение по времени на тест 1 с
Ограничение по памяти на тест 256 МБ
Ввод стандартный ввод
Вывод стандартный вывод

Дан взвешенный неориентированный граф $G$, содержащий $n$ вершин и $m$ ребер.


Разбейте вершины графа на два не пустых множества так, чтобы ребро минимального веса, соединяющее вершины из одного множества, имело максимально большой вес.


Гарантируется, что граф не содержит петель и его нельзя разбить так, чтобы такого ребра не существовало.


Входные данные


В первой строке задано число вершин $n$ ($3 \leq n \leq 10^5$) и число ребер $m$ ($3\leq m \leq 10^5$) графа.


В следующих $m$ строках заданы ребра в формате $u$, $v$, $w$ ($1\leq u, v \leq n$, $u\neq v$, $1 \leq w \leq 10^5$), где $u$ и $v$ задают начальную и конечную вершину ребра, а $w$ — его вес.


Выходные данные


В единственной строке выведите максимальный возможный вес ребра, которое имеет минимальный вес среди тех, что соединяют вершины, принадлежащие одному множеству.


Примеры


Входные данные

3 4
1 2 1
1 2 2
1 3 3
3 2 4
Выходные данные
4
Входные данные
4 5
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
Выходные данные
2

Примечание


Рассмотрим первый пример из условия. В нем возможно всего 3 различных разбиения, удовлетворяющих условию, рассмотрим каждое из них:

  • $\{\{1, 2\}, \{3\}\}$, в таком случае ребра $1$ и $2$ будут будут соединять вершины из одного множества, то есть ответ $1$;
  • $\{\{1, 3\}, \{2\}\}$, в таком случае только ребро $3$ будет соединять вершины из одного множества, то есть ответ $3$;
  • $\{\{2, 3\}, \{1\}\}$, в таком случае только ребро $4$ будет соединять вершины из одного множества, то есть ответ $4$.

Получаем, что ответ на тест достигается при третьем варианте разбиения.


Во втором тесте ответ достигается на разбиении $\{\{1, 3\}, \{2, 4\}\}$. Легко убедиться, расписав все возможные разбиения, что не существует разбиения данного графа, на котором ответ был бы больше.


Решение

Решить задачу с помощью бинарного поиска по ответу.


Предположим, что ответ — $x$. Тогда все ребра, вес которых меньше либо равен $x$, должны соединять вершины из разных множеств, то есть двудольным является граф, построенный на ребрах с весом, меньшим либо равным $x$. Покажем монотонность результата построения в зависимости от $x$. Так, если для некоторого $x$ можно построить граф, удовлетворяющий условию, то граф можно построить и для всех $y < x$. Это следствие того, что для $y$ можно взять такое же разбиение на множества, как и для $x$, а в таком случае ребра между вершинами из одного множества будут иметь вес, больше либо равный $x > y$. Если же для некоторого $x$ нельзя построить граф, удовлетворяющий условию, то его нельзя построить и для $z > x$, так как граф, построенный на ребрах весом меньше $x$, не является двудольным (то есть существует ребро между вершинами из одного множества), а добавлением ребер нельзя восстановить двудольность графа.


Теперь опишем проверку того, что граф удовлетворяет условию, то есть является двудольным. Для этого нужно запустить обход всех вершин (например, в глубину либо в ширину) для каждой компоненты связности. Во время обхода каждой вершине нужно поставить в соответствие $0$ либо $1$. Это делается так:

  • Начинаем обход с некоторой вершины, в соответствие которой ставится $0$.
  • При переходе по ребру от вершины $a$ к вершине $b$ вершине $b$ ставится в соответствие число, противоположное поставленному в соответствие вершине $a$ (например, если $val[a] = 0$, то $val[b] = 1$, и наоборот).

После обхода нужно проверить, что не существует ребра между вершинами, которым соответствует одно и то же число. Если это так, то заданный граф является двудольным.

Сложность одной итерации бинарного поиска равна $O(n + m)$, а решение целиком имеет сложность $O((n + m) \log \max w)$.


Код на Python
import sys

def bfs(g, cl, m, v):
    qu = [v]
    cl[v] = 1

    l = 0
    while l != len(qu):
        v = qu[l]
        l += 1

        for u, w in g[v]:
            if w > m:
                continue
            if cl[u] == 0:
                cl[u] = 3 - cl[v]
                qu.append(u)
            elif cl[v] == cl[u]:
                return False

    return True

def check(g, m):
    cl = [0 for i in range(len(g))]

    for i in range(len(g)):
        if cl[i] == 0 and not bfs(g, cl, m, i):
            return False

    return True

def main():
    n, m = map(int, sys.stdin.readline().split())
    ed = [tuple(map(int, sys.stdin.readline().split())) for i in range(m)]

    g = [[] for i in range(n)]
    mx = 0
    for v, u, w in ed:
        g[v - 1].append((u - 1, w))
        g[u - 1].append((v - 1, w))
        mx = max(mx, w)

    if check(g, mx):
        sys.stdout.write(str(mx) + "\n")
        return

    l = 0
    r = mx + 1

    while r - l > 1:
        m = (l + r) // 2
        if check(g, m):
            l = m
        else:
            r = m

    sys.stdout.write(str(r) + "\n")

main()

Код на C++
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <utility>

struct Solution {
    int n, m;
    std::vector<std::vector<std::pair<int, int>>> graph;
    std::vector<int> colors;

    bool dfs(int v, int color, int bound) {
        colors[v] = color;
        for (const auto &edge : graph[v]) {
            if (edge.second >= bound) {
                continue;
            }
            if (colors[edge.first] == color) {
                return false;
            }
            if (colors[edge.first] == -1) {
                if (!dfs(edge.first, 1 - color, bound)) {
                    return false;
                }
            }
        }
        return true;
    }

    bool check(int bound) {
        for (int i = 0; i < n; i++) {
            if (colors[i] == -1) {
                if (!dfs(i, 0, bound)) {
                    return false;
                }
            }
        }
        return true;
    }

    void run(std::istream &in, std::ostream &out) {
        in >> n >> m;
        graph.assign(n, std::vector<std::pair<int, int>>());
        for (int i = 0; i < m; i++) {
            int u, v, w;
            in >> u >> v >> w;
            u--;
            v--;
            graph[u].emplace_back(v, w);
            graph[v].emplace_back(u, w);
        }
        int l = 0;
        int r = 1000000001;
        while (r - l > 1) {
            int m = (l + r) / 2;
            colors.assign(n, -1);
            if (!check(m)) {
                r = m;
            } else {
                l = m;
            }
        }
        out << l << "\n";
    }
};

int main() {
    std::cin.sync_with_stdio(false);
    std::cin.tie(nullptr);
    Solution().run(std::cin, std::cout);
    return 0;
}

Код на Java
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Graph_AD_Correct {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        Graph solver = new Graph();
        solver.solve(1, in, out);
        out.close();
    }

    static class Graph {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            int m = in.readInt();
            //noinspection unchecked
            List<Graph.Edge>[] g = new List[n];
            for (int i = 0; i < n; i++) {
                g[i] = new ArrayList<>();
            }
            int left = Integer.MAX_VALUE;
            int right = Integer.MIN_VALUE;
            for (int i = 0; i < m; i++) {
                int x = in.readInt() - 1;
                int y = in.readInt() - 1;
                int w = in.readInt();
                g[x].add(new Graph.Edge(y, w));
                g[y].add(new Graph.Edge(x, w));
                left = Math.min(left, w);
                right = Math.max(right, w);
            }
            int[] color = new int[n];
            int ans = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (isBipartite(n, color, g, mid)) {
                    ans = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            if (ans == -1) {
                throw new AssertionError();
            }
            out.printLine(ans);
        }

        private boolean isBipartite(int n, int[] color, List<Graph.Edge>[] g, int mid) {
            Arrays.fill(color, -1);
            for (int i = 0; i < n; i++) {
                if (color[i] == -1) {
                    if (!dfs(i, -1, 0, color, g, mid)) {
                        return false;
                    }
                }
            }
            return true;
        }

        private boolean dfs(int x, int p, int curColor, int[] color, List<Graph.Edge>[] g, int mid) {
            color[x] = curColor;
            for (Graph.Edge e : g[x]) {
                if (e.w >= mid) {
                    continue;
                }
                int y = e.to;
                if (y == p) {
                    continue;
                }
                if (color[y] == color[x]) {
                    return false;
                }
                if (color[y] == -1 && !dfs(y, x, 1 - curColor, color, g, mid)) {
                    return false;
                }
            }
            return true;
        }

        static class Edge {
            int to;
            int w;

            Edge(int to, int w) {
                this.to = to;
                this.w = w;
            }

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(int i) {
            writer.println(i);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

F. Поиск

Ограничение по времени на тест 2 с
Ограничение по памяти на тест 512 МБ
Ввод стандартный ввод
Вывод стандартный вывод

Разработчики Яндекс.Поиска постоянно работают над улучшением алгоритмов ранжирования. Один из алгоритмов, который хотят опробовать, таков.


Поисковый алгоритм состоит из трех этапов: поиск по базе, отбор документов и фильтрация. Во время поиска по базе отбираются $n$ документов-кандидатов для показа пользователю. Каждому документу сопоставляется целое число — релевантность, показывающее, насколько документ подходит пользователю. Чем выше релевантность, тем лучше документ подходит по данному запросу. Обратите внимание, что релевантность может быть даже отрицательной в случае, если документ не имеет никакого отношения к запросу.


Ранжирующий алгоритм хранит данные в закольцованном списке, таким образом, после документа с номером $i$ ($i < n$) следующим в списке является документ с номером $i + 1$, а следующим после документа с номером $n$ будет документ с номером $1$. Во время отбора документов алгоритм выберет некоторый документ (назовем его начальным) и сколько-то следующих за начальным документов, которые будут переданы на фильтрацию.


Во время фильтрации из списка документов, полученных при отборе, может быть удалено несколько документов, но не более $k$. Кроме того, после фильтрации должен остаться хотя бы один документ. Оставшиеся после фильтрации документы показываются пользователю.


Релевантностью выдачи назовем сумму релевантностей документов в ней. По релевантностям документов, полученных во время поиска, определите, какую наибольшую релевантность выдачи можно получить при оптимальной работе алгоритма.


Входные данные


В первой строке задано целое число $t$ — количество тестовых случаев. Далее следует описание тестовых случаев.


Описание каждого теста состоит из двух строк.


В первой строке задано два целых числа $n$ и $k$ ($1 \leq n \leq 100\,000$, $0 \leq k \leq min(n - 1, 100)$) — количество документов, полученных во время поиска, и максимальное количество документов, которые могут быть удалены после фильтрации соответственно.


Во второй строке содержатся $n$ целых чисел $a_i$ ($-10^9 \leq a_i \leq 10^9$) — релевантности документов.


Гарантируется что сумма $n$ по всем тестовым случаям не превосходит $100\,000$.


Выходные данные


Для каждого тестового случая выведите одно целое число — ответ на задачу.


Пример


Входные данные

6
4 0
1 -2 9 10
6 1
5 -5 5 -5 5 -5
6 2
5 -5 5 -5 5 -5
4 3
5 -5 5 -5
8 1
-3 -1 5 6 -200 -200 5 -1
3 1
-1 -2 -3
Выходные данные
20
10
15
10
14
-1

Примечание


В первом примере выгодно выбрать в качестве начального документ с релевантностью $9$ и отправить на фильтрацию его и следующие 2 документа. На стадии фильтрации необходимо оставить все документы.


Во втором примере выгодно выбрать в качестве начального любой документ с релевантностью $5$, отправить на стадию фильтрации его и следующие за ним 2 документа. На стадии фильтрации необходимо удалить документ с релевантностью $-5$, таким образом, на выдачу попадут два документа с релевантностью $5$.


В пятом примере выгодно выбрать в качестве начального документ с номером $7$ и отправить на стадию фильтрации его и следующие $5$ документов. Таким образом, на стадию фильтрации попадут документы с релевантностями $[5, -1, -3, -1, 5, 6]$. На стадии фильтрации выгодно удалить документ с релевантностью $-3$, в результате чего на выдачу попадут документы с релевантностями $[5, -1, -1, 5, 6]$ с суммарной релевантностью $14$.


В последнем примере релевантность выдачи получится отрицательной, так как пользователю необходимо показать хотя бы один документ.


Решение

Если все релевантности документов отрицательны, то ответ — максимум по всем числам. Поскольку нам запрещено брать пустое множество, лучше обработать этот случай отдельно. Все последующие состояния динамики могут соответствовать пустому подотрезку с суммой $0$, но это не улучшит ответ, поскольку мы всегда можем взять какой-то один неотрицательный элемент и это будет не хуже.


Решим задачу, если нет цикличности массива.


Пусть $dp_{i, j}$ — максимальная сумма, которая может быть на каком-то подотрезке $[l; i]$ ($l$ тут не фиксировано и выбирается так, чтобы ответ был максимален), если из него удалили не более $k$ элементов.


Пересчет: $dp_{i, j} = \max({0, dp_{i - 1, j} + a_i, dp_{i - 1, j - 1}})$, что соответствует:


  1. $0$ — попробовать начать новый «пустой» отрезок в этом месте.
  2. $dp_{i - 1, j} + a_i$ — продолжить какой-то оптимальный отрезок, добавив в него i-й элемент.
  3. $dp_{i - 1, j - 1}$ — продолжить какой-то оптимальный отрезок, удалив из него i-й элемент.

Такая динамика считается за $O(nk)$, и ответом на задачу в этом случае является $\max\limits_{\substack{1 \leq i \leq n \\ 0 \leq j \leq k}}{dp_{i, j}}$.


Таким образом, мы учли все подотрезки массива, которые не проходят через стык первого и n-го элемента.


Теперь учтем оставшиеся отрезки.


Пусть $dpl_{i, j}$ — максимальная сумма, которая может быть на некотором подотрезке $[1; i]$, если из него удалили ровно $k$ элементов.


Пересчет: $dpl_{i, j} = \max({dpl_{i - 1, j} + a_i, dpl_{i - 1, j - 1}})$, что соответствует:


  1. $dpl_{i - 1, j} + a_i$ — продолжить отрезок, добавив в него i-й элемент.
  2. $dpl_{i - 1, j - 1}$ — продолжить отрезок, удалив из него i-й элемент.

В отличие от первой динамики, нет необходимости начинать новый отрезок, поскольку левая граница фиксирована.


Аналогично, $dpr_{i, j}$ — максимальная сумма, которая может быть на некотором подотрезке $[i; n]$, если из него удалили ровно $k$ элементов.


Пересчет: $dpr_{i, j} = \max({dpr_{i + 1, j} + a_i, dpr_{i + 1, j - 1}})$, что соответствует:


  1. $dpr_{i +1, j} + a_i$ — продолжить отрезок, добавив в него i-й элемент.
  2. $dpr_{i + 1, j - 1}$ — продолжить отрезок, удалив из него i-й элемент.

Обе эти динамики можно посчитать за $O(nk)$.


Как теперь учесть все отрезки, проходящие через стык первого и n-го элемента? Переберем префикс $p$, который войдет в ответ, а также количество элементов $q$, которое мы удалили на этом префиксе. Самое оптимальное состояние — это $dpl_{p, q}$. Теперь нужно соеденить это состояние с самым оптимальным суффиксом — если точнее, с $\max\limits_{\substack{p < i \leq n \\ 0 \leq j \leq k - q}}{dpr_{i, j}}$.


Этот максимум можно предпросчитать еще одной динамикой $dpr\_max_{i, j} = \max{(dpr_{i, j}, dpr\_max_{i + 1, j}, dpr\_max_{i, j - 1})}$. Сложность такого предпросчета — $O(nk)$, и после него можно находить оптимальный суффикс для каждой фиксированной пары $p$ и $q$ за $O(1)$.


Получаем решение за $O(nk)$ времени и памяти.


Код на Python
import sys

def solve():
    n, k = map(int, sys.stdin.readline().split())
    arr = list(map(int, sys.stdin.readline().split()))

    ans = max(arr)
    if ans <= 0:
        return ans

    dp_l = [[0 for j in range(k + 2)] for i in range(n + 2)]
    dp_r = [[0 for j in range(k + 2)] for i in range(n + 2)]

    for i in range(1, n + 1):
        for j in range(k + 1):
            dp_l[i][j] = max(0, dp_l[i - 1][j] + arr[i - 1])
            if j: dp_l[i][j] = max(dp_l[i][j], dp_l[i - 1][j - 1])
            ans = max(ans, dp_l[i][j])

    for i in range(1, n + 1):
        for j in range(k + 1):
            dp_l[i][j] = dp_l[i - 1][j] + arr[i - 1]
            if j: dp_l[i][j] = max(dp_l[i][j], dp_l[i - 1][j - 1])

    for i in range(n, 0, -1):
        for j in range(k + 1):
            dp_r[i][j] = dp_r[i + 1][j]  + arr[i - 1]
            if j: dp_r[i][j] = max(dp_r[i][j], dp_r[i + 1][j - 1])

    for i in range(1, n + 1):
        for j in range(k + 1):
            if i != 1: dp_l[i][j] = max(dp_l[i][j], dp_l[i - 1][j])
            if j: dp_l[i][j] = max(dp_l[i][j], dp_l[i][j - 1])

    for i in range(n, 0, -1):
        for j in range(k + 1):
            if i != n: dp_r[i][j] = max(dp_r[i][j], dp_r[i + 1][j])
            if j: dp_r[i][j] = max(dp_r[i][j], dp_r[i][j - 1])

    for i in range(1, n):
        for j in range(k + 1):
            ans = max(ans, dp_l[i][j] + dp_r[i + 1][k - j])

    return ans

def main():
    t = int(sys.stdin.readline())

    ans = []
    for i in range(t):
        ans.append(str(solve()))

    sys.stdout.write("\n".join(ans) + "\n")

main()

Код на C++
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int ll;
typedef long double ld;

const int INF = 1000 * 1000 * 1000 + 21;
const ll LLINF = (1ll << 60) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 100 * 1000 + 227;
const int MAX_K = 105;

int n, k;
int arr[MAX_N];
ll dp_l[MAX_N][MAX_K];
ll dp_r[MAX_N][MAX_K];

void solve() {
    scanf("%d%d", &n, &k);

    ll ans = -LLINF;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
        ans = max(ans, (ll)arr[i]);
    }

    if (ans <= 0) {
        printf("%lld\n", ans);
        return;
    }

    for (int i = 0; i <= k; ++i) {
        dp_l[n + 1][i] = 0;
        dp_r[n + 1][i] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            dp_l[i][j] = max(0ll, dp_l[i - 1][j] + arr[i - 1]);
            if (j) {
                dp_l[i][j] = max(dp_l[i][j], dp_l[i - 1][j - 1]);
            }

            ans = max(ans, dp_l[i][j]);
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            dp_l[i][j] = dp_l[i - 1][j] + arr[i - 1];
            if (j) {
                dp_l[i][j] = max(dp_l[i][j], dp_l[i - 1][j - 1]);
            }
        }
    }

    for (int i = n; i >= 1; --i) {
        for (int j = 0; j <= k; ++j) {
            dp_r[i][j] = dp_r[i + 1][j] + arr[i - 1];
            if (j) {
                dp_r[i][j] = max(dp_r[i][j], dp_r[i + 1][j - 1]);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            if (i != 1) {
                dp_l[i][j] = max(dp_l[i][j], dp_l[i - 1][j]);
            }
            if (j) {
                dp_l[i][j] = max(dp_l[i][j], dp_l[i][j - 1]);
            }
        }
    }

    for (int i = n; i >= 1; --i) {
        for (int j = 0; j <= k; ++j) {
            if (i != n) {
                dp_r[i][j] = max(dp_r[i][j], dp_r[i + 1][j]);
            }
            if (j) {
                dp_r[i][j] = max(dp_r[i][j], dp_r[i][j - 1]);
            }
        }
    }

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= k; ++j) {
            ans = max(ans, dp_l[i][j] + dp_r[i + 1][k - j]);
        }
    }

    printf("%lld\n", ans);
}

int main() {
#ifdef CH_EGOR
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#else
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif

    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }

    return 0;
}

Код на Java
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ch_egor
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        MaxSum solver = new MaxSum();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }

    static class MaxSum {
        static final long LLINF = (1L << 60) + 5;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            int k = in.nextInt();

            int[] arr = new int[n];
            long[][] dp_l = new long[n + 2][k + 2];
            long[][] dp_r = new long[n + 2][k + 2];

            long ans = -LLINF;
            for (int i = 0; i < n; ++i) {
                arr[i] = in.nextInt();
                ans = Math.max(ans, arr[i]);
            }

            if (ans <= 0) {
                out.println(ans);
                return;
            }

            for (int i = 0; i <= k; ++i) {
                dp_l[n + 1][i] = 0;
                dp_r[n + 1][i] = 0;
            }

            for (int i = 1; i <= n; ++i) {
                for (int j = 0; j <= k; ++j) {
                    dp_l[i][j] = Math.max(0L, dp_l[i - 1][j] + arr[i - 1]);
                    if (j != 0) {
                        dp_l[i][j] = Math.max(dp_l[i][j], dp_l[i - 1][j - 1]);
                    }

                    ans = Math.max(ans, dp_l[i][j]);
                }
            }

            for (int i = 1; i <= n; ++i) {
                for (int j = 0; j <= k; ++j) {
                    dp_l[i][j] = dp_l[i - 1][j] + arr[i - 1];
                    if (j != 0) {
                        dp_l[i][j] = Math.max(dp_l[i][j], dp_l[i - 1][j - 1]);
                    }
                }
            }

            for (int i = n; i >= 1; --i) {
                for (int j = 0; j <= k; ++j) {
                    dp_r[i][j] = dp_r[i + 1][j] + arr[i - 1];
                    if (j != 0) {
                        dp_r[i][j] = Math.max(dp_r[i][j], dp_r[i + 1][j - 1]);
                    }
                }
            }

            for (int i = 1; i <= n; ++i) {
                for (int j = 0; j <= k; ++j) {
                    if (i != 1) {
                        dp_l[i][j] = Math.max(dp_l[i][j], dp_l[i - 1][j]);
                    }
                    if (j != 0) {
                        dp_l[i][j] = Math.max(dp_l[i][j], dp_l[i][j - 1]);
                    }
                }
            }

            for (int i = n; i >= 1; --i) {
                for (int j = 0; j <= k; ++j) {
                    if (i != n) {
                        dp_r[i][j] = Math.max(dp_r[i][j], dp_r[i + 1][j]);
                    }
                    if (j != 0) {
                        dp_r[i][j] = Math.max(dp_r[i][j], dp_r[i][j - 1]);
                    }
                }
            }

            for (int i = 1; i < n; ++i) {
                for (int j = 0; j <= k; ++j) {
                    ans = Math.max(ans, dp_l[i][j] + dp_r[i + 1][k - j]);
                }
            }

            out.println(ans);
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(long i) {
            writer.println(i);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new UnknownError();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new UnknownError();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c)) {
                    res.appendCodePoint(c);
                }
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return nextString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}
Источник: https://habr.com/ru/company/yandex/blog/493966/

Вернуться к списку

Интересные статьи

Интересные статьи

Telegram, Signal, Wickr Me: выбираем самый безопасный мессенджер и разбираемся, существует ли он
Telegram, Signal, Wickr Me: выбираем самый безопасный мессенджер и разбираемся, существует ли он
Нас часто спрашивают, насколько хорошо те или иные популярные мессенджеры хранят тайны своих пользователей — переписку и пересылаемые файлы, существуют ли риски взлома самих сервисов,...
Hack The Box — прохождение Craft. Копаемся в Git, эксплуатируем уязвимости в API, разбираемся с Vault
Hack The Box — прохождение Craft. Копаемся в Git, эксплуатируем уязвимости в API, разбираемся с Vault
Данной статьей я начну публикацию решений отправленных на дорешивание машин с площадки HackTheBox. Надеюсь, что это поможет хоть кому-то развиваться в области ИБ. Мы рассмотрим, как можно проэк...
Как решить актуальные задачи ИТ в управлении ремонтами оборудования
Как решить актуальные задачи ИТ в управлении ремонтами оборудования
Чем большим количеством информации о состоянии оборудования вы располагаете, тем более предсказуема для вас работа всего предприятия. Справиться с нарастающим потоком данных, выделить главное и п...
Восстановление резервной копии сайта на «1С-Битрикс» стандартными средствами
Восстановление резервной копии сайта на «1С-Битрикс» стандартными средствами
Приступая к животрепещущей теме резервного копирования на «Битрикс», прежде всего хотелось бы поблагодарить разработчиков, реализовавших автоматическое резервное копирование в облачное хранилище в вер...
Реальные сроки изучения слепой печати при низкой мотивации
Реальные сроки изучения слепой печати при низкой мотивации
В статье я опишу свой сугубо субъективный пример того, сколько времени занимает обучение методу комфортной слепой печати. Это с учётом того, что мне данный навык не был критически важен, но иметь...