Предметный тур. Информатика. 3 этап

Информатика. 8–11 классы

Задача 1.1.(10 баллов)

Контейнеры

Имя входного файла: стандартный ввод или input.txt.

Имя выходного файла: стандартный вывод или output.txt.

Ограничение по времени выполнения программы: 1 с.

Ограничение по памяти: 64 Мбайт.

Условие

Кот Матроскин дорос до высокой должности в Трансагенстве. Бочку он уже не катит, а занимается отправкой грузов контейнерами. В точке отправления скопились \(a\) больших контейнеров и \(b\) малых. Матроскин должен спланировать и заказать необходимое количество платформ для их перевозки (открытых вагонов, предназначенных для перевозки грузов, не боящихся атмосферных воздействий). На одну платформу технически можно поместить либо два больших контейнера, либо один большой и два малых. Иных способов загрузить платформу нет. Так как заказ платформы стоит денег, то экономный Матроскин никогда не отправит недогруженную платформу. Если некоторое количество контейнеров не получится загрузить сейчас, он отправит их на ожидание до следующего заказа.

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

Формат входных данных

В единственной строке содержатся два целых числа \(a\) и \(b\) через пробел — количество больших и малых контейнеров в точке отправления соответственно, \(0 \leqslant a, b \leqslant 100\).

Формат выходных данных

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

Тестовые данные

Номер теста	Стандартный ввод	Стандартный вывод
1	5 7	4

Пример программы-решения

Ниже представлено решение на языке C++.

C++

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int a, b;
    cin >> a >> b;
    int b1 = min(a, b / 2);
    a -= b1;
    b -= b1 * 2;
    cout << b1 + a / 2 << endl;
}

Задача 1.2.(15 баллов)

Три города

Имя входного файла: стандартный ввод или input.txt.

Имя выходного файла: стандартный вывод или output.txt.

Ограничение по времени выполнения программы: 1 с.

Ограничение по памяти: 64 Мбайт.

Условие

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

Для определенности, пусть расстояние между Первым и Вторым городами равно \(A\), расстояние между Вторым и Третьим городами равно \(B\), причем \(A \leqslant B\). Известно, что если из Первого во Второй лететь самолетом, а затем из Второго в Третий ехать поездом, время в пути составит \(X\) ч. Если же из Первого во Второй ехать поездом, а затем из Второго в Третий лететь самолетом, то время в пути составит \(Y\) ч.

Самолет летит со скоростью, в \(k\) раз превышающей скорость поезда. По заданным числам \(X,~Y,~k\) требуется определить, во сколько раз расстояние \(B\) больше расстояния \(A\).

Формат входных данных

В одной строке через пробел заданы три целых числа:

\(X\) — время движения, если из Первого во Второй город лететь самолетом, а затем из Второго в Третий ехать поездом;
\(Y\) — время движения, если из Первого во Второй город ехать поездом, а затем из Второго в Третий лететь самолетом;
\(k\) — коэффициент, показывающий, во сколько раз самолет быстрее поезда.
\(1 \leqslant X,~Y \leqslant 7 \cdot 10^5\);
\(2 \leqslant k \leqslant 1000\);
\(X \geqslant Y\).

Формат выходных данных

Вывести одно число — отношение, показывающее, во сколько раз расстояние \(B\) больше расстояния \(A\).

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

Тестовые данные

Номер теста	Стандартный ввод	Стандартный вывод
1	5 3 3	3
2	12 12 3	1

Примечания

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

После некоторых рассуждений можно получить, что если, например, взять расстояние \(A\) равным 15 км, а расстояние \(B\) равным 45 км, скорость поезда равной 10 км/ч, а скорость самолета равной 30 км/ч, то получим требуемые результаты: \[\displaystyle\frac{15}{30} + \frac{45}{10} = 5,\] \[\displaystyle\frac{15}{10} + \frac{45}{30} = 3.\] Отношение \(\displaystyle \frac BA\) равно \(\displaystyle \frac {45}{15}\) и равно 3.

Пример программы-решения

Ниже представлено решение на языке C++.

C++

#include<bits/stdc++.h>
using namespace std;
int main() {
    int X, Y, k;
    cin >> X >> Y >> k;
    int rat= (X * k - Y) / (Y * k - X);
    cout << rat << endl;
}

Задача 1.3.(20 баллов)

Круглая география

Имя входного файла: стандартный ввод или input.txt.

Имя выходного файла: стандартный вывод или output.txt.

Ограничение по времени выполнения программы: 1 с.

Ограничение по памяти: 128 Мбайт.

Условие

Чего только ни встретишь в глубинах космоса! Есть, например, удивительная планета, покрытая океаном. В этом океане встречаются острова. Они имеют форму абсолютно правильного круга. Внутри этих островов могут быть озера. Они тоже имеют форму круга. Внутри этих озер могут быть свои острова. И верно, они тоже имеют форму круга. Внутри этих островов... Ну, вы поняли.

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

Формат входных данных

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

В первой строке ввода задано одно натуральное число \(n\) — количество окружностей, \(1 \leqslant n \leqslant 1000\). Далее в \(n\) строках заданы по три целых числа \(x,~y,~R\) через пробел — описание очередной окружности. Числа \(x\) и \(y\) задают координаты центра (\(-100 \leqslant x,~y \leqslant 100\)), а \(R\) — радиус окружности (\(1 \leqslant R \leqslant 100\)).

Гарантируется, что никакие две окружности на входе не пересекаются и не касаются.

Формат выходных данных

Вывести в ответ \(n\) строк. Для каждой окружности на входе в соответствующую строку вывести либо слово Island, если она является островом, либо Lake, если она является озером. Порядок вывода должен совпадать с порядком окружностей на входе.

Примечания

Рис. 1.1.

На рис. 1.1 представлена карта для примера из условия. Синим обозначены водные пространства, коричневым — острова.

Тестовые данные

Номер теста	Стандартный ввод	Стандартный вывод
1	26 -6 7 4 -7 8 1 -5 5 1 -4 8 1 -5 -3 5 -6 -3 3 3 12 1 16 11 2 9 0 9 9 6 2 4 1 3 3 0 1 5 2 1 11 -4 4 12 -4 2 12 -4 1 28 3 10 23 5 4 23 5 2 23 5 1 24 -3 2 30 9 3 32 1 5 30 4 1 32 0 2 32 0 3	Island Lake Lake Lake Island Lake Island Island Island Lake Lake Island Island Lake Island Lake Island Lake Island Lake Lake Lake Lake Island Lake Island

Номер теста

Стандартный ввод

Стандартный вывод

Island
Lake
Lake
Lake
Island
Lake
Island
Island
Island
Lake
Lake
Island
Island
Lake
Island
Lake
Island
Lake
Island
Lake
Lake
Lake
Lake
Island
Lake
Island

Пример программы-решения

Ниже представлено решение на языке C++.

C++

#include<bits/stdc++.h>
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define x first
#define y second
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int INF = 1e18;
const int MOD = 1e9 + 7;
const int LG = 19;


struct circ{
    pair<double, double> c;
    double R;
};


double dist(pair<double, double> a, pair<double, double> b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}




bool inside(circ inc, circ outc){
    return (dist(inc.c, outc.c) + inc.R < outc.R);
}


signed main(){
    int n;
    cin >> n;
    vector<circ> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i].c.x >> v[i].c.y >> v[i].R;
    }
    vi mask(n, 0);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i != j && inside(v[i], v[j])){
                mask[i]++;
            }
        }
    }
    for(int i = 0; i < n; i++){
       cout << ((mask[i] % 2)?  "Lake\n" : "Island\n");
    }
}

Задача 1.4.(25 баллов)

Мэллори подменяет сообщение

Имя входного файла: стандартный ввод или input.txt.

Имя выходного файла: стандартный вывод или output.txt.

Ограничение по времени выполнения программы: 1 с.

Ограничение по памяти: 64 Мбайт.

Условие

Алиса посылает Бобу сообщение, которое состоит из \(n\) положительных целых чисел. Активная злоумышленница Мэллори пытается нарушить целостность сообщения. Она перехватывает эти посылаемые числа и по очереди заменяет их на другие, после чего посылает эти искаженные числа Бобу.

Мэллори не может менять полученные числа произвольным образом. Ее алгоритм построения искаженных чисел следующий: исходно у нее было число \(t_0 = 0\). Перехватив очередное число Алисы \(a_i\), Мэллори берет имеющееся у себя на данный момент число \(t_{i-1}\) и формирует из него новое число \(t_i\) либо как \(t_i = a_i + t_{i-1}\) — этот вариант изменения доступен всегда, либо как \(t_i = a_i - t_{i-1}\), такой вариант доступен, если \(a_i > t_{i-1}\), то есть получающееся в итоге число является положительным и не противоречит характеру посылаемых чисел. После этого Мэллори пересылает полученное число \(t_i\) Бобу и использует новое \(t_i\) для следующей подмены.

Если вариант замены единственный (\(t_{i-1} \geqslant a_i\)), то Мэллори делает замену \(t_i = a_i + t_{i-1}\) без вариантов. Если же возможны оба варианта замены, то Мэллори поступает случайным образом, и на выходе может получиться как \(t_i = a_i + t_{i-1}\), так и \(t_i = a_i - t_{i-1}\). При этом известно, что вариант подмены с вычитанием Мэллори сделает ровно \(k\) раз из \(n\).

Получив вместо последовательности \(a_1,a_2,\ldots, a_n\) последовательность \(t_1,t_2,\ldots,t_n\), и, зная все проделки Мэллори, Боб хочет понять объем работы по восстановлению правильного сообщения. По заданному числу \(k\) и последовательности \(t_i\) он просит вывести сумму всех возможных последовательностей, которые потенциально могла бы исходно выслать ему Алиса. Если нет ни одного сообщения, из которого могла бы получиться последовательность \(t_i\), вывести \(0\).

Так как ответ может оказаться очень большим, нужно вывести его остаток от деления на число \(10^9 + 7\).

Формат входных данных

В первой строке содержатся два целых числа \(n\) и \(k\) через пробел, \(1 \leqslant n \leqslant 1000\), \(0 \leqslant k \leqslant n\).

Во второй строке содержатся \(n\) целых чисел \(t_i\) через пробел, \(1 \leqslant t_i \leqslant 10^5\).

Формат выходных данных

Вывести одно число — сумму всех возможных последовательностей, которые могла бы потенциально послать Алиса таких, что применив к каждой из них некоторым образом свой алгоритм подмены, Мэллори получит последовательность \(t_i\), причем вычитание в каждом из этих вариантов она произведет ровно \(k\) раз.

Тестовые данные

Номер теста	Стандартный ввод	Стандартный вывод
1	5 3 2 5 8 7 12	252
2	5 0 2 5 8 7 12	0
3	5 1 2 5 8 7 12	28

Примечания

Рассмотрим первый пример: \(n = 5\), \(k = 3\). Существует ровно шесть последовательностей, которые исходно могла бы подготовить Алиса для пересылки таких, что, применив к каждой из них некоторым образом алгоритм подмены, Мэллори получит \(2, 5, 8, 7, 12\). Приведем все эти последовательности:

\(2, 7, 3, 15, 5~(2 - 0 = 2,~7 - 2 = 5,~3 + 5 = 8,~15 - 8 = 7,~5 + 7 = 12)\);
\(2, 3, 13, 15, 5~(2 - 0 = 2,~3 + 2 = 5,~13 - 5 = 8,~15 - 8 = 7,~5 + 7 = 12)\);
\(2, 3, 3, 15, 19~(2 - 0 = 2,~3 + 2 = 5,~3 + 5 = 8,~15 - 8 = 7,~19 - 7 = 12)\);
\(2, 7, 3, 15, 19~(2 + 0 = 2,~7 - 2 = 5,~3 + 5 = 8,~15 - 8 = 7,~19 - 7 = 12\));
\(2, 7, 13, 15, 5~(2 + 0 = 2,~7 - 2 = 5,~13 - 5 = 8,~15 - 8 = 7,~5 + 7 = 12)\);
\(2, 3, 13, 15, 19~(2 + 0 = 2,~3 + 2 = 5,~13 - 5 = 8,~15 - 8 = 7,~19 - 7 = 12)\).

В каждом случае для достижения последовательности \(t_i\) в исходной последовательности Мэллори производит ровно три вычитания. Можно видеть, что сумма всех чисел во всех этих последовательностях равна 252.

Во втором примере \(k = 0\). Можно показать, что Алиса не может сгенерировать ни одной последовательности, из которой можно получить заданную последовательность \(t_i\), ни разу не использовав подмены с вычитанием. Таким образом, ответ равен \(0\).

Пример программы-решения

Ниже представлено решение на языке C++.

C++

#include<bits/stdc++.h>
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define x first
#define y second
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
const int INF = 1e18;
const int MOD = 1e9 + 7;
const int LG = 19;

signed main(){
       ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    vi v(n + 1, 0);
    for1(i, n){
        cin >> v[i];
    }
    vi add(n + 1, -1), subs(n + 1, 0);
    for1(i, n){
        if(v[i] > v[i - 1]){
            add[i] = v[i] - v[i - 1];
        }
        subs[i] = v[i] + v[i - 1];
    }
    vector<vector<pii> > dp(n + 1, vector<pii>(n + 1, {0, 0}));
    dp[0][0] = {0, 1};
    for1(j, n){
        for0(i, n + 1){
            if(i > 0){
       dp[i][j].x = (dp[i - 1][j - 1].x + (dp[i - 1][j - 1].y * subs[j]) % MOD) % MOD;
                dp[i][j].y = dp[i - 1][j - 1].y;
            }
            if(add[j] > 0){
           (dp[i][j].x += dp[i][j - 1].x + (dp[i][j - 1].y * add[j]) % MOD) %= MOD;
                (dp[i][j].y += dp[i][j - 1].y) %= MOD;
            }
        }
    }
    cout << dp[k][n].x << endl;
}

Задача 1.5.(30 баллов)

Обезьяна и Word

Имя входного файла: стандартный ввод или input.txt.

Имя выходного файла: стандартный вывод или output.txt.

Ограничение по времени выполнения программы: 1 с.

Ограничение по памяти: 128 Мбайт.

Условие

Одна обезьяна решила проверить известную гипотезу об обезьянах и печатных машинках. Так как на дворе был XXI век, обезьяна открыла Word и начала печатать в нем случайные слова. \(i\)-е по порядку слово она вставляла на \(p_i\)-ю позицию, после чего все ранее напечатанные слова, находящиеся в этой или более правой позиции, естественным образом сдвигались на длину этого слова правее. В итоге у обезьяны получился текст из одной строки, разбитой на слова, между которыми стояло ровно по одному пробелу. Знаков препинания, начальных и концевых пробелов в ее тексте не было. Все слова состояли из заглавных и прописных латинских букв.

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

Формат входных данных

В первой строке находится число \(n\) — количество слов, которые напечатала обезьяна, \(1 \leqslant n \leqslant 10^5\).

В следующих \(n\) строках находятся по одному слову \(w_i\) и одному числу \(pos_i\) через пробел. Это означает, что обезьяна вставила слово \(w_i\) так, что оно стало на позицию \(pos_i\), при этом все ранее напечатанные слова, имеющие такую или большую позицию, сместились на длину этого слова и одного пробела вправо. Слово \(w_i\) состоит из заглавных и прописных латинских букв и имеет длину не более 9. Позиция \(pos_i\), куда его вставила обезьяна, находится в пределах от \(1\) до \(i\).

Формат выходных данных

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

Тестовые данные

Номер теста	Стандартный ввод	Стандартный вывод
1	5 Tolstoy 1 Peace 2 and 2 Leo 1 War 3	Leo Tolstoy War and Peace
2	7 a 1 bb 1 ccc 1 dddd 1 eeeee 1 ffffff 1 ggggggg 1	ggggggg ffffff eeeee dddd ccc bb a

Пример программы-решения

Ниже представлено решение на языке C++.

C++

#include<bits/stdc++.h>
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define x first
#define y second
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int INF = 1e18 + 1;
const int MOD = 1e9 + 7;
const int LG = 19;
const int N = (1 << LG);

vi tr(2 * N, 1);
vi res(N, 0);
void build(){
    for(int i = N - 1; i >= 0; i--){
        tr[i] = tr[2 * i] + tr[2 * i + 1];
    }
}

void push(int t, int a, int cpos){
    if(t >= N){
        res[t - N] = a;
        return;
    }

    if(cpos <= tr[2 * t]){
        tr[2 * t]--;
        push(2 * t, a, cpos);
    }
    else{
        tr[2 * t + 1]--;
        push(2 * t + 1, a, cpos - tr[2 * t]);
    }
}
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<string> v(n);
    vi pos(n);
    for0(i, n){
        cin >> v[i] >> pos[i];
    }
    build();
    for(int i = n - 1; i >= 0; i--){
        push(1, i, pos[i]);
    }
    for0(i, n - 1){
        cout << v[res[i]]<< ' ';
    }
    cout << v[res[n - 1]];
    cout << endl;
}