👨🏾‍⚕️ ✍️ 🕳️ Onde resolver problemas reais para candidatos a Yandex: treinamento em Codeforces e análises ☦️ 👩🏼‍⚖️ 🕵🏼

Habr, sou eu de novo, Alexei Cancer (foto não minha). No ano passado, além do trabalho principal, me tornei um dos autores de tarefas para candidatos ao Yandex. Hoje, nossa equipe publica pela primeira vez em muito tempo tarefas reais da Habrr para desenvolvedores que se instalam na empresa. Essas tarefas foram utilizadas até fevereiro de 2020 na seleção de um estágio para backenders. As soluções foram verificadas por um computador. Agora, os candidatos recebem tarefas semelhantes.

O interrogatório e o código são deliberadamente ocultos nos spoilers. Se você estiver se preparando para entrevistas com grandes empresas de TI, tente resolver um ou mais problemas antes de assistir à análise. Você pode enviar a solução para verificação à Codeforces - a resposta virá imediatamente ( link para Codeforces e observe) O código é apresentado em Python, C ++ e Java. Importante: o código "olimpíada" do autor não se destina à produção, está escrito com base no fato de que o sistema o verificará automaticamente.

Os autores e meus colegas: tarefa A - Pavel Doroshkevich, B e F - Egor Chunaev, E - Andrey Khalyavin, C e D - eu.

A. Aniversário de Vasya
　Solução e código

B. Chave privada
　Solução e código

C. Programador na praia
　Solução e código

D. Movendo pedaços
　Solução e código

E. Separando a coluna
　Solução e código

F. Search
　Solution and code

A. aniversário de Vasya

Prazo por teste	3 s
Limite de memória por teste	256 MB
Entrar	entrada padrão
Conclusão	saída padrão

Vasya e seus amigos adoram comer deliciosamente. No seu aniversário, todos são obrigados a surpreender os outros, preparando novos pratos saborosos e saudáveis.

Hoje é o aniversário de Vasya e ele convidou seus amigos para provar n de seus melhores pratos. O nome de cada um deles consiste em letras minúsculas em inglês, números e o sublinhado.

Cozinhar no número i requer z _i ingredientes. Para cada ingrediente, seu nome é conhecido, a quantidade necessária para uma porção do prato, bem como a unidade de medida em que essa quantidade é definida. Além disso, Vasya sabe que o i-th obra-prima culinária vai querer experimentar com _i amigos.

As seguintes unidades são usadas:

g, kg - gramas e quilogramas, respectivamente;
l, ml - litros e mililitros respectivamente;
cnt, dezenas - uma peça e dez peças, respectivamente.

Em um quilograma, 1000 gramas e em um litro, 1000 mililitros. Você pode fazer uma transferência de uma unidade de medida para outra, se e somente se elas indicarem simultaneamente massa, volume ou quantidade.

Vasya tem dois diretórios de ingredientes. O primeiro para cada ingrediente indica sua quantidade na embalagem e o preço por embalagem. O segundo diretório para cada ingrediente indica o conteúdo de proteínas, gorduras, carboidratos e o valor energético de uma certa quantidade desse ingrediente.

Vasya precisa cozinhar todos os pratos, sem comprar nada extra. Para fazer isso, ele precisa determinar quais ingredientes e em qual quantidade deve ser comprada na loja.

Como os amigos do aniversariante são muito cuidadosos com a nutrição, antes de experimentar os pratos da Vasina, eles vão querer descobrir tudo: como Vasya preparou os pratos, seu valor energético e o conteúdo de proteínas, gorduras e carboidratos. Vasya precisa preparar esta informação.

É necessário ajudar o aniversariante a calcular quanto dinheiro é necessário para comprar produtos na loja, quais ingredientes e em que quantidade você precisa comprar, bem como para cada prato, calcular o conteúdo de proteínas, gorduras, carboidratos e valor energético se você o comer completamente.

Dados de entrada

A primeira linha contém um número inteiro n (1 ≤ n ≤ 1000) - o número de pratos que Vasya decidiu cozinhar.

Em seguida, segue uma descrição de n pratos. A primeira linha contém a sequência d _i e números inteiros com _i , z _i (1 ⩽ c _i , z _i ⩽ 100) - o nome do prato, o número de amigos que desejam experimentar esse prato e o número de ingredientes necessários para cozinhar. O nome do prato consiste em letras minúsculas em inglês, números e um sublinhado. Seu comprimento não excede 20 caracteres.

As seguintes linhas z _i contêm descrições dos ingredientes. A linha com o número j contém a cadeia s _{i, j} é o nome do ingrediente, o número inteiro a _{i, j}(1 ≤ a _{i, j} ≤ 1000) é a quantidade necessária do ingrediente e a cadeia u _{i, j} é o nome da unidade de medida da quantidade. O nome do ingrediente consiste em letras minúsculas em inglês, números e sublinhado. O comprimento da linha não excede 20 caracteres.

A próxima linha contém o número inteiro k (1 ≤ k ≤ 1000) - o número de ingredientes no catálogo de preços.

Cada uma das próximas k linhas contém quatro valores de t _i p _i a _i u _i descrevendo o ingrediente.

t _i - o nome do ingrediente, que consiste em letras minúsculas em inglês, números e sublinhado. O comprimento da linha não excede 20 caracteres;
p _i é o custo do ingrediente, dado um número inteiro (1 ⩽ p _i ⩽ 1000);
a _i - a quantidade de ingrediente na embalagem em unidades, especificada por um número inteiro (1 ⩽ a _i ⩽ 1000);
u _i - unidade de medição de quantidade (l, ml, g, kg, cnt ou dezenas).

A próxima linha contém o número m (1 ≤ m ≤ 1000) - o número de ingredientes no catálogo de alimentos.

Em seguida, estão de m linhas, cada uma das quais contém sete valores t _i um _i u _i pr _i f _i CH _i fv _i descrevendo o ingrediente.

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).

É garantido que:

os catálogos listam todos os ingredientes necessários para cozinhar;
não há dois pratos com o mesmo nome;
não há dois ingredientes no mesmo catálogo com o mesmo nome;
não há dois ingredientes no mesmo prato com o mesmo nome;
para quaisquer duas menções a um ingrediente, as unidades de medida nas quais são dadas suas quantidades podem ser convertidas uma na outra.

Resultado

A primeira linha deve conter um único número inteiro: a quantia que Vasya precisa gastar na preparação para o feriado.

Em seguida, k linhas devem seguir, em cada uma das quais um espaço indica o nome do ingrediente e um número inteiro - o número de pacotes que você precisa comprar. Os ingredientes exibidos nessas k linhas devem corresponder aos ingredientes descritos no primeiro diretório.

As próximas n linhas devem conter um espaço entre o nome do prato e suas características, descritas por quatro números reais: proteínas, gorduras, carboidratos e valor energético.

Ingredientes e pratos podem ser exibidos em qualquer ordem.

Sua resposta será considerada correta se todos os números inteiros corresponderem aos números correspondentes na resposta do júri e, para todos os números reais na resposta, seu erro absoluto ou relativo não exceda 10 ^-3 . Mais formalmente, deixe o número real na sua resposta ser A e o número correspondente na resposta do júri seja B. Então o número A será considerado correto se

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

Exemplo

Dados de entrada Resultado

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

Nota

No primeiro exemplo, Vasya precisa cozinhar 7 sanduíches e 9 omeletes.

Para preparar todos os primeiros pratos, você precisa de 10 ⋅ 7 gramas de manteiga, 2 1 7 pedaços de pão e 30 ⋅ 7 gramas de salsicha. Cada sanduíche conterá

$0.8 ⋅ \frac {10}{100} + 7.3 ⋅ \frac {2}{5} + 10 ⋅ \frac {30}{100} =6$ grama de proteína

$72.5 ⋅ \frac {10}{100} + 1.6 ⋅ \frac {2}{5} + 18 ⋅ \frac {30}{100} =13.29$ gramas de gordura e

$1.3 ⋅ \frac {10}{100} + 52.3 ⋅ \frac {2}{5} + 1.5 ⋅ \frac {30}{100} =21.5$ grama de carboidratos. O valor da energia será

$661 ⋅ \frac {10}{100} + 248 ⋅ \frac {2}{5} + 210 ⋅ \frac {30}{100} =228.3$ .

Para preparar todos os segundos pratos, você precisa de 4 ⋅ 9 = 36 ovos, 120 ⋅ 9 = 1080 mililitros de leite, 9 gramas de sal, 50 ⋅ 9 = 450 gramas de salsicha. Cada omelete conterá

$13 ⋅ 4+ 3 ⋅ \frac {120}{1000} + 10 ⋅ \frac {50}{100} =57.36$ grama de proteína

$12 ⋅ 4+ 4.5 ⋅ \frac {120}{1000} + 18 ⋅ \frac {50}{100} =57,54$ e

$1 ⋅ 4+ 4.7 ⋅ \frac {120}{1000} + 1.5 ⋅ \frac {50}{100} =5.314$ carboidratos. O valor da energia será

$16 ⋅ 4+ 60 ⋅ \frac {120}{1000} + 210 ⋅ \frac {50}{100} =177.8$ kcal.

No total, são necessários 70 gramas de manteiga, 36 ovos, 1080 litros de leite, 9 gramas de sal, 210 + 450 = 660 gramas de linguiça e 14 fatias de pão torrado.

Assim, na loja você precisa comprar um pacote de manteiga, 4 dúzias de ovos, 2 pacotes de salsicha e leite, um pacote de sal e pão torrado, pagando 120 + 61 ⋅ 4 + 100 ⋅ 2 + 58 ⋅ 2 + 14 + 40 = 734 rublos .

Decisão

, 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- .

Código 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ódigo C ++

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>
#include <unordered_map>

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

using namespace std;

typedef long long int ll;
typedef long double ld;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    return 0;
}

Código 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. Chave Privada

Prazo por teste	2 s
Limite de memória por teste	256 MB
Entrar	entrada padrão

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, .

A primeira linha contém dois números inteiros $x$ e $y$ ( $1 \leq x \leq y \leq 10^{12}$ ) - uma descrição da chave pública.

Resultado

Imprima um único número inteiro - o número de chaves privadas para as quais essa chave é pública.

Exemplos

Dados de entrada

5 10

Resultado

Dados de entrada

10 11

Resultado

0 0

Dados de entrada

527 9486

Resultado

Nota

No primeiro exemplo, existem duas chaves privadas para as quais ( $5, 10$ ) é a chave pública: ( $5, 10$ ) e ( $10, 5$ )

No segundo exemplo, Dima estava enganado, porque nenhuma chave privada gera uma chave pública ( $10, 11$ )

No terceiro exemplo, chaves privadas adequadas são ( $527, 9486$ ), ( $1054, 4743$ ), ( $4743, 1054$ ), ( $9486, 527$ )

MDC (o maior fator comum) de dois números naturais $p$ e $q$ chamado o maior número $k$ de tal modo que $p$ dividido por $k$ e $q$ dividido por $k$ . Por exemplo, GCD ( $6, 15$ ) é igual $3$ e GCD ( $16, 8$ ) é igual $8$ .

NOC (o menor múltiplo comum) de dois números naturais $p$ e $q$ chamado o menor número $k$ de tal modo que $k$ dividido por $p$ e $k$ dividido por $q$ . Por exemplo, NOC ( $2, 3$ ) é igual $6$ e NOC ( $10, 20$ ) é igual a 20.

Solução e código

$y$ $x$ , , , .

- $p$ , $q$ , $gcd(p, q) = x$ , $lcm(p, q) = y$ . $p' = \frac{p}{x}$ $q' = \frac{q}{x}$ , $gcd(p', q') = 1$ , $lcm(p', q') = \frac{y}{x}$ .

, $p'$ , $q'$ , $lcm$ $\frac{y}{x}$ .

$x = 1$ , , $x' = 1$ , $y' = \frac{y}{x}$ .

$O(factor(y) + number\_of\_divisors(y) \cdot \log{(y}))$ .

$p'$ , $q' = \frac{y'}{p'}$ , $y' = lcm(p', q') = \frac{p' \cdot q'}{gcd(p', q')} = \frac{p' \cdot q'}{1} = p' \cdot q'$ . , , $gcd(p', \frac{y'}{p'}) = 1$ , $O(\log{(y')})$ .

. $1$ $\sqrt{y'}$ , $O(\sqrt{y'})$ . , $2 \cdot \sqrt{y'}$ , , $gcd(p', \frac{y'}{p'}) = 1$ , $2 \cdot \sqrt{y'}$ , $O(\sqrt{y'}\log{y'})$ .

$O(\sqrt{y} \log{(y)})$ .

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>

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

using namespace std;

typedef long long int ll;
typedef long double ld;

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

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

ll x, y;

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

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

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

    y /= x;

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

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

    return 0;
}

$O(factor(y))$ .

$z$ , $y'$ . $lcm(p', q') = y'$ , $p'$ , $q'$ $z^{\alpha}$ , $\alpha$ — , $z$ $y'$ . $gcd(p', q') = 1$ , $z$ .

, , $y'$ , , $p'$ $q'$ . $2^{number\_of\_distinct\_prime\_divisors(y')}$ .

Python

x, y = map(int, input().split())

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

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

    if y != 1:
        ans += 1

    print(2 ** ans)

C++

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>

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

using namespace std;

typedef long long int ll;
typedef long double ld;

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

ll x, y;

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

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

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

    y /= x;

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

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

    return 0;
}

Java

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.io.InputStream;

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

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

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

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

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

    }

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

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

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

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

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

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

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

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

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

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

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

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

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

    }
}

C. Programador de praia

Todas as línguas	Pitão	Java
2	3 c
256

. , . , , , , , , . , .

, $n$ ( $2 \leq n \leq 10^6$ ) . 2: ( ), . , , . :

- $a_i$ ( $1 \leq i \leq n$ , $0 \leq a_i \leq 10^9$ )
Em seguida, a dissimilaridade das duas espreguiçadeiras é calculada como o XOR (OR bit a bit exclusivo) dos números atribuídos a essas espreguiçadeiras. Quanto menor o valor da dissimilaridade, mais semelhantes serão as espreguiçadeiras.

Ajude o programador Aleksey a entender qual o valor mínimo para a diferença entre espreguiçadeiras que ele pode alcançar comparando todas as espreguiçadeiras gratuitas em pares.

Dados de entrada

A primeira linha contém um número $T$ ( $1 \leq T \leq 1000$ ) - o número de testes. Cada teste consiste em duas linhas.

A primeira linha de cada teste recebe um número $n$ ( $2 \leq n \leq 10^6$ ) - o número de espreguiçadeiras.

A segunda linha de cada teste contém $n$ números $a_i$ ( $1 \leq i \leq n$ , $0 \leq a_i \leq 10^9$ ) - os valores que foram colocados nas espreguiçadeiras de acordo com os sinais externos.

Montante $n$ em todos os testes não excede $10^6$ .

Resultado

Para cada caso de teste, imprima uma linha na qual deve haver um único número - o valor mínimo de dissimilaridade.

Exemplos

Dados de entrada

1 1
5
1 2 4 8 16

Resultado

Dados de entrada

Resultado

6
2

Nota

1 2.

2 4. 4 6.

, , . , : , .

, 2 . $z$ , XOR , . – $z$ .

, . $k$ – , ( $k=0$ , ). XOR , , $x$ , $[2^{x-1}, 2^x - 1]$ ( $x = 0$ $0$ , , $x=1$ $1$ , , $x=2$ 2, 3 . .). , , - , $k$ . $2^k$ . , XOR .

, , XOR . , , 2 , . , $[a, b]$ , $a$ $b$ – .

Python

import sys


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

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

C++

#include <algorithm>
#include <cstdint>
#include <cstdio>

using namespace std;

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

Java

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

D.

	Python	Java
1	5 c	1
256

, .

$m$ , , $n$ . . , . $a, b, l, r$ $l$ $r$ $a$ $b$ . $a$ . , .

. , , , . , , $a, b, l, r$ , , $l$ $r$ $a$ . , , . , $l$ $r$ $a$ $b$ .

, .

$n, m$ $q$ ( $1 \leq n, q \leq 100\,000, 2 \leq m \leq 100\,000$ ) — , , , , .

$n$ $p_i$ ( $1 \leq p_i \leq m$ ), $i$ - , $i$ .

$q$ As linhas contêm descrições de solicitações de movimentação de blocos em ordem cronológica.

Cada solicitação é descrita por quatro números $a_i, b_i, l_i, r_i$ ( $1 \leq a_i, b_i \leq m, a_i \neq b_i, 1 \leq l_i \leq r_i \leq n$ ) e denota uma ordem para mover pedaços com números com $l_i$ de $r_i$ (inclusive) do servidor $a_i$ Ao servidor $b_i$ .

Resultado

Impressão $q$ linhas. De acordo com o número $i$ impressão $1$ se pedido com número $i$ será executado e $0$ , se não.

Exemplos

Dados de entrada

1 2 1
1 1
1 2 1 1

Resultado

1 1

Dados de entrada

1 2 1
1 1
2 1 1 1

Resultado

0 0

Dados de entrada

Resultado

Nota

Considere o terceiro exemplo. Inicialmente, o local dos chunks nos servidores é descrito por uma matriz $[1, 2, 3, 4, 5]$ .

Na primeira solicitação, você precisa mover o pedaço com o número $1$ do servidor $1$ Ao servidor $2$ . Pedaço com um número $1$ está no servidor $1$ , então a mudança será feita. Após executar a solicitação, o local dos chunks nos servidores é descrito por uma matriz $[2, 2, 3, 4, 5]$ .

Na segunda consulta, você precisa mover os pedaços $1, 2$ e $3$ do servidor $2$ Ao servidor $3$ . Chunk $3$ não localizado no servidor $2$ e no servidor $3$ , . .

$4$ $4$ $2$ . $4$ $4$ , . $[2, 2, 3, 2, 5]$ .

$1, 2, 3$ $4$ $2$ $5$ . $3$ $3$ , $2$ , .

$2$ $3$ $3$ $2$ , $2$ $2$ , .

$3$ $3$ $2$ . $3$ $3$ , $[2, 2, 2, 2, 5]$ .

, . , $a$ , $l$ $r$ . 2 Split Merge, $O(\log n)$ . , . $r - l + 1$ , $1$ , , $0$ . $O(1)$ .

$a$ , $b$ . Split Merge, $O(\log n)$ . $O(q \log n)$ . $0$ , .

Python

import sys
import random

INF = 10**9 + 21

random.seed(227)


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

        self.l = None
        self.r = None

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

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

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

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

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

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

    root = t;

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

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

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

    return root

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

    root = t

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

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

    return root

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

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

    return cur

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

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

    return cur

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

    tree = None

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

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

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

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

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

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

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

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

            ans[i] = "1"

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

main()

c : . , . , ,

$[l, r]$

$a$ –

$1$ ,

$0$ .

$1$ ,

$b$ . :

$O(q \log n)$ .

C++

#include <iostream>
#include <vector>

using namespace std;

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

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

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

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

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

Python

MAX = 1000000000

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

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

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

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

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

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

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

E.

	Python	Java
1	3 c	2
256

$G$ , $n$ $m$ .

Divida os vértices do gráfico em dois conjuntos não vazios para que a borda do peso mínimo que conecta os vértices de um conjunto tenha o maior peso possível.

É garantido que o gráfico não contém loops e não pode ser dividido para que essa aresta não exista.

Dados de entrada

A primeira linha contém o número de vértices $n$ ( $3 \leq n \leq 10^5$ ) e o número de arestas $m$ ( $3\leq m \leq 10^5$ ) gráfico.

Na sequência $m$ linhas recebem arestas no formato $u$ , $v$ , $w$ ( $1\leq u, v \leq n$ , $u\neq v$ , $1 \leq w \leq 10^5$ ), Onde $u$ e $v$ defina o vértice inicial e final da aresta e $w$ - o seu peso.

Resultado

Em uma única linha, imprima o peso máximo possível da aresta, que tem o peso mínimo entre aqueles que conectam vértices pertencentes ao mesmo conjunto.

Exemplos

Dados de entrada

Resultado

Dados de entrada

Resultado

Nota

Considere o primeiro exemplo da condição. Nele, existem possivelmente apenas 3 partições diferentes que satisfazem a condição, consideramos cada uma delas:

$\{\{1, 2\}, \{3\}\}$ neste caso as costelas $1$ e $2$ , $1$ ;
$\{\{1, 3\}, \{2\}\}$ , $3$ , $3$ ;
$\{\{2, 3\}, \{1\}\}$ , $4$ , $4$ .

, .

$\{\{1, 3\}, \{2, 4\}\}$ . , , , .

, — $x$ . , $x$ , , , , $x$ . $x$ . , $x$ , , $y < x$ . , $y$ , $x$ , , $x > y$ . $x$ , , $z > x$ , , $x$ , ( ), .

, , . (, ) . $0$ $1$ . :

, $0$ .
$a$ $b$ $b$ , $a$ (, $val[a] = 0$ , $val[b] = 1$ , ).

, , . , .

$O(n + m)$ , $O((n + m) \log \max w)$ .

Python

import sys

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

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

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

    return True

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

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

    return True

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

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

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

    l = 0
    r = mx + 1

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

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

main()

C++

#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <utility>

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

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

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

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

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

Java

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

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

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

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

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

        static class Edge {
            int to;
            int w;

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

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

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

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

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

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

    }

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

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

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

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

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

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

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

        }

    }
}

F.

	Python	Java
2	4 c	2 c
512

. . , , .

: , . $n$ - . — , , . , . , , .

, , $i$ ( $i < n$ ) $i + 1$ , $n$ $1$ . ( ) - , .

, , , $k$ . , . .

. , , , .

$t$ — . .

$n$ $k$ ( $1 \leq n \leq 100\,000$ , $0 \leq k \leq min(n - 1, 100)$ ) — , , , .

$n$ inteiros $a_i$ ( $-10^9 \leq a_i \leq 10^9$ ) - a relevância dos documentos.

Garantido que o valor $n$ em todos os casos de teste não excede $100\,000$ .

Resultado

Para cada caso de teste, imprima um número inteiro - a resposta para o problema.

Exemplo

Dados de entrada

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

Resultado

vinte
10
quinze
10
14
-1

Nota

No primeiro exemplo, é vantajoso selecionar como um documento inicial relevante $9$ e envie-o e os 2 documentos a seguir para filtragem. Na fase de filtragem, todos os documentos devem ser deixados.

No segundo exemplo, é vantajoso selecionar qualquer documento relevante como inicial $5$ , envie-o para o estágio de filtragem e 2 documentos a seguir. Na fase de filtragem, você deve excluir o documento com relevância $-5$ Assim, serão emitidos dois documentos relevantes $5$ .

No quinto exemplo, é vantajoso escolher o documento com o número como inicial $7$ $5$ . , $[5, -1, -3, -1, 5, 6]$ . $-3$ , $[5, -1, -1, 5, 6]$ $14$ .

, .

, — . , . $0$ , , - .

, .

$dp_{i, j}$ — , - $[l; i]$ ( $l$ , ), $k$ .

: $dp_{i, j} = \max({0, dp_{i - 1, j} + a_i, dp_{i - 1, j - 1}})$ , :

$0$ — «» .
$dp_{i - 1, j} + a_i$ — - , i- .
$dp_{i - 1, j - 1}$ — - , i- .

$O(nk)$ , $\max\limits_{\substack{1 \leq i \leq n \\ 0 \leq j \leq k}}{dp_{i, j}}$ .

, , n- .

$dpl_{i, j}$ — , $[1; i]$ , $k$ .

: $dpl_{i, j} = \max({dpl_{i - 1, j} + a_i, dpl_{i - 1, j - 1}})$ , :

$dpl_{i - 1, j} + a_i$ — , i- .
$dpl_{i - 1, j - 1}$ — , i- .

, , .

, $dpr_{i, j}$ — , $[i; n]$ , $k$ .

: $dpr_{i, j} = \max({dpr_{i + 1, j} + a_i, dpr_{i + 1, j - 1}})$ , :

$dpr_{i +1, j} + a_i$ — , i- .
$dpr_{i + 1, j - 1}$ — , i- .

$O(nk)$ .

, n- ? $p$ , , $q$ , . — $dpl_{p, q}$ . — , $\max\limits_{\substack{p < i \leq n \\ 0 \leq j \leq k - q}}{dpr_{i, j}}$ .

$dpr\_max_{i, j} = \max{(dpr_{i, j}, dpr\_max_{i + 1, j}, dpr\_max_{i, j - 1})}$ . — $O(nk)$ , $p$ $q$ $O(1)$ .

$O(nk)$ .

Python

import sys

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

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

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

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

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

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

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

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

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

    return ans

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

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

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

main()

C++

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>

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

using namespace std;

typedef long long int ll;
typedef long double ld;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    return 0;
}

Java

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.io.InputStream;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

            out.println(ans);
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

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

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

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

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

    }

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

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

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

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

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

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

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

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

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

        }

    }
}

Onde resolver problemas reais para candidatos a Yandex: treinamento em Codeforces e análises

A. aniversário de Vasya

Dados de entrada

Resultado

Exemplo

Nota

B. Chave Privada

Resultado

Exemplos

Nota

C. Programador de praia

Dados de entrada

Resultado

Exemplos

Nota

D.

Resultado

Exemplos

Nota

E.

Dados de entrada

Resultado

Exemplos

Nota

F.

Resultado

Exemplo

Nota

More articles: