👃 🤶 🗜️ Where to solve real problems for Yandex candidates: training on Codeforces and analysis 📟 🧑 👉

Habr, it's me again, Alexei Cancer (photo not mine). Last year, in addition to the main work, I happened to become one of the authors of tasks for candidates for Yandex. Today, our team for the first time in a long time publishes on Habrr real tasks for developers who get settled in the company. These tasks were used until February 2020 in the selection for an internship for backenders. The solutions were checked by a computer. Now candidates get similar tasks.

Debriefing and code are deliberately hidden in spoilers. If you are preparing for interviews with large IT companies, try to solve one or more problems before watching the analysis. You can send the solution for verification to Codeforces - the answer will come immediately ( link to Codeforces and note) The code is presented in Python, C ++ and Java. Important: the author’s “Olympiad” code is not intended for production, it is written on the basis that the system will check it automatically.

The authors and my colleagues: task A - Pavel Doroshkevich, B and F - Egor Chunaev, E - Andrey Khalyavin, C and D - me.

A. Vasya’s birthday
　Solution and code

B. Private key
　Solution and code

C. Programmer on the beach
　Solution and code

D. Moving chunks
　Solution and code

E. Separating the column
　Solution and code

F. Search
　Solution and code

A. Vasya’s birthday

Time limit per test	3 s
Memory limit per test	256 MB
Enter	standard input
Conclusion	standard output

Vasya and his friends love to eat deliciously. On his birthday, everyone is obliged to surprise others by preparing new tasty and healthy dishes.

Today is Vasya’s birthday, and he invited his friends to taste n of his best dishes. The name of each of them consists of lowercase English letters, numbers and the underscore.

Cooking at number i requires z _i ingredients. For each ingredient, its name is known, the required quantity for one portion of the dish, as well as the unit of measure in which this quantity is set. In addition, Vasya knows that the i-th culinary masterpiece will want to try with _i friends.

The following units are used:

g, kg - grams and kilograms respectively;
l, ml - liters and milliliters respectively;
cnt, tens - one piece and ten pieces respectively.

In one kilogram 1000 grams and in one liter 1000 milliliters. You can make a transfer from one unit of measurement to another if and only if they simultaneously indicate either mass, or volume, or quantity.

Vasya has two ingredient directories. The first for each ingredient indicates its quantity in the package and the price per package. The second directory for each ingredient indicates the content of proteins, fats, carbohydrates and the energy value of a certain amount of this ingredient.

Vasya needs to cook all the dishes, while not buying anything extra. To do this, he needs to determine what ingredients and in what quantity must be purchased at the store.

Since friends of the birthday boy are very careful about nutrition, before they try Vasina’s dishes, they will want to find out everything: how Vasya prepared the dishes, their energy value and the content of proteins, fats and carbohydrates. Vasya needs to prepare this information.

It is necessary to help the birthday person calculate how much money is needed to buy products in the store, what ingredients and in what quantity you need to buy, as well as for each dish, calculate the content of proteins, fats, carbohydrates and energy value if you eat it completely.

Input data

The first line contains an integer n (1 ≤ n ≤ 1000) - the number of dishes that Vasya decided to cook.

Then follows a description of n dishes. The first line contains the string d _i and integers with _i , z _i (1 ⩽ c _i , z _i ⩽ 100) - the name of the dish, the number of friends who want to try this dish, and the number of ingredients needed for cooking. The name of the dish consists of lowercase English letters, numbers and an underscore. Its length does not exceed 20 characters.

The following z _i lines contain descriptions of the ingredients. The line with number j contains the string s _{i, j} is the name of the ingredient, the integer a _{i, j}(1 ≤ a _{i, j} ≤ 1000) is the required quantity of the ingredient and the string u _{i, j} is the name of the unit of measure for the quantity. The name of the ingredient consists of lowercase English letters, numbers and the underscore. The line length does not exceed 20 characters.

The next line contains the integer k (1 ≤ k ≤ 1000) - the number of ingredients in the price catalog.

Each of the next k lines contains four t _i p _i a _i u _i values describing the ingredient.

t _i - the name of the ingredient, consisting of lowercase English letters, numbers and the underscore. The line length does not exceed 20 characters;
p _i is the cost of the ingredient, given an integer (1 ⩽ p _i ⩽ 1000);
a _i - the amount of ingredient in the package in units, specified by an integer (1 ⩽ a _i ⩽ 1000);
u _i - unit of measurement of quantity (l, ml, g, kg, cnt or tens).

The next line contains the number m (1 ≤ m ≤ 1000) - the number of ingredients in the food catalog.

Next are m lines, each of which contains seven values t _i a _i u _i pr _i f _i ch _i fv _i describing the ingredient.

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

It is guaranteed that:

the catalogs list all the ingredients necessary for cooking;
there are no two dishes with the same name;
there are no two ingredients in the same catalog with the same name;
there are no two ingredients in the same dish with the same name;
for any two mentions of an ingredient, the units of measure in which its quantities are given can be converted into each other.

Output

The first line should contain a single integer: the amount that Vasya needs to spend on preparing for the holiday.

Then k lines should follow, in each of which a space indicates the name of the ingredient and an integer - the number of packages that you need to buy. The ingredients displayed in these k lines should correspond to the ingredients described in the first directory.

The next n lines should contain a space between the name of the dish and its characteristics, described by four real numbers: proteins, fats, carbohydrates and energy value.

Ingredients and dishes are allowed to be displayed in any order.

Your answer will be considered correct if all integers match the corresponding numbers in the jury's answer, and for all real numbers in the answer their absolute or relative error does not exceed 10 ^-3 . More formally, let the real number in your answer be A, and the corresponding number in the jury's answer be B. Then the number A will be considered correct if

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

Example

Input data Output

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

Note

In the first example, Vasya needs to cook 7 sandwiches and 9 omelets.

To prepare all the first dishes you need 10 ⋅ 7 grams of butter, 2 1 7 pieces of bread and 30 ⋅ 7 grams of sausage. Each sandwich will contain

$0.8 ⋅ \frac {10}{100} + 7.3 ⋅ \frac {2}{5} + 10 ⋅ \frac {30}{100} =6$ gram of protein

$72.5 ⋅ \frac {10}{100} + 1.6 ⋅ \frac {2}{5} + 18 ⋅ \frac {30}{100} =13.29$ grams of fat and

$1.3 ⋅ \frac {10}{100} + 52.3 ⋅ \frac {2}{5} + 1.5 ⋅ \frac {30}{100} =21.5$ gram of carbohydrates. Energy value will be

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

To prepare all the second courses you need 4 ⋅ 9 = 36 eggs, 120 ⋅ 9 = 1080 milliliters of milk, 9 grams of salt, 50 ⋅ 9 = 450 grams of sausage. Each omelet will contain

$13 ⋅ 4+ 3 ⋅ \frac {120}{1000} + 10 ⋅ \frac {50}{100} =57.36$ gram of protein

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

$1 ⋅ 4+ 4.7 ⋅ \frac {120}{1000} + 1.5 ⋅ \frac {50}{100} =5.314$ carbohydrates. Energy value will be

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

In total, 70 grams of butter, 36 eggs, 1080 liters of milk, 9 grams of salt, 210 + 450 = 660 grams of sausage and 14 slices of toast bread are needed.

Thus, in the store you need to buy one pack of butter, 4 dozen eggs, 2 packs of sausage and milk, one pack of salt and toast bread, paying 120 + 61 ⋅ 4 + 100 ⋅ 2 + 58 ⋅ 2 + 14 + 40 = 734 rubles .

Decision

, n dishes, prices k , catalog, , m .

:

1. , , .
2. , , .

.

. dishes prices.

1. - inredients, — , — ( ).
2. .
3. , ingredients .
4. , prices .
5. , . , 32- .
6. , k .

, - , 0.

. dishes catalog:

1. .
2. , , .
3. .
4. .

. 10 1000, Decimal . 1000, . , .

float , 6-7 . double . , .

- :

$O(\sum_{i=1}^{n}z_i)$ , z_i — i- .

Python code

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 ++ Code

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

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

using namespace std;

typedef long long int ll;
typedef long double ld;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    return 0;
}

Java code

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. Private Key

Time limit per test	2 s
Memory limit per test	256 MB
Enter	standard input
Conclusion	standard output

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

The first line contains two integers $x$ and $y$ ( $1 \leq x \leq y \leq 10^{12}$ ) - a description of the public key.

Output

Print a single integer - the number of private keys for which this key is public.

Examples

Input data

5 10

Output

Input data

10 11

Output

Input data

527 9486

Output

Note

In the first example, there are two private keys for which ( $5, 10$ ) is the public key: ( $5, 10$ ) and ( $10, 5$ )

In the second example, Dima was mistaken, because not a single private key generates a public key ( $10, 11$ )

In the third example, suitable private keys are ( $527, 9486$ ), ( $1054, 4743$ ), ( $4743, 1054$ ), ( $9486, 527$ )

GCD (the greatest common factor) of two natural numbers $p$ and $q$ called the largest number $k$ such that $p$ divided by $k$ and $q$ divided by $k$ . For example, GCD ( $6, 15$ ) is equal $3$ , and GCD ( $16, 8$ ) is equal $8$ .

NOC (the smallest common multiple) of two natural numbers $p$ and $q$ called the smallest number $k$ such that $k$ divided by $p$ and $k$ divided by $q$ . For example, NOC ( $2, 3$ ) is equal $6$ , and NOC ( $10, 20$ ) is equal to 20.

Solution and 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. Beach programmer

	All languages	Python	Java
Time limit per 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$ ).
Then the dissimilarity of the two sunbeds is calculated as the XOR (bitwise exclusive OR) of the numbers assigned to these sunbeds. The less the value of dissimilarity, the more similar the sunbeds.

Help programmer Aleksey understand what minimum value for the difference between sun beds he can achieve by comparing all free sun beds in pairs.

Input data

The first line contains a number $T$ ( $1 \leq T \leq 1000$ ) - the number of tests. Each test consists of two lines.

The first line of each test is given a number $n$ ( $2 \leq n \leq 10^6$ ) - the number of sunbeds.

The second line of each test contains $n$ numbers $a_i$ ( $1 \leq i \leq n$ , $0 \leq a_i \leq 10^9$ ) - the values that were put in the sunbeds in accordance with external signs.

Amount $n$ in all tests does not exceed $10^6$ .

Output

For each test case print one line in which there should be a single number - the minimum value of dissimilarity.

Examples

Input data

1
5
1 2 4 8 16

Output

Input data

Output

6
2

Note

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

Each request is described by four numbers $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$ ) and denotes an order for moving chunks with numbers with $l_i$ by $r_i$ (inclusive) from the server $a_i$ to server $b_i$ .

Output

Print $q$ lines. In line with number $i$ print $1$ if request with number $i$ will be executed and $0$ , if not.

Examples

Input data

1 2 1
1
1 2 1 1

Output

Input data

1 2 1
1
2 1 1 1

Output

Input data

Output

Note

Consider the third example. Initially, the location of chunks on servers is described by an array $[1, 2, 3, 4, 5]$ .

In the first request, you need to move the chunk with the number $1$ from server $1$ to server $2$ . Chunk with a number $1$ is on the server $1$ , so the move will be made. After executing the request, the location of the chunks on the servers is described by an array $[2, 2, 3, 4, 5]$ .

In the second query, you need to move the chunks $1, 2$ and $3$ from server $2$ to server $3$ . Chunk $3$ not located on the server $2$ , and on the server $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
Memory limit per test	256 MB
Enter	standard input
Conclusion	standard output

Dan weighted undirected graph $G$ containing $n$ peaks and $m$ ribs.

Break the vertices of the graph into two non-empty sets so that the edge of minimum weight connecting the vertices from one set has the largest possible weight.

It is guaranteed that the graph does not contain loops and cannot be split so that such an edge does not exist.

Input data

The first line contains the number of vertices $n$ ( $3 \leq n \leq 10^5$ ) and the number of edges $m$ ( $3\leq m \leq 10^5$ ) graph.

In the following $m$ lines are given edges in the format $u$ , $v$ , $w$ ( $1\leq u, v \leq n$ , $u\neq v$ , $1 \leq w \leq 10^5$ ), where $u$ and $v$ set the start and end vertex of the edge, and $w$ - its weight.

Output

In a single line print the maximum possible weight of the edge, which has the minimum weight among those that connect vertices belonging to the same set.

Examples

Input data

Output

Input data

Output

Note

. 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)$ ) - the number of documents received during the search, and the maximum number of documents that can be deleted after filtering, respectively.

The second line contains $n$ integers $a_i$ ( $-10^9 \leq a_i \leq 10^9$ ) - the relevance of the documents.

Guaranteed that the amount $n$ in all test cases does not exceed $100\,000$ .

Output

For each test case print one integer - the answer to the problem.

Example

Input data

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

Output

twenty
10
fifteen
10
14
-1

Note

In the first example, it’s advantageous to select as an initial document with relevance $9$ and send it and the following 2 documents for filtering. At the filtration stage, all documents must be left.

In the second example, it’s advantageous to select any document with relevance as the initial $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}$ — , $[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);

        }

    }
}

Where to solve real problems for Yandex candidates: training on Codeforces and analysis

A. Vasya’s birthday

Input data

Output

Example

Note

B. Private Key

Output

Examples

Note

C. Beach programmer

Input data

Output

Examples

Note

D.

Output

Examples

Note

E.

Input data

Output

Examples

Note

F.

Output

Example

Note

More articles: