Оффлайн
- Регистрация
- 14.05.16
- Сообщения
- 11.398
- Реакции
- 501
- Репутация
- 0
Разборы и код сознательно спрятаны в спойлеры. Если вы интересуетесь
You must be registered for see links
или готовитесь к собеседованиям в большие IT-компании, попробуйте решить одну или несколько задач, прежде чем смотреть разбор. Код представлен на Python, C++ и Java.Авторы и мои коллеги: задача A — Павел Дорошкевич, B и F — Егор Чунаев, E — Андрей Халявин, C и D — я.
You must be registered for see links
You must be registered for see links
You must be registered for see links
You must be registered for see links
You must be registered for see links
You must be registered for see links
You must be registered for see links
You must be registered for see links
You must be registered for see links
You must be registered for see links
You must be registered for see links
You must be registered for see links
A. День рождения Васи
Ограничение по времени на тест | 3 с |
Ограничение по памяти на тест | 256 МБ |
Ввод | стандартный ввод |
Вывод | стандартный вывод |
Сегодня у Васи день рождения, и он позвал своих друзей отведать n своих самых лучших блюд. Название каждого из них состоит из строчных букв английского алфавита, цифр и знака подчеркивания.
Для приготовления блюда с номером i требуется z[SUB]i[/SUB] ингредиентов. Для каждого ингредиента известно его название, требуемое количество для одной порции блюда, а также единица измерения, в которой это количество задано. Помимо этого, Васе известно, что i-й кулинарный шедевр захотят попробовать c[SUB]i[/SUB] друзей.
Используются следующие единицы измерения:
- g, kg — граммы и килограммы соответственно;
- l, ml — литры и миллилитры соответственно;
- cnt, tens — одна штука и десять штук соответственно.
В одном килограмме 1000 грамм и в одном литре 1000 миллилитров. Делать перевод из одной единицы измерения в другую можно тогда и только тогда, когда они одновременно обозначают или массу, или объем, или количество.
У Васи есть два справочника ингредиентов. В первом для каждого ингредиента указано его количество в упаковке и цена за упаковку. Во втором справочнике для каждого ингредиента указано содержание белков, жиров, углеводов и энергетическая ценность некоторого количества данного ингредиента.
Васе нужно приготовить все блюда, при этом не купить ничего лишнего. Для этого ему нужно определить, какие ингредиенты и в каком количестве необходимо приобрести в магазине.
Так как друзья именинника очень следят за питанием, то они, перед тем как попробовать Васины блюда, захотят узнать всё: как Вася готовил блюда, их энергетическую ценность и содержание белков, жиров и углеводов. Васе нужно подготовить эту информацию.
Необходимо помочь имениннику подсчитать, сколько требуется потратить денег на покупку продуктов в магазине, какие ингредиенты и в каком количестве нужно купить, а также для каждого блюда посчитать содержание белков, жиров, углеводов и энергетическую ценность, если его съесть полностью.
Входные данные
Первая строка содержит целое число n (1 ⩽ n ⩽ 1000) — количество блюд, которое решил приготовить Вася.
Затем следует описание n блюд. В первой строке содержатся строка d[SUB]i[/SUB] и целые числа с[SUB]i[/SUB], z[SUB]i[/SUB] (1 ⩽ с[SUB]i[/SUB], z[SUB]i[/SUB] ⩽ 100) — название блюда, количество друзей, желающих отведать данное блюдо, и количество ингредиентов необходимых для приготовления. Название блюда состоит из строчных букв английского алфавита, цифр и знака подчеркивания. Его длина не превосходит 20 символов.
В следующих z[SUB]i[/SUB] строках содержатся описания ингредиентов. В строке с номером j содержатся строка s[SUB]i, j[/SUB] — название ингредиента, целое число a[SUB]i, j[/SUB] (1 ⩽ a[SUB]i, j[/SUB] ⩽ 1000) — требуемое количество ингредиента и строка u[SUB]i, j[/SUB] — название единицы измерения количества. Название ингредиента состоит из строчных букв английского алфавита, цифр и знака подчеркивания. Длина строки не превосходит 20 символов.
Следующая строка содержит целое число k (1 ⩽ k ⩽ 1000) — количество ингредиентов в каталоге цен.
В каждой из следующих k строк содержатся четыре значения t[SUB]i[/SUB] p[SUB]i[/SUB] a[SUB]i[/SUB] u[SUB]i[/SUB], описывающих ингредиент.
- t[SUB]i[/SUB] — название ингредиента, состоящее из строчных букв английского алфавита, цифр и знака подчеркивания. Длина строки не превосходит 20 символов;
- p[SUB]i[/SUB] — стоимость ингредиента, заданная целым числом (1 ⩽ p[SUB]i[/SUB] ⩽ 1000);
- a[SUB]i[/SUB] — количество ингредиента в упаковке в единицах, заданное целым числом (1 ⩽ a[SUB]i[/SUB] ⩽ 1000);
- u[SUB]i[/SUB] — единица измерения количества (l, ml, g, kg, cnt или tens).
Следующая строка содержит число m (1 ⩽ m ⩽ 1000) — количество ингредиентов в каталоге еды.
Далее расположены m строк, в каждой из которых содержатся семь значений t[SUB]i[/SUB] a[SUB]i[/SUB] u[SUB]i[/SUB] pr[SUB]i[/SUB] f[SUB]i[/SUB] ch[SUB]i[/SUB] fv[SUB]i[/SUB], описывающих ингредиент.
- t[SUB]i[/SUB] — название ингредиента, состоящее из строчных букв английского алфавита, цифр и знака подчеркивания. Длина строки не превосходит 20 символов;
- a[SUB]i[/SUB] — количество ингредиента, для которого указаны характеристики ингредиента, заданное целым числом (1 ⩽ a[SUB]i[/SUB] ⩽ 1000);
- u[SUB]i[/SUB] — единица измерения (l, ml, g, kg, cnt или tens);
- pr[SUB]i[/SUB] f[SUB]i[/SUB] ch[SUB]i[/SUB] fv[SUB]i[/SUB] — содержание белков, жиров, углеводов и энергетическая ценность ингредиента соответственно, заданные вещественными числами с не более чем шестью знаками после запятой (0 ⩽ pr[SUB]i[/SUB], f[SUB]i[/SUB], ch[SUB]i[/SUB] ⩽ 1000, 0 ⩽ fv[SUB]i[/SUB] ⩽ 10 000).
Гарантируется, что:
- в каталогах перечислены все ингредиенты, необходимые для приготовления блюд;
- не существует двух блюд с одинаковым названием;
- не существует двух ингредиентов в одном каталоге с одинаковым названием;
- не существует двух ингредиентов в одном блюде с одинаковым названием;
- для любых двух упоминаний ингредиента единицы измерения, в которых заданы его количества, можно перевести друг в друга.
Выходные данные
Первая строка должна содержать одно целое число: сумма, которую нужно потратить Васе на подготовку к празднику.
Далее должны следовать k строк, в каждой из которых через пробел указано название ингредиента и целое число — количество упаковок, которое необходимо купить. Ингредиенты, выведенные в этих k строках, должны соответствовать ингредиентам, описанным в первом справочнике.
В следующих n строках через пробел должны быть указаны название блюда и его характеристики, описанные четырьмя вещественными числами: белки, жиры, углеводы и энергетическая ценность.
Ингредиенты и блюда разрешается выводить в любом порядке.
Ваш ответ будет считаться правильным, если все целые числа совпадают с соответствующими числами в ответе жюри, а для всех вещественных чисел в ответе их абсолютная или относительная погрешность не превосходит 10[SUP]-3[/SUP]. Более формально, пусть вещественное число в вашем ответе равно A, а соответствующее число в ответе жюри равно B. Тогда число A будет считаться корректным, если
Пример
Входные данные | Выходные данные |
2 sandwich 7 3 butter 10 g toasted_bread 2 cnt sausage 30 g omelet 9 4 egg 4 cnt milk 120 ml salt 1 g sausage 50 g 7 egg 61 1 tens milk 58 1 l sausage 100 480 g butter 120 180 g cream 100 350 g salt 14 1000 g toasted_bread 40 20 cnt 8 egg 1 cnt 13 12 1 16.4 milk 1 l 3 4.5 4.7 60 chocolate 90 g 6.8 36.3 47.1 546 salt 1 kg 0 0 0 0 strawberry 100 g 0.4 0.1 7 35 sausage 100 g 10 18 1.5 210 toasted_bread 5 cnt 7.3 1.6 52.3 248 butter 100 g 0.8 72.5 1.3 661 | 734 egg 4 milk 2 sausage 2 butter 1 cream 0 salt 1 toasted_bread 1 sandwich 6.00 13.29 21.50 228.3 omelet 57.360 57.540 5.314 177.800 |
В первом примере Васе необходимо приготовить 7 бутербродов и 9 омлетов.
Для приготовления всех первых блюд необходимо 10 ⋅ 7 грамм масла, 2 1 7 кусочков хлеба и 30 ⋅ 7 грамм колбасы. В каждом из бутерброде будет содержаться
Для приготовления всех вторых блюд необходимо 4 ⋅ 9 = 36 яиц, 120 ⋅ 9 = 1080 миллилитров молока, 9 грамм соли, 50 ⋅ 9 = 450 грамм колбасы. В каждом омлете будет содержаться
Всего необходимо 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 достаточно для выполнения операций и вывода результатов. Его можно использовать, если корректно делать округление.
Асимптотическая сложность алгоритма при использовании хэш-таблиц для каталога и справочника:
Код на 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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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 > 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 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.mult, &sz);
arr.name = buf;
arr.igs.resize(sz);
for (int j = 0; j < sz; ++j) {
scanf("%s", buf);
arr.igs[j].first = buf;
arr.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.igs.size(); ++j) {
ig_info& cur_info = info[arr.igs[j].first];
cur_info.buy_cnt += arr.mult * arr.igs[j].second;
for (int k = 0; k < 4; ++k) {
arr.arr[k] += ((double)arr.igs[j].second / (double)cur_info.eg_cnt) * cur_info.arr[k];
}
}
}
ll ans = 0;
for (auto& cur_info : info) {
cur_info.second.buy_cnt = (cur_info.second.buy_cnt + cur_info.second.cnt - 1) / cur_info.second.cnt;
ans += cur_info.second.buy_cnt * cur_info.second.cost;
}
printf("%lld\n", ans);
for (const auto& cur_info : info) {
printf("%s %lld\n", cur_info.first.c_str(), cur_info.second.buy_cnt);
}
for (int i = 0; i < n; ++i) {
printf("%s ", arr.name.c_str());
for (int j = 0; j < 4; ++j) {
printf("%.20lf%c", (double)arr.arr[j], " \n"[j == 3]);
}
}
return 0;
}
Код на Java
import java.i
utputStream;import java.io.IOException;
import java.io.InputStream;
import java.i
utputStream;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.i
utputStreamWriter;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 = new Recipes.Recipe();
recipes.name = in.nextString();
recipes.mult = in.nextLong();
int ingredientsSize = in.nextInt();
recipes.ingredients = new Recipes.Ingredient[ingredientsSize];
for (int j = 0; j < recipes.ingredients.length; ++j) {
recipes.ingredients[j] = new Recipes.Ingredient();
recipes.ingredients[j].name = in.nextString();
recipes.ingredients[j].cnt = readCnt(in);
}
}
int k = in.nextInt();
HashMap 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 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.ingredients.length; ++j) {
Recipes.IngredientBuyInfo curBuyInfo = ingredientBuyInfo.get(recipes.ingredients[j].name);
curBuyInfo.buyCnt += recipes.mult * recipes.ingredients[j].cnt;
Recipes.IngredientEnergyInfo curEnergyInfo = ingredientEnergyInfo.get(recipes.ingredients[j].name);
for (int p = 0; p < CNT_ENERGY; ++p) {
recipes.energyArr[p] += ((double) recipes.ingredients[j].cnt / (double) curEnergyInfo.cnt) * curEnergyInfo.energyArr[p];
}
}
}
long totalCost = 0;
for (HashMap.Entry entry : ingredientBuyInfo.entrySet()) {
totalCost += entry.getValue().cost * ((entry.getValue().buyCnt + entry.getValue().cnt - 1) / entry.getValue().cnt);
}
out.println(totalCost);
for (HashMap.Entry 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.name + " ");
for (int j = 0; j < CNT_ENERGY; ++j) {
out.print(String.format("%.20f", recipes.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 = 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 = 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 '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);
}
}
public void println(Object... objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
public void println(long i) {
writer.println(i);
}
}
}
B. Закрытый ключ
Ограничение по времени на тест | 2 с |
Ограничение по памяти на тест | 256 МБ |
Ввод | стандартный ввод |
Вывод | стандартный вывод |
Во всех крупных IT-компаниях немалое внимание уделяется вопросам информационной безопасности, и Яндекс — не исключение.
Дима и Егор разрабатывают новый сервис YD (Yandex Dorogi) и в данный момент проводят аудит его безопасности. Для шифрования пользовательских данных в YD используется алгоритм шифрования с открытым ключом YS (Yandex Shifrovatel).
Схема работы YS такова: для каждого сервиса генерируется закрытый ключ (
Дима уже сгенерировал закрытый ключ для YD и получил на его основе открытый ключ (
Входные данные
В первой строке содержатся два целых числа
Выходные данные
Выведите одно целое число — количество закрытых ключей, для которых данный ключ является открытым.
Примеры
Входные данные
5 10
Выходные данные
2
Входные данные
10 11
Выходные данные
0
Входные данные
527 9486
Выходные данные
4
Примечание
В первом примере существует два закрытых ключа, для которых (
Во втором примере Дима ошибся, потому что ни один закрытый ключ не порождает открытый ключ (
В третьем примере подходящими закрытыми ключами являются (
НОД (наибольшим общим делителем) двух натуральных чисел
НОК (наименьшим общим кратным) двух натуральных чисел
Решение и код
Если
Иначе рассмотрим какую-то пару
Иными словами, задачу можно свести к задаче нахождения количества пар взаимно простых чисел
Далее будем предполагать что
Первый вариант решения
Решение за
Зафиксируем
Под факторизацией подразумевается любой способ нахождения делителей. С учетом достаточно маленьких ограничений их можно найти просто проверкой всех целых чисел от
Получаем решение за
Код на С++
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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 /freopen("output.txt", "w", stdout);
#else
//freopen("", "r", stdin);
//freopen("", "w", stdout);
#endif
scanf("%lld%lld", &x, &y);
if (y % x != 0) {
return 0 * printf("0\n");
}
y /= x;
ll ans = 0;
for (ll i = 1; i * i i) == 1) {
ans += 1 + (i * i != y);
}
}
}
printf("%lld\n", ans);
return 0;
}
Второй вариант решения
Решение за
Рассмотрим простое число
Иными словами, для каждого простого числа, на которое делится
Код на Python
x, y = map(int, input().split())
if y % x != 0:
print(0)
else:
y //= x
i = 2
ans = 0
while i * i /= i
i += 1
if y != 1:
ans += 1
print(2 ** ans)
Код на C++
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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 /freopen("output.txt", "w", stdout);
#else
//freopen("", "r", stdin);
//freopen("", "w", stdout);
#endif
scanf("%lld%lld", &x, &y);
if (y % x != 0) {
return 0 * printf("0\n");
}
y /= x;
ll ans = 0;
for (ll i = 2; i * i = i;
}
}
}
ans += (y != 1);
printf("%lld\n", (1ll code>
Код на Java
import java.i
utputStream;import java.io.IOException;
import java.io.InputStream;
import java.i
utputStream;import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.i
utputStreamWriter;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 = i;
}
}
}
if (y != 1) {
++ans;
}
out.println(1L = numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new UnknownError();
}
if (numChars '9') {
throw new UnknownError();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null) {
return filter.isSpaceChar(c);
}
return isWhitespace(c);
}
public static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void close() {
writer.close();
}
public void println(long i) {
writer.println(i);
}
public void println(int i) {
writer.println(i);
}
}
}
C. Программист на пляже
Ограничение по времени на тест | 2 с |
Ограничение по памяти на тест | 256 МБ |
Ввод | стандартный ввод |
Вывод | стандартный вывод |
Однажды программист Алексей из Яндекса взял отпуск и уехал отдыхать на море. В один из дней он пошел на пляж, причем пошел туда не один. Возможно, он пошел туда с мамой, возможно, с бабушкой, а, возможно, с другом или подругой. Важно, что пошел он туда не один.
На пляже программист Алексей обнаружил, что осталось всего
- Каждому лежаку каким-то образом по его внешним признакам назначается некоторое число
(
,
).
- Затем непохожесть двух лежаков вычисляется как XOR (побитовое исключающее ИЛИ) чисел назначенных этим лежакам. Чем значение непохожести меньше, тем более похожи лежаки.
Помогите программисту Алексею понять, какого минимального значения непохожести лежаков он может достичь, сравнив попарно все свободные лежаки.
Входные данные
В первой строке задано число
В первой строке каждого теста задано число
Во второй строке каждого теста заданы
Сумма
Выходные данные
Для каждого теста выведите по одной строке, в которой должно быть единственное число – минимальное значение непохожести.
Примеры
Входные данные
1
5
1 2 4 8 16
Выходные данные
3
Входные данные
2
2
2 4
4
2 4 6 8
Выходные данные
6
2
Примечание
В первом примере Алексей выберет лежаки со значениями 1 и 2.
В первой части второго примера Алексей может взять только лежаки со значениями 2 и 4. Во второй части он выберет лежаки со значениями 4 и 6.
Решение
Зададим все числа в их двоичном представлении, дополнив ведущими нулями так, чтобы их длины были одинаковы. Далее построим на этих значениях бор, где первое от корня ребро задается старшим разрядом: спускаясь вглубь дерева, вы переходите от старших разрядов к младшим.
Далее найдем все самые отдаленные от корня вершины, которые содержат ровно 2 числа. Каждой такой вершине поставим в соответствие число
Покажем, что это и правда ответ на задачу. Зададим расстояние от всех выбранных вершин до ближайших листьев числом
На самом деле, задачу можно решить без помощи бора, просто отсортировав все числа и взяв попарный XOR между соседними после сортировки числами. Ведь все числа, которые попадали в самые глубокие вершины, содержащие ровно 2 числа, являются также соседними числами после сортировки. Это действительно так, поскольку по построению бора ни одно другое число не может иметь значение из отрезка
Код на 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)
print(r)
if __name__ == '__main__':
main()
Код на C++
#include
#include
#include
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);
}
sort(v, v + n);
int ans = INT32_MAX;
for (int i = 1; i < n; ++i) {
ans = min(ans, v ^ v[i - 1]);
}
printf("%d\n", ans);
}
return 0;
}
Код на Java
import java.i
utputStream;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 code>
D. Перемещение чанков
Ограничение по времени на тест | 1 с |
Ограничение по памяти на тест | 256 МБ |
Ввод | стандартный ввод |
Вывод | стандартный вывод |
Хранение данных в распределенном хранилище является крайне сложной задачей, однако инженеры Яндекса успешно с ней справляются.
Один из кластеров хранилища состоит из
При построении распределенных систем очень важно избегать возможности конфликта изменений на кластере. Перед выполнением каждого из запросов необходимо убедиться, что все чанки, участвующие в запросе, находятся на ожидаемом сервере. Иными словами, перед выполнением запроса, описываемого параметрами
По заданному начальному состоянию кластера и списку запросов перемещения чанков определите, какие запросы будут выполнены.
Входные данные
В первой строке заданы три целых числа
Во второй строке содержатся
В следующих
Каждый запрос описывается четверкой чисел
Выходные данные
Выведите
Примеры
Входные данные
1 2 1
1
1 2 1 1
Выходные данные
1
Входные данные
1 2 1
1
2 1 1 1
Выходные данные
0
Входные данные
5 5 6
1 2 3 4 5
1 2 1 1
2 3 1 3
4 2 4 4
2 5 1 4
3 2 2 3
3 2 3 3
Выходные данные
1
0
1
0
0
1
Примечание
Рассмотрим третий пример. Изначально расположение чанков на серверах описывается массивом
В первом запросе требуется переместить чанк с номером
Во втором запросе требуется переместить чанки
В третьем запросе требуется переместить чанк
В четвертом запросе требуется переместить чанки
В пятом запросе требуется переместить чанки
В шестом запросе требуется переместить чанк
Решение и код
Можно хранить для каждого сервера по одному декартову дереву, содержащему все находящиеся на нем чанки. Для этого при поступлении запроса нужно достать из декартова дерева, соответствующего вершине
Далее в зависимости от ответа вырезанные чанки нужно вернуть либо обратно на сервер
E. Разделение графа
Ограничение по времени на тест | 1 с |
Ограничение по памяти на тест | 256 МБ |
Ввод | стандартный ввод |
Вывод | стандартный вывод |
Дан взвешенный неориентированный граф
Разбейте вершины графа на два не пустых множества так, чтобы ребро минимального веса, соединяющее вершины из одного множества, имело максимально большой вес.
Гарантируется, что граф не содержит петель и его нельзя разбить так, чтобы такого ребра не существовало.
Входные данные
В первой строке задано число вершин
В следующих
Выходные данные
В единственной строке выведите максимальный возможный вес ребра, которое имеет минимальный вес среди тех, что соединяют вершины, принадлежащие одному множеству.
Примеры
Входные данные
3 4
1 2 1
1 2 2
1 3 3
3 2 4
Выходные данные
4
Входные данные
4 5
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
Выходные данные
2
Примечание
Рассмотрим первый пример из условия. В нем возможно всего 3 различных разбиения, удовлетворяющих условию, рассмотрим каждое из них:
-
, в таком случае ребра
и
будут будут соединять вершины из одного множества, то есть ответ
;
-
, в таком случае только ребро
будет соединять вершины из одного множества, то есть ответ
;
-
, в таком случае только ребро
будет соединять вершины из одного множества, то есть ответ
.
Получаем, что ответ на тест достигается при третьем варианте разбиения.
Во втором тесте ответ достигается на разбиении
Решение
Решить задачу с помощью бинарного поиска по ответу.
Предположим, что ответ —
Теперь опишем проверку того, что граф удовлетворяет условию, то есть является двудольным. Для этого нужно запустить обход всех вершин (например, в глубину либо в ширину) для каждой компоненты связности. Во время обхода каждой вершине нужно поставить в соответствие
- Начинаем обход с некоторой вершины, в соответствие которой ставится
.
- При переходе по ребру от вершины
к вершине
вершине
ставится в соответствие число, противоположное поставленному в соответствие вершине
(например, если
, то
, и наоборот).
После обхода нужно проверить, что не существует ребра между вершинами, которым соответствует одно и то же число. Если это так, то заданный граф является двудольным.
Сложность одной итерации бинарного поиска равна
Код на 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 == 0:
cl = 3 - cl[v]
qu.append(u)
elif cl[v] == cl:
return False
return True
def check(g, m):
cl = [0 for i in range(len(g))]
for i in range(len(g)):
if cl == 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
#include
#include
#include
#include
struct Solution {
int n, m;
std::vector>> graph;
std::vector 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 == -1) {
if (!dfs(i, 0, bound)) {
return false;
}
}
}
return true;
}
void run(std::istream &in, std:
stream &out) {in >> n >> m;
graph.assign(n, std::vector>());
for (int i = 0; i < m; i++) {
int u, v, w;
in >> u >> v >> w;
u--;
v--;
graph.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 code>
Код на Java
import java.i
utputStream;import java.io.IOException;
import java.io.InputStream;
import java.i
utputStream;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.i
utputStreamWriter;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[] g = new List[n];
for (int i = 0; i < n; i++) {
g = 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 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[] g, int mid) {
Arrays.fill(color, -1);
for (int i = 0; i < n; i++) {
if (color == -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[] 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 '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null) {
return filter.isSpaceChar(c);
}
return isWhitespace(c);
}
public static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}
F. Поиск
Ограничение по времени на тест | 2 с |
Ограничение по памяти на тест | 512 МБ |
Ввод | стандартный ввод |
Вывод | стандартный вывод |
Разработчики Яндекс.Поиска постоянно работают над улучшением алгоритмов ранжирования. Один из алгоритмов, который хотят опробовать, таков.
Поисковый алгоритм состоит из трех этапов: поиск по базе, отбор документов и фильтрация. Во время поиска по базе отбираются
Ранжирующий алгоритм хранит данные в закольцованном списке, таким образом, после документа с номером
Во время фильтрации из списка документов, полученных при отборе, может быть удалено несколько документов, но не более
Релевантностью выдачи назовем сумму релевантностей документов в ней. По релевантностям документов, полученных во время поиска, определите, какую наибольшую релевантность выдачи можно получить при оптимальной работе алгоритма.
Входные данные
В первой строке задано целое число
Описание каждого теста состоит из двух строк.
В первой строке задано два целых числа
Во второй строке содержатся
Гарантируется что сумма
Выходные данные
Для каждого тестового случая выведите одно целое число — ответ на задачу.
Пример
Входные данные
6
4 0
1 -2 9 10
6 1
5 -5 5 -5 5 -5
6 2
5 -5 5 -5 5 -5
4 3
5 -5 5 -5
8 1
-3 -1 5 6 -200 -200 5 -1
3 1
-1 -2 -3
Выходные данные
20
10
15
10
14
-1
Примечание
В первом примере выгодно выбрать в качестве начального документ с релевантностью
Во втором примере выгодно выбрать в качестве начального любой документ с релевантностью
В пятом примере выгодно выбрать в качестве начального документ с номером
В последнем примере релевантность выдачи получится отрицательной, так как пользователю необходимо показать хотя бы один документ.
Решение
Если все релевантности документов отрицательны, то ответ — максимум по всем числам. Поскольку нам запрещено брать пустое множество, лучше обработать этот случай отдельно. Все последующие состояния динамики могут соответствовать пустому подотрезку с суммой
Решим задачу, если нет цикличности массива.
Пусть
Пересчет:
-
— попробовать начать новый «пустой» отрезок в этом месте.
-
— продолжить какой-то оптимальный отрезок, добавив в него i-й элемент.
-
— продолжить какой-то оптимальный отрезок, удалив из него i-й элемент.
Такая динамика считается за
Таким образом, мы учли все подотрезки массива, которые не проходят через стык первого и n-го элемента.
Теперь учтем оставшиеся отрезки.
Пусть
Пересчет:
-
— продолжить отрезок, добавив в него i-й элемент.
-
— продолжить отрезок, удалив из него i-й элемент.
В отличие от первой динамики, нет необходимости начинать новый отрезок, поскольку левая граница фиксирована.
Аналогично,
Пересчет:
-
— продолжить отрезок, добавив в него i-й элемент.
-
— продолжить отрезок, удалив из него i-й элемент.
Обе эти динамики можно посчитать за
Как теперь учесть все отрезки, проходящие через стык первого и n-го элемента? Переберем префикс
Этот максимум можно предпросчитать еще одной динамикой
Получаем решение за
Код на 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 code>
Код на C++
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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 = 1; --i) {
for (int j = 0; j = 1; --i) {
for (int j = 0; j /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.i
utputStream;import java.io.IOException;
import java.io.InputStream;
import java.i
utputStream;import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.i
utputStreamWriter;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 = 1; --i) {
for (int j = 0; j = 1; --i) {
for (int j = 0; j = numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new UnknownError();
}
if (numChars '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);
}
}
}