e-olymp 7232. Комплектация компьютеров

21/12/2020 by Куліш Марія

Задача

В наличии есть такие системные блоки: $a_1$ поддерживают только VGA интерфейс, $a_2$ поддерживают только DVI и $a_3$ поддерживают оба интерфейса VGA и DVI. Аналогично по мониторам: $b_1$ поддерживают только VGA, $b_2$ — только DVI, $b_3$ — оба интерфейса.

Какое наибольшее количество компьютерных комплектов возможно собрать, если в каждом комплекте у системного блока с монитором должен быть совместимый графический интерфейс?

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

В первой строке три числа $a_1, a_2$ и $a_3$ и во второй строке три числа $b_1,b_2$ и $b_3$ — целые неотрицательные.

Причем $ 0 \leqslant a_1, a_2, a_3, b_1, b_2, b_3 \leqslant 100$ и $a_1+a_2+a_3$ $=$ $b_1+b_2+b_3$.

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

Ответ к задаче.

Тесты

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

Код

#include <iostream>

using namespace std;


int complect(int & b, int & a) {
  int com = min(a, b);
  a -= com;
  b -= com;
  return com;
}
int main() {
  int a1, a2, a3, b1, b2, b3, c;//c-все возможные комплекты
  cin >> a1 >> a2 >> a3 >> b1 >> b2 >> b3;
  c = 0;
  c += complect(a1, b1);
  c += complect(a2, b2);
  c += complect(a1, b3);
  c += complect(a2, b3);
  c += complect(a3, b3);
  c += complect(b1, a3);
  c += complect(b2, a3);

  cout << c;
  return 0;
}

#include <iostream>

using namespace std;

int complect(int & b, int & a) {

int com = min(a, b);

a -= com;

b -= com;

return com;

}

int main() {

int a1, a2, a3, b1, b2, b3, c;//c-все возможные комплекты

cin >> a1 >> a2 >> a3 >> b1 >> b2 >> b3;

c = 0;

c += complect(a1, b1);

c += complect(a2, b2);

c += complect(a1, b3);

c += complect(a2, b3);

c += complect(a3, b3);

c += complect(b1, a3);

c += complect(b2, a3);

cout << c;

return 0;

}

Решение

Составим все комбинации системных блоков с мониторами, у которых есть совместимый графический интерфейс. Порядок составления комплектов важен. Сначала посчитаем сколько можно составить комплектов $а_1$ с $b_1$ и $a_2$ с $b_2$, так как они поддерживают только один тип интерфейса. Далее посчитаем возможные комплекты $а_1$ с $b_3$, $a_2$ с $b_3$ и $a_3$ с $b_3$ $a_3$ с $b_1$ и $a_3$ с $b_2$ из оставшегося оборудования. Выведем общее количество компьютерных комплектов.

Ссылки

Код в ideone
Засчитанное решение на e-olymp
Задача на e-olymp

Related Images:

e-olymp 4020. Культ-орки на лестнице

10/02/2020 by Мария Жаркая

Задача

В Летней Кинематографической Школе пришло время обеда и эльф Коля поспешил в столовую. Однако для того, чтобы попасть в столовую, Коле нужно подняться по длинной лестнице, а на каждой её ступеньке в это время суток стоит по культ-орку. Каждый культ-орк разрешает Коле пройти по своей ступеньке только после того, как Коля запишется на мероприятие, которое этот культ-орк организует. При этом никакие два культ-орка не проводят одно и то же мероприятие, и все мероприятия проходят в разное время.

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

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

В первой строке вводятся два числа $n$ и $k$ $(1 \leqslant n \leqslant 10000, 0 \leqslant k \leqslant 20)$, $n$ — количество ступенек на лестнице, $k$ — максимальное количество ступенек, через которые Коля может перепрыгнуть за один прыжок (то есть, например, на первом шаге Коля может прыгнуть на $(k + 1)$-ую или более низкие ступеньки). Во второй строке вводятся $n$ чисел: $i$-ое число указывает на длительность в минутах того мероприятия, которое проведёт культ-орк, стоящий на $i$-ой ступеньке. Каждое мероприятие не может длиться более $24$ часов. Ступеньки нумеруются снизу вверх, ступенькой номер $n$ считается весь этаж столовой.

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

Выведите одно число — минимальное количество минут, которое Коле придётся распланировать.

Тесты

№	Входные данные	Выходные данные
1	5 2 7 3 9 2 11	14
2	6 1 59 32 4 21 5 1	42
3	10 3 40 55 85 29 158 105 115 281 320 10	144
4	15 4 67 20 85 12 345 9 234 115 190 47 5 17 23 89 130	156
5	4 0 100 20 31 49	200

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

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int stairs[n + 1]; int time[n + 1]; // массивы для времени каждого мероприятия и потраченного времени;
    for(int i = 1; i < n + 1; ++i) {
        cin >> stairs[i]; 
        if (i <= k + 1) time[i] = stairs[i];
    }
    time[0] = 0; 
    for(int i = 2; i <= n; ++i) {
        if (i > k + 1) time[i] = time[i - 1] + stairs[i]; // начальный минимум;
        for(int j = 2; j <= k+1; ++j) {
            if (i - j >= 0) time[i] =  min(time[i - j] + stairs[i], time[i]); // выбор минимально затраченного времени;
        }
    }
    cout << time[n];
}

#include <iostream>

using namespace std;

int main() {

int n, k;

cin >> n >> k;

int stairs[n + 1]; int time[n + 1]; // массивы для времени каждого мероприятия и потраченного времени;

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

cin >> stairs[i];

if (i <= k + 1) time[i] = stairs[i];

}

time[0] = 0;

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

if (i > k + 1) time[i] = time[i - 1] + stairs[i]; // начальный минимум;

for(int j = 2; j <= k+1; ++j) {

if (i - j >= 0) time[i] = min(time[i - j] + stairs[i], time[i]); // выбор минимально затраченного времени;

}

cout << time[n];

}

Решение

Для каждой ступеньки будем считать минимальное время, которое она отнимет у эльфа, учитывая сколько ступенек можно пропустить (от $0$ до $k + 1$). То есть будем прыгать со ступенек пониже (если это возможно) и сравнивать значения на каждой. Под значением подразумевается сумма уже найденного значения на более низкой ступеньке и времени, которое отнимет мероприятие $i$-ой ступеньки. Таким образом мы узнаем, какие ступеньки выгодно перепрыгнуть. $0$-я ступенька займет $0$ минут, так как эльф не потратит время. Изначально за минимум на ступеньках до $k + 1$ включительно можно взять время мероприятия соответствующей ступеньки, для остальных — сумму значения предыдущей ступеньки и времени мероприятия данной ступеньки. В случае, если эти значения не минимальные, они заменятся на подходящие.
Ответом будет значение на последней ступеньке, так как к ней будет проложен путь, который «займет» минимум времени эльфа на развлечения.

Ссылки

Условие задачи на e-olymp
Код программы на ideone

Related Images:

e-olymp 7849. Обменять max и min

20/12/2019 by Катя Романцова

Условие задачи

Задан массив из $n$ целых чисел. Замените все наибольшие его элементы на наименьший, а наименьшие элементы на наибольший.

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

В первой строке записано число $n ( n \leqslant 100 )$. В следующей строке записано $n$ целых чисел, каждое из которых по модулю не превосходит $100$.

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

Вывести обновленный массив.

Тесты

№	Входные данные	Выходные данные
1	7 3 5 -7 7 5 -9 -4	3 5 -7 -9 5 7 -4
2	2 1 2	2 1
3	9 12 99 87 42 55 8 65 40 72	12 8 87 55 99 65 40 72
4	8 -9 0 7 -5 2 5 1 -2	7 0 -9 -5 2 5 1 -2

Код

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int *x = new int [n];
    for ( int i = 0; i < n; i++ ) cin >> x [i];
    int min = 100; 
    int max = -100;
    for ( int i = 0; i < n; i++ ) {
        if ( x [i] > max ) max = x [i];
        if ( x [i] < min ) min = x [i];
    }
    for ( int i = 0; i < n; i++ ) {
        if ( x [i] == max ) x [i] = min;
        else if ( x [i] == min ) x [i] = max;
    }
    for ( int i = 0; i < n; i++ ) cout << x [i] << " ";
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int *x = new int [n];

for ( int i = 0; i < n; i++ ) cin >> x [i];

int min = 100;

int max = -100;

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

if ( x [i] > max ) max = x [i];

if ( x [i] < min ) min = x [i];

}

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

if ( x [i] == max ) x [i] = min;

else if ( x [i] == min ) x [i] = max;

}

for ( int i = 0; i < n; i++ ) cout << x [i] << " ";

return 0;

}

Решение

Для начала нам надо найти максимум и минимум в массиве. Для этого введем переменные максимума и минимума равные $-100$ и $100$. (Так как элементы массива по условию не должны превышать значения $|100|$ ). Проверяем. Если значение элемента массива больше значения переменной максимума, присваиваем переменной это значение. Аналогично и для минимума. Затем присвоим максимальному элементу массива минимальное, а минимальному — максимальное.

Ссылки

Условие задачи на E-olymp

Код на Ideone

Засчитанное решение на E-olymp

Related Images:

e-olymp 806. Платформы — 3

08/12/2019 by Мария Жаркая

Задача

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю, у героя уходит $|y_{2} — y_{1}|^2$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3|y_{3} -y_{1}|^2$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-й платформы до $n$-й (последней).

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

Первая строка содержит количество платформ $n$ $(2 \leqslant n \leqslant 10^5)$, вторая — $n$ целых чисел, значения которых не превышают по модулю $4000$ — высоты платформ.

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

Выведите единственное целое число — искомую величину энергии.

Тесты

№	Входные данные	Выходные данные
1	4 1 2 3 30	731
2	4 0 1 6 8	40
3	8 1 15 16 23 42 10 84 5	828
4	7 57 54 -55 -34 21 88 -100	55189
5	7 -4000 4000 -4000 4000 -4000 4000 -4000	0

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

#include <iostream>
using namespace std;

int main() {
    int n; long long j, sj, bj; // "цены" прыжка, суперприёма и 3-го типа прыжка
    cin >> n;
    int platforms[n]; long long energy[n]; // создаём массивы для платформ и энергии
    for (int i = 0; i < n; ++i) { 
                cin >> platforms[i]; //считываем высоты платформ  
    }
    energy[0] = 0; 
    for (int i = 1; i < n; ++i) {
        // обычный прыжок
        j = (platforms[i] - platforms[i - 1]) * (platforms[i] - platforms[i - 1]);
        // 3-й тип прыжка
        bj = (platforms[i] - platforms[i + 1]) * (platforms[i] - platforms[i + 1]) + 
        3 * (platforms[i + 1] - platforms[i - 1])*(platforms[i + 1] - platforms[i - 1]);
        // суперприём 
        if (i == 1) sj = max(j, bj);
        else sj = 3 * (platforms[i] - platforms[i - 2]) * (platforms[i] - platforms[i - 2]);
        if (i == n - 1) bj = max(j, sj);
        //количество энергии на i-й платформе
        energy[i] = min(energy[i - 1] + bj, min(energy[i - 1] + j, energy[i - 2] + sj));
    }
    cout << energy[n - 1];
}

#include <iostream>

using namespace std;

int main() {

int n; long long j, sj, bj; // "цены" прыжка, суперприёма и 3-го типа прыжка

cin >> n;

int platforms[n]; long long energy[n]; // создаём массивы для платформ и энергии

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

cin >> platforms[i]; //считываем высоты платформ

}

energy[0] = 0;

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

// обычный прыжок

j = (platforms[i] - platforms[i - 1]) * (platforms[i] - platforms[i - 1]);

// 3-й тип прыжка

bj = (platforms[i] - platforms[i + 1]) * (platforms[i] - platforms[i + 1]) +

3 * (platforms[i + 1] - platforms[i - 1])*(platforms[i + 1] - platforms[i - 1]);

// суперприём

if (i == 1) sj = max(j, bj);

else sj = 3 * (platforms[i] - platforms[i - 2]) * (platforms[i] - platforms[i - 2]);

if (i == n - 1) bj = max(j, sj);

//количество энергии на i-й платформе

energy[i] = min(energy[i - 1] + bj, min(energy[i - 1] + j, energy[i - 2] + sj));

}

cout << energy[n - 1];

}

Решение

Чтобы решить задачу, мы создадим массив $energy$, где будем хранить минимальную энергию, которую герой потратит для прыжка на очередную $i$-ю платформу. Для этого необходимо для каждой платформы, начиная со второй, рассмотреть три вида прыжка:

прыжок с предыдущей $i — 1$ платформы.
суперприём, то есть прыжок c $i — 2$ платформы.
3-й вид: суперприём с $i — 1$ платформы на $i + 1$ и прыжок назад на $i$.

«Цены» за обычный прыжок и суперприём мы можем найти из формул данных в условии, с 3-м же сложнее — результатом будет сумма «цены» суперприёма $3(y_{i+1} — y_{i-1})^2$ и «цены» прыжка назад $(y_{i} — y_{i+1})^2$.

Для понимания схемы можно рассмотреть в качестве примера второй тест.
Синим обозначен 3-ий тип. Красными цифрами — весь путь.

второй тест

Каждый из 3-х путей даст своё значение энергии, равное сумме «цены» прыжка на $i$-ю платформу и значения в той, из которой герой совершил прыжок. Наименьшей энергией для этой платформы будет минимум из этих трех значений.
На второй платформе $(i = 1)$ в случае суперприёма мы выходим за границы массива и получаем независимое значение, поэтому эффективнее будет в качестве «цены» выбирать максимум из двух других уже найденных значений. Аналогично на последней $(i = n — 1)$ и 3-м типе прыжка, максимум будет невыгодным и соответственно не будет выбран как минимум в $energy_{i}$.

Ссылки

Условие задачи на e-olymp
Код программы на ideone

Related Images:

e-olymp 7534. Замкнутое сокровище

03/06/2019 by Алина Гук

Задача взята с сайта e-olymp

Задача

Группа из $n$ бандитов спрятала украденное сокровище в комнате. Дверь в комнату следует отпереть только когда понадобится вынести сокровище. Так как бандиты не доверяют друг другу, они хотят иметь возможность открыть комнату и унести украденное только если этого захотят не менее $m$ из них.

Они решили разместить несколько замков на двери таким образом, чтобы она открывалась только когда открыты все замки. Каждый замок может иметь до $n$ ключей, распределенных среди некоторого подмножества бандитов. Группа бандитов может открыть замок, только если кто-то в группе имеет ключ к этому замку.

По имеющимся значениям $n$ и $m$ определить такое наименьшее количество замков, что если ключи от них правильно распределить среди бандитов, то каждая группа состоящая из не менее чем $m$ бандитов сможет открыть все замки, но никакая группа из меньшего числа бандитов открыть все замки не сможет.

Например, если $n = 3$ и $m = 2$, то достаточно $3$ замков — ключи от замка $1$ получают бандиты $1$ и $2$, ключи от замка $2$ получают бандиты $1$ и $3$, ключи от замка $3$ получают бандиты $2$ и $3$. Ни один из бандитов не может открыть все замки самостоятельно, но любая группа из $2$ бандитов может открыть все замки. Можно убедиться, что $2$ замков для этого случая не достаточно.

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

Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит два числа $n(1 \leqslant n \leqslant 30)$ и $m(1 \leqslant m \leqslant n)$.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	4 3 2 5 1 10 7 5 3	3 1 210 10
2	2 5 3 3 2	10 3
3	6 2 1 7 2 3 1 5 4 3 2 9 2	1 7 1 10 3 9

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

#include <iostream>
#include <cstring>
#define MAX 31
using namespace std;

int main() {
    int tests, n, m;
    long long c[MAX][MAX];
    memset(c, 0, sizeof(c));
    for(int i = 0; i < MAX; i++) c[i][0] = 1;
    for(int i = 0; i < MAX; i++)
        for(int j = 1; j <= MAX; j++)
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    cin >> tests;
    while(tests--) {
        cin >> n >> m;
        cout << c[n][m - 1] << "\n";
    }
    
    return 0;
}

#include <iostream>

#include <cstring>

#define MAX 31

using namespace std;

int main() {

int tests, n, m;

long long c[MAX][MAX];

memset(c, 0, sizeof(c));

for(int i = 0; i < MAX; i++) c[i][0] = 1;

for(int i = 0; i < MAX; i++)

for(int j = 1; j <= MAX; j++)

c[i][j] = c[i - 1][j] + c[i - 1][j - 1];

cin >> tests;

while(tests--) {

cin >> n >> m;

cout << c[n][m - 1] << "\n";

}

return 0;

}

Решение

Для каждой группы из $m-1$ бандитов существует замок такой, что его могут открыть все остальные группы, кроме этой. Потому что, просто обьеденив две группы с одинаковыми замками, мы получим одну большую чем $m-1$, которая не может открыть замок. Таким образом, всего должно быть столько замков, сколько существует способов выбрать $m-1$ группу из $n$ бандитов. То есть $C_{n}^{m-1}$.

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

Ссылки

Условие задачи на e-olymp

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

Треугольник Паскаля на Wikipedia

Related Images:

e-olymp 497. Лентяй

21/05/2019 by Андрей Зиновьев

Задача

Студент Валера являет собой классический пример лентяя. На занятия он практически не ходит, и только в конце семестра появляется в университете и сдает ”хвосты”. Его заветная мечта: найти такой день, когда можно будет сдать сразу все долги. У него есть расписание работы преподавателей, из которого точно известно, с какого и по какой день месяца каждый преподаватель ежедневно будет доступен. Помогите Валере написать программу, которая по расписанию будет определять, сможет ли Валера сдать все долги за один день или нет.

Входные данные:
Первая строка содержит количество тестов. Каждый тест состоит из количество предметов $n$ $(1 \le n \le 100)$, которые нужно сдать Валере. Далее идет $n$ строк, каждая из которых состоит из двух чисел $a$ и $b$ $(1 \le a \le b \le 31)$, задающих интервал работы очередного преподавателя.

Выходные данные:
Для каждого теста вывести в отдельной строке "YES" если возможно встретить всех преподавателей за один день, или "NO", если это невозможно.

Тесты

Входные данные	Вывод программы
2 1 1 2 2 1 2 3 4	YES NO
1 1 5 6	YES
2 2 1 4 7 9 3 1 30 2 5 5 10	NO YES

Continue reading →

Related Images:

e-olymp 7368. Средний балл для фигуристов

25/12/2018 by Алина Гук

Задача взята с сайта e-olymp

Задача

Спортсменам-фигуристам [latex]n[/latex] судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей[latex]\left( 0 \lt n \leqslant 10, 0 \lt m \leqslant 100 \right)[/latex] для каждого из фигуристов.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 4 7 8 9 8 10 6 5 5 4 7 9 9 10 7 7 7 7 10 9 8	8.33 5.33 9.00 8.50
2	3 4 1 2 3 3 5 2 7 1 6 9 8 3	2.00 3.00 6.00 8.00
3	10 2 1 2 3 4 5 6 7 8 9 10 1 1 1 2 2 2 3 3 3 4	5.50 2.50

Код программы (Потоковая обработка)

#include <iostream>
#include <iomanip>
using namespace std;
 
int main() {
    cout << fixed << setprecision(2);
    int n, m, tmp, sumGl, sumMin, sumMax, valMin, valMax, countMin, countMax;
    cin >> n >> m;
    for(int j = 0 ; j < m ; j++){
        sumGl = sumMin = sumMax = 0;
        valMin = 11;
        valMax = 0;
        countMin = countMax = 0;
        for(int i = 0 ; i < n; i++) {
            cin >> tmp;
            sumGl += tmp;
            if(tmp < valMin) {
                sumMin = tmp;
                valMin = tmp;
                countMin = 1;
            }
            else if(tmp == valMin) {
                sumMin += tmp;
                countMin++;
            }
            if(tmp > valMax) {
                sumMax = tmp;
                valMax =tmp;
                countMax = 1;
            }
            else if(tmp == valMax) {
                sumMax += tmp;
                countMax++;
            }
        }
        cout << (sumGl - sumMax - sumMin) / (double)(n - countMax - countMin) << " ";
    }
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

cout << fixed << setprecision(2);

int n, m, tmp, sumGl, sumMin, sumMax, valMin, valMax, countMin, countMax;

cin >> n >> m;

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

sumGl = sumMin = sumMax = 0;

valMin = 11;

valMax = 0;

countMin = countMax = 0;

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

cin >> tmp;

sumGl += tmp;

if(tmp < valMin) {

sumMin = tmp;

valMin = tmp;

countMin = 1;

}

else if(tmp == valMin) {

sumMin += tmp;

countMin++;

}

if(tmp > valMax) {

sumMax = tmp;

valMax =tmp;

countMax = 1;

}

else if(tmp == valMax) {

sumMax += tmp;

countMax++;

}

cout << (sumGl - sumMax - sumMin) / (double)(n - countMax - countMin) << " ";

}

return 0;

}

Решение

Читая каждую оценку:

Добавляем оценку к общей сумме;
Если введенная оценка равна минимальной, то добавляем ее к сумме минимальных и увеличиваем счётчик количества минимальных.
Если введенная оценка меньше минимальной, то минимальной становится введённая оценка. Счетчик количества минимальных равен [latex]1.[/latex] Сумма минимальных равна введённой оценке.
Если введенная оценка равна максимальной, то добавляем ее к сумме максимальных и увеличиваем счётчик количества максимальных.
Если введенная оценка больше максимальной, то максимальной становится введённая оценка. Счетчик количества максимальных равен [latex]1.[/latex] Сумма максимальных равна введённой оценке.

Тогда после введения всех [latex]n[/latex] оценок имеем:

[latex]sumMax[/latex] — сумма максимальных оценок.
[latex]sumMin[/latex] — сумма минимальных оценок.
[latex]countMax[/latex] — количество максимальных оценок.
[latex]countMin[/latex] — количество минимальных оценок.
[latex]sumGl[/latex] — общая сумма оценок.

Для нахождения среднего арифметического значения оценок, соответствующего условию будем применять формулу: [latex]S_с = \frac{sumGL-sumMin-sumMax}{n-countMin-countMax}[/latex]

Код программы (Массивы)

#include <iostream> 
#include <iomanip> 
using namespace std; 
 
double res(int *arr, int len) {
    int min,max;
    min = arr[0];
    max = arr[0];
    for(int i = 1; i < len; i++) {
        if(arr[i] > max) {
            max = arr[i];
        }   
        if(arr[i]<min) {
            min = arr[i];
        }
    }
    int sum = 0;
    int count = 0;
    for(int i = 0; i < len; i++) {
        if(arr[i] != max && arr[i] != min) {
            sum += arr[i];
            count++;
        }
    }  
    return sum/((double)count);
 
} 
 
int main() {  
    int m, n;
    cin >> n >> m;
    cout << fixed << setprecision(2);
    for(int i = 0; i < m; i++) {
        int* arr = new int[n];
        for(int j = 0 ; j < n; j++) {
            cin >> arr[j];
        }
        cout << res(arr, n) << " ";
        delete[] arr;
    }
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

double res(int *arr, int len) {

int min,max;

min = arr[0];

max = arr[0];

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

if(arr[i] > max) {

max = arr[i];

}

if(arr[i]<min) {

min = arr[i];

}

int sum = 0;

int count = 0;

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

if(arr[i] != max && arr[i] != min) {

sum += arr[i];

count++;

}

return sum/((double)count);

}

int main() {

int m, n;

cin >> n >> m;

cout << fixed << setprecision(2);

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

int* arr = new int[n];

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

cin >> arr[j];

}

cout << res(arr, n) << " ";

delete[] arr;

}

return 0;

}

Решение

Делаем без счетчиков, запоминаем все элементы. Находим минимум и максимум, дальше проходим по всем оценкам и, если она не минимальная и не максимальная, добавляем к сумме и увеличиваем количество оценок, которые учитываются для среднего значения. В конце выводим среднее значение с двумя знаками после запятой.

Ссылки

Условие задачи на e-olymp

Код программы на ideone (Потоковая обработка)

Код программы на ideone (Массивы)

Related Images:

e-olymp 5282. Седловые точки

22/12/2018 by Иван Киреев

Задача. Седловые точки

Задана матрица $K$, содержащая $n$ строк и $m$ столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.
Найдите количество седловых точек заданной матрицы.

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

Первая строка содержит целые числа $n$ и $m$. $(1 \leq n, m \leq 750)$. Далее следуют $n$ строк по $m$ чисел в каждой. $j$-ое число $i$-ой строки равно $k_{ij}$. Все $k_{ij}$ по модулю не превосходят $1000$.

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

Выведите количество седловых точек.

Тесты

№	Ввод	Вывод
1	2 2 0 0 0 0	4
2	2 2 1 2 3 4	1
3	5 5 100 -100 100 1000 110 10 -1000 100 -1000 110 100 -1000 100 100 110 1000 -1000 1000 1000 100 1000 -1000 1000 1000 -1000	1
4	4 4 1000 1000 100 100 1000 1000 1000 1000 100 100 100 1000 100 1000 1000 1000	4
5	2 3 1 -1 1 0 -1 0	2
6	5 1 -1 0 -1 0 -1	2
7	4 2 1 2 -2 1 -1 2 -2 -1	1
8	3 3 5 1 3 3 1 2 1 1 2	3
7	3 3 5 2 3 3 4 2 1 8 2	0

Решение

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

Вариант решения за $O\left(n^2\right)$

Для этого мы просто сравниваем каждый максимум с каждым минимумом и считаем их совпадения. В этом случае алгоритм будет выполнятся за $O(n^2)$, где $n$ это наибольшая из длин массивов. Это значит что при достаточно больших массивах программа будет работать непозволительно долго. Но такой подход достаточно прост в реализации и интуитивно понятен.

#include <iostream>
#define N 750
using namespace std;
 
int main() {
    int n, m, MIN[N], MAX[N];
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int input;
            cin >> input;
            if (i == 0) MAX[j] = input;
            else if (MAX[j] < input) MAX[j] = input;
            if (j == 0) MIN[i] = input;
            else if (MIN[i] > input) MIN[i] = input;
        }
    }
    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (MIN[i] == MAX[j]) count++;
    cout << count;
    return 0;
}

#include <iostream>

#define N 750

using namespace std;

int main() {

int n, m, MIN[N], MAX[N];

cin >> n >> m;

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

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

int input;

cin >> input;

if (i == 0) MAX[j] = input;

else if (MAX[j] < input) MAX[j] = input;

if (j == 0) MIN[i] = input;

else if (MIN[i] > input) MIN[i] = input;

}

int count = 0;

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

for (int j = 0; j < m; j++)

if (MIN[i] == MAX[j]) count++;

cout << count;

return 0;

}

Вариант решения за $O\left(n\log n\right)$

В этом случае мы сортируем массивы, для установления взаимосвязи между элементами в них. А далее заведя два указателя на элементы массивов проверяем на равенство только не меньшие элементы от текущих в разных массивах. Если равных элементов окажется несколько подряд, то их количество будет равно произведению количества их повторений в каждом из массивов. Дойдя до конца одного из них нужно не забыть проверить остались ли в другом массиве равные последнему в пройденном элементы. Проверять стоит лишь не меньшие элементы. Таким алгоритмом мы проверяем совпадения линейно за $O(n)$, где $n$ это наибольшая из длин массивов, но для него необходимо отсортировать оба массива за $O(n\log n)$. Таким образом мы получаем вычислительную сложность $O(n\log n)$, что уже быстрее предыдущего варианта.

#include <iostream>
#define N 750
using namespace std;
 
void merge_sort(int *arr, int n) {
    if (n == 1) return;
    int len_l = n / 2, len_r = n - len_l;
    int l[len_l], r[len_r];
    for (int i = 0; i < n; i++)
        if (i < len_l) l[i] = arr[i];
        else r[i - len_l] = arr[i];
    merge_sort(l, len_l);
    merge_sort(r, len_r);
    int i = 0, j = 0;
    while (i < len_l && j < len_r)
        if (l[i] < r[j]) arr[i + j] = l[i++];
        else arr[i + j] = r[j++];
    while (i < len_l) arr[i + j] = l[i++];
    while (j < len_r) arr[i + j] = r[j++];
}
 
int main() {
    int n, m, MIN[N], MAX[N];
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int input;
            cin >> input;
            if (i == 0) MAX[j] = input;
            else if (MAX[j] < input) MAX[j] = input;
            if (j == 0) MIN[i] = input;
            else if (MIN[i] > input) MIN[i] = input;
        }
    }
    merge_sort(MAX, m);
    merge_sort(MIN, n);
    int i = 0, j = 0, count_i = 1, count_j = 1, counter = 0;
    while (i < n && j < m) {
        while (i < n-1 && MIN[i] == MIN[i+1]) {
            count_i++;
            i++;
        } 
        while (j < m-1 && MAX[j] == MAX[j+1]) {
            count_j++;
            j++;
        }
        if (MIN[i] < MAX[j]) {
            i++;
            count_i = 1;
        } else if (MIN[i] > MAX[j]) {
            j++;
            count_j = 1;
        } else {
            counter += count_i * count_j;
            i++;
            j++;
            count_i = 1;
            count_j = 1;
        }
    }
    while (i < n && MIN[i] <= MAX[m-1]) {
        while (i < n-1 && MIN[i] == MIN[i+1]) {
            count_i++;
            i++;
        } 
        if (MIN[i] == MAX[m-1]) {
            i++;
            counter += count_i;
            count_i = 1;
        }
 
    }
    while (j < m && MAX[j] <= MIN[n-1]) {
        while (j < m-1 && MAX[j] == MAX[j+1]) {
            count_j++;
            j++;
        } 
        if (MAX[j] == MIN[n-1]) {
            j++;
            counter += count_j;
            count_j = 1;
        }
 
    }
    cout << counter;
    return 0;
}

#include <iostream>

#define N 750

using namespace std;

void merge_sort(int *arr, int n) {

if (n == 1) return;

int len_l = n / 2, len_r = n - len_l;

int l[len_l], r[len_r];

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

if (i < len_l) l[i] = arr[i];

else r[i - len_l] = arr[i];

merge_sort(l, len_l);

merge_sort(r, len_r);

int i = 0, j = 0;

while (i < len_l && j < len_r)

if (l[i] < r[j]) arr[i + j] = l[i++];

else arr[i + j] = r[j++];

while (i < len_l) arr[i + j] = l[i++];

while (j < len_r) arr[i + j] = r[j++];

}

int main() {

int n, m, MIN[N], MAX[N];

cin >> n >> m;

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

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

int input;

cin >> input;

if (i == 0) MAX[j] = input;

else if (MAX[j] < input) MAX[j] = input;

if (j == 0) MIN[i] = input;

else if (MIN[i] > input) MIN[i] = input;

}

merge_sort(MAX, m);

merge_sort(MIN, n);

int i = 0, j = 0, count_i = 1, count_j = 1, counter = 0;

while (i < n && j < m) {

while (i < n-1 && MIN[i] == MIN[i+1]) {

count_i++;

i++;

}

while (j < m-1 && MAX[j] == MAX[j+1]) {

count_j++;

j++;

}

if (MIN[i] < MAX[j]) {

i++;

count_i = 1;

} else if (MIN[i] > MAX[j]) {

j++;

count_j = 1;

} else {

counter += count_i * count_j;

i++;

j++;

count_i = 1;

count_j = 1;

}

while (i < n && MIN[i] <= MAX[m-1]) {

while (i < n-1 && MIN[i] == MIN[i+1]) {

count_i++;

i++;

}

if (MIN[i] == MAX[m-1]) {

i++;

counter += count_i;

count_i = 1;

}

while (j < m && MAX[j] <= MIN[n-1]) {

while (j < m-1 && MAX[j] == MAX[j+1]) {

count_j++;

j++;

}

if (MAX[j] == MIN[n-1]) {

j++;

counter += count_j;

count_j = 1;

}

cout << counter;

return 0;

}

Related Images:

e-olymp 8529. Преобразование Капрекара

29/11/2018 by Кирилл Веремйов

Задача

Индийский математик Д. Р. Капрекар известен своими работами по теории чисел. Одна из его работ посвящена так называемому преобразованию Капрекара. Рассмотрим следующую операцию. Пусть задано число $x$. Пусть $M$ — наибольшее число, которое можно получить из $x$ перестановкой его цифр, а $m$ — наименьшее число (это число может содержать ведущие нули). Обозначим как $K(x)$ разность $M$ — $m$, дополненную при необходимости ведущими нулями так, чтобы число цифр в ней было равно числу цифр в $x$.

Например $K(100) = 100 — 001 = 099$, $K(2414) = 4421 — 1244 = 3177$.

Капрекар доказал, что если начать с некоторого четырехзначного числа $x$, в котором не все цифры равны между собой, и последовательно применять к нему эту операцию (вычислять $K(x)$, $K(K(x))$, . . . ), то рано или поздно получится число $6174$. Для него верно равенство $K(6174) = 7641 — 1467 = 6174$, поэтому на нем процесс зациклится.

Ваша задача состоит в том, чтобы написать программу, вычисляющую $K(x)$ по числу $x.$

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

Одно целое число без ведущих нулей $x$ ($1$ ≤ $x$ ≤ $10^9$).

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

Выведите $K(x)$.

Тесты

Входные данные	Выходные данные
100	099
1000000000	0999999999
2414	3177
6174	6174
5	0
7272	5445
142857	750843
495	495
55	00
56	09
554	099
12345	41976

Решение

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

int main() {
	long long x, K = 0, xm = 0, xM = 0;
	//Вводимое число, искомое число, максимальное и минимальное из комбинации цифр
	cin >> x;
	int N[11];
	int n = 0;
	
	while(x != 0){//Количество цифр в числе, запись их в массив цифр
		N[n] = abs(x % 10);
		n++;
		x /= 10;
	}
	
	bool t = true;

	sort(N , N+n);//Сортировка цифр по возрастанию

	long long ten = 1;
	
	for(int j = 0; j < n-1; j++){
		ten *= 10;
	}
	
	long long ten_copy = ten;
	
	for(int i = 0; i < n; i++){//Преобразование цифр в наименьшее число
		xm += N[i] * ten;
		ten /= 10;
	}
	
	for(int i = n-1; i >= 0; i--){//Преобразование цифр в наибольшее число
		xM += N[i] * ten_copy;
		ten_copy /= 10;
	}
	
	K = xM - xm;
	int c = 0;
	
	long long K_tmp = K;
	//Проверка на равенство количества цифр исходного числа и числа K
	while(K_tmp != 0){
		c++;
		K_tmp /= 10;
	}
	
	//Добавление недостающих ведущих нулей
	for(int i = 0; i < n-c; i++) cout << 0;
	
	if(K!=0)//Если K==0, то нули были выведены предыдущим циклом
		cout << K;//Вывод числа K
		
	return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long long x, K = 0, xm = 0, xM = 0;

//Вводимое число, искомое число, максимальное и минимальное из комбинации цифр

cin >> x;

int N[11];

int n = 0;

while(x != 0){//Количество цифр в числе, запись их в массив цифр

N[n] = abs(x % 10);

n++;

x /= 10;

}

bool t = true;

sort(N , N+n);//Сортировка цифр по возрастанию

long long ten = 1;

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

ten *= 10;

}

long long ten_copy = ten;

for(int i = 0; i < n; i++){//Преобразование цифр в наименьшее число

xm += N[i] * ten;

ten /= 10;

}

for(int i = n-1; i >= 0; i--){//Преобразование цифр в наибольшее число

xM += N[i] * ten_copy;

ten_copy /= 10;

}

K = xM - xm;

int c = 0;

long long K_tmp = K;

//Проверка на равенство количества цифр исходного числа и числа K

while(K_tmp != 0){

c++;

K_tmp /= 10;

}

//Добавление недостающих ведущих нулей

for(int i = 0; i < n-c; i++) cout << 0;

if(K!=0)//Если K==0, то нули были выведены предыдущим циклом

cout << K;//Вывод числа K

return 0;

}

Объяснение

Поскольку нужно находить минимальную и максимальную комбинацию из цифр числа, удобно в самом начале записать это число в виде массива и отсортировать. Далее найти, собственно, искомые числа, и получить из них само $K(x)$. Потом остаётся проверить количество цифр и вывести, при недостатке, соответствующее количество нулей.

Код на ideone
Зачтено на e-olymp

Related Images:

e-olymp 3867. Ленивый Мишка

23/09/2018 by Иван Киреев

Задача. Ленивый Мишка

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

На мытье посуды уйдет [latex]t_1[/latex] секунд
Пропылесосить квартиру можно за [latex]t_2[/latex] секунд
Процесс игры с Маринкой займет [latex]t_3[/latex] секунд

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

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

Три целых числа [latex]t_1[/latex], [latex]t_2[/latex], [latex]t_3[/latex] ([latex]1 ≤ t_1, t_2, t_3 ≤ 1000[/latex]).

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

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

Тесты

№	Ввод	Вывод
1	1 7 2	1
2	100 45 1	1
3	66 9 888	9
4	5 800 4	4
5	25 46 25	25
6	13 10 12	10
7	999 995 1000	995

Решение 1

Мишка выбирает мамино поручение, что занимает наименьшее количество времени. Нам дано время за которое Мишка выполнит данные поручения. Найдём из них наименьшее и выведем на экран. Воспользуемся функцией int min (int, int); из библиотеки cmath.

Код 1

#include <iostream>
#include <cmath>

using namespace std;

int main ()
{
    short t1, t2, t3;
    cin >> t1 >> t2 >> t3;
    cout << min (min (t1, t2), t3); //Находим минимум 3х переменных и выводим.
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main ()

{

short t1, t2, t3;

cin >> t1 >> t2 >> t3;

cout << min (min (t1, t2), t3); //Находим минимум 3х переменных и выводим.

return 0;

}

Решение 2

Для нахождения минимума трёх чисел заведём переменную min и воспользуемся логическим ветвлением.

Код 2

#include <iostream>

using namespace std;

int main ()
{
    short t1, t2, t3, min;
    cin >> t1 >> t2 >> t3;
    min = t1; //Переменная отвечающая за минимальное значение.
    if (t2 < min) min = t2;
    if (t3 < min) min = t3;
    cout << min;
    return 0;
}

#include <iostream>

using namespace std;

int main ()

{

short t1, t2, t3, min;

cin >> t1 >> t2 >> t3;

min = t1; //Переменная отвечающая за минимальное значение.

if (t2 < min) min = t2;

if (t3 < min) min = t3;

cout << min;

return 0;

}

Ссылки

Первое решение

Второе решение

Условие задачи

Компиляция первого решения

Компиляция второго решения

Related Images:

e-olymp 7368. Средний балл для фигуристов

02/01/2018 by Валерия Ларикова

Задача

Спортсменам — фигуристам [latex]n[/latex] судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей [latex](0 < n ≤ 10, 0 < m ≤ 100)[/latex] для каждого из фигуристов.

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

В одной строке вывести [latex]m[/latex] чисел с точностью до двух десятичных знаков — балл каждого спортсмена.

Тесты

#	Входные данные	Выходные данные
1	5 4 7 8 9 8 10 6 5 5 4 7 9 9 10 7 7 7 7 10 9 8	8.33 5.33 9.00 8.50
2	6 3 6 7 6 5 4 3 9 8 5 5 6 5 7 6 4 1 2 2	5.25 7.00 3.50
3	4 5 6 7 8 6 9 8 5 4 7 6 7 5 4 3 9 3 7 8 7 6	7.00 6.50 6.00 4.00 7.00
4	4 4 7 7 2 3 9 8 3 3 5 4 9 7 4 3 2 6	3.00 8.00 6.00 3.50
5	8 5 4 5 6 7 7 4 9 8 3 5 6 6 7 8 5 9 7 6 3 9 3 7 9 7 5 6 4 3 7 7 5 7 9 8 4 6 7 9 9 4	6.60 6.17 6.75 5.00 7.00

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

#include <iostream>
#include <iomanip>//данная библиотека позволяет устанавливать количество знаков после запятой 
#include <cmath>//данная библиотеа помогает вычислить min и max
#include <climits>//определяет константы с ограничениями целочисленного типа данных
using namespace std;
 
int main() {
    double n, m;
    double x, min = INT_MAX, max = INT_MIN, sum = 0, a = 0, b = 0;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j ++){
            cin >> x;
            if (max == x) a++;
            if (max < x) {
                if (max != min) sum += a*max;
                a = 1;
                max = x;
            }
            if ( min == x) b++;
            if (min > x) {
                if (max != min) sum += b*min;
                b = 1;
                min = x;
            }
        if (x!= min and x != max) sum += x;
        }
        cout << fixed << setprecision(2) << sum / (n - a - b) << " ";//функция с её аргументом позволяет вывеси результат, округлённый до двух десятичных знаков
        sum = a = b = 0;
        min = INT_MAX;
        max = INT_MIN;
    }
    return 0;
}

#include <iostream>

#include <iomanip>//данная библиотека позволяет устанавливать количество знаков после запятой

#include <cmath>//данная библиотеа помогает вычислить min и max

#include <climits>//определяет константы с ограничениями целочисленного типа данных

using namespace std;

int main() {

double n, m;

double x, min = INT_MAX, max = INT_MIN, sum = 0, a = 0, b = 0;

cin >> n >> m;

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

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

cin >> x;

if (max == x) a++;

if (max < x) {

if (max != min) sum += a*max;

a = 1;

max = x;

}

if ( min == x) b++;

if (min > x) {

if (max != min) sum += b*min;

b = 1;

min = x;

}

if (x!= min and x != max) sum += x;

}

cout << fixed << setprecision(2) << sum / (n - a - b) << " ";//функция с её аргументом позволяет вывеси результат, округлённый до двух десятичных знаков

sum = a = b = 0;

min = INT_MAX;

max = INT_MIN;

}

return 0;

}

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

Для решения задачи нам необходимо изъять все минимальные и максимальные значения в каждой строчке. Переменные [latex]a[/latex] и [latex]b[/latex] — это количество вхождений максимума и минимума соответственно. Берем любой элемент строки, который обозначили переменной [latex]x[/latex], и будем считать, что он минимальный и максимальный. Далее сравниваем элементы между собой и находим максимум и минимум и подсчитываем их количество. Ещё нам необходимо посчитать сумму оставшихся значений, а также их количество по формуле [latex]n-a-b[/latex]. А затем вычисляем среднее арифметическое для оставшихся значений по формуле [latex]\frac{sum}{n-a-b}[/latex] и выводим результат.

Ссылка на e-olymp

Ссылка на ideone

Related Images:

e-olymp 7457. Max-Min в двійковій системі счислення

20/12/2017 by Александра Рябова

Умова

Вивчаючи двійкову систему числення, Василько вирішив попрактикуватися і придумав таку вправу. Він із бітів числа створював найбільше і найменше число, переставляючи біти, після чого знаходив їх різницю. Проте хлопець не знає, чи правильно виконує вправу. Допоможіть йому. Напишіть програму, яка за даним числом [latex]N[/latex] знаходить різницю між найбільшим і найменшим числом, які утворюються із бітів заданого числа. У найбільшого числа найбільший біт співпадає з найбільшим бітом заданого числа.

Пояснення

[latex]N = 13_{10}[/latex], в двійковій системі числення — [latex]1101_2[/latex], найбільше число [latex]1110_2[/latex] = [latex]14_{10}[/latex], найменше число [latex]0111_2[/latex] = [latex]7_{10}[/latex]. [latex]14-7=7[/latex].

Вхідні дані

В єдиному рядку записане число N ([latex]N<2^{31}[/latex]).

Вихідні дані

Єдине число — відповідь до вправи Василька.

Тести

Вхідні дані	Вихідні дані
$2$	$1$
$15$	$0$
$86$	$105$
$1000$	$945$
$40$	$45$

Код програми

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

long long max_number(long long n1, long long n0)
{
    long long  number;
    for (int i=n0+n1-1; i>=n0; i--)
    {
        number+=pow(2, i);  
    }
    return(number);
}

long long min_number(long long n1, long long n0)
{
    long long  number;
    for (int i=n1-1; i>=0; i--)
    {
        number+=pow(2, i);  
    }
    return(number);
}

int main() 
{
    long long n;
    cin >> n;
    long long n1=0;
    long long n0=0;
    while (n>0)
    {
        if (n%2==1) n1++;
        else n0++;
        n/=2;
    }
    
    cout << max_number (n1, n0) - min_number (n1, n0);
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

long long max_number(long long n1, long long n0)

{

long long number;

for (int i=n0+n1-1; i>=n0; i--)

{

number+=pow(2, i);

}

return(number);

}

long long min_number(long long n1, long long n0)

{

long long number;

for (int i=n1-1; i>=0; i--)

{

number+=pow(2, i);

}

return(number);

}

int main()

{

long long n;

cin >> n;

long long n1=0;

long long n0=0;

while (n>0)

{

if (n%2==1) n1++;

else n0++;

n/=2;

}

cout << max_number (n1, n0) - min_number (n1, n0);

return 0;

}

Рішення

Процес вирішення даної задачі поділяється на 4 кроки:

За допомогою циклу рахуємо кількість одиниць та нулів у двійковому вигляді поданого числа [latex]n[/latex].
Створимо функцію [latex]max\_number[/latex], яка за поданою кількістю нулів та одиниць буде повертати найбільше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Очевидно, що отримати найбільше число в двійковому вигляді можна, якщо записати спочатку всі одиниці, а потім — усі нулі.
Створимо функцію [latex]min\_number[/latex], яка за поданою кількістю нулів та одиниць буде повертати найменше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Зрозуміло, що найменше число буде виглядати навпаки — спочатку будуть стояти всі нулі, а потім — усі одиниці.
Виведемо на екран різницю підрахованих функціями [latex]max\_number[/latex] та [latex]min\_number[/latex] значень.

Посилання

Код програми на ideone
Умова на сайті E-Olymp

Related Images:

e-olymp 695. Range Variation Query

19/05/2016 by Сплошнов Кирилл

Условие

Задача взята отсюда.

Последовательность [latex]a_n[/latex] задается следующей формулой: [latex]a_n = n^2 \mod 12345 + n^3 \mod 23456[/latex].

Требуется много раз отвечать на запросы следующего вида:

найти разность между максимальным и минимальным значением среди элементов [latex]a_i, a_{i+1}, \ldots, a_j[/latex];
присвоить элементу [latex]a_i[/latex] значение [latex]j[/latex].

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

Первая строка содержит натуральное число [latex]k[/latex] [latex](k \leq 10^5)[/latex] — количество запросов. Следующие [latex]k[/latex] строк содержат запросы, по одному в строке. Запрос номер [latex]i[/latex] описывается двумя целыми числами [latex]x_i[/latex], [latex]y_i[/latex].

Если [latex]x_i > 0[/latex], то требуется найти разность между максимальным и минимальным значением среди элементов [latex]a_{xi}, a_{xi+1}, \ldots, a_{yi}[/latex]. При этом [latex]1 \leq x_i \leq y_i \leq 10^5[/latex].

Если [latex]x_i < 0[/latex], то требуется присвоить элементу [latex]a_{-xi}[/latex] значение [latex]y_i[/latex]. При этом [latex]-10^5 \leq x_i \leq 1[/latex] и [latex]|y_i| \leq 10^5[/latex].

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

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

Тесты

№	Входные данные	Выходные данные
1	7 1 3 2 4 -2 -100 1 5 8 9 -3 -101 2 3	34 68 250 234 1
2	4 1 100000 100000 100000 -100000 42000 1 100000	35753 0 41998
3	13 1 17 -5 -400 -3 500 3 5 1 17 -2 345 2 345 2 3 2 5 -1 -100000 -2 100000 1 2 1 100000	5200 900 5602 35813 155 900 200000 200000

Код

#include <iostream>
#include <utility>
#include <algorithm>
#define SIZE 100000
using namespace std;

void build(pair<int, int>* tree, int pos, int l, int r)
{
    if (l == r)
    {
        tree[pos].first = (l % 12345) * (l % 12345) % 12345 + ((l % 23456) * (l % 23456) % 23456) * (l % 23456) % 23456;
        tree[pos].second = tree[pos].first;
    }
    else
    {
        int m = (l + r) / 2;
        build(tree, pos * 2, l, m);
        build(tree, pos * 2 + 1, m + 1, r);
        tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));
    }
}

pair<int, int> get(pair<int, int>* tree, int pos, int l, int r, int ql, int qr)
{
    if (l == ql && r == qr)
        return tree[pos];
    else
    {
        int m = (l + r) / 2;
        if (qr <= m)
            return get(tree, pos * 2, l, m, ql, qr);
        else if (ql >= m + 1)
            return get(tree, pos * 2 + 1, m + 1, r, ql, qr);
        else
        {
            pair<int, int> a = get(tree, pos * 2, l, m, ql, m);
            pair<int, int> b = get(tree, pos * 2 + 1, m + 1, r, m + 1, qr);
            return make_pair(max(a.first, b.first), min(a.second, b.second));
        }
    }
}

void modify(pair<int, int>* tree, int pos, int l, int r, int npos, int nv)
{
    if (l == r)
    {
        tree[pos].first = nv;
        tree[pos].second = nv;
    }
    else
    {
        int m = (l + r) / 2;
        if (npos <= m)
            modify(tree, pos * 2, l, m, npos, nv);
        else
            modify(tree, pos * 2 + 1, m + 1, r, npos, nv);
        tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    pair<int, int> tree[SIZE * 4];
    build(tree, 1, 1, SIZE);
    int n, x, y;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        if (x > 0)
        {
            pair<int, int> query = get(tree, 1, 1, SIZE, x, y);
            cout << query.first - query.second << endl;
        }
        else
            modify(tree, 1, 1, SIZE, -x, y);
    }
    return 0;
}

#include <iostream>

#include <utility>

#include <algorithm>

#define SIZE 100000

using namespace std;

void build(pair<int, int>* tree, int pos, int l, int r)

{

if (l == r)

{

tree[pos].first = (l % 12345) * (l % 12345) % 12345 + ((l % 23456) * (l % 23456) % 23456) * (l % 23456) % 23456;

tree[pos].second = tree[pos].first;

}

else

{

int m = (l + r) / 2;

build(tree, pos * 2, l, m);

build(tree, pos * 2 + 1, m + 1, r);

tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));

}

pair<int, int> get(pair<int, int>* tree, int pos, int l, int r, int ql, int qr)

{

if (l == ql && r == qr)

return tree[pos];

else

{

int m = (l + r) / 2;

if (qr <= m)

return get(tree, pos * 2, l, m, ql, qr);

else if (ql >= m + 1)

return get(tree, pos * 2 + 1, m + 1, r, ql, qr);

else

{

pair<int, int> a = get(tree, pos * 2, l, m, ql, m);

pair<int, int> b = get(tree, pos * 2 + 1, m + 1, r, m + 1, qr);

return make_pair(max(a.first, b.first), min(a.second, b.second));

}

void modify(pair<int, int>* tree, int pos, int l, int r, int npos, int nv)

{

if (l == r)

{

tree[pos].first = nv;

tree[pos].second = nv;

}

else

{

int m = (l + r) / 2;

if (npos <= m)

modify(tree, pos * 2, l, m, npos, nv);

else

modify(tree, pos * 2 + 1, m + 1, r, npos, nv);

tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));

}

int main()

{

ios::sync_with_stdio(false);

pair<int, int> tree[SIZE * 4];

build(tree, 1, 1, SIZE);

int n, x, y;

cin >> n;

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

{

cin >> x >> y;

if (x > 0)

{

pair<int, int> query = get(tree, 1, 1, SIZE, x, y);

cout << query.first - query.second << endl;

}

else

modify(tree, 1, 1, SIZE, -x, y);

}

return 0;

}

Решение

Задача решается с помощью стандартного Дерева Отрезков (подробно про ДО прочитать можно, например, на сайте Е-maxx, ссылка ниже). Отметим особенности построения данного дерева. В вершинах дерева хранить будем не по одному, а по два значения — соответственно максимум и минимум на отрезке. Тогда при построении дерева, спускаясь до листа, будем считать элемент последовательности по формуле, данной в условии, и это значение будет как минимумом, так и максимум для отрезка из одного элемента. Для остальных элементов имеем:

tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));

1	tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));

Где элементы с номерами [latex]pos * 2[/latex] и [latex]pos * 2 + 1[/latex] — левый и правый потомок соответственно. Для удобства, дерево нумеруется с единицы.

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

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

Таким образом, в самой программе мы просто строим дерево, а потом в цикле отвечаем на запросы, выполняя необходимые действия (как описано в условии). При запросе типа [latex]1[/latex] [latex](x_i > 0)[/latex] выводим разницу между полученными максимумом и минимумом.

Ссылки

Засчитанное решение на сайте e-olymp.
Рабочий код на Ideone.
Статья про Дерево Отрезков на e-maxx.

Related Images:

A299

26/03/2016 by Сплошнов Кирилл

Условие

Дана последовательность действительных чисел [latex]a_1, a_2, \dots, a_n[/latex]. Требуется домножить все члены последовательности на квадрат её наименьшего члена, если [latex]a_1 \geq 0[/latex], в противном случае — на квадрат наибольшего.

Решение

Для решения воспользуемся стандартным классом vector. Для этого заведем переменную данного типа, заполним её числами со входного потока. Далее, в зависимости от первого (нулевого) элемента вектора, воспользуемся стандартной функцией min_element() или max_element() (библиотека algorithm). Далее умножим каждый элемент на (соответственно) минимум/максимум и выведем последовательность.

Тесты

№	Входные данные	Выходные данные
1	-2 2 43 5 -10 12 0 -1	-3698 3698 79507 9245 -18490 22188 0 -1849
2	0 100 99 0 -1 1	0 100 99 0 -1 1
3	42 1 1 1 0 -1 24 -24 -42	74088 1764 1764 1764 0 -1764 42336 -42336 -74088

Код

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

int main() 
{
	vector<int> x;
	int a;
	while (cin >> a)
		x.push_back(a);
	if (x.at(0) >= 0)
	{
		int min = *min_element(x.begin(), x.end());
		for (int &i : x)
			i *= min * min;
	}
	else
	{
		int max = *max_element(x.begin(), x.end());
		for (int &i : x)
			i *= max * max;
	}
	for (int i : x)
		cout << i << " ";
	return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

vector<int> x;

int a;

while (cin >> a)

x.push_back(a);

if (x.at(0) >= 0)

{

int min = *min_element(x.begin(), x.end());

for (int &i : x)

i *= min * min;

}

else

{

int max = *max_element(x.begin(), x.end());

for (int &i : x)

i *= max * max;

}

for (int i : x)

cout << i << " ";

return 0;

}

Замечание

Перед изменением значения членов последовательности и их выводом нам необходимо найти минимум или максимум, для чего необходимо знать значения всех её членов. В связи с этим, решить задачу в формате «считал — вывел» (потоковой обработкой) невозможно.

Ссылки

Код на ideaone (vector).

Related Images:

Mif 15

26/10/2015 by Женя Максимова

Задача. Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин в четырехмерном пространстве.

Тесты

(1)

№	[latex]A_0[/latex]	[latex]A_1 [/latex]	[latex]A_2[/latex]	[latex]A_3[/latex]	[latex]B_0[/latex]	[latex]B_1[/latex]	[latex]B_2[/latex]	[latex]B_3[/latex]
1	1	0	0	0	2	0	0	0
2	1	0	0	0	3	0	0	0
3	-1	1	0	6	-2	-1	1	6
4	1	1	1	1	2	2	2	2
5	1	1	1	2	8	5	7	10
6	1	1	0	0	1	0	1	1
7	3	4	7	8	9	5	6	2
8	1	2	2	3	1	4	8	9

(2)

№	[latex]C_0[/latex]	[latex]C_1[/latex]	[latex]C_2[/latex]	[latex]C_3[/latex]	[latex]D_0[/latex]	[latex]D_1[/latex]	[latex]D_2[/latex]	[latex]D_3[/latex]	[latex]r[/latex]
1	1	1	0	0	2	1	0	0	1.000000
2	2	4	0	0	2	4	3	0	4.000000
3	-1	-1	0	6	2	1	1	6	1.154701
4	-9	-9	-9	-9	-5	-5	-5	-5	12.000000
5	8	0	0	0	2	1	1	1	1.414214
6	2	3	2	0	1	4	9	1	3.000000
7	7	4	11	15	15	5	12	9	9.000000
8	5	7	2	23	4	8	8	21	13.000000

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

#include "stdio.h"
#include <cmath>

double dot(double * u, double * v);
double abs(double * u);
double min(double a, double b, double c, double d);
void prod(double k, double * u, double * v);
void diff(double * a, double * b, double * c);
void summ(double * a, double * b, double * c);
bool in(double s);
bool in(double s, double t);
double sd(double s, double t);
double _(double s);

double P0[4],P1[4],Q0[4],Q1[4];
double u[4],v[4],w0[4];

double InterSegmentDistance4d()
//input: four 4d points P0, P1, Q0, Q1
// output: r = minimal distance between lines segments P0P1 and Q0Q1
    {
        double r = 0;
        //calculation of three vectors
        //u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0
        diff(P1, P0, u);  diff(Q1, Q0, v);  diff(Q0, P0, w0);
        //calculation of supporting scalar variables
        //a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v
        double  a, b, c, d, e;
        a = dot(u,u);  // a=u^2;
        b = dot(u,v);         
        c = dot(v,v);  // c=v^2;
        d = dot(u,w0);
        e = dot(v,w0);
        //calculation of main determinant
        // D = b^2 - a*c
        double D = b*b - a*c;
        if (D == 0) //lines are parallel
            {
                double t0=-e/c; 
                double t1=-e/c; 
                double s0 = (-e+b)/c ; 
                double s1= (e-c)*b/(c*a);
                if (in(t0) || in(t1) || in(s0) || in(s1))
                    {
                        double wq[4];
                        prod(e/c,v,  wq);  //projection w0 on line q
                        double wd[4];
                         diff(w0,wq,  wd);
                          r = abs(wd);
                           return r ; //r = |w0 - wq|
                    }
                //else minimal distance between segments equals minimal distance between ends of segments
                        r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));
                         return r;   
            }
        // else lines are not parallel
            {
                //calculation of determinants
                double D1 = b*e - c*d,  D2 = a*e - b*d;
                //calculation of parameters for minimal segment between lines
                double sc = D1/D, tc = D2/D;
                if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines
                    {
                        return r = sd(sc,tc); // r = |wc|
                    }
                //else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]
                    {
                        double t1 = 0,   s1=_(d/a);
                        double t2 = _(-2*e/c), s2=0;
                        double t3 = 1,   s3=_(2*(b+d)/a);
                        double t4 = _(2*(b+e)/c), s4=0;
                         return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4)); 
                    }
            }
    }

int main()
    {
        scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);
        scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);
        scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);
        scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);
         printf("%lf\n", InterSegmentDistance4d());
          return 0;
    }

double dot(double * u, double * v)//scalar production of two vectors
    {
        return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];
    }

double abs(double * u)//length of vector
    {
        return sqrt(dot(u,u));
    }

double min(double a, double b, double c, double d)//minimal from four values
    {
        double m = a;
        if(m>b) m = b;
         if(m>c) m = c;
          if(m>d) m = d;
           return m;
    }

void diff(double * a, double * b, double * c)//difference of two 4d objects(points or vectors)
    {
        c[0]=a[0]-b[0];
        c[1]=a[1]-b[1];
        c[2]=a[2]-b[2];
        c[3]=a[3]-b[3];
    }

void summ(double * a, double * b, double * c)//sum of two 4d objects(points or vecrors)
    {
        c[0]=a[0]+b[0];
        c[1]=a[1]+b[1];
        c[2]=a[2]+b[2];
        c[3]=a[3]+b[3];
    }

void prod(double k, double * u, double * v)//production of number and vector
    {
        v[0] = k * u[0];
        v[1] = k * u[1];
        v[2] = k * u[2];
        v[3] = k * u[3];
    }

bool in(double s)//checking if the vatue is in [0,1]
    {
        return 0 <= s && s <= 1 ;
    }

bool in(double s, double t)//checking if the value is in [0,1]x[0,1]
    {
        return  in(t) && in(s);
    }

double sd(double s, double t)//distance between two points defined by two parameters s and t
    {
        double Pc[4], Qc[4], W[4];
        prod(s,u, Pc);
        prod(t,v, Qc);
         summ(Pc,P0, Pc);
         summ(Qc,Q0, Qc);
          diff(Qc, Pc, W);
           return  abs(W);
    }

double _(double s)//restrict a value s on the interval [0,1]
    {
        double s1 = s;
        if(s > 1)s1 = 1;
        if(s < 0)s1 = 0;
         return s1;
    }

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

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

#include "stdio.h"

#include <cmath>

double dot(double * u, double * v);

double abs(double * u);

double min(double a, double b, double c, double d);

void prod(double k, double * u, double * v);

void diff(double * a, double * b, double * c);

void summ(double * a, double * b, double * c);

bool in(double s);

bool in(double s, double t);

double sd(double s, double t);

double _(double s);

double P0[4],P1[4],Q0[4],Q1[4];

double u[4],v[4],w0[4];

double InterSegmentDistance4d()

//input: four 4d points P0, P1, Q0, Q1

// output: r = minimal distance between lines segments P0P1 and Q0Q1

{

double r = 0;

//calculation of three vectors

//u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0

diff(P1, P0, u); diff(Q1, Q0, v); diff(Q0, P0, w0);

//calculation of supporting scalar variables

//a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v

double a, b, c, d, e;

a = dot(u,u); // a=u^2;

b = dot(u,v);

c = dot(v,v); // c=v^2;

d = dot(u,w0);

e = dot(v,w0);

//calculation of main determinant

// D = b^2 - a*c

double D = b*b - a*c;

if (D == 0) //lines are parallel

{

double t0=-e/c;

double t1=-e/c;

double s0 = (-e+b)/c ;

double s1= (e-c)*b/(c*a);

if (in(t0) || in(t1) || in(s0) || in(s1))

{

double wq[4];

prod(e/c,v, wq); //projection w0 on line q

double wd[4];

diff(w0,wq, wd);

r = abs(wd);

return r ; //r = |w0 - wq|

}

//else minimal distance between segments equals minimal distance between ends of segments

r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));

return r;

}

// else lines are not parallel

{

//calculation of determinants

double D1 = b*e - c*d, D2 = a*e - b*d;

//calculation of parameters for minimal segment between lines

double sc = D1/D, tc = D2/D;

if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines

{

return r = sd(sc,tc); // r = |wc|

}

//else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]

{

double t1 = 0, s1=_(d/a);

double t2 = _(-2*e/c), s2=0;

double t3 = 1, s3=_(2*(b+d)/a);

double t4 = _(2*(b+e)/c), s4=0;

return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4));

}

int main()

{

scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);

scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);

scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);

scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);

printf("%lf\n", InterSegmentDistance4d());

return 0;

}

double dot(double * u, double * v)//scalar production of two vectors

{

return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];

}

double abs(double * u)//length of vector

{

return sqrt(dot(u,u));

}

double min(double a, double b, double c, double d)//minimal from four values

{

double m = a;

if(m>b) m = b;

if(m>c) m = c;

if(m>d) m = d;

return m;

}

void diff(double * a, double * b, double * c)//difference of two 4d objects(points or vectors)

{

c[0]=a[0]-b[0];

c[1]=a[1]-b[1];

c[2]=a[2]-b[2];

c[3]=a[3]-b[3];

}

void summ(double * a, double * b, double * c)//sum of two 4d objects(points or vecrors)

{

c[0]=a[0]+b[0];

c[1]=a[1]+b[1];

c[2]=a[2]+b[2];

c[3]=a[3]+b[3];

}

void prod(double k, double * u, double * v)//production of number and vector

{

v[0] = k * u[0];

v[1] = k * u[1];

v[2] = k * u[2];

v[3] = k * u[3];

}

bool in(double s)//checking if the vatue is in [0,1]

{

return 0 <= s && s <= 1 ;

}

bool in(double s, double t)//checking if the value is in [0,1]x[0,1]

{

return in(t) && in(s);

}

double sd(double s, double t)//distance between two points defined by two parameters s and t

{

double Pc[4], Qc[4], W[4];

prod(s,u, Pc);

prod(t,v, Qc);

summ(Pc,P0, Pc);

summ(Qc,Q0, Qc);

diff(Qc, Pc, W);

return abs(W);

}

double _(double s)//restrict a value s on the interval [0,1]

{

double s1 = s;

if(s > 1)s1 = 1;

if(s < 0)s1 = 0;

return s1;

}

Алгоритм и его обоснование

Расстояние между отрезками в четырехмерном пространстве находится по-разному, в зависимости от взаимного расположения этих отрезков. Тут мы можем выделить два основных случая:

Отрезки лежат на параллельных прямых или на одной прямой.
Отрезки лежат на пересекающихся либо на скрещивающихся прямых.

Чтобы выяснить, с каким случаем мы имеем дело, рассмотрим общую картину взаимного расположения отрезков и опишем ее математически:

По условию нам заданы 4 точки: [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] и [latex]D[/latex] — концы двух отрезков. Для удобства представления уравнений и точек, связанных с ними, обозначим их [latex]P_0[/latex], [latex]P_1[/latex], [latex]Q_0[/latex] и [latex]Q_1[/latex] соответственно. Через эти пары точек мы можем провести 2 прямые [latex]p[/latex] и [latex]q[/latex], параметрические уравнения которых имеют вид:

[latex]

\begin{matrix}
\vec p = P_0 + \vec u \cdot s \\
\vec q = Q_0 + \vec v \cdot t
\end{matrix}

[/latex],

где векторы:

[latex]

\begin{matrix}

\vec u = P_1 — P_0\\

\vec v = Q_1 — Q_0

\end{matrix}

[/latex],

а [latex]s[/latex] и [latex]t[/latex] — параметры. При [latex]s=0[/latex] или [latex] t=0[/latex] мы получаем начальную точку соответствующего отрезка, а при [latex]s=1[/latex] или [latex]t=1[/latex] — конечную. При произвольном значении параметра мы получаем произвольную точку на прямой.

Рассмотрим вектор [latex]\vec w = Q — P[/latex] , соединяющий 2 произвольные точки на этих прямых. Легко показать, что вектор [latex]\vec w[/latex] соединяет 2 ближайшие точки [latex]Q_c[/latex] и [latex]P_c[/latex] при условии:

[latex]\vec w \perp p[/latex] и [latex]\vec w \perp q[/latex].

Этому условию соответствует система из двух уравнений:

[latex] \begin{cases}
\vec u \cdot \vec w = 0\\
\vec v \cdot \vec w = 0
\end{cases}

[/latex]

Распишем ее для [latex]\vec w = Q_0 — P_0 + \vec v \cdot t — \vec u \cdot s = \vec w_0 + \vec v \cdot t — \vec u \cdot s[/latex] :
[latex]

\begin{cases}
\vec u \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0\\
\vec v \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0
\end{cases}

[/latex]

Введем вспомогательные скалярные переменные:
[latex]

\begin{matrix}

a&=&\vec u \cdot \vec u\\
b&=&\vec u \cdot \vec v\\
c&=&\vec v \cdot \vec v\\
d&=&\vec u \cdot \vec w_0\\
e&=&\vec v \cdot \vec w_0

\end{matrix}

[/latex]

Теперь наша система будет выглядеть так:

[latex]

\begin{cases}
d — a \cdot s + b \cdot t = 0 \\
e — b \cdot s + c \cdot t = 0
\end{cases}
[/latex]

Перепишем систему в удобном для нас виде:

[latex] \begin{cases}
a \cdot s — b \cdot t = d \\
b \cdot s — c \cdot t = e
\end{cases}
[/latex]

Решение этой системы мы можем получить, например, методом Крамера.

Главный определитель системы: [latex]D = b^2 — a \cdot c[/latex]

Два вспомогательных определителя:
[latex] \begin{matrix}
D_1 = b \cdot e — c \cdot d\\
D_2 = a \cdot e — b \cdot d\\
\end{matrix}
[/latex] Если [latex]D \neq 0[/latex], то существует единственное решение:

[latex]

\begin{cases}
s_c = \frac{D_1}{D} \\
t_c = \frac{D_2}{D}
\end{cases}
[/latex]

Если же мы получаем [latex]D = 0[/latex], легко показать, что отрезки параллельны. То есть мы имеем дело со случаем 1.

Тогда:

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

Найдем проекцию точки [latex]P_0[/latex] на линию [latex]q[/latex]. Для этого сначала найдем вектор, который является проекцией вектора [latex]\vec w_0[/latex] на линию [latex]q[/latex].

[latex]\vec w_q=(\vec w_0 \cdot \vec v) \cdot \frac{\vec v}{v^2}[/latex].
Конец полученного вектора находится в точке [latex]Q_0[/latex], а начало в новой точке [latex]P_{0q}=Q_0-\vec w_q[/latex]. Соединим точки [latex]P_0[/latex] и [latex]P_{0q}[/latex] вектором [latex]\vec w_p = P_{0q} — P_0[/latex]. Длина полученного вектора и будет искомым расстоянием: [latex]r = \left| P_0 P_{0q} \right|[/latex].

Для проверки условия а) необходимо получить проекции остальных исходных точек на отрезки:
[latex] \begin{matrix}
P_{1q} = P_{0q} + \vec u\\
Q_{0p} = P_0 + \vec w_q\\
Q_{1p} = Q_{0p} + \vec v
\end{matrix}
[/latex]

Если точка [latex]P_{0q}[/latex] лежит на прямой [latex]q[/latex], задаваемой уравнением:
[latex]\vec q = Q_0 + \vec v \cdot t[/latex],
то определить, принадлежит ли точка [latex]P_{0q}[/latex] отрезку [latex]Q_0 Q_1[/latex] можно, решив уравнение:
[latex]P_{0q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q + \vec v \cdot t[/latex].
Домножив обе части скалярно на вектор [latex]\vec v[/latex], мы получим уравнение: [latex] 0 = e + c \cdot t[/latex], отсюда [latex]t = \frac{-e}{c}[/latex].

Если [latex]t \in \left[0,1\right][/latex], то точка [latex]P_{0q}[/latex] лежит на отрезке [latex]Q_0 Q_1[/latex]. Если же нет, переходим к аналогичной проверке следующих точек:

[latex]P_{1q}:[/latex] [latex]P_{1q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q — \vec u + \vec v \cdot t[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec v[/latex], мы получим уравнение:

[latex] 0 = e — b + c \cdot t[/latex],
отсюда [latex]t = \frac{-e+b}{c}[/latex].
[latex]Q_{0p}:[/latex] [latex]Q_{0p} = P_0 + \vec u \cdot s[/latex].
[latex]0 =-\vec w_q + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec u[/latex], мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} + a \cdot s[/latex],
отсюда [latex]s = \frac{e \cdot b}{c \cdot a}[/latex].
[latex]Q_{1p}:[/latex] [latex]Q_{1p} = P_0 + \vec u \cdot s[/latex].
[latex] 0 = -\vec w_q — \vec v + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec u[/latex], мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} — b + a \cdot s[/latex],
отсюда [latex]s = \frac{(e — c) \cdot b}{c \cdot a}[/latex].
б) В противном случае, расстояние между отрезками равняется минимальному расстоянию между их концами. Здесь задача предельно упрощается. Мы находим длины отрезков, попарно соединяющих 4 исходные точки, и выбираем наименьший из них.

Если же исходные отрезки лежат на пересекающихся либо на скрещивающихся прямых, мы также рассматриваем 2 случая:

а) Оба конца кратчайшего отрезка, соединяющего прямые, лежат на соответствующих исходных отрезках:
[latex]P_c \in P_0 P_1[/latex] и [latex]Q_c \in Q_0 Q_1[/latex].

В этом случае пара параметров [latex](s_c, \; t_c)[/latex] принадлежит области: [latex](s,t):\left[0,1\right]\times \left[0,1\right].[/latex]

То есть, решение тривиально: ответом будет дина вектора [latex]\vec w_c[/latex]

б) Хотя бы один из концов кратчайшего отрезка, соединяющего прямые, не лежит на исходном отрезке, то есть:
[latex]P_c \not\in P_0 P_1[/latex] или [latex]Q_c \not\in Q_0 Q_1[/latex],
что соответствует значениям параметров [latex]s_c \not\in \left[0,1\right][/latex] или [latex]t_c \not\in \left[0,1\right][/latex].

В этом случае минимальное расстояние между отрезками определяется на границе области: [latex](s,t):\left[0,1\right]\times \left[0,1\right][/latex] (см. рисунок ниже):

Здесь решением является длина кратчайшего отрезка.

Длину отрезка, соединяющего 2 прямые, можно оценивать по квадрату длины вектора [latex]\vec v[/latex]: [latex]w^2=(\vec w)^2=(\vec w_0 — \vec u \cdot s + \vec v \cdot t)^2[/latex].

В частности, минимум [latex]w^2[/latex] достигается в точке [latex](s_c,t_c)[/latex].
Однако в случае б) мы должны найти минимум расстояния на границе нашей области, то есть решить задачу нахождения минимума при ограничениях (решить задачу условной минимизации). В нашем случае ограничения имеют очень простой вид — оси координат, и две линии, параллельные им. Поэтому мы можем решить на четырех границах 4 упрощенные задачи минимизации, а затем выбрать наименьшее решение.

Замечание: В пространстве параметров функция [latex]w^2(s,t)[/latex] представляет из себя эллиптический параболоид. Однако для простоты мы выше изобразили его линии уровня в виде окружностей. Типичный вид эллиптического параболоида и его линий уровня представлен на рисунках ниже:

Рассмотрим поочередно все 4 ограничения и решим задачу для них:

(1) Пусть [latex]t=t_1=0[/latex].

Тогда: [latex]{w^2\mid_{t_1=0}} = (\vec w_0-\vec u \cdot s_1)^2[/latex].

Для определения экстремума приравняем производную к нулю:[latex] \begin{array}{r}
\frac{d}{ds_1}{(\vec w_0-\vec u \cdot s_1)^2}=0\\
2 \cdot (\vec w_0-\vec u \cdot s_1) \cdot (- \vec u)=0\\
-d +a \cdot s_1=0\\
s_1=\frac{d}{a}
\end{array}
[/latex]

Легко показать, что при [latex]s_1>1[/latex] мы должны присвоить ему значение [latex]s_1=1[/latex], а если [latex]s<0[/latex] — значение [latex]s_1=0[/latex], так как мы не должны выходить за границы исходных отрезков.

Подставим полученное значение [latex]s[/latex] в уравнение прямой [latex]p[/latex] для точки [latex]P_c[/latex]:[latex]P_c = P_0 + \vec u \cdot s.[/latex]

А точка [latex]Q_c[/latex] совпадает с точкой [latex]Q_0[/latex]. Тогда первый минимум равен: [latex]r_1 = Q_0 P_c[/latex].

Аналогично найдем три остальных минимума [latex]r_2, r_3, r_4[/latex], приравняв [latex]s[/latex] к нулю, а затем [latex]t[/latex] и [latex]s[/latex] к единице. Наименьший из них и есть искомое расстояние [latex]r[/latex].

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

Related Images:

А410е

25/12/2014 by Носуленко Марк

Дана целочисленная матрица [latex][a_{ij}], ij=1,\ldots,n.[/latex] Получить [latex]b_{1},\ldots,b_{n}[/latex], где [latex]b_{i}[/latex] — это: [latex]\underset{1\leq j\leq n}{\max a_{ij}}\cdot \underset{1\leq j\leq n}{\min a_{ji}}[/latex].

Исходя из задачи ясно, что из данной матрицы надо взять максимальный элемент [latex]i[/latex]-й строки и умножить его на минимальный элемент [latex]i[/latex]-го столбца. Так например, если нам дана матрица 2-го порядка [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] то [latex]b_{1}= 2[/latex], [latex]b_{2}= 4[/latex].

Для нахождения максимума [latex]a_{ij}[/latex], введем переменную и будем придавать ей начальное значение 1-го элемента [latex]i[/latex]-й строки. Дабы при расчете максимума проходя по элементам строки мы не сравнивали каждый [latex]i[/latex]-й элемент с 1-м, придавать начальное значение максимуму мы будем в цикле по [latex]i[/latex]. Аналогично с минимумом [latex]a_{ji}[/latex], одно единственное но, начальное значение минимума будет равно первому элементу [latex]i[/latex]-го столбца.

Тесты:

Матрица порядка [latex]n[/latex], где [latex]n[/latex]:	[latex]a[i][j][/latex]:	Результат:	Комментарий:
2	[latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex]	2 4	Пройден.
3	[latex]\begin{Vmatrix}1&2&3\\4&1&-6\\1&-2&-1\end{Vmatrix}[/latex]	3 -8 -6	Пройден.

#include <iostream>
using namespace std;
int main() {
    int n,maxa,mina;
    cin >>n;
    int a[n][n];
    for(int i=0; i<n;++i){
        for(int j=0;j<n;++j){
            cin >>a[i][j];
        }
    }
    int b[n];
    for(int i=0;i<n;++i){
        maxa=a[i][0]; //Придаем максимуму значение первого элемента i-й строки.
        mina=a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.
        for(int j=0;j<n;++j){
            maxa=(maxa>a[i][j]?maxa:a[i][j]); //Вычисляем максимум i-й строки.
            mina=(mina<a[j][i]?mina:a[j][i]); //Минимум i-го столбца.
        }
        b[i]=maxa*mina; //Наш результат.
    }   for(int i=0;i<n;++i){
        cout <<b[i]<<" ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,maxa,mina;

cin >>n;

int a[n][n];

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

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

cin >>a[i][j];

}

int b[n];

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

maxa=a[i][0]; //Придаем максимуму значение первого элемента i-й строки.

mina=a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.

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

maxa=(maxa>a[i][j]?maxa:a[i][j]); //Вычисляем максимум i-й строки.

mina=(mina<a[j][i]?mina:a[j][i]); //Минимум i-го столбца.

}

b[i]=maxa*mina; //Наш результат.

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

cout <<b[i]<<" ";

}

return 0;

}

Ссылка на код.

Related Images:

Ю11.15

29/10/2014 by Ілларіонова Марія Валеріївна

Метод парабол. Найти минимум заданной функции [latex]y=f(x)[/latex], двигаясь от заданной точки [latex]x_{0}[/latex] по методу парабол:

[latex]x_{i+1}=x_{i}-\frac{h}{2}\frac{f\left( x_{i}+h\right)-f\left( x_{i}-h\right)}{f\left( x_{i}+h\right)-2f\left( x_{i}\right)+f\left( x_{i}-h\right)}, i=0,1,\ldots[/latex], пока не будет достигнута заданная точность.

Функция [latex]x^{3}+10\sin (5x)[/latex]:

[latex]x_{0}[/latex]	[latex]\varepsilon[/latex]	Точка минимума по графику.	Точка минимума по программе.	Комментарий.
0	0,001	-0,315353	-0,315353	Тест пройден.
1	0,0001	0,932048	0,932048	Тест пройден.
2	0,0001	2,14327	2,14327	Тест пройден.
-3	0,01	-2,93616	-2,93616	Тест пройден.
-2	0,0001	-1,6017	-1,6017	Тест пройден.

Код программы (C++):

Для функции [latex]x^{3}+10\sin (5x)[/latex] (функцию всегда можно изменить, достаточно исправить строку 6):

#include <iostream>
#include <math.h>
using namespace std;

double f(double x) {
    return x*x*x+10*sin(5*x);
}

int main() {
    double h=0.001;
    double x, pogr;
    cin >> x >> pogr;
    if (x==0) x+=0.1;
    while ((f(x+h)-2*f(x)+f(x-h))/(h*h)<=0) x+=0.1;
    double x1;
    x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));
    while (fabs(x1-x)>pogr) {
        x=x1;
        x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));
    }
    cout << x1;
    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

double f(double x) {

return x*x*x+10*sin(5*x);

}

int main() {

double h=0.001;

double x, pogr;

cin >> x >> pogr;

if (x==0) x+=0.1;

while ((f(x+h)-2*f(x)+f(x-h))/(h*h)<=0) x+=0.1;

double x1;

x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));

while (fabs(x1-x)>pogr) {

x=x1;

x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));

}

cout << x1;

return 0;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
    public static double f (double x) {
        return x*x*x+10*Math.sin(5*x);
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in =  new Scanner (System.in);
        double h=0.001;
        double x, pogr;
        x=in.nextDouble();
        pogr=in.nextDouble();
        if (x==0) x+=0.1;
        while ((f(x+h)-2*f(x)+f(x-h))/(h*h)<=0) x+=0.1;
        double x1;
        x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));
        while (Math.abs(x1-x)>pogr) {
            x=x1;
            x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));
        }
        System.out.format ("%f%n", x1);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static double f (double x) {

return x*x*x+10*Math.sin(5*x);

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner (System.in);

double h=0.001;

double x, pogr;

x=in.nextDouble();

pogr=in.nextDouble();

if (x==0) x+=0.1;

while ((f(x+h)-2*f(x)+f(x-h))/(h*h)<=0) x+=0.1;

double x1;

x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));

while (Math.abs(x1-x)>pogr) {

x=x1;

x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));

}

System.out.format ("%f%n", x1);

}

Чтобы сделать программу, я почитала “Численные методы” Н. Н. Калиткина, где и было сказано, что в качестве вспомогательного шага [latex]h[/latex] при расчётах на ЭВМ обычно выбирают значение 0,001.

Далее пользователю предоставляется возможность ввести значение [latex]x_{0}[/latex] и задать точность [latex]\varepsilon[/latex]. Корень [latex]x[/latex] является минимумом функции тогда и только тогда, когда вторая производная этой функции больше 0. Поэтому мы запускаем цикл, который будет сдвигать наше [latex]x_{0}[/latex] в положительном направлении оси [latex]x[/latex], пока вторая производная функции не будет удовлетворять условию задачи.

Далее мы вычисляем значение [latex]x_{i+1}[/latex], и запускаем цикл, который будет продолжаться до тех пор, пока разница между [latex]x_{i}[/latex] и [latex]x_{i+1}[/latex] не будет меньше заданной погрешности [latex]\varepsilon[/latex].

Затем на экран выводится сама точка минимума функции.

Программу можно посмотреть здесь (C++) и здесь (Java).

Related Images:

А170

28/10/2014 by Байков Дмитро

Задача. Даны натуральные числа [latex]n, a_{1}, a_{2},\ldots, a_{n} (n\geq 4)[/latex]. Числа [latex]a_{1}, a_{2},\ldots , a_{n}[/latex] — это измеренные в сотых долях секунды результаты [latex]n[/latex] спортсменов в беге на [latex]100[/latex] м. Составить команду из четырёх лучших бегунов для участия в эстафете [latex]4\times100[/latex], т.е. указать одну из четверок натуральных чисел [latex]i, j, k, l[/latex], для которой [latex]1\leq i\leq j\leq k\leq l\leq n[/latex] и [latex]a_{i} + a_{j}+a_{k} + a_{l}[/latex] имеет наименьшее значение.

Тесты

n	c	Результаты бега спортсменов	Номера спортсменов, избранных для команды	Комментарий
6	3	11.77 12.34 12.14 11.15 11.16 11.40	4 5 6	Пройден
6	4	11.68 0 12.15 11.54 11.26 11.00	Введен отрицательный или нулевой результат	Не пройден
6	2	11.68 -12.34 12.14 11.55 11.29 11.00	Введен отрицательный или нулевой результат	Не пройден

Код программы на C++:

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

int mini(double x[],int n) //Функция, которая возвращает номер бегуна с наилучшим результатом.
{ 
   double minn = numeric_limits<double>::infinity(); int mini;
	for (int i = 0; i < n ; i ++)//Цикл для нахождения минимального значения.
	{
		double t = x[i];
		if (t <= minn) 
		{
			mini = i;
			minn = t;
		}
	}
	return mini; //Возвращение номера минимального значения
} 
 
void team(double x[], int n, int c)//Функция выводящая на экран номера наилучших спортсменов.
{
	int counters[c]; //Массив номеров бегунов.
	for (int i = 0; i < c ; i ++)
	{
		counters[i] = mini( x , n );
		x[ counters[i] ] = numeric_limits<double>::infinity();
	}
	sort(counters, counters + c); //Сортировка номеров бегунов
	for (int i = 0; i < c ; i ++)
	{
		cout<<counters[i] + 1 <<" ";
	}
}

int main() 
{
	int n, c, k = 0; //Описание переменных для хранения входных данных./
	cin>>n>>c;
	double x[n]; //Описание массива для хранения входных данных.//
	for (int i = 0; i < n ; i ++)
	{
		cin>>x[i];
		if (x[i] <= 0)  //Проверка массива на отрицательный (либо нулевой) элемент.
		{
			cout<<"Введен отрицательный или нулевой результат";
			return 0;
		}
	}
	team(x, n ,c);
	return 0;
}

#include <iostream>

#include <algorithm>

#include <limits>

using namespace std;

int mini(double x[],int n) //Функция, которая возвращает номер бегуна с наилучшим результатом.

{

double minn = numeric_limits<double>::infinity(); int mini;

for (int i = 0; i < n ; i ++)//Цикл для нахождения минимального значения.

{

double t = x[i];

if (t <= minn)

{

mini = i;

minn = t;

}

return mini; //Возвращение номера минимального значения

}

void team(double x[], int n, int c)//Функция выводящая на экран номера наилучших спортсменов.

{

int counters[c]; //Массив номеров бегунов.

for (int i = 0; i < c ; i ++)

{

counters[i] = mini( x , n );

x[ counters[i] ] = numeric_limits<double>::infinity();

}

sort(counters, counters + c); //Сортировка номеров бегунов

for (int i = 0; i < c ; i ++)

{

cout<<counters[i] + 1 <<" ";

}

int main()

{

int n, c, k = 0; //Описание переменных для хранения входных данных./

cin>>n>>c;

double x[n]; //Описание массива для хранения входных данных.//

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

{

cin>>x[i];

if (x[i] <= 0) //Проверка массива на отрицательный (либо нулевой) элемент.

{

cout<<"Введен отрицательный или нулевой результат";

return 0;

}

team(x, n ,c);

return 0;

}

В этой задаче необходимо было найти номера лучших бегунов, для создания из них команды. Размер команды вводим сразу же после общего количества бегунов с клавиатуры. Для нахождения номеров бегунов нам потребуется функция mini, которая находит минимальный элемент массива и возвращает его значение, а также функция team, вызывающая функцию mini. В функции team уже создан массив номеров бегунов, в который мы вначале введем данные и отсортируем его по возрастанию. Также будем выводить номер этого минимального элемента на экран, прибавляя 1 (как бы считая бегунов с 1, а не с 0), и присваивать этому (найденному) элементу массива какое-то большое значение для того, чтобы при следующей проверке программа не считала его минимальным элементом, а находила следующий минимальный.

В строках

for (int i = 0; i < n ; i ++)
{
	cin>>x[i];
	if (x[i] <= 0)  //Проверка массива на отрицательный (либо нулевой) элемент.
	{
		cout<<"Введен отрицательный или нулевой результат";
		return 0;
	}
}

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

{

cin>>x[i];

if (x[i] <= 0) //Проверка массива на отрицательный (либо нулевой) элемент.

{

cout<<"Введен отрицательный или нулевой результат";

return 0;

}

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

В конечном итоге, применяем функцию team и получаем, собственно, ответ.

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

import java.util.*;
import java.lang.*;
import java.io.*;

class Runners
{
	public static void main (String[] args) throws java.lang.Exception
	{
		//Описание переменных для хранения входных данных./
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int c = in.nextInt();
		int[] counters = new int[c]; //Массив номеров бегунов.
		int k = 0; 
		double[] x = new double[n]; //Описание массива для хранения входных данных.//
		for (int i = 0; i < n; i++)
			x[i] = in.nextDouble();
		for (int i = 0; i < c; i++)
		{
			double minn = Double.POSITIVE_INFINITY; int mini = 0;
			for (int j = 0; j < n; j++) //Цикл для нахождения минимального значения.
			{
				if (x[j] <= minn) 
				{
					mini = j;
					minn = x[j];
				}
			}
			counters[i] = mini;
			x[counters[i]] = Double.POSITIVE_INFINITY;
		}
		Arrays.sort(counters, 0, c); //Сортировка номеров бегунов
		for (int i = 0; i < c ; i ++)
			System.out.printf(counters[i] + 1 + " ");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Runners

{

public static void main (String[] args) throws java.lang.Exception

{

//Описание переменных для хранения входных данных./

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int c = in.nextInt();

int[] counters = new int[c]; //Массив номеров бегунов.

int k = 0;

double[] x = new double[n]; //Описание массива для хранения входных данных.//

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

x[i] = in.nextDouble();

for (int i = 0; i < c; i++)

{

double minn = Double.POSITIVE_INFINITY; int mini = 0;

for (int j = 0; j < n; j++) //Цикл для нахождения минимального значения.

{

if (x[j] <= minn)

{

mini = j;

minn = x[j];

}

counters[i] = mini;

x[counters[i]] = Double.POSITIVE_INFINITY;

}

Arrays.sort(counters, 0, c); //Сортировка номеров бегунов

for (int i = 0; i < c ; i ++)

System.out.printf(counters[i] + 1 + " ");

}

Related Images:

Horse-racing Duals

16/10/2014 by Вустянюк Ігор Дмитрович

Horses2

Задача

Рассмотрим последнюю задачу уровня Easy с сайта codingame.com. Некоторое количество лошадей участвует в скачках и у каждой есть некая характеристика, выраженная целым числом. Формат скачек — парные заезды — и организаторы хотят, чтобы в заезде участвовали две лошади, различие между которыми (т.е. разность их характеристик) минимальна.

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

Первая строка: число n — количество лошадей.

Следующие n строк — в каждой указано одно целое число — характеристика соответствующей лошади.

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

Наименьшая положительная разность характеристик.

Решение

Пусть задана конечная последовательность целых чисел a. В исходной формулировке задачи, без каких-либо оптимизаций, от нас требуют найти [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right|[/latex]. Если решать задачу в лоб, нам понадобятся два цикла: один пробегает все значения по i, а другой — все значения по [latex] j > i [/latex]. На каждом шаге внешнего цикла будет проделано [latex] n — i [/latex] шагов внутреннего. Итого получаем приблизительную оценку сложности такого алгоритма: [latex] n\left( n — i \right)[/latex], что асимптотически эквивалентно [latex] n^2 [/latex].

Оказывается, можно решить задачу «проще». Как утверждают авторитетные источники, сложность встроенного в стандартную библиотеку алгоритма сортировки составляет [latex] O(n \cdot \log \left( n \right) [/latex], что при больших значениях n лучше, чем [latex] n^2 [/latex]. Пусть b — конечная последовательность, в которой элементы последовательности a расположены по возрастанию. Поскольку множество значений у этих последовательностей одинаково, имеем: [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right| [/latex]. Однако нам уже не нужен двойной цикл. Благодаря монотонному возрастанию последовательности b, при любом [latex] i [/latex] имеем [latex] b_{i+1} — b_{i} > 0 [/latex] и при любых [latex] i,j [/latex] если [latex]i < j[/latex], то [latex] b_{j} — b_{i} \geq b_{i+1} — b_{i}[/latex].

Значит, [latex] D = min_{1 \leq i \leq n} \left( b_{i+1} — b_{i} \right) [/latex], а эту проверку можно провести за n действий. Таким образом, новая сложность составит примерно [latex] n \cdot log(n) + n [/latex], что асимптотически эквивалентно [latex] n \cdot log(n) [/latex] и, значит, для больших значений лучше «безоптимизационного» подхода.

Код на С++

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
	int n;	// Количество лошадей
	cin >> n;
	int horses[n];	
	for (int i = 0; i < n; i++) {	// Помещаем характеристики лошадей
		cin >> horses[i];			// в массив
	}	
	std::sort(horses, horses + n);	// Сортируем массив horses по возрастанию
	int min_dif = horses[1] - horses[0];
	for (int i = 1; i < n - 1; i++) {	// Поиск минимальной разницы характеристик
	    int cur_dif = horses[i+1] - horses[i];
	    if (cur_dif < min_dif)
	        min_dif = cur_dif;
	}
	cout << min_dif;
	return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

int main()

{

int n; // Количество лошадей

cin >> n;

int horses[n];

for (int i = 0; i < n; i++) { // Помещаем характеристики лошадей

cin >> horses[i]; // в массив

}

std::sort(horses, horses + n); // Сортируем массив horses по возрастанию

int min_dif = horses[1] - horses[0];

for (int i = 1; i < n - 1; i++) { // Поиск минимальной разницы характеристик

int cur_dif = horses[i+1] - horses[i];

if (cur_dif < min_dif)

min_dif = cur_dif;

}

cout << min_dif;

return 0;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] horses = new int[n];
		for (int i = 0; i < n; i++)
			horses[i] = in.nextInt();
		Arrays.sort(horses);
		int min_dif = horses[1] - horses[0];
		for (int i = 1; i < n-1; i++) {
			int cur_dif = horses[i+1] - horses[i];
			if (cur_dif < min_dif)
				min_dif = cur_dif;
		}
		System.out.println(min_dif);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[] horses = new int[n];

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

horses[i] = in.nextInt();

Arrays.sort(horses);

int min_dif = horses[1] - horses[0];

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

int cur_dif = horses[i+1] - horses[i];

if (cur_dif < min_dif)

min_dif = cur_dif;

}

System.out.println(min_dif);

}

Подтверждение

Related Images:

Temperatures

14/10/2014 by Вустянюк Ігор Дмитрович

Задача взята с сайта codingame.com

Задача.

Задан набор целых чисел (значения температуры за различные моменты времени). Нужно вывести из них ближайшее к нулю.

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

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

Вывести нуль, если [latex] N = 0[/latex]. В противном случае вывести число, ближайшее к нулю, причём если два числа разных знаков одинаково близки к нулю, нужно вывести положительное.

Решение.

Сначала отфильтруем случай, когда [latex] N = 0[/latex]. В этом случае, как от нас и требуют, напечатаем нуль.

Если же [latex] N > 0 [/latex], прибегнем к уже знакомому нам приёму. Введём новую переменную — min — и присвоим ей первое число. Затем в цикле for будем эту переменную менять, если наткнёмся число, более близкое к нулю, чем хранящееся в min. Вот основной вопрос: когда нам нужно менять min? «Число [latex] a [/latex] ближе к нулю, чем число [latex] b [/latex]» означает, что [latex] a [/latex] по модулю меньше, чем [latex] b [/latex]. Значит, если число, прочитанное на текущем шаге цикла, по модулю строго меньше, чем число, хранящееся в min, переменную min нужно обновить. Но есть ещё один случай, когда переменную min следует обновить — это тот случай, когда текущее число положительно и столь же близко к нулю, как и число, хранящееся в min. Это действие даёт нам гарантию того, что если два числа разных знаков одинаково близки к нулю, будет выведено положительное.

Код на С++

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main()
{
	int N;
	cin >> N;
	if (N == 0)
        cout << 0 << endl;
    else {
        int min, temp;
        cin >> min;
        for (int i = 1; i < N; i++) {
            cin >> temp;
            if ((abs(temp) < abs(min)) || (temp == abs(min)))
                min = temp;
	    }
	    cout << min;
    }
	return 0;
}

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

int main()

{

int N;

cin >> N;

if (N == 0)

cout << 0 << endl;

else {

int min, temp;

cin >> min;

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

cin >> temp;

if ((abs(temp) < abs(min)) || (temp == abs(min)))

min = temp;

}

cout << min;

}

return 0;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		if (N == 0)
			System.out.println(0);
		else {
			int min = in.nextInt(), temp;
			for (int i = 1; i < N; i++) {
				temp = in.nextInt();
				if ((Math.abs(temp) < Math.abs(min)) || (temp == Math.abs(min)))
					min = temp;
			}
			System.out.println(min);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int N = in.nextInt();

if (N == 0)

System.out.println(0);

else {

int min = in.nextInt(), temp;

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

temp = in.nextInt();

if ((Math.abs(temp) < Math.abs(min)) || (temp == Math.abs(min)))

min = temp;

}

System.out.println(min);

}

P.S.. Возможно, усложнив оператор ветвления можно сделать алгоритм более эффективным за счёт уменьшения числа сравнений или присваиваний.