И опять «низкая» таблица

12/07/2018 by Кирилл Волков

Задача

В тридевятом государстве новое соревнование. Организаторы поняли, что предыдущая задача «Низкая таблица» была слишком простой и решили усложнить жизнь нашей Аленушке. Она совсем растерялась и снова умоляет Вас о помощи. Итак, вот новое условие: каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, состоящую из $n$ строк и $n$ столбцов. В каждой строке и столбце выбрано по одной ячейке, для которой указана минимальная площадь, которую должна занимать эта ячейка — $S_i$ для ячейки, расположенной в $i$-ой строке. Остальные могут иметь площадь $0.$ Задача участников аналогична предыдущей — начертить таблицу наименьшей высоты.

Входные данные

В первой строке содержится единственное натуральное число $n \leqslant 20.$
Во второй строке содержатся $n$ натуральных чисел $S_{1}, \ldots, S_{n}$, не превышающие $10^{4}.$

Выходные данные

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

Тесты

Входные данные	Выходные данные
3 1 2 3	17191
19 2899 338 8846 5896 3325 9199 6493 211 7878 6083 2074 8493 2889 3743 133 5725 9453 7890 3594	1548340398
18 3823 5708 1356 9979 8801 5310 2123 4575 566 5039 9367 26 1966 6540 1514 7193 7667 994	1252560358
8 8283 8769 3568 869 8285 4494 7185 4519	340953967
9 6375 3059 6206 4221 6027 2064 6278 1347 996	301905233
17 2765 8226 4472 1139 9080 675 3712 7735 9566 223 8899 9716 6594 9631 8871 6176 313	1414903854
10 2654 7458 2284 8767 6061 1149 7243 607 757 8532	385237635
6 6429 9121 9490 7035 6352 2021	231968881
8 52 6380 8169 5689 367 2403 3112 2850	185108459
2 8063 3128	21235115
9 9226 7811 4279 68 5976 1418 9721 6784 8580	418145363
13 8987 3714 247 679 1416 3489 1501 7654 2164 9101 7347 4043 3289	591377417
18 9349 9854 4308 1799 1501 8647 6300 9379 1123 7369 1164 3083 1207 2754 2933 1051 8566 4016	1324052855
3 1311 2984 9564	35581065
16 3460 6135 8911 5656 5496 5463 9566 8473 7575 7444 2717 8241 9868 6698 849 7118	1576424119
15 2264 4988 4454 726 17 9279 422 7916 698 5780 2517 9352 6291 2954 4775	763779068
10 3625 7189 773 7283 2952 7865 588 1670 1013 2982	305484098
18 2741 2630 4163 4926 9431 2212 6978 1607 9489 6746 4947 3333 3144 4809 3352 207 1919 1918	1207862952
5 4320 8413 1175 4527 1519	88794894
6 9534 5380 2500 683 4281 4803	145815522
14 1458 1341 6248 8840 8877 6891 409 5853 6726 6401 4932 9007 5710 745	905996755

Код программы

#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

int main(){
    int n;
    cin >> n;
    double sqrtOfHeight = 0;
    for(int i = 0; i < n; i++){
        int square;
        cin >> square;
        sqrtOfHeight +=  sqrt(square);
    }
    cout << (unsigned long long) (1000 * sqrtOfHeight * sqrtOfHeight);
    return 0;
}

#include <iostream>

#include <cmath>

#include <climits>

using namespace std;

int main(){

int n;

cin >> n;

double sqrtOfHeight = 0;

for(int i = 0; i < n; i++){

int square;

cin >> square;

sqrtOfHeight += sqrt(square);

}

cout << (unsigned long long) (1000 * sqrtOfHeight * sqrtOfHeight);

return 0;

}

Решение задачи

Поменяем местами строки таблицы так, чтобы ячейки, для которых указана минимальная площадь, лежали на главной диагонали. От этого не изменится ни ширина, ни высота таблицы. Обозначим эти ячейки $S_{ii}$ для ячейки, лежащей на пересечении $i$-ой строки и $i$-ого столбца.
Докажем, что минимальная площадь указанной в условии таблицы $S = \left (\sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{nn}} \right )^2.$ Воспользуемся методом математической индукции.
База индукции. Случай при $n=2$ был доказан здесь.
Предположение индукции. Пусть утверждение верно $\forall n \leq k, \ k \geq 2.$
Шаг индукции. Докажем, что утверждение верно для $n = k+1.$ Рассмотрим подтаблицу $T_1$ нашей таблицы $T$, которая состоит из первых $k$ столбцов и $k$ строк исходной таблицы. По предположени индукции ее минимальная площадь $S_{T_1} = \left (\sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{kk}} \right )^2.$ Теперь можем рассматривать таблицу $T$ как таблицу, состоящую из двух строк и двух столбцов, так, что таблица $T_1$ будет верхней левой ячейкой. Тогда, учитывая утверждение, доказанное в базе индукции находим минимальную площать таблицы $T$ $$\begin{multline}S_{T} = \left (\sqrt{S_{T_1}}+\sqrt{S_{k+1k+1}} \right ) ^ 2 = \\ = \left (\sqrt{\left (\sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{kk}} \right )^2}+\sqrt{S_{k+1k+1}} \right ) ^ 2 = \\ = \left ( \sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{kk}}+\sqrt{S_{k+1k+1}}\right )^2.\end{multline}$$ Что и требовалось доказать. Заметим, что для тривиального случая $n = 1$ формула также остается в силе. Пусть $h$ высота таблицы, а $l$ — ее ширина. Учитывая, что по условию $l = 1,$ а $S = hl,$ находим, что минимальное значение высоты таблицы $h_{min} = \left ( \sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{nn}}\right )^2.$

Ссылки

Код решения на Ideone

Related Images:

«Низкая» таблица

11/07/2018 by Кирилл Волков

Задача

В тридевятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, состоящую из двух столбцов и двух строк. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Известно, что для правой верхней и левой нижней ячейки это значение равно $0.$ Но вот незадача: значения минимальных площадей для левой верхней — $S_{11}$ и правой нижней — $S_{22}$ ячеек могут быть какими угодно (в пределах разумного, конечно, хотя кто их этих сказочных персонажей разберет). Задача участников — начертить таблицу наименьшей высоты. Аленушка очень хочет победить, но она плохо знает математику, поэтому просит Вас помочь ей в этом непростом деле.

Входные данные

В единственной строке содержатся два натуральных числа: $S_{11}, \ S_{22},$ не превышающие $10^{14}.$

Выходные данные

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

Тесты

Входные данные	Выходные данные
1 2	5828
466 1194	3151849
8067 2659	19988861
5125 6755	23647646
3317 2652	11900840
25 9293	10282002
7081 7189	10282002
8192 1042	15077308
6795 1568	14891264
680 4510	8692456
9107 4760	27035040
7095 7846	29863113
6142 3794	19590583
9347 3639	24650258
8495 5394	27427394
2179 8718	19613999
1187 778	3886963
71 5592	6923209
100000000000000 100000000000000	400000000000000000

Код программы

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    unsigned long long s1;
    unsigned long long s2;
    cin >> s1 >> s2;
    double sqrtOfHeight = sqrt(s1) + sqrt(s2);
    cout << (unsigned long long) (1000 * sqrtOfHeight * sqrtOfHeight);
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

unsigned long long s1;

unsigned long long s2;

cin >> s1 >> s2;

double sqrtOfHeight = sqrt(s1) + sqrt(s2);

cout << (unsigned long long) (1000 * sqrtOfHeight * sqrtOfHeight);

}

Решение задачи

Пусть $h$ и $l$ — высота и ширина таблицы соответственно. Тогда ее площадь $S=hl.$ В силу того, что $l=1,$ задача о нахождении минимальной высоты таблицы сводится к нахождению ее минимальной площади. Обозначим высоту $i$-ой строки $h_i$, ширину $j$-го столбца $l_j$, а площадь ячейки таблицы, находящейся на пересечении $i$-ой строки и $j$-го столбца — $S_{ij}.$ Тогда $$\begin{multline}S = S_{11} +S_{12}+S_{21}+S_{22}=S_{11}+l_2 h_1+l_1 h_2+S_{22}= \\ =S_{11}+S_{11} \frac{l_2}{l_1} +S_{22} \frac{l_1}{l_2}+S_{22} = S_{11}+S_{11} y+S_{22} y^{-1}+S_{22},\end{multline}$$ где $y=\frac{l_2}{l_1}.$ Зафиксируем теперь $S_{11}$ и $S_{22}$ и рассмотрим функцию площади $S \left( y \right ) = S_{11}+S_{11} y+S_{22} y^{-1}+S_{22}.$ Найдем наименьшее значение данной функции. $\frac{\mathrm{d} S \left( y \right )}{\mathrm{d} y} = S_{11}-\frac{S_{22}}{y^{2}}.$ Приравнивая производную функции к нулю, находим, что функция имеет единственную стационарную точку $y_{0} = \sqrt{\frac{S_{22}}{S_{11}}}.$ Легко убедиться, что $y_0$ – точка глобального минимума, тогда $\min\limits_{y \in D\left(S\right)}S\left( y \right ) = S \left(y_0\right) = S_{11} + S_{22} + 2 \cdot \sqrt{S_{11} \cdot S_{22}} = \left( \sqrt{S_{11}} + \sqrt{S_{22}} \right )^2.$ Очевидно теперь, что минимальное значение площадь таблицы будет принимать при $S_{11}={S_{11}}’, \ S_{22}={S_{22}}’$ где ${S_{11}}’, \ {S_{22}}’$ – данные в условии минимальные значения площадей соответствующих ячеек. Отсюда имеем минимальное значение высоты таблицы $h_{min}=\left( \sqrt{{S_{11}}’} + \sqrt{{S_{22}}’} \right )^2.$

Ссылки

Код решения на Ideone

Related Images:

e-olymp 5274. Фенечка

24/06/2018 by Кирилл Волков

Задача

Саша находится в процессе творческого поиска. Она хочет сплести ещё одну фенечку, но испытывает сложности при выборе цветов. Сейчас все $n$ ниток, которые она планирует использовать для плетения, выложены в ряд. В процессе размышления Саша время от времени заменяет нитку одного цвета ниткой другого, а также для проверки того, что узор получается тем, который подразумевается, проверяет, что некоторые последовательности цветов ниток равны.

Напишите программу, которая автоматизирует эти проверки.

Входные данные

В первой строке записаны два целых числа $n$ и $k$ — количество ниток в фенечке и запросов к программе, соответственно $(1 \leq n, k \leq 100000).$ Во второй строке записана строка из $n$ символов — цвета ниток в начальном состоянии. Каждый цвет обозначается строчной или прописной буквой латинского алфавита или цифрой. В следующих $k$ строках заданы запросы двух видов:

«* i c» — заменить нитку с номером $i$ на нитку цвета $c$,
«? i j len» — проверить, равны ли последовательности цветов ниток, начинающиеся в позициях $i$ и $j$ и имеющие длину $len$.

Выходные данные

Для каждого запроса второго вида выведите «+», если последовательности равны, или «-« в противном случае.

Тесты

Входные данные	Выходные данные
6 3 abccba ? 2 4 2 * 4 a ? 1 4 2	-+
7 4 abacaba ? 1 5 3 * 6 c ? 2 6 2 ? 3 5 3	+-+
8 3 atgthcta ? 2 4 3 * 8 h ? 4 7 2	-+
9 3 abbababba ? 1 6 4 * 2 c ? 1 6 4	+-

Код программы

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<unsigned long long> t;
vector<unsigned long long> codes;
const unsigned long long prime = 61;
vector<unsigned  long long> pows;

void build (int v, int tl, int tr) {
    if (tl == tr){
        t[v] = codes[tl] * pows[tl - 1];
    }
    else {
        int tm = (tl + tr) / 2;
        build (2 * v, tl, tm);
        build (2 * v + 1, tm + 1, tr);
        t[v] = t[2 * v] + t[2 * v + 1];
    }
}

unsigned long long sum (int v, int tl, int tr, int l, int r) {
    if (l > r){
        return 0;
    }
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return sum (2 * v, tl, tm, l, min(r, tm))
           + sum (2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}

void update (int v, int tl, int tr, int pos, unsigned long long newVal) {
    if (tl == tr)
        t[v] = newVal * pows[pos - 1];
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update (v*2, tl, tm, pos, newVal);
        else
            update (2 * v + 1, tm + 1, tr, pos, newVal);
        t[v] = t[2 * v] + t[2 * v + 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    t.resize(4 * n);
    string a;
    cin >> a;
    codes.resize(n + 1);
    for(int i = 1; i <= n; i++){
        codes[i] = a[i - 1] - 'A' + 1;
    }
    pows.resize(n + 1);
    pows[0] = 1;
    for(int i = 1; i <= n; i++){
        pows[i] = pows[i - 1] * prime;
    }
    build(1, 1, n);
    cin.ignore();
    for(int t = 0; t < k; t++){
        char q;
        cin >> q;
        if(q == '?'){
            int i, j, len;
            cin >> i >> j >>len;
            if(i > j){
                swap(i, j);
            }
            if(sum(1, 1, n, i, i + len - 1) * pows[j - i] == sum(1, 1, n, j, j + len - 1)){
                cout << "+";
            }
            else{
                cout << "-";
            }
        }
        else if(q == '*'){
            int temp;
            char c;
            cin >> temp >> c;
            update(1, 1, n, temp, c - 'A' + 1);
        }
        cin.ignore();
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector<unsigned long long> t;

vector<unsigned long long> codes;

const unsigned long long prime = 61;

vector<unsigned long long> pows;

void build (int v, int tl, int tr) {

if (tl == tr){

t[v] = codes[tl] * pows[tl - 1];

}

else {

int tm = (tl + tr) / 2;

build (2 * v, tl, tm);

build (2 * v + 1, tm + 1, tr);

t[v] = t[2 * v] + t[2 * v + 1];

}

unsigned long long sum (int v, int tl, int tr, int l, int r) {

if (l > r){

return 0;

}

if (l == tl && r == tr)

return t[v];

int tm = (tl + tr) / 2;

return sum (2 * v, tl, tm, l, min(r, tm))

+ sum (2 * v + 1, tm + 1, tr, max(l, tm + 1), r);

}

void update (int v, int tl, int tr, int pos, unsigned long long newVal) {

if (tl == tr)

t[v] = newVal * pows[pos - 1];

else {

int tm = (tl + tr) / 2;

if (pos <= tm)

update (v*2, tl, tm, pos, newVal);

else

update (2 * v + 1, tm + 1, tr, pos, newVal);

t[v] = t[2 * v] + t[2 * v + 1];

}

int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int n, k;

cin >> n >> k;

t.resize(4 * n);

string a;

cin >> a;

codes.resize(n + 1);

for(int i = 1; i <= n; i++){

codes[i] = a[i - 1] - 'A' + 1;

}

pows.resize(n + 1);

pows[0] = 1;

for(int i = 1; i <= n; i++){

pows[i] = pows[i - 1] * prime;

}

build(1, 1, n);

cin.ignore();

for(int t = 0; t < k; t++){

char q;

cin >> q;

if(q == '?'){

int i, j, len;

cin >> i >> j >>len;

if(i > j){

swap(i, j);

}

if(sum(1, 1, n, i, i + len - 1) * pows[j - i] == sum(1, 1, n, j, j + len - 1)){

cout << "+";

}

else{

cout << "-";

}

else if(q == '*'){

int temp;

char c;

cin >> temp >> c;

update(1, 1, n, temp, c - 'A' + 1);

}

cin.ignore();

}

return 0;

}

Решение задачи

Наивный алгоритм тратит на выполнение первого запроса $O\left(1\right)$ единиц времени, а на выполнение запросов второго типа — $O\left(n\right)$ единиц времени. Таким образом получаем ассиптотическую временную сложность $O\left(kn\right),$ из-за чего задача не проходит по времени.
Для сравнения строк будем использовать полиномиальный хеш, зависящий от $p$ (в нашем случае $p = 61$), при этом будем отождествлять равенство хешей по модулю $m$ (в нашем случае $m = 2^{64}$) и самих строк (при этом может случиться так, что хеши будут совпадать, а сами строки — нет, но вероятность достаточно мала и мы будем ею пренебрегать). Таким образом мы получаем возможность сравнивать строки за $O\left(1\right)$ единиц времени. Будем использовать для хранения текущего состояния строки (а точнее ее хеша) дерево отрезков, при этом на нижнем ярусе будем хранить хеши каждого отдельного символа строки с учетом его месторасположения в строке. Таким образом получим возможность выполнять запросы и первого, и второго типов за $O\left(\log{n}\right)$ единиц времени, при этом следует учесть, что хеши двух одинаковых подстрок будут отличаться в $p^{j-i} \mod m$ раз, где $i$ — меньший из индексов начала сравниваемых подстрок, $j$ — больший. Таким образом, получаем итоговую асимптотическую сложность алгоритма $O\left(k\log{n}\right)$

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

e-olymp 4000. Обход в глубину

05/06/2018 by Кирилл Волков

Задача

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

Входные данные

В первой строке содержится количество вершин графа $n$ и выделенная вершина $s$ $\left (1 \leq s \leq n \leq 100 \right).$ В следующих n строках записано по n чисел — матрица смежности графа, в котрой цифра «$0$» означает отсутствие ребра между вершинами, а цифра «$1$» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

Выходные данные

Выведите искомое количество вершин.

Тесты

Входные данные	Выходные данные
3 1 0 0 1 0 0 0 1 0 0	2
4 2 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0	4
6 2 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0	3
4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	1
5 3 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0	5

Код программы

#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>

using namespace std;

void dfs(int cur, vector<vector<int>> & adj, vector<bool> & was, int & count){
    if(!was[cur]){
        was[cur] = true;
        count++;
        for(int i = 0; i < adj[cur].size(); i++){
            dfs(adj[cur][i], adj, was, count);
        }
    }
}

int getCount(int start, vector<vector<int>> & adj){
    vector<bool> was(adj.size(), false);
    int count = 0;
    dfs(start, adj, was, count);
    return count;
}

int main() {
    int n;
    cin >> n;
    int start;
    cin >> start;
    start--;
    vector<vector<int>> adj(n, vector<int>());
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int temp;
            cin >> temp;
            if(temp == 1){
                adj[i].push_back(j);
            }
        }
    }
    cout << getCount(start, adj);
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

#include <vector>

using namespace std;

void dfs(int cur, vector<vector<int>> & adj, vector<bool> & was, int & count){

if(!was[cur]){

was[cur] = true;

count++;

for(int i = 0; i < adj[cur].size(); i++){

dfs(adj[cur][i], adj, was, count);

}

int getCount(int start, vector<vector<int>> & adj){

vector<bool> was(adj.size(), false);

int count = 0;

dfs(start, adj, was, count);

return count;

}

int main() {

int n;

cin >> n;

int start;

cin >> start;

start--;

vector<vector<int>> adj(n, vector<int>());

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

int temp;

cin >> temp;

if(temp == 1){

adj[i].push_back(j);

}

cout << getCount(start, adj);

return 0;

}

Решение задачи

Для хранения графа воспользуемся списками смежности. Реализуем стандартный поиск в глубину. Пусть $c$ количество вершин в компоненте графа. Изначально $c = 0.$ При посещении очередной, не посещенной ранее вершины, значение $c$ увеличивается на один. Таким образом, при полном обходе компоненты графа $c$ будет искомым числом.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

e-olymp 1225. Черный Ящик

18/05/2018 by Кирилл Волков

Задача

Черный Ящик представляет собой примитивную базу даных. Он может хранить массив целых чисел, а также имеет специальную переменную $i$. В начальный момент Черный Ящик пустой, переменная $i$ равна $0$. Черный Ящик обрабатывает последовательность команд (транзакций). Существует два типа транзакций:
ADD(x): добавить элемент x в Черный Ящик;
GET: увеличить $i$ на $1$ и вывести $i$-ый минимальный элемент среди всех чисел, находящихся в Черном Ящике.
Помните, что $i$-ый минимальный элемент находится на $i$-ом месте после того как все элементы Черного Ящика будут отсортированы в неубывающем порядке.
Рассмотрим работу черного ящика на примере:

№	Транзакция	$i$	Содержимое Черного Ящика после транзакции	Ответ
1	ADD(3)	0	3
2	GET	1	3	3
3	ADD(1)	1	1, 3
4	GET	2	1, 3	3
5	ADD(-4)	2	-4, 1, 3
6	ADD(2)	2	-4, 1, 2, 3
7	ADD(8)	2	-4, 1, 2, 3, 8
8	ADD(-1000)	2	-1000, -4, 1, 2, 3, 8
9	GET	3	-1000, -4, 1, 2, 3, 8	1
10	GET	4	-1000, -4, 1, 2, 3, 8	2
11	ADD(2)	4	-1000, -4, 1, 2, 2, 3, 8

Необходимо разработать эффективный алгоритм выполнения заданной последовательности транзакций. Максимальное количество транзакций ADD и GET равно $30000$ (каждого типа).
Опишем последовательность транзакций двумя целочисленными массивами:

$A_1, \ A_2, \ldots , \ A_m:$ последовательность элементов, которая будет добавляться в Черный Ящик. Элементами являются целые числа, по модулю не большие $2 000 000 000$, $m \leq 30000$. Для выше описанного примера $A = \left (3, 1, -4, 2, 8, -1000, 2 \right).$
$u_1, \ u_2, \ldots , \ u_n:$ последовательность указывает на количество элементов в Черном Ящике в момент выполнения первой, второй, … $n$-ой транзакции GET. Для выше описанного примера $u = \left (1, 2, 6, 6 \right ).$

Работа Черного Ящика предполагает, что числа в последовательности $u_1, \ u_2, \ldots , \ u_n$ отсортированы в неубывающем порядке, $n \leq m$, а для каждого $p \left (1 \leq p \leq n \right )$ имеет место неравенство $p \leq u(p) \leq m$. Это следует из того, что для $p$-го элемента последовательности $u$ мы выполняем GET транзакцию, которая выводит $p$-ый минимальный элемент из набора чисел $A_1, \ A_2, \ldots , \ A_{u_p}$.

Входные данные

Состоит из следующего набора чисел: $m, \ n, \ A_1, \ A_2, \ldots , \ A_m, \ u_1, \ u_2, \ldots , \ u_n.$ Все числа разделены пробелами и (или) символом перевода на новую строку.

Выходные данные

Вывести ответы Черного Ящика на последовательность выполненных транзакций. Каждое число должно выводиться в отдельной строке.

Тесты

Входные данные	Выходные данные
7 4 3 1 -4 2 8 -1000 2 1 2 6 6	3 3 1 2
8 3 5 8 3 7 3 5 7 0 2 3 3	5 5 8
10 4 6 3 7 3 8 4 7 4 6 15 4 6 8 9	3 3 4 4
5 5 1 2 3 4 5 1 2 3 4 5	1 2 3 4 5
11 5 4 6 8 9 5 3 6 8 10 12 13 6 7 8 9 10	3 4 5 6 6

Код программы

#include <iostream>
#include <vector>
#include <set>
#include <climits>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int m, n;
    cin >> m >> n;
    vector<int> nums(m);
    for(int i = 0; i < m; i++){
        cin >> nums[i];
    }
    multiset<int> blackBox;
    blackBox.insert(INT_MAX);
    auto it = blackBox.begin();
    for(int i = 0; i < n; i++){
        int req;
        cin >> req;
        for(int j = blackBox.size() - 1; j < req; j++){
            blackBox.insert(nums[j]);
            if(nums[j] < *it) it--;
        }
        cout << *it << endl;
        it++;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <set>

#include <climits>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int m, n;

cin >> m >> n;

vector<int> nums(m);

for(int i = 0; i < m; i++){

cin >> nums[i];

}

multiset<int> blackBox;

blackBox.insert(INT_MAX);

auto it = blackBox.begin();

for(int i = 0; i < n; i++){

int req;

cin >> req;

for(int j = blackBox.size() - 1; j < req; j++){

blackBox.insert(nums[j]);

if(nums[j] < *it) it--;

}

cout << *it << endl;

it++;

}

return 0;

}

Решение задачи

Пусть nums — множество всех элементов последовательности $A_n$. blackBox — мультимножество, представляющее собой описанный в задаче Черный Ящик на $i$-ом запросе. Изначально blackBox содержит «бесконечность» для избежания выхода за пределы. it — итератор, указывающий на $i$-ый минимальный элемент blackBox. Изначально данный итератор указывает на первый элемент множества. На $i$-ом запросе в blackBox копируются элементы массива nums от $u_{i-1}-1$-го до $u_{i}-1$-го (примем, что $u_0$ = 0). Тогда при добавлении в blackBox элемента, меньшего, чем тот, на который в данный момент указывает итератор it — $min_i$, $i$-ым минимальным элементом, становится элемент, предшествующий $min_i$. После выполнения ответа на $i$-ый запрос итератор должен указывать на $i+1$-ый минимальный элемент, то есть на элемент, следующий за $min_i$.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

e-olymp 440. Подделка чека

27/02/2018 by Кирилл Волков

Задача

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

Входные данные

Во входном файле в первой строке содержится одно целое положительное число не более чем из $100$ цифр.

Выходные данные

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

Тесты

Входные данные	Выходные данные
$123321$	$332121$
$7888778888878888788878878777887$	$8888878888788878887778878777887$
$1091$	$9100$
$26364$	$64263$
$98765$	$98765$

Код программы

String

#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;
    string maxS = s;
    int start = s.size() - 1;
    bool found = false;
    for(int i = 0; i < s.size() and !found; i++){
        for(int j = i; j < s.size() and !found; j++){
            if(s[j] > s[i]){
                start = i;
                found = true;
            }
        }
    }
    for(int j = start + 1; j < s.size(); j++){
        if(s[j] >= s[start]) {
            string curMax = s;
            for (int k = j; k < s.size(); k++) {
                curMax.insert(start + k - j, 1, s[k]);
                curMax.erase(k + 1, 1);
                maxS = max(curMax, maxS);
            }
        }
    }
    cout << maxS;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

string s;

cin >> s;

string maxS = s;

int start = s.size() - 1;

bool found = false;

for(int i = 0; i < s.size() and !found; i++){

for(int j = i; j < s.size() and !found; j++){

if(s[j] > s[i]){

start = i;

found = true;

}

for(int j = start + 1; j < s.size(); j++){

if(s[j] >= s[start]) {

string curMax = s;

for (int k = j; k < s.size(); k++) {

curMax.insert(start + k - j, 1, s[k]);

curMax.erase(k + 1, 1);

maxS = max(curMax, maxS);

}

cout << maxS;

return 0;

}

C-String

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_LENGTH = 101;

int main() {
    char s[MAX_LENGTH];
    cin >> s;
    char maxS[MAX_LENGTH];
    strcpy(maxS, s);
    int size = strlen(s);
    int start = size - 1;
    bool found = false;
    for(int i = 0; i < size and !found; i++){
        for(int j = i; j < size and !found; j++){
            if(s[j] > s[i]){
                start = i;
                found = true;
            }
        }
    }
    for(int j = start + 1; j < size; j++){
        if(s[j] >= s[start]) {
            char curMax[MAX_LENGTH];
            strcpy(curMax, s);
            for (int k = j; k < size; k++) {
                char temp = s[k];
                for(int i = k; i >  start + k - j; i--){
                    curMax[i] = curMax[i - 1];
                }
                curMax[start + k - j] = temp;
                if(strncmp(curMax, maxS, size) > 0){
                    strcpy(maxS, curMax);
                }
            }
        }
    }
    cout << maxS;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

const int MAX_LENGTH = 101;

int main() {

char s[MAX_LENGTH];

cin >> s;

char maxS[MAX_LENGTH];

strcpy(maxS, s);

int size = strlen(s);

int start = size - 1;

bool found = false;

for(int i = 0; i < size and !found; i++){

for(int j = i; j < size and !found; j++){

if(s[j] > s[i]){

start = i;

found = true;

}

for(int j = start + 1; j < size; j++){

if(s[j] >= s[start]) {

char curMax[MAX_LENGTH];

strcpy(curMax, s);

for (int k = j; k < size; k++) {

char temp = s[k];

for(int i = k; i > start + k - j; i--){

curMax[i] = curMax[i - 1];

}

curMax[start + k - j] = temp;

if(strncmp(curMax, maxS, size) > 0){

strcpy(maxS, curMax);

}

cout << maxS;

return 0;

}

Решение задачи

Пусть заданы два числа: $a = \overline{a_1a_2 \ldots a_k},\ b = \overline{b_1b_2 \ldots b_k}$. Тогда $a > b \Leftrightarrow \exists i: \ \forall j < i \ a_j = b_j \ \wedge \ a_i = b_i$. Отсюда получаем необходимое условие получения максимального числа при перестановке в записи числа $a$ групп цифр $\overline{a_ia_{i+1} \ldots a_l}$ и $\overline{a_ja_{j+1} \ldots a_m} \ l<j$ местами: $i = \min_{1 < s < k} s: \ \exists t>s: \ a_t \gt a_s$. Если такое $i$ существует, то далее мы делаем перебор по всем возможным перестановкам, таким что первая группа чисел начинается с индекса $i$ и таким образом находим максимально возможное число. В противном случае данное число уже является максимальным.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp. String
Решение на e-olymp. C-String
Код решения на Ideone. String
Код решения на Ideone. C-String

Related Images:

e-olymp 88. Месть Ли Чака

04/02/2018 by Кирилл Волков

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

Входные данные

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

Выходные данные

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

Код программы

#include <iostream>
#include <vector>

using  namespace std;

const int INF = 10000000;
const string GAYBRASH = "GAYBRASH";
const string LICHACK = "LICHACK";

struct node{
    int x;
    int y;
};

vector<node> getChildrenBFS(char ** map, node parent, string hero){
    string bannedChars = "R";
    if(hero == LICHACK) bannedChars.push_back('e');
    vector<node> children;
    node leftChild = {parent.x - 1, parent.y};
    node rightChild = {parent.x + 1, parent.y};
    node downChild = {parent.x, parent.y + 1};
    node upChild = {parent.x, parent.y - 1};
    if(bannedChars.find(map[leftChild.y][leftChild.x]) == string::npos){
        children.push_back(leftChild);
    }
    if(bannedChars.find(map[rightChild.y][rightChild.x]) == string::npos){
        children.push_back(rightChild);
    }
    if(bannedChars.find(map[downChild.y][downChild.x]) == string::npos){
        children.push_back(downChild);
    }
    if(bannedChars.find(map[upChild.y][upChild.x]) == string::npos){
        children.push_back(upChild);
    }
    return children;
}

void dfsSecondPlayer(char ** map, int ** moves, string hero, node currentNode, int move){
    moves[currentNode.y][currentNode.x] = move;
    move++;
    vector<node> children = getChildrenBFS(map, currentNode, hero);
    vector<node> queue;
    for(auto e: children) {
        if (move < moves[e.y][e.x]) {
            dfsSecondPlayer(map, moves, hero, e, move);
        }
    }
}
void dfsFirstPlayer(char ** map, int ** moves, int ** secondPlayer, string hero, node currentNode, int move){
    moves[currentNode.y][currentNode.x] = move;
    move++;
    vector<node> children = getChildrenBFS(map, currentNode, hero);
    vector<node> queue;
    for(auto e: children){
        if(move < moves[e.y][e.x] && move < secondPlayer[e.y][e.x]){
            dfsFirstPlayer(map, moves, secondPlayer, hero, e, move);
        }
    }
}
int main() {
    int tests;
    cin >> tests;
    for(; tests > 0; tests--){
        int m;
        int n;
        cin >> m >> n;
        cin.ignore();
        node g;
        node l;
        node e;
        char **map = new char*[m];
        for(int i = 0; i < m; i++){
            map[i] = new char[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                map[i][j] = cin.get();
                switch(map[i][j]){
                    case 'g':
                        g.x = j;
                        g.y = i;
                        break;
                    case 'l':
                        l.x = j;
                        l.y = i;
                        break;
                    case 'e':
                        e.x = j;
                        e.y = i;
                        break;
                }
            }
            cin.ignore();
        }
        int **liChack = new int*[m];
        for(int i = 0; i < m; i++){
            liChack[i] = new int[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                liChack[i][j] = INF;
            }
        }
        dfsSecondPlayer(map, liChack, LICHACK, l, 0);
        int **gaybrash = new int*[m];
        for(int i = 0; i < m; i++){
            gaybrash[i] = new int[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                gaybrash[i][j] = INF;
            }
        }
        dfsFirstPlayer(map, gaybrash, liChack, GAYBRASH, g, 0);
        bool OK = gaybrash[e.y][e.x] != INF;
        cout << (OK ? "YES" : "NO") << endl;
        for(int i = 0; i < m; i++){
            delete[] map[i];
        }
        delete[] map;
        for(int i = 0; i < m; i++){
            delete[] gaybrash[i];
        }
        delete[] gaybrash;
        for(int i = 0; i < m; i++){
            delete[] liChack[i];
        }
        delete[] liChack;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

#include <iostream>

#include <vector>

using namespace std;

const int INF = 10000000;

const string GAYBRASH = "GAYBRASH";

const string LICHACK = "LICHACK";

struct node{

int x;

int y;

};

vector<node> getChildrenBFS(char ** map, node parent, string hero){

string bannedChars = "R";

if(hero == LICHACK) bannedChars.push_back('e');

vector<node> children;

node leftChild = {parent.x - 1, parent.y};

node rightChild = {parent.x + 1, parent.y};

node downChild = {parent.x, parent.y + 1};

node upChild = {parent.x, parent.y - 1};

if(bannedChars.find(map[leftChild.y][leftChild.x]) == string::npos){

children.push_back(leftChild);

}

if(bannedChars.find(map[rightChild.y][rightChild.x]) == string::npos){

children.push_back(rightChild);

}

if(bannedChars.find(map[downChild.y][downChild.x]) == string::npos){

children.push_back(downChild);

}

if(bannedChars.find(map[upChild.y][upChild.x]) == string::npos){

children.push_back(upChild);

}

return children;

}

void dfsSecondPlayer(char ** map, int ** moves, string hero, node currentNode, int move){

moves[currentNode.y][currentNode.x] = move;

move++;

vector<node> children = getChildrenBFS(map, currentNode, hero);

vector<node> queue;

for(auto e: children) {

if (move < moves[e.y][e.x]) {

dfsSecondPlayer(map, moves, hero, e, move);

}

void dfsFirstPlayer(char ** map, int ** moves, int ** secondPlayer, string hero, node currentNode, int move){

moves[currentNode.y][currentNode.x] = move;

move++;

vector<node> children = getChildrenBFS(map, currentNode, hero);

vector<node> queue;

for(auto e: children){

if(move < moves[e.y][e.x] && move < secondPlayer[e.y][e.x]){

dfsFirstPlayer(map, moves, secondPlayer, hero, e, move);

}

int main() {

int tests;

cin >> tests;

for(; tests > 0; tests--){

int m;

int n;

cin >> m >> n;

cin.ignore();

node g;

node l;

node e;

char **map = new char*[m];

for(int i = 0; i < m; i++){

map[i] = new char[n];

}

for(int i = 0; i < m; i++){

for(int j = 0; j < n; j++){

map[i][j] = cin.get();

switch(map[i][j]){

case 'g':

g.x = j;

g.y = i;

break;

case 'l':

l.x = j;

l.y = i;

break;

case 'e':

e.x = j;

e.y = i;

break;

}

cin.ignore();

}

int **liChack = new int*[m];

for(int i = 0; i < m; i++){

liChack[i] = new int[n];

}

for(int i = 0; i < m; i++){

for(int j = 0; j < n; j++){

liChack[i][j] = INF;

}

dfsSecondPlayer(map, liChack, LICHACK, l, 0);

int **gaybrash = new int*[m];

for(int i = 0; i < m; i++){

gaybrash[i] = new int[n];

}

for(int i = 0; i < m; i++){

for(int j = 0; j < n; j++){

gaybrash[i][j] = INF;

}

dfsFirstPlayer(map, gaybrash, liChack, GAYBRASH, g, 0);

bool OK = gaybrash[e.y][e.x] != INF;

cout << (OK ? "YES" : "NO") << endl;

for(int i = 0; i < m; i++){

delete[] map[i];

}

delete[] map;

for(int i = 0; i < m; i++){

delete[] gaybrash[i];

}

delete[] gaybrash;

for(int i = 0; i < m; i++){

delete[] liChack[i];

}

delete[] liChack;

}

return 0;

}

Решение задачи

Предположим, что существует безопасный для Гайбраша маршрут. Это означает, что Ли Чак не может перехватить его ни в одной точке этого маршрута, то есть, что в любую точку маршрута Гайбраш попадает как минимум на один ход раньше, чем Ли Чак. В противном случае безопасного хода нет.
Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. С помощью поиска в глубину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в глубину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае -нет.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

e-olymp 480. Возведение в степень — 2

22/12/2017 by Кирилл Волков

Задача

Для заданных $A$, $B$ и $M$ вычислить $A^B \mod M$.

Входные данные

Во входном файле даны три натуральных числа $A$, $B$, $M$ $(1 ≤ A, \, B ≤ 10^{18}, \, 2 ≤ M ≤ 2 \cdot 10^9)$, записанные в одной строке через пробел.

Выходные данные

В выходной файл выведите одно число, равное $A^B \mod M$.

Тесты

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

Код программы

#include <iostream>
#include 
#include 
using namespace std;

long long modPow(long long base, long long exponent, long long mod){
    base %= mod;
    long long pow;
    if(exponent == 0){
        pow = 1;
    }
    else if(exponent % 2 == 0){
        pow = modPow(base * base, exponent / 2, mod) % mod;
    }
    else{
        pow = (base * modPow(base, exponent - 1, mod)) % mod;
    }
    return pow;
}

int main(){
    long long a, b, m;
    cin >> a >> b >> m;
    cout << modPow(a, b, m);
    return 0;
}

#include <iostream>

#include

using namespace std;

long long modPow(long long base, long long exponent, long long mod){

base %= mod;

long long pow;

if(exponent == 0){

pow = 1;

}

else if(exponent % 2 == 0){

pow = modPow(base * base, exponent / 2, mod) % mod;

}

else{

pow = (base * modPow(base, exponent - 1, mod)) % mod;

}

return pow;

}

int main(){

long long a, b, m;

cin >> a >> b >> m;

cout << modPow(a, b, m);

return 0;

}

Решение задачи

По свойствам операций со сравнениями по модулю:
$$C \equiv C \mod K \pmod K$$
$$CD \equiv (C \mod K) \cdot (D \mod K) \pmod K$$
$$C \equiv D \pmod K \Rightarrow C^n \equiv D^n \pmod K$$
Отсюда выводим рекуррентную формулу бинарного возведения в степень по модулю:
$$
A^B \mod M =
\begin{cases}
1 \text{ при } B = 0\\
\left ( \left (A \mod M \right ) \left ( (A \mod M)^{B-1} \mod M \right )\right )\mod M \\ \text{ при } B \equiv 1 \pmod 2\\
\left ( \left (A \mod M \right)^2 \right)^{\frac{B}{2}} \mod M \text{ при } B \equiv 0 \pmod 2 \wedge B \neq 0
\end{cases}
$$

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

e-olymp 61. Уборка снега

13/12/2017 by Кирилл Волков

Задача

Зимой, когда дни стают короче, а ночи длиннее, необходимо задуматься об уборке снега с улиц. Поскольку бюджет нашего города очень маленький, у нас в распоряжении только один снегоход. Несмотря на это дороги должны быть прочищены. И каждый раз, когда выпадает много снега, ночью снегоход нашего города выезжает со своего гаража и объезжает весь город, очищая дороги. Какое минимальное время нужно снегоходу, чтобы очистить все проезжие полосы всех дорог и вернуться назад?

При этом известно, что:

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

Входные данные

Первая строка содержит два числа $x$ и $y$ $(-30000 ≤ x, y ≤ 30000)$ — координаты ангара (в метрах), откуда начинает свое движение снегоход. Далее в каждой отдельной строке заданы координаты (в метрах) начала и конца улиц (по $4$ числа в строке). В городе может быть до $100$ улиц.

Выходные данные

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

Тесты

Входные данные	Выходные данные
$0$ $0$ $0$ $0$ $-1000$ $2000$ $0$ $0$ $1000$ $2000$	$0:27$
$0$ $1000$ $0$ $0$ $0$ $3000$ $0$ $0$ $1000$ $1000$ $0$ $0$ $3000$ $0$ $3000$ $0$ $3000$ $3000$ $3000$ $3000$ $0$ $3000$ $0$ $3000$ $1000$ $2000$ $3000$ $0$ $2000$ $1000$ $3000$ $3000$ $2000$ $2000$	$1:46$
$-500$ $0$ $-1000$ $0$ $0$ $0$ $0$ $0$ $1000$ $0$ $-1000$ $1000$ $0$ $0$ $-1000$ $1000$ $0$ $2000$ $0$ $2000$ $1000$ $1000$ $1000$ $1000$ $0$ $1000$ $0$ $1000$ $0$ $0$	$0:49$
$1000$ $500$ $-1000$ $0$ $1000$ $0$ $-1000$ $1000$ $1000$ $1000$ $-1000$ $0$ $-1000$ $1000$ $1000$ $0$ $1000$ $1000$ $-1000$ $0$ $1000$ $1000$ $1000$ $0$ $-1000$ $1000$ $-1000$ $1000$ $0$ $2000$ $0$ $2000$ $1000$ $1000$	$1:20$
$500$ $-500$ $0$ $0$ $1000$ $-1000$ $1000$ $-1000$ $2000$ $0$ $2000$ $0$ $3000$ $-1000$ $3000$ $-1000$ $4000$ $0$ $4000$ $0$ $5000$ $-1000$ $5000$ $-1000$ $6000$ $0$ $0$ $0$ $8000$ $0$	$1:39$

Код программы

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    double temp;
    cin >> temp >> temp;
    double lengthOfRoads = 0;
    double firstX, firstY, secondX, secondY;
    while (cin >> firstX >> firstY >> secondX >> secondY)
    {
        lengthOfRoads += sqrt((secondX - firstX)*(secondX - firstX)+(secondY - firstY)*(secondY - firstY));
    }
    int minutes = round(3 * lengthOfRoads / 500);
    cout<< minutes / 60 << ":" << minutes % 60;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double temp;

cin >> temp >> temp;

double lengthOfRoads = 0;

double firstX, firstY, secondX, secondY;

while (cin >> firstX >> firstY >> secondX >> secondY)

{

lengthOfRoads += sqrt((secondX - firstX)*(secondX - firstX)+(secondY - firstY)*(secondY - firstY));

}

int minutes = round(3 * lengthOfRoads / 500);

cout<< minutes / 60 << ":" << minutes % 60;

return 0;

}

Решение задачи

Начало пути всегда находится на одной из данных дорог. Составим оптимальный алгоритм движения снегохода. По каждой из дорог необходимо проехать в одну и другую сторону. Снегоход может начинать движение в любую сторону. Во время движения ему необходимо двигаться прямо, не разворачиваясь, настолько долго, насколько это возможно. В случае, если на пути следования снегоходу встречается поворот, ему необходимо повернуть и далее работать по тому же алгоритму, принимая за начальную точку точку поворота. После возвращения из поворота снегоход должен продолжить движение по алгоритму. Когда снегоход попадает в тупик, возвращается на перекресток, на котором был совершен поворот или попадает в начальную точку, ему необходимо развернуться и двигаться обратно по той же траектории. По возвращении в начальную точку снегоход должен, в случае необходимости, двигаться во все оставшиеся стороны по такому же алгоритму. Таким образом, при движении по такому алгоритму, снегоход будет проезжать по каждой дороге по одному разу в каждую сторону, то есть не будет нигде проезжать «лишние» километры, следовательно время, за которое снегоход может объехать все дороги по одному разу в каждую сторону и есть искомым. Таким образом нам необходимо посчитать сумму длин всех дорог $L$, координаты начала и конца которых даны во входном потоке. Снегоход всегда двигается со скоростью $V = 20 км/час = \frac{1000}{3}м/мин$. По каждой из дорог снегоход проезжает два раза, таким образом общее искомое время минутах:
$t = \frac{2L}{V} = \frac{3L}{500}$.
Округлив полученное значение $t$ до целых минут и представив это время в виде часов и минут, получаем ответ.
Замечание. Как видно из алгоритма решения, не имеет значения, где конкретно расположена точка начала движения, главное, чтобы она располагалась на одной из улиц.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

e-olymp 7107. Без лифта

02/12/2017 by Кирилл Волков

Задача

Три друга – Андрей, Борис и Владимир живут соответственно на $a$, $b$ и $v$ этажах многоэтажного дома. Они занимаются спортом, поэтому никогда не пользуются лифтом. Однажды им потребовалось срочно встретиться у кого-то из них дома.

Составьте программу, которая определяла бы номер этажа, на котором они встретятся, при чем время до встречи было бы минимальным. Учтите, что скорость спуска по лестнице в $\frac{47}{31}$ раза больше, чем скорость подъема.

Входные данные

Программа получает на вход три натуральных числа – номера этажей, на которых живут друзья ($1 \leq a, b, v \leq 28$).

Выходные данные

Программа выводит номер этажа, на котором они встречаются.

Тесты

Входные данные	Выходные данные
$1$ $5$ $8$	$5$
$1$ $1$ $2$	$1$
$4$ $11$ $14$	$4$
$6$ $3$ $2$	$3$
$2$ $9$ $1$	$2$

Код программы

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int minFloor = min(min(a, b), c);
    int maxFloor = max(max(a, b), c);
    int middleFloor = a + b + c - minFloor - maxFloor;
    int resultFloor;
    if(31 * (maxFloor - minFloor) < 47 * (middleFloor - minFloor)){
        resultFloor = minFloor;
    }
    else{
        resultFloor = middleFloor;
    }
    cout << resultFloor;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

int minFloor = min(min(a, b), c);

int maxFloor = max(max(a, b), c);

int middleFloor = a + b + c - minFloor - maxFloor;

int resultFloor;

if(31 * (maxFloor - minFloor) < 47 * (middleFloor - minFloor)){

resultFloor = minFloor;

}

else{

resultFloor = middleFloor;

}

cout << resultFloor;

return 0;

}

Решение задачи

По условию скорость спуска по лестнице в $\frac{47}{31}$ раза больше, чем скорость подъема. Назовем эту величину коэффициентом подъема.
Примем, что человек спускается на один этаж за единицу времени. Тогда он поднимается на один этаж за единицу времени, умноженную на коэффициент подъема.
Вначале необходимо установить, какой из этажей является максимальным, какой — минимальным, какой — промежуточным.
Очевидно, что друг, живущий на промежуточном этаже доберется до максимального этажа быстрее, чем тот, кто живет на минимальном, а также доберется до минимального этажа быстрее, чем тот, кто живет на максимальном. Кроме того, друг, живущий на максимальном этаже, быстрее спустится на минимальный этаж, чем живущий на минимальном поднимется на максимальный. Отсюда получаем, что если друзья будут подниматься на максимальный этаж, то потраченное время не будет наименьшим возможным. То есть друзья могут встретиться либо на минимальном, либо на промежуточном этаже. Время, потраченное на спуск на минимальный этаж, численно равно разнице между максимальным и минимальным этажом. Время, потраченное на путь к промежуточному этажу, численно равно максимуму между разницей между минимальным и промежуточным этажами, умноженной на коэффициент подъема и разницей между максимальным и промежуточным этажами. Так как разница между максимальным и промежуточным этажами всегда не превышает разницы между максимальным и минимальным этажами, то для определения искомого этажа нам достаточно сравнивать разницу между максимальным и минимальным этажами и разницу между минимальным и промежуточным этажами, умноженной на коэффициент подъема.
В случае, если первая величина будет меньше второй, то друзья должны встретиться на минимальном этаже, в противном случае — на промежуточном.

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

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

e-olymp 7369. Километровые столбы (Mileposts)

01/11/2017 by Кирилл Волков

Задача

Андрей очень любит ездить по железной дороге. Он садится у окна и внимательно следит за местностью, которую он проезжает. Особенно он обращает внимание на километровые столбы. Каждый столб с километражем, который при делении на $7$ дает в остатке $3$, он считает «счастливым». Составьте программу, которая бы определяла количество «счастливых» столбов, если во время езды он проезжает столбы с отметками от $a$ до $b.$

Входные данные

Два натуральных числа $a$ и $b$ ($0 ≤ a < b ≤ 10^9$).

Выходные данные

Вывести количество «счастливых» столбов.

Тесты

Входные данные	Выходные данные
$0$ $5$	$1$
$26$ $49$	$3$
$73$ $80$	$2$
$5$ $8$	$0$
$17$ $37$	$3$

Код программы

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin>>a>>b;
    int result = (b+4)/7 - (a+4)/7 + (a%7==3);
    cout<<result;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b;

cin>>a>>b;

int result = (b+4)/7 - (a+4)/7 + (a%7==3);

cout<<result;

return 0;

}

Решение задачи

Количество «счастливых» столбцов $l$ от $0$ до $n$, то есть количество натуральных чисел $k$ от $0$ до $n$, таких, что $k \mod7 = 3$, равно количеству чисел от $0$ до $n-3$, делящихся нацело на $7$, увеличенному на $1.$ То есть $l = \frac{n-3}{7}+1 = \frac{n+4}{7}$ (деление целочисленное). Тогда количество «счастливых» столбов на промежутке от $a$ до $b$ равно разнице количества «счастливых» столбов на промежутке от $0$ до $b$ и количества «счастливых столбов» на промежутке от $0$ до $a.$ Кроме того, если столб с отметкой $a$ является счастливым, мы должны увеличить полученный результат на $1$. Отсюда получаем итоговую формулу решения, указанную в коде программы.

Ссылки

Условие задачи на e-olymp
Код решения