Как найти решение задачи на codeforces - Исправление недочетов и поиск решений вместе с Examum.ru

#	Name
4A	Watermelon brute force, math	800	x390653
71A	Way Too Long Words strings	800	x287241
231A	Team brute force, greedy	800	x241681
1A	Theatre Square math	1000	x208687
158A	Next Round *special problem, implementation	800	x192208
50A	Domino piling greedy, math	800	x187422
282A	Bit++ implementation	800	x185930
263A	Beautiful Matrix implementation	800	x183144
112A	Petya and Strings implementation, strings	800	x172483
339A	Helpful Maths greedy, implementation, sortings, strings	800	x162766
281A	Word Capitalization implementation, strings	800	x160243
236A	Boy or Girl brute force, implementation, strings	800	x155963
118A	String Task implementation, strings	1000	x154216
266A	Stones on the Table implementation	800	x147144
791A	Bear and Big Brother implementation	800	x142846
546A	Soldier and Bananas brute force, implementation, math	800	x134750
617A	Elephant math	800	x134174
59A	Word implementation, strings	800	x130397
69A	Young Physicist implementation, math	1000	x129453
977A	Wrong Subtraction implementation	800	x125263
96A	Football implementation, strings	900	x124874
110A	Nearly Lucky Number implementation	800	x114930
734A	Anton and Danik implementation, strings	800	x112940
116A	Tram implementation	800	x110428
41A	Translation implementation, strings	800	x109628
266B	Queue at the School constructive algorithms, graph matchings, implementation, shortest paths	800	x106938
677A	Vanya and Fence implementation	800	x105413
271A	Beautiful Year brute force	800	x104335
58A	Chat room greedy, strings	1000	x103715
122A	Lucky Division brute force, number theory	1000	x99031
1030A	In Search of an Easy Problem implementation	800	x95960
160A	Twins greedy, sortings	900	x94764
467A	George and Accommodation implementation	800	x93741
344A	Magnets implementation	800	x91452
136A	Presents implementation	800	x91194
486A	Calculating Function implementation, math	800	x88595
200B	Drinks implementation, math	800	x87922
318A	Even Odds math	900	x87442
61A	Ultra-Fast Mathematician implementation	800	x85893
133A	HQ9+ implementation	900	x85481
705A	Hulk implementation	800	x83293
228A	Is your horseshoe on the other hoof? implementation	800	x82857
405A	Gravity Flip greedy, implementation, sortings	900	x78035
469A	I Wanna Be the Guy greedy, implementation	800	x76272
479A	Expression brute force, math	1000	x74963
1328A	Divisibility Problem math	800	x74469
144A	Arrival of the General implementation	800	x74456
148A	Insomnia cure constructive algorithms, implementation, math	800	x73117
580A	Kefa and First Steps brute force, dp, implementation	900	x72364
520A	Pangram implementation, strings	800	x72218
158B	Taxi *special problem, greedy, implementation	1100	x72000
208A	Dubstep strings	900	x71459
131A	cAPS lOCK implementation, strings	1000	x70281
443A	Anton and Letters constructive algorithms, implementation	800	x70177
25A	IQ test brute force	1300	x68479
268A	Games brute force	800	x68353
996A	Hit the Lottery dp, greedy	800	x68333
785A	Anton and Polyhedrons implementation, strings	800	x67265
337A	Puzzles greedy	900	x65839
141A	Amusing Joke implementation, sortings, strings	800	x65424
1335A	Candies and Two Sisters math	800	x64961
4C	Registration System data structures, hashing, implementation	1300	x63021
510A	Fox And Snake implementation	800	x62706
230A	Dragons greedy, sortings	1000	x62230
492B	Vanya and Lanterns binary search, implementation, math, sortings	1200	x61200
427A	Police Recruits implementation	800	x59419
155A	I_love_%username% brute force	800	x59049
230B	T-primes binary search, implementation, math, number theory	1300	x58277
750A	New Year and Hurry binary search, brute force, implementation, math	800	x57997
339B	Xenia and Ringroad implementation	1000	x57510
1352A	Sum of Round Numbers implementation, math	800	x57082
581A	Vasya the Hipster implementation, math	800	x56743
723A	The New Year: Meeting Friends implementation, math, sortings	800	x56253
732A	Buy a Shovel brute force, constructive algorithms, implementation, math	800	x56067
451A	Game With Sticks implementation	900	x54873
1154A	Restoring Three Numbers math	800	x54517
1399A	Remove Smallest greedy, sortings	800	x53171
1409A	Yet Another Two Integers Problem greedy, math	800	x53065
189A	Cut Ribbon brute force, dp	1300	x52997
151A	Soft Drinking implementation, math	800	x51278
466A	Cheap Travel implementation	1200	x50381
472A	Design Tutorial: Learn from Math math, number theory	800	x49414
432A	Choosing Teams greedy, implementation, sortings	800	x48522
1367A	Short Substrings implementation, strings	800	x48102
1512A	Spy Detected! brute force, implementation	800	x48025
758A	Holiday Of Equality implementation, math	800	x47766
381A	Sereja and Dima greedy, implementation, two pointers	800	x47526
490A	Team Olympiad greedy, implementation, sortings	800	x47394
1343B	Balanced Array constructive algorithms, math	800	x47083
455A	Boredom dp	1500	x46867
630A	Again Twenty Five! number theory	800	x46689
706B	Interesting drink binary search, dp, implementation	1100	x46629
32B	Borze expression parsing, implementation	800	x46524
1560A	Dislike of Threes implementation	800	x46111
579A	Raising Bacteria bitmasks	1000	x45797
1703A	YES or YES? brute force, implementation, strings	800	x45685
313A	Ilya and Bank Account implementation, number theory	900	x45654
703A	Mishka and Game implementation	800	x45076
1742A	Sum implementation	800	x44679
1475A	Odd Divisor math, number theory	900	x44608

Источник

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

Разборы и код сознательно спрятаны в спойлеры. Если вы готовитесь к собеседованиям в большие IT-компании, попробуйте решить одну или несколько задач, прежде чем смотреть разбор. Отправить решение для проверки можно на Codeforces — ответ придёт сразу же (ссылка на Codeforces и примечание). Код представлен на Python, C++ и Java. Важно: авторский «олимпиадный» код не предназначен для продакшена, он написан исходя из того, что система будет проверять его автоматически.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В следующих z_i строках содержатся описания ингредиентов. В строке с номером j содержатся строка s_{i, j} — название ингредиента, целое число a_{i, j} (1 ⩽ a_{i, j} ⩽ 1000) — требуемое количество ингредиента и строка u_{i, j} — название единицы измерения количества. Название ингредиента состоит из строчных букв английского алфавита, цифр и знака подчеркивания. Длина строки не превосходит 20 символов.

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

В каждой из следующих k строк содержатся четыре значения t_i p_i a_i u_i, описывающих ингредиент.

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

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

Далее расположены m строк, в каждой из которых содержатся семь значений t_i a_i u_i pr_i f_i ch_i fv_i, описывающих ингредиент.

t_i — название ингредиента, состоящее из строчных букв английского алфавита, цифр и знака подчеркивания. Длина строки не превосходит 20 символов;
a_i — количество ингредиента, для которого указаны характеристики ингредиента, заданное целым числом (1 ⩽ a_i ⩽ 1000);
u_i — единица измерения (l, ml, g, kg, cnt или tens);
pr_i f_i ch_i fv_i — содержание белков, жиров, углеводов и энергетическая ценность ингредиента соответственно, заданные вещественными числами с не более чем шестью знаками после запятой (0 ⩽ pr_i, f_i, ch_i ⩽ 1000, 0 ⩽ fv_i ⩽ 10 000).

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

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

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

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

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

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

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

Ваш ответ будет считаться правильным, если все целые числа совпадают с соответствующими числами в ответе жюри, а для всех вещественных чисел в ответе их абсолютная или относительная погрешность не превосходит 10^-3. Более формально, пусть вещественное число в вашем ответе равно A, а соответствующее число в ответе жюри равно B. Тогда число A будет считаться корректным, если

$frac{|A - B|}{max(1,B)}⩽10^{-3}$ .

Пример

Примечание

В первом примере Васе необходимо приготовить 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)$ , где z_i — количество ингредиентов в 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("%lldn", ans);

    for (const auto& cur_info : info) {
        printf("%s %lldn", 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. Закрытый ключ

Во всех крупных 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

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

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

10 11

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

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

527 9486

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

Примечание

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

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

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

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

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

Решение и код

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

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

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

Далее будем предполагать что $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$ , это можно сделать алгоритмом Евклида за .

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

Получаем решение за .

Код на С++

#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("0n");
    }

    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("%lldn", ans);

    return 0;
}

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

Решение за .

Рассмотрим простое число $z$ , на которое делится $y'$ . Если , то либо $p'$ , либо $q'$ должно делится на $z^{alpha}$ , где $alpha$ — максимальная степень, с которой $z$ входит в $y'$ . Чтобы выполнялось , одно из этих чисел не должно делиться на $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("0n");
    }

    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("%lldn", (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. Программист на пляже

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

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

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

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

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

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

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

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

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

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

Примеры

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

1
5
1 2 4 8 16

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

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

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

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$ – числа из некоторой выбранной нами вершины.

Код на 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("%dn", 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. Перемещение чанков

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

1 2 1
1
1 2 1 1

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

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

1 2 1
1
2 1 1 1

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

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

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

Примечание

Рассмотрим третий пример. Изначально расположение чанков на серверах описывается массивом .

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

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

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

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

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

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

Решение и код

Первый способ

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

$a$ , все чанки от

$l$ до

$r$ . Это можно сделать за 2 операции Split и одну операцию Merge, то есть за

. Далее нужно проверить количество чанков, которые удалось достать из этого сервера. Если их в точности

, то валидация пройдена и нужно вывести

$1$ , если же нет, то ответ

$0$ . Количество чанков можно проверить за

$O(1)$ .

Далее в зависимости от ответа вырезанные чанки нужно вернуть либо обратно на сервер

$a$ , либо на сервер

$b$ . Это делается с помощью одной операции Split и двух операций Merge, то есть за сложность

. Итоговая сложность

. Решение можно немного модифицировать и совершать меньше операций в случае ответа

$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 отложенным изменением: на минимум и максимум. Каждое из деревьев отрезков содержит номера серверов, на которых находится каждый из чанков. При поступлении запроса нужно проверить, что и минимум, и максимум на отрезке

равны

$a$ – в таком случае ответ

$1$ , иначе ответ

$0$ . Если ответ

$1$ , то нужно отложенно изменить все значения на этом отрезке на

$b$ . Итоговая сложность решения такая же:

Код на 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. Разделение графа

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

Примечание

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

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

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

Решение

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

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

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

$0$ либо

$1$ . Это делается так:

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

Сложность одной итерации бинарного поиска равна , а решение целиком имеет сложность .

Код на 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. Поиск

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

Примечание

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

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

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

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

Решение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как теперь учесть все отрезки, проходящие через стык первого и n-го элемента? Переберем префикс $p$ , который войдет в ответ, а также количество элементов $q$ , которое мы удалили на этом префиксе. Самое оптимальное состояние — это $dpl_{p, q}$ . Теперь нужно соеденить это состояние с самым оптимальным суффиксом — если точнее, с $maxlimits_{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("%lldn", 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("%lldn", 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);

        }

    }
}

Источник

A (Div2) Результат игры

В этой игре можно было просто сделать, то, что просят в условии.А именно, завести счётчик, перебрать все клетки поля, и для каждой клетки найти сумму чисел в клетках, стоящих с ней на одной горизонтали, сумму чисел в клетках, стоящих с ней на одной вертикали, и сравнить эти суммы. Если сумма по вертикали больше, увеличить счётчик на один. После того, как перебраны все клетки, вывести счётчик. Максимальная сумма может быть 2 × 30 × 100 = 6 000, поэтому для её достаточно типа int.

B (Div2) След

Извиняюсь за кривой

Давайте для начала отсортируем радиусы окружностей по убыванию. Пусть у нас теперь радиус первой окружности — r₁, второй окружности — r₂, …, последней окружности — r_n, где r₁ > r₂ > … > r_n. Внешняя область — так, которая снаружи первой окружности — покрашена в синий цвет, значит, область между первой и второй окружностью покрашена в красный. Далее, область между второй и третьей окружностью покрашена в синий цвет, между третьей и четвёртой — в красный, между четвёртой и пятой — в синий, и так далее.

Первая область, закрашенная в красный цвет (область между первой и второй окружностями) — это вся область внутри первой окружности, из которой выкинули внутреннюю область второй окружности. Значит, площадь это области равна π × (r₁² - r₂²). Аналогично, площадь второй красной области (между третьей и четвёртой окружностями) равна π × (r₃² - r₄²). И так далее. Значит, суммарная их площадь равна π × (r₁² - r₂² + r₃² - r₄² + r₅² - r₆² + …). Значит, чтобы посчитать ответ можно, например, сложить квадраты радиусов окружностей с нечётным номером, вычесть из полученной суммы квадраты радиусов всех окружностей с чётными номерами, и полученную величину умножить на pi.

Может возникнуть небольшое затруднение с последней окружностью. Если число окружностей нечётно, то последняя область — не кольцо между двумя окружностями, а круг. Но это, на самом деле, ничего не меняет: тогда последняя окружность имеет нечётный номер, и квадрат её радиуса надо тоже прибавить к сумме.

A (Div1) — C (Div2) Сообщение

Для начала, добавим к строке s с обоих концов по 2000 фиктивному символу — например, <<#>>. Заметим, что это не повлияло на ответ. Действительно, пусть мы взяли подстроку t, частично или полностью состоящую из <<#>>. Тогда все символы <<#>> надо было бы заменить. Но если бы их просто не было, то нужные символы надо было бы добавить.

Рассмотрим оптимальную подстроку t, и последовательность действий, которую надо с ней сделать, чтобы превратить её в строку u. Рассмотрим первое добавление или удаление символа с одного из концов.

Заметим, что это не удаление. Ведь если мы выбрали подстроку t и удалили из неё, к примеру, последний символ, то его не надо было бы и брать, потому что для строки t без последнего символа надо на одно действие меньше, чем для всей строки t.

А теперь заметим, что это и не добавление. Действительно, пусть мы рассмотрели строку t, некоторое время меняли в ней символы на другие, и наконец, добавили один, скажем, в начале. Тогда — Если слева от строки есть символ (то есть, строка там ещё не кончается), то можно было его взять сразу (то есть, рассмотреть не t, а t с ещё одним символом слева). Вместо того, чтобы добавлять символ, можно заменить существующий — это тоже занимает одной действие. — Если слева от строки нету символа (то есть, первый символ t является первым символом строки s), тогда в t есть как минимум 2000 <<#>>. Значит, либо ответ для такой строки как минимум 2000, потому что каждую решётку надо удалить или заменить; либо никаких символов, кроме решёток, в строке t нет, и тогда надо сделать как минимум |u| действий, потому что каждый символ u надо добавить (или сделать из другого символа). Но чтобы получить всего |u| действий, достаточно взять любую подстроку длины |u|.

Таким образом, существует оптимальная подстрока t, из которой получается u без добавлений и удалений. Это ключевой момент решения! Ведь это означает, что длина такой строки равна длине u. Значит, достаточно перебрать подстроки строки s длины |u|. Всего таких подстрок O(|s|), и для каждой подстроки легко за время O(|u|) посчитать необходимое количество изменений — это просто количество символов, которые надо заменить.

Таким образом, получается очень простое в написании решение за время O(|s| × |u|).

B (Div1) — D (Div2) Подозреваемые

Будем называть людей, которые сказали <<Убийство совершил подозреваемый номер a_i>> обвиняющими, а людей, которые сказали <<Подозреваемый номер a_i не совершал убийства>> — оправдывающими. Рассмотрим подозреваемого номер k. Предположим, что он совершил убийство и посчитаем, сколько тогда человек сказали правду. Люди, которые сказали правду — это люди, которые обвиняли его, и люди, которые оправдывали не его. Таким образом, их количество — это количество людей, которые обвинили его, плюс количество людей, которые оправдали кого-либо, и минус количество людей, которые оправдали его. Таким образом, нам надо знать — количество людей, которые кого-либо обвиняют (это легко посчитать за O(n)) — для каждого подозреваемого количество людей которые его обвиняют — для каждого подозреваемого количество людей которые его оправдывают Последние две величины легко посчитать за время O(n) для всех подозреваемых. Действительно, пусть i-того человека обвиняют x_i людей и оправдывают y_i людей. Тогда надо просто для каждого человека номер i, если он оправдывающий, то увеличить y_{a_i}, а если обвиняет — увеличить x_{a_i}.

После этих действий можно за O(1) посчитать для каждого подозреваемого число людей, которые говорят правду в том случае, если он преступник, и если это количество равно m, то данный человек может быть преступником. А после того, как мы нашли список возможных преступников, то не составляет труда для каждого человека определить, может ли он говорить правду и может ли он врать.

С (Div1) — E (Div2) Шифр

Давайте в словах записывать вместо букв цифры: вместо <> — 0, вместо <> — 1, и так далее. Тогда разрешенные операции такие: рассмотреть два соседних числа, и одно из них увеличить на один, а другое — уменьшить на один. Для начала докажем ключевое утверждение задачи: два слова имеют одинаковый смысл тогда и только тогда, когда у них одинаковая длина и одинакова сумма букв.

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

1. Переформулировка первая. Представим себе, что у нас вместо каждого числа — стопка монет, от 0 до 25 штук. Тогда разрешенные действия — это переложить одну монету из какой-то стопки в соседнюю так, чтобы во всех стопках оставалось от 0 до 25 монет.

2. Переформулировка вторая. Рассмотрим последовательность s_i (i = 0, …, n), такую, что s_i равно сумме первых i чисел в слове. Последовательность неубывает и разность между соседними элементами последовательности не превосходит 25. Тогда разрешенная операция — это изменить одно из чисел на один в любую сторону, так, чтобы разность между любыми двумя соседними числами по-прежнему не превосходила 25, и последовательность по-прежнему неубывала.

Таким образом, нам надо посчитать, сколько слов такой же длинны имеют такую же сумму букв. Это легко сделать сразу для всех слов длины не больше 100. Посчитаем с помощью динамики такую величину x[l][s] : количество слов длины l с суммой букв s. — База динамики: l = 0. Есть ровно одно слово (пустое, оно же единственное слово длины 0) с суммой букв 0, и по 0 слов с любой другой суммой букв. — Переход динамики: очень простой. Чтобы узнать, сколько слов длины l имеют сумму s, надо перебрать, какая может быть последняя буква у этого слова: x[l][s] = x[l - 1][s] + x[l - 1][s - 1] + … + x[l - 1][s - 25]. Конечно, надо не забыть считать эту величину по модулю 10⁹ + 7.

После того, как мы посчитали эту величину для всех 0 ≤ l ≤ 100, 0 ≤ s ≤ 2500 за O(100² × 25) памяти и O(100² × 25²) времени, надо просто для каждого слова найти его длину сумму букв и вывести ответ (не забыв вычесть 1).

D (Div1) Улики

Как придумать формулу

Простите все, кому это непривычно, но поскольку интерпретатор ТеХа на Codeforces в данный момент несколько кривоват, вместо традиционных нижних индексов будут нетрадиционные верхние. Это не степени, о степенях я буду оповещать отдельно.

Говоря математическим языком, в задаче надо посчитать количество способов дополнить граф до связного минимальным количеством ребер. Понятно, что сам граф не имеет значения — важны только компоненты связности. Более того, сами компоненты связности не важны, важны только их размеры.

Итак, пусть у нас есть k компонент связности размера s¹, s², …, s^k.Посмотрим, чем равна искомая величина для маленьких k.

Пусть k = 1. Тогда граф уже связный, есть 1 способ добавить ноль ребер.

Пусть k = 2. Тогда в графе две компоненты связности и надо добавить одно ребро между ними. Существует s¹ способ выбрать вершину из первой компоненты, s² способов — из второй, всего s¹s² способов.

Пусть k = 3. Тогда в графе три компоненты связности, и надо провести два ребра, которые будут соединять различные пары компонент связности. Общее количество способов будет равно s¹s² × s¹s³ + s¹s² × s²s³ + s¹s³ × s²s³ = s¹s²s³ × (s¹ + s² + s³) = s¹s²s³ × n.

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

Пусть k = 4. Тогда в графе 4 компоненты связности размера s¹, s², s³, s⁴. Надо провести три ребра. Немного подумав, можно понять, что эти рёбра либо будут соединять одну из компонент связности с остальными тремя, либо первую со второй, вторую — с третьей, а третью — с четвёртой (разумеется, компоненты могут следовать в любом порядке).

Количество способов первого типа: (s¹)³ × s²s³s⁴ + (s²)³ × s¹s³s⁴ + (s³)³ × s¹s²s⁴ + (s⁴)³ × s¹s²s³ = ((s¹)² + (s²)² + (s³)² + (s⁴)²) × (s¹s²s³s⁴).

Количество способов второго типа: есть две компоненты связности, из которых выходит по два ребра. Пусть это первая и вторая. Тогда одно ребро проведено между ними, и ещё одно — из них в другие компоненты связности. Эти два ребра могут быть проведены двумя способами: от первой к третьей, а от второй к четвёртой, или наоборот. Значит, количество таких способов равно 2 × (s¹)² × (s²)² × s³ × s⁴ = 2s¹s² × (s¹s²s³s⁴). И Таких слагаемых 6 штук. Просуммировав их всех и прибавив к ним способы первого типа, можно вынести множитель (s¹s²s³s⁴) за скобки, и останется аккурат формула квадрата суммы 4-х слагаемых. Значит, общее количество способов будет равно (s¹s²s³s⁴) × n².

На этом месте можно было уже легко догадаться до формулы (s¹s²… s^k) × n^k - 2, тем более, что в первом случае получается как раз 1 = (s¹) × n^- 1.

Как доказать формулу

Осталось только эту формулу доказать (хотя, конечно, для того, чтобы сдать задачу, доказательства не требовалось =))

Итак, пусть есть некий набор из k - 1 ребра, который дополняет граф до связного. Построим по нему две последовательности чисел: (x^1, x^2, …, x^{k-2}) и (a^1,a^2,…,a^k). При это каждое x может быть любым числом от 1 до n, а aⁱ может быть любым числом от 1 до sⁱ. Легко понять что таких пар последовательностей аккурат столько же, сколько (якобы!) способов дополнить наш граф до связного.

Пара последовательностей же строится следующим образом.

Для начала заметим, что этот набор из k - 1 ребра как бы образует дерево, в вершинах которого — компоненты связности.

Рассмотрим минимальную по номеру компоненту связности, из которой выходит только одно дополняющее ребро. Пусть это компонента номер i и ребро соединяет вершину номер t в компоненте номер i и вершину номер b в другой компоненте. Тогда x¹ = b, а aⁱ равно (внимание!) номеру вершины t среди вершин компоненты i, то есть, числу от 1 до sⁱ.
Одна из компонент связности теперь отвалилась от графа. Остальные k - 2 ребер дополняют оставшиеся k - 2 компоненты до связного графа. Повторим ту же процедуру еще k - 1 раз.
Осталось одно ребро. Оно соединяет две компоненты связности u и v, которые ещё не упомянуты во второй последовательности. Первая же последовательность заполнена — в ней как раз k - 2 элемента. Осталось во вторую последовательность на места номер u и v записать номера концов оставшегося ребра среди вершин компонент номер u и v соответственно.

Итого, для каждого способа дополнить граф до связного существует такая пара последовательностей. Заметим, что если компонента i была <<висячей>>, то есть, соединялась только с одной другой компонентой, то её вершины не упоминаются в первой последовательности. А если не была висячей — то упоминаются, потому что все рёбра, которые выходят из этой компоненты, надо выкинуть. Каждое ребро, которое мы выкидываем, упирается одним концов в висячую компоненту. И когда было выкинуто первое ребро, выходящее из компоненты i, компонента i не была висячей. Значит, при выкидывании этого ребра в первую последовательность была записана вершина из компоненты i.

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

Значит, в начальный момент, и каждый момент в процессе построения первой последовательности, по оставшемуся куску последовательности можно судить, какие вершины в данный момент висячие.

Итак, пусть у нас есть какой-то, неизвестный способ дополнить граф до связного и мы построили по нему две последовательности (x¹, x², …, x^k - 2) и (a¹, a², …, a^k). Восстановим по ним дополнение графа до связного.

Рассмотрим x¹. Это число говорит нам, что сначала было выкинуто ребро одним концом в x¹, а другим — в наименьшей по номеру висячей компоненте связности. Мы можем её определить, так как знаем текущий список висячих компонент. Пусть это компонента i. Тогда в aⁱ записан номер вершины в компоненте i, которая соединена с x¹. Итак, одно ребро восстановили. Выкидываем компоненту номер i.
Делаем эту операцию ещё k - 1 раз. Выкинуты k - 2 компоненты и восстановлены k - 2 ребра. Осталось два неиспользованных элемента второй последовательности, которые определяют вершины в двух оставшихся компонентах. Эти вершины и надо соединить k - 1-ым ребром.

Итого, по каждой паре последовательностей восстанавливается дополнение до связного графа, из которого эта пара последовательностей была получена. Значит, количество способов дополнить граф до связного равно количеству пар последовательностей, которое и равно (s¹s²… s^k) × n^k - 2.

E (Div1) Оладьи миссис Хадсон

Для начала заметим, что легко придумать очень простое решение этой задачи. Можно просто хранить остаток от деления каждой из цен на каждое из 25 простых чисел от 2 до 97. Тогда каждый запрос будет выполняться за O(25 × 10000). И всего решение будет работать за O(25 × 10000 × 30000) = O(7, 5 × 10⁹) взятий по модулю. К сожалению, это не укладывается в ограничение по времени =)

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

Нет смысла приводить здесь нудные вычисления, показывающие, что это действительно дает прирост производительности — гораздо проще написать программу, которая это подсчитает. Получается порядка 3 × 10⁷ чисел, остатки которых надо перемножить, вместо 10 000 × 30 000 = 3 × 10⁸.

Однако всё же 3 × 10⁷ × 25 = 7, 5 × 10⁸ взятий по модулю. Понятно, что это всё равно не уложится в 5 секунд.

Вторая идея авторского решения.

Рассмотрим 4 модуля:

1224469897 = 7 × 17 × 37 × 47 × 61 × 97

1503325967 = 11 × 13 × 41 × 43 × 67 × 89

1336143462 = 2 × 3 × 23 × 31 × 53 × 71 × 83

937397015 = 5 × 19 × 29 × 59 × 73 × 79

Квадрат всех этих 4 чисел влезает в знаковый 64-битный тип данных и их произведение делится на все простые числа до 100. Для каждой из 10 000 цен чисел будем хранить остаток этой цены по каждому из четырех модулей. Легко посчитать остаток произведения и прибавить к нему константу. По четырём остаткам легко определить, какой будет минимальный делитель — перебрать 25 вариантов.

Итого, такая оптимизация дает асимптотику O(4 × (3 × 10⁷)) = O(1, 2 × 10⁸).

Источник

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

It is needless to say the importance of competitive programming in any Software Engineer’s journey. Most of the beginners have no idea how to use Codeforces and end up wasting a lot of time on it. Most of them also get demotivated when they are not able to solve problems and end up with the thought that they are not capable of doing it.

Codeforces is one of the best platforms for competitive coding and is usually known for its short challenges/contests where programmers from every corner of the world participate. Here you can practice problems from very beginner level to very advanced level. But most people don’t know how to start with Codeforces and how to utilize it fully.

So, here are the few tips that can be followed:

If you are a beginner in competitive coding then don’t directly jump into the contests. First, go into the PROBLEMSET option and set the difficulty level from 800-1000. After that, all the problems of that difficulty level will appear in front of you, and start solving the problems from there. Then solve at least 30-40 problems to get familiar with the type of questions and platform. As soon as you become familiar with those problems you can start with the contests.
Try giving all the contests (there are 2-3 contests every week). Initially, it is possible that you might solve 1 or 2 problems in the contests, or it also might happen that you were not able to solve even a single problem, but you don’t have to lose hope and keep practicing the problems. You can’t become the “top” coder in 1 or 2 months. It requires high consistency and a lot of practice.
As contests are time-bound, so you also have to focus on them and should try solving problems as fast as you can.
Watch editorials only if you have given sufficient time to that problem and don’t watch editorial completely, first see the tags and then start thinking about the problem again. Even after then, if you have no idea how to solve the question then go for the editorial.
After each contest, try to up solve the remaining problems of the contest. It is really important as you will be able to learn many new concepts and tricks from it. For those who don’t know, up-solving means solving the remaining problems of the contests which you were not able to solve during the contest.
After solving any practice problems look at solutions of other users as well as you will learn different and easy approaches from those solutions which will surely help you in further problems.
Keep increasing the difficulty level of the questions as soon as you become confident in solving the questions of a particular difficulty level.
You can also add the tags if you want to practice problems related to a particular topic.
As you will do more and more problems your confidence will keep increasing and if you will remain consistent you will surely become a top coder.
Lastly, BE CONSISTENT and KEEP PRACTICING.

Important Tip:

One most important thing to remember is – never lose confidence as sometimes it will happen that you might find some questions which will seem difficult for you and you will have no idea on how to solve them but never get scared of them. Give adequate time in trying to solve the problem and look out for editorials or take help from your seniors if you get trapped in a particular problem. But don’t get demotivated and never think you can’t do the questions as nothing is impossible.

About the Contests:

In Codeforces, the contests are very frequent. There are 2-3 contests every week and the duration of each contest is 2-3 hours mostly. Some contests are available to you according to your rankings as well. If you are a beginner then you can give contests rated for Division 2, Division 3, and Division 4. Your rating will increase or decrease on the basis of problems you solve in each contest and in how much time you solve it. The lesser time you take for each problem, the more will be your rating.

Last Updated :
02 Jun, 2022

Like Article

Save Article

Источник

Алгопрог вам дает, в первую очередь, знания алгоритмов (ну и смежных тем). Но мало их знать, надо уметь их применять в реальной жизни,
особенно если вы — школьник и хотите участвовать в олимпиадах. Если вы на начальных уровнях алгопрога (примерно до 3 уровня), то пока просто решайте алгопрог.
Но добравшись до уровня 3 (или даже можно чуть раньше), начинайте более-менее регулярно
тренироваться на задачах из реальной жизни — в первую очередь, конечно, решая раунды на
codeforces, и прорешивая старые олимпиады.

Что решать?

А именно, во-первых, регулярно пишите раунды на cf. В идеале у вас на cf должен быть рейтинг, более-менее
соответствующий вашему уровню на алгопроге. Примерно так:

Уровень на алгопроге	Рейтинг на cf
4	1400
6	1600
8	1750
10	1900
12	2050

Примечание: раньше в этой табличке были другие числа — потому что на алгопроге была другая система уровней («дореформенная»).

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

Что значит решать cf? Там есть регулярные раунды, но также есть огромный архив старых раундов.
Если вы хотите что-то порешать, а сейчас раунда нет — просто берете случайный старый раунд
и решаете. (Собственно, примерно так мы и делаем на продвинутых задачах для старших уровней по воскресеньям.)

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

Работа над ошибками

Но не менее важно после написанного тура (раунда на cf, что реального, что виртуального, подготовочного тура к олимпиаде,
реальной олимпиады) провести «работу над ошибками» — разобраться, могли ли вы выступить лучше и как.

Для этого сначала прочитайте разбор — на cf почти к каждому раунду есть разбор, к другим олимпиадам тоже можно найти, если поискать,
в крайнем случае найдите решения жюри или других участников.
(Конечно, можно немного поразбирать ошибки сразу после контеста и без чтения разбора, особенно если вам немного
не хватило времени дорешать задачу, но разбор все равно обязательно надо прочитать.)
По каждой задаче, которую вы не решили полностью, подумайте: вообще, вы понимаете, как ее предлагалось решать?
Хватает ли у вас теоретических знаний, знаете ли вы нужные алгоритмы?

Если не хватает, то ладно: значит вы действительно вряд ли могли решить эту задачу. Конечно, вы можете попробовать
разобраться в соответствующем алгоритме, особенно если он выглядит не сложным, или если это не настоящий алгоритм,
а скорее какая-то оптимизация. Но если вы еще только на 3-5 уровне алгопрога, то понятно, что многие алгоритмы вы пока еще не знаете,
так что не надо про это слишком переживать.

А вот если по разбору вы поняли, что вы в принципе всё, что надо, знали — вот тогда тщательно подумайте,
почему у вас все-таки не получилось решить эту задачу. Может быть, вы ее недотестировали,
может быть, вы, думая над этой задачей, пошли куда-то не в ту сторону, или, например,
напрасно пытались сдать жадность, когда там динамика. Или может быть вы слишком много времени потратили
на другой задаче, и на эту просто не осталось времени… В общем, поймите, что во время контеста пошло не так,
и что надо исправить, чтобы в следующий раз выступить лучше. И в любом случае напишите-таки решение и сдайте его.

Мой курс по алгоритмическому программированию (и подготовке к олимпиадам) для школьников, студентов и всех желающих — algoprog.ru

Источник