🦂 👩🏾‍🤝‍👨🏻 👩🏽‍🚒 Où résoudre des problèmes réels pour les candidats Yandex: formation sur Codeforces et analyse 🌔 ⏹️ 🎴

Habr, c'est encore moi, Alexei Cancer (photo pas la mienne). L'année dernière, en plus du travail principal, il m'est arrivé de devenir l'un des auteurs de tâches pour les candidats à Yandex. Aujourd'hui, notre équipe publie pour la première fois depuis longtemps sur Habrr de vraies tâches pour les développeurs qui s'installent dans l'entreprise. Ces tâches ont été utilisées jusqu'en février 2020 dans la sélection d'un stage pour les backenders. Les solutions ont été vérifiées par un ordinateur. Désormais, les candidats obtiennent des tâches similaires.

Le débriefing et le code sont délibérément cachés dans les spoilers. Si vous vous préparez à des entretiens avec de grandes sociétés informatiques, essayez de résoudre un ou plusieurs problèmes avant de regarder l'analyse. Vous pouvez envoyer la solution pour vérification à Codeforces - la réponse viendra immédiatement ( lien vers Codeforces et note) Le code est présenté en Python, C ++ et Java. Important: le code «Olympiade» de l'auteur n'est pas destiné à la production, il est écrit sur la base que le système le vérifiera automatiquement.

Les auteurs et mes collègues: tâche A - Pavel Doroshkevich, B et F - Egor Chunaev, E - Andrey Khalyavin, C et D - moi.

A.
　Solution et code d' anniversaire de Vasya

B. Clé privée
　Solution et code

C. Programmeur sur la plage
　Solution et code

D. Déplacement de morceaux
　Solution et code

E. Séparation de la colonne
　Solution et code

F. Recherche
　Solution et code

Anniversaire de A. Vasya

Limite de temps par test	3 s
Limite de mémoire par test	256 Mo
Entrer	entrée standard
Conclusion	sortie standard

Vasya et ses amis adorent manger délicieusement. Le jour de son anniversaire, chacun est obligé de surprendre les autres en préparant de nouveaux plats savoureux et sains.

Aujourd'hui, c'est l'anniversaire de Vasya, et il a invité ses amis à déguster n de ses meilleurs plats. Le nom de chacun d'eux se compose de lettres anglaises minuscules, de chiffres et du trait de soulignement.

La cuisson au numéro i nécessite des ingrédients z _i . Pour chaque ingrédient, son nom est connu, la quantité requise pour une portion du plat, ainsi que l'unité de mesure dans laquelle cette quantité est fixée. De plus, Vasya sait que le i-ème chef-d'œuvre culinaire voudra essayer avec _mes amis.

Les unités suivantes sont utilisées:

g, kg - grammes et kilogrammes respectivement;
l, ml - litres et millilitres respectivement;
cnt, des dizaines - une seule pièce et dix pièces respectivement.

Dans un kilogramme 1000 grammes et dans un litre 1000 millilitres. Vous pouvez effectuer un transfert d'une unité de mesure à une autre si et seulement si elles indiquent simultanément soit la masse, soit le volume, soit la quantité.

Vasya a deux répertoires d'ingrédients. Le premier pour chaque ingrédient indique sa quantité dans l'emballage et le prix par emballage. Le deuxième répertoire pour chaque ingrédient indique la teneur en protéines, graisses, glucides et la valeur énergétique d'une certaine quantité de cet ingrédient.

Vasya a besoin de cuisiner tous les plats, sans rien acheter de plus. Pour ce faire, il doit déterminer quels ingrédients et quelle quantité doivent être achetés au magasin.

Comme les amis de l'anniversaire font très attention à la nutrition, avant d'essayer les plats de Vasina, ils voudront tout savoir: comment Vasya a préparé les plats, leur valeur énergétique et la teneur en protéines, graisses et glucides. Vasya doit préparer ces informations.

Il est nécessaire d'aider l'anniversaire à calculer combien d'argent est nécessaire pour acheter des produits dans le magasin, quels ingrédients et en quelle quantité vous devez acheter, ainsi que pour chaque plat, calculer le contenu en protéines, lipides, glucides et valeur énergétique si vous le mangez complètement.

Des données d'entrée

La première ligne contient un entier n (1 ≤ n ≤ 1000) - le nombre de plats que Vasya a décidé de cuisiner.

Suit une description de n plats. La première ligne contient la chaîne d _i et des entiers avec _i , z _i (1 ⩽ c _i , z _i ⩽ 100) - le nom du plat, le nombre d'amis qui veulent essayer ce plat et le nombre d'ingrédients nécessaires à la cuisson. Le nom du plat se compose de lettres anglaises minuscules, de chiffres et d'un trait de soulignement. Sa longueur ne dépasse pas 20 caractères.

Les lignes z _i suivantes contiennent des descriptions des ingrédients. La ligne avec le numéro j contient la chaîne s _{i, j} est le nom de l'ingrédient, l'entier a _{i, j}(1 ≤ a _{i, j} ≤ 1000) est la quantité requise de l'ingrédient et la chaîne u _{i, j} est le nom de l'unité de mesure de la quantité. Le nom de l'ingrédient se compose de lettres anglaises minuscules, de chiffres et du trait de soulignement. La longueur de ligne ne dépasse pas 20 caractères.

La ligne suivante contient l'entier k (1 ≤ k ≤ 1000) - le nombre d'ingrédients dans le catalogue de prix.

Chacune des k lignes suivantes contient quatre valeurs t _i p _i a _i u _i décrivant l'ingrédient.

t _i - le nom de l'ingrédient, composé de lettres anglaises minuscules, de chiffres et du trait de soulignement. La longueur de ligne ne dépasse pas 20 caractères;
p _i est le coût de l'ingrédient, étant donné un entier (1 ⩽ p _i ⩽ 1000);
a _i - la quantité d'ingrédient dans l'emballage en unités, spécifiée par un entier (1 ⩽ a _i ⩽ 1000);
u _i - unité de mesure de la quantité (l, ml, g, kg, cnt ou dizaines).

La ligne suivante contient le nombre m (1 ≤ m ≤ 1000) - le nombre d'ingrédients dans le catalogue des aliments.

Viennent ensuite m lignes, chacune contenant sept valeurs t _i a _i u _i pr _i f _i ch _i fv _i décrivant l'ingrédient.

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

Il est garanti que:

les catalogues répertorient tous les ingrédients nécessaires à la cuisson;
il n'y a pas deux plats du même nom;
il n'y a pas deux ingrédients dans le même catalogue avec le même nom;
il n'y a pas deux ingrédients dans le même plat avec le même nom;
pour deux mentions quelconques d'un ingrédient, les unités de mesure dans lesquelles ses quantités sont données peuvent être converties l'une en l'autre.

Production

La première ligne doit contenir un seul entier: le montant que Vasya doit dépenser pour préparer les vacances.

Ensuite, k lignes doivent suivre, dans chacune desquelles un espace indique le nom de l'ingrédient et un entier - le nombre de paquets que vous devez acheter. Les ingrédients affichés dans ces k lignes doivent correspondre aux ingrédients décrits dans le premier répertoire.

Les n lignes suivantes doivent contenir un espace entre le nom du plat et ses caractéristiques, décrites par quatre nombres réels: protéines, lipides, glucides et valeur énergétique.

Les ingrédients et les plats peuvent être affichés dans n'importe quel ordre.

Votre réponse sera considérée comme correcte si tous les nombres entiers correspondent aux nombres correspondants dans la réponse du jury, et pour tous les nombres réels dans la réponse, leur erreur absolue ou relative ne dépasse pas 10 ^-3 . Plus formellement, que le nombre réel dans votre réponse soit A et le nombre correspondant dans la réponse du jury soit B. Ensuite, le nombre A sera considéré comme correct si

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

Exemple

Des données d'entrée Production

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

Remarque

Dans le premier exemple, Vasya doit cuire 7 sandwichs et 9 omelettes.

Pour préparer tous les premiers plats, vous avez besoin de 10 ⋅ 7 grammes de beurre, 2 1 7 morceaux de pain et 30 ⋅ 7 grammes de saucisse. Chaque sandwich contiendra

$0.8 ⋅ \frac {10}{100} + 7.3 ⋅ \frac {2}{5} + 10 ⋅ \frac {30}{100} =6$ gramme de protéine

$72.5 ⋅ \frac {10}{100} + 1.6 ⋅ \frac {2}{5} + 18 ⋅ \frac {30}{100} =13.29$ grammes de gras et

$1.3 ⋅ \frac {10}{100} + 52.3 ⋅ \frac {2}{5} + 1.5 ⋅ \frac {30}{100} =21.5$ gramme de glucides. La valeur énergétique sera

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

Pour préparer tous les deuxièmes plats, vous avez besoin de 4 ⋅ 9 = 36 œufs, 120 ⋅ 9 = 1080 millilitres de lait, 9 grammes de sel, 50 ⋅ 9 = 450 grammes de saucisse. Chaque omelette contiendra

$13 ⋅ 4+ 3 ⋅ \frac {120}{1000} + 10 ⋅ \frac {50}{100} =57.36$ gramme de protéine

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

$1 ⋅ 4+ 4.7 ⋅ \frac {120}{1000} + 1.5 ⋅ \frac {50}{100} =5.314$ les glucides. La valeur énergétique sera

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

Au total, 70 grammes de beurre, 36 œufs, 1080 litres de lait, 9 grammes de sel, 210 + 450 = 660 grammes de saucisse et 14 tranches de pain grillé sont nécessaires.

Ainsi, dans le magasin, vous devez acheter un paquet de beurre, 4 douzaines d'œufs, 2 paquets de saucisse et de lait, un paquet de sel et du pain grillé, en payant 120 + 61 ⋅ 4 + 100 ⋅ 2 + 58 ⋅ 2 + 14 + 40 = 734 roubles .

Décision

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

Code 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()

Code 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;
}

Code 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. Clé privée

Limite de temps par test	2 s
Limite de mémoire par test	256 Mo
Entrer	entrée standard
Conclusion	sortie standard

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

La première ligne contient deux entiers $x$ et $y$ ( $1 \leq x \leq y \leq 10^{12}$ ) - une description de la clé publique.

Production

Imprime un seul entier - le nombre de clés privées pour lesquelles cette clé est publique.

Exemples

Des données d'entrée

5 10

Production

Des données d'entrée

10 11

Production

Des données d'entrée

527 9486

Production

Remarque

Dans le premier exemple, il existe deux clés privées pour lesquelles ( $5, 10$ ) est la clé publique: ( $5, 10$ ) et ( $10, 5$ )

Dans le deuxième exemple, Dima s'est trompé, car aucune clé privée ne génère de clé publique ( $10, 11$ )

Dans le troisième exemple, les clés privées appropriées sont ( $527, 9486$ ), ( $1054, 4743$ ), ( $4743, 1054$ ), ( $9486, 527$ )

GCD (le plus grand facteur commun) de deux nombres naturels $p$ et $q$ appelé le plus grand nombre $k$ tel que $p$ divisé par $k$ et $q$ divisé par $k$ . Par exemple, GCD ( $6, 15$ ) est égal $3$ et GCD ( $16, 8$ ) est égal $8$ .

NOC (le plus petit multiple commun) de deux nombres naturels $p$ et $q$ appelé le plus petit nombre $k$ tel que $k$ divisé par $p$ et $k$ divisé par $q$ . Par exemple, NOC ( $2, 3$ ) est égal $6$ et NOC ( $10, 20$ ) est égal à 20.

Solution et code

$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. Programmeur de plage

	Toutes les langues	Python	Java
Limite de temps par test	2 s	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$ ).
Ensuite, la dissimilarité des deux chaises longues est calculée comme le OU exclusif (OU exclusif au niveau du bit) des nombres attribués à ces chaises longues. Moins la valeur de dissimilarité est grande, plus les transats sont similaires.

Aidez le programmeur Aleksey à comprendre quelle valeur minimale pour la différence entre les chaises longues il peut atteindre en comparant toutes les chaises longues gratuites par paires.

Des données d'entrée

La première ligne contient un nombre $T$ ( $1 \leq T \leq 1000$ ) - le nombre de tests. Chaque test se compose de deux lignes.

Un numéro est attribué à la première ligne de chaque test $n$ ( $2 \leq n \leq 10^6$ ) - le nombre de transats.

La deuxième ligne de chaque test contient $n$ Nombres $a_i$ ( $1 \leq i \leq n$ , $0 \leq a_i \leq 10^9$ ) - les valeurs qui ont été mises dans les transats conformément aux signes extérieurs.

Montant $n$ dans tous les tests ne dépasse pas $10^6$ .

Production

Pour chaque scénario de test, imprimez une ligne sur laquelle il ne devrait y avoir qu'un seul chiffre - la valeur minimale de dissimilarité.

Exemples

Des données d'entrée

1
5
1 2 4 8 16

Production

Des données d'entrée

Production

6
2

Remarque

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

Chaque demande est décrite par quatre chiffres $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$ ) et désigne un ordre de déplacement de morceaux avec des nombres $l_i$ par $r_i$ (inclus) depuis le serveur $a_i$ au serveur $b_i$ .

Production

Impression $q$ lignes. En ligne avec le numéro $i$ impression $1$ si demande avec numéro $i$ sera exécuté et $0$ , si non.

Exemples

Des données d'entrée

1 2 1
1
1 2 1 1

Production

Des données d'entrée

1 2 1
1
2 1 1 1

Production

Des données d'entrée

Production

Remarque

Prenons le troisième exemple. Initialement, l'emplacement des morceaux sur les serveurs est décrit par un tableau $[1, 2, 3, 4, 5]$ .

Dans la première demande, vous devez déplacer le bloc avec le numéro $1$ du serveur $1$ au serveur $2$ . Morceau avec un nombre $1$ est sur le serveur $1$ , donc le mouvement sera fait. Après avoir exécuté la demande, l'emplacement des morceaux sur les serveurs est décrit par un tableau $[2, 2, 3, 4, 5]$ .

Dans la deuxième requête, vous devez déplacer les morceaux $1, 2$ et $3$ du serveur $2$ au serveur $3$ . Tronçon $3$ ne se trouve pas sur le serveur $2$ et sur le serveur $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
Limite de mémoire par test	256 Mo
Entrer	entrée standard
Conclusion	sortie standard

Graphique non orienté pondéré Dan $G$ contenant $n$ pics et $m$ travers de porc.

Divisez les sommets du graphique en deux ensembles non vides afin que le bord du poids minimum reliant les sommets d'un ensemble ait le plus grand poids possible.

Il est garanti que le graphe ne contient pas de boucles et ne peut pas être divisé de sorte qu'une telle arête n'existe pas.

Des données d'entrée

La première ligne contient le nombre de sommets $n$ ( $3 \leq n \leq 10^5$ ) et le nombre d'arêtes $m$ ( $3\leq m \leq 10^5$ ) graphique.

Dans ce qui suit $m$ les lignes reçoivent des bords au format $u$ , $v$ , $w$ ( $1\leq u, v \leq n$ , $u\neq v$ , $1 \leq w \leq 10^5$ ), où $u$ et $v$ définir le sommet de début et de fin de l'arête, et $w$ - son poids.

Production

Sur une seule ligne, imprimez le poids maximum possible du bord, qui a le poids minimum parmi ceux qui relient les sommets appartenant au même ensemble.

Exemples

Des données d'entrée

Production

Des données d'entrée

Production

Remarque

. 3 , , :

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

, .

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

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

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

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

, , . , .

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

Python

import sys

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

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

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

    return True

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

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

    return True

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

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

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

    l = 0
    r = mx + 1

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

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

main()

C++

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

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

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

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

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

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

Java

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

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

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

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

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

        static class Edge {
            int to;
            int w;

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

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

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

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

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

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

    }

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

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

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

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

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

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

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

        }

    }
}

F.

	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)$ ) - le nombre de documents reçus pendant la recherche et le nombre maximal de documents pouvant être supprimés après filtrage, respectivement.

La deuxième ligne contient $n$ entiers $a_i$ ( $-10^9 \leq a_i \leq 10^9$ ) - la pertinence des documents.

Garanti que le montant $n$ dans tous les cas de test ne dépasse pas $100\,000$ .

Production

Pour chaque scénario de test, imprimez un entier - la réponse au problème.

Exemple

Des données d'entrée

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

Production

vingt
dix
quinze
dix
14
-1

Remarque

Dans le premier exemple, il est avantageux de sélectionner comme document initial pertinent $9$ et l'envoyer et les 2 documents suivants pour le filtrage. Au stade de la filtration, tous les documents doivent être laissés.

Dans le deuxième exemple, il est avantageux de sélectionner n'importe quel document pertinent comme premier $5$ , 2 . $-5$ , , $5$ .

$7$ $5$ . , $[5, -1, -3, -1, 5, 6]$ . $-3$ , $[5, -1, -1, 5, 6]$ $14$ .

, .

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

, .

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

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

$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}$ - le montant maximum qui peut être sur une sous-section $[1; i]$ s'il en est retiré exactement $k$ éléments.

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

$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);

        }

    }
}

Où résoudre des problèmes réels pour les candidats Yandex: formation sur Codeforces et analyse

Anniversaire de A. Vasya

Des données d'entrée

Production

Exemple

Remarque

B. Clé privée

Production

Exemples

Remarque

C. Programmeur de plage

Des données d'entrée

Production

Exemples

Remarque

D.

Production

Exemples

Remarque

E.

Des données d'entrée

Production

Exemples

Remarque

F.

Production

Exemple

Remarque

More articles: