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 9081. Автомобілі

30/11/2019 by Артем Рогулин

Завдання

Троє водіїв вирішили опробувати нове шосе. Перший їхав зі сталою швидкістю $v_1$ км/год. протягом $t_1$ годин. Другий їхав зі сталою швидкістю $v_2$ км/год. протягом $t_2$ годин, третій – зі сталою швидкістю $v_3$ км/год. протягом $t_3$ годин. Хто з них проїхав найдовший шлях?

Вхідні дані

В одному рядку через пропуск ввести на стандартний пристрій введення значення $v_1$, $v_2$, $v_3$, $t_1$, $t_2$, $t_3$. Інтервал значень швидкостей – від $30$ до $100$ км/год. включно. Час у дорозі – з інтервалу $[1;15]$ годин.

Вихідні дані

Якщо найдовший шлях проїхав один водій, вивести на стандартний пристрій введення номер водія. Якщо найдовший шлях проїхали два або три водія, треба ввести в одному рядку через пропуск їх номери у порядку зростання.

Тести

№	Вхідні дані	Вихідні дані
1.	38 9 54 5 62 3	1
2.	30 9 45 6 90 3	1 2 3
3.	30 15 45 5 50 9	1 3
4.	50 6 42 14 84 7	2 3

Код програми

#include <iostream>
using namespace std;
 
int main() {
    int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв
    int t1, t2, t3; // Час, який вони їхали
    int s1, s2, s3; // І відстань
    int max_; // Також, змінну, де буде зберігатися максимальна відстань
    cin >> v1 >> t1; // Прочитуємо швидкість і час для кожного водія
    cin >> v2 >> t2; 
    cin >> v3 >> t3;
    s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них
    s2 = v2 * t2; 
    s3 = v3 * t3;
    max_ = max(max(s1, s2), s3); // Виявляємо максимальну відстань
    if ( s1 == max_ )  // Перевіряючи, чи є пройдена відстань максимальною
        cout << "1 "; // Виводимо номер відповідного водія
    if ( s2 == max_ )
        cout << "2 ";
    if ( s3 == max_ )
        cout << 3;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв

int t1, t2, t3; // Час, який вони їхали

int s1, s2, s3; // І відстань

int max_; // Також, змінну, де буде зберігатися максимальна відстань

cin >> v1 >> t1; // Прочитуємо швидкість і час для кожного водія

cin >> v2 >> t2;

cin >> v3 >> t3;

s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них

s2 = v2 * t2;

s3 = v3 * t3;

max_ = max(max(s1, s2), s3); // Виявляємо максимальну відстань

if ( s1 == max_ ) // Перевіряючи, чи є пройдена відстань максимальною

cout << "1 "; // Виводимо номер відповідного водія

if ( s2 == max_ )

cout << "2 ";

if ( s3 == max_ )

cout << 3;

return 0;

}

Пояснення

Відповіддю до задачі є номери водіїв, що проїхали максимальну відстань. Для цього треба використати формулу, знайому всім ще зі школи: $S = Vt$. Після знаходження відстані пройденої кожним водієм, ми знаходимо максимальну серед них. Далі нам залишається тільки виводити у порядку зростання номери водіїв, які пройшли максимальну відстань.

Примітка: Швидкість і час вводяться попарно для кожного водія.

Посилання

Related Images:

e-olymp 845. Открытка и конверт

25/06/2019 by Максим Евчук

Задача

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

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

В первой строке находятся размеры открытки, во второй — размеры конверта. Размеры открытки и конверта — целые положительные числа, не превосходящие $100.$

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

Если открытку можно вложить в конверт, вывести $Possible,$ если нет — вывести $Impossible$.

Тесты

№	Входные данные	Выходные данные
1	1 10 9 9	Possible
2	20 40 2 4	Possible
3	50 20 40 40	Impossible
4	10 4 5 5	Impossible

#include <cmath>

#include <iostream>

using namespace std;

int main() {
  int H, W, h, w, t, d2;
  cin >> h >> w >> H >> W;
  if (W < H) {
    t = W;
    W = H;
    H = t;
  }
  if (h >= w) {
    t = h;
    h = w;
  } else t = w;
  d2 = t * t + h * h;
  if (h <= H and t <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= t * t - h * h) cout << "Possible";
  else cout << "Impossible";
  return 0;
}

#include <cmath>

#include <iostream>

using namespace std;

int main() {

int H, W, h, w, t, d2;

cin >> h >> w >> H >> W;

if (W < H) {

t = W;

W = H;

H = t;

}

if (h >= w) {

t = h;

h = w;

} else t = w;

d2 = t * t + h * h;

if (h <= H and t <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= t * t - h * h) cout << "Possible";

else cout << "Impossible";

return 0;

}

Второй способ решения

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

int main() {
  int H, W, h, w;
  cin >> h >> w >> H >> W;
  int t = max(H, W);
  H = min(H, W);
  W = t;
  t = max(h, w);
  h = min(h, w);
  w = t;
  int d2 = w * w + h * h;
  if (h <= H and w <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= w * w - h * h)
    cout << "Possible";
  else cout << "Impossible";
  return 0;
}

#include <cmath>

#include <iostream>

using namespace std;

int main() {

int H, W, h, w;

cin >> h >> w >> H >> W;

int t = max(H, W);

H = min(H, W);

W = t;

t = max(h, w);

h = min(h, w);

w = t;

int d2 = w * w + h * h;

if (h <= H and w <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= w * w - h * h)

cout << "Possible";

else cout << "Impossible";

return 0;

}

Код без условных операторов

#include <cmath> 
#include 

#include 

using namespace std;

int main() {
  int H, W, h, w;
  cin >> h >> w >> H >> W;
  int t = max(H, W);
  H = min(H, W);
  W = t;
  t = max(h, w);
  h = min(h, w);
  w = t;
  int d2 = w * w + h * h;
  (h <= H and w <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= w * w - h * h) and cout << "Possible";
  !(h <= H and w <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= w * w - h * h) and cout << "Impossible";
  return 0;
}

#include <cmath>

#include

using namespace std;

int main() {

int H, W, h, w;

cin >> h >> w >> H >> W;

int t = max(H, W);

H = min(H, W);

W = t;

t = max(h, w);

h = min(h, w);

w = t;

int d2 = w * w + h * h;

(h <= H and w <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= w * w - h * h) and cout << "Possible";

!(h <= H and w <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= w * w - h * h) and cout << "Impossible";

return 0;

}

Решение
Объявляем и вводим переменные $H$, $W$, $h$, $w$, где будем хранить длины открыток и конверта. Потом находим наибольшую сторону конверта и открытки, найдем диагональ конверта. Пользуясь тем, что мы знаем точно какие варианты «Possible» ставим выводим их, а в противном случае «Impossible».Утверждение: если выполняются четыре тривиальных неравенства: — то открытку в конверт можно вставить тогда и только тогда, когда можно расположить один из противоположных концов открытки на нижнем основании конверта, а второй — на верхнем и при этом открытка помещается в конверт. Из утверждения следует, что открытку нужно «поднять» на максимальный угол и посмотреть, входит ли открытка в таком положении в конверт, то есть меньше ли горизонтальное измерение «поднятой» открытки, чем ширина конверта.

Ссылки

ideone
e-olymp
e-olymp
ideone
ideone (без условных операторов)
e-olymp

Related Images:

e-olymp 657. Игра с монетами

22/06/2019 by Богдан Подгорный

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

Условие

Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более $ K$ стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.

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

В первой строке находится сначала число стопок $ N,$ за ним идут $ N$ чисел, задающих количество монет в стопках слева направо, а затем число $ K.$ Все числа в строке разделены пробелами.
$ 1 \leqslant N \leqslant 180, 1 \leqslant K \leqslant 80,$ количество монет в стопке — не менее $ 1$ и не более $ 20 000$.

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

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

Тесты

№	Inputs	Outputs
1	3 4 9 1 3	14
2	4 1 2 2 7 3	5
3	5 3 4 8 1 7 2	18
4	12 67 8 6 12 6 90 54 89 145 32 45 65 4	357
5	14 32 53 5 52 9 8 17 5 87 44 51 12 15 56 10	312
6	14 76 112 3 1 98 4 172 33 65 90 2 71 18 32 14	777

Код

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

int sum[190][90][3];

int solution(vector<int>&arr, int l, int k, int p){
    if(sum[l][k][p]){
        return sum[l][k][p];
    }
    int ans = 0;
    if(arr.size() - l <= k){
        for(int i = l; i < arr.size(); i++){
            ans += arr[i];
        }
        if(p == 2){
            sum[l][k][p] = 0;
            return sum[l][k][p];
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
    if(p == 1){
        int temp = 0;
        for(int i = 1; i <= k; i++){
            temp += arr[(l-1) + i];
            ans = max(ans, temp + solution(arr, l+i, i, 3-p));
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
    else{
        int ans = INT_MAX;
        for(int i = 1; i <= k; i++){
            ans = min(ans, solution(arr, l+i, i, 3-p));
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
}

int main() {
    int n, k, a;
    vector<int> coins;
    cin >> n;
    for(int i = 0; i > a;
        coins.push_back(a);
    }
    cin >> k;
    cout << solution(coins, 0, k, 1);
    return 0;
}

#include <iostream>

#include <vector>

#include <limits.h>

using namespace std;

int sum[190][90][3];

int solution(vector<int>&arr, int l, int k, int p){

if(sum[l][k][p]){

return sum[l][k][p];

}

int ans = 0;

if(arr.size() - l <= k){

for(int i = l; i < arr.size(); i++){

ans += arr[i];

}

if(p == 2){

sum[l][k][p] = 0;

return sum[l][k][p];

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

if(p == 1){

int temp = 0;

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

temp += arr[(l-1) + i];

ans = max(ans, temp + solution(arr, l+i, i, 3-p));

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

else{

int ans = INT_MAX;

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

ans = min(ans, solution(arr, l+i, i, 3-p));

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

int main() {

int n, k, a;

vector<int> coins;

cin >> n;

for(int i = 0; i > a;

coins.push_back(a);

}

cin >> k;

cout << solution(coins, 0, k, 1);

return 0;

}

Решение

Анализируя задачу, становится понятно, что ее можно решить методами динамического программирования, а именно трехмерная динамика по параметрам: количество уже взятых стопок — l, количество стопок, которые можно взять kи какой игрок сейчас ходит p. Каждый игрок старается ходить оптимально, тогда для первого игрока задача взять максимальное количество монет, а для второго игрока задача оставить наименьшее количество монет оппоненту. Решение исполнено с помощью рекурсии, где терминальный случай-когда в массиве осталось количество стопок, меньшее или равное тому, сколько игрок может взять. Также стоит проверять высчитывалась ли раньше данная позиция, иначе задача не зайдет по времени.

Ссылки

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 891. Покупка цветов

14/10/2018 by Иван Киреев

Задача. Покупка цветов

На День учителя Вася решил купить букет цветов. В магазине продаются ромашки по $a$ рублей за штуку и гладиолусы по $b$ рублей за штуку ($a < b$). У Васи есть $c$ рублей. Он хочет составить букет из максимально возможного количества цветов, и при этом потратить как можно больше денег. Другими словами, из всех букетов с максимально возможным количеством цветов он хочет выбрать самый дорогой, но не дороже $c$ рублей. Помогите ему вычислить стоимость такого букета.

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

Три целых числа $a$, $b$, $c$ ($1 ≤ a < b ≤ 100, 0 ≤ c ≤ 1000$).

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

Выведите одно число — стоимость самого дорогого букета из максимального количества цветов.

Тесты

№	Ввод	Вывод
1	5 7 0	0
2	3 5 10	9
3	2 3 11	11
4	48 64 306	304
5	17 20 100	100
6	13 15 260	260
7	29 53 999	986
8	17 28 16	0
7	75 100 1000	1000

Решение

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

Далее, что бы найти решение для оставшихся вариантов, необходимо найти наибольшую сумму стоимостей максимального количества цветов не превышающую $c$ рублей. Максимальное количество цветов n будет равно количеству цветов с минимальной стоимостью которое можно купить за имеющиеся у Васи деньги. ($c / a$).

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

Код

#include <iostream>
using namespace std;

int main() {
    int a, b, c, max;
    cin >> a >> b >> c;
    if (c % a == 0) max = c;
    else {
        int n = c / a; // максимальное количество цветков
        max = 0;
        for (int i = 0; i <= (n / 2) && max != c; i++) {
            int first = (n - i) * b +  i * a;
            if (first > max && first <= c) max = first;
            int second = (n - i) * a +  i * b;
            if (second > max && second <= c) max = second;
        } 
    }
    cout << max;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c, max;

cin >> a >> b >> c;

if (c % a == 0) max = c;

else {

int n = c / a; // максимальное количество цветков

max = 0;

for (int i = 0; i <= (n / 2) && max != c; i++) {

int first = (n - i) * b + i * a;

if (first > max && first <= c) max = first;

int second = (n - i) * a + i * b;

if (second > max && second <= c) max = second;

}

cout << max;

return 0;

}

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

Решение

Код на ideone

Related Images:

e-olymp 93. Truck driving

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

Task

Umidsh Izadish is a truck driver and wants to drive from a city to another city while there exists a dedicated straight road between each pair of cities in that country. Amount of consumed fuel is the distance between two cities which is computed from their coordinates. There is a gas station in each city, so Umidsh can refuel the gas container of his truck. Your job is to compute the minimum necessary volume of gas container of Umidsh’s Truck.

Input data

The first line of input contains an integer, the number of test cases. Following, there are data for test cases. Each test case begins with a line containing one integer, $C$ $(2 ≤ C ≤ 200)$, which is the number of cities. The next $C$ lines each contain two integers $x$, $y$ $(0 ≤ x, y≤ 1000)$ representing the coordinate of one city. First city is the source city and second is the destination city of Umidsh.

Output data

There should be one line for each test case in output. Each line should contain one floating point number which is the minimum necessary volume of truck’s gas container, printed to three decimals.

Tests

Input	Output
$2$ $2$ $0$ $0$ $3$ $4$ $3$ $17$ $4$ $19$ $4$ $18$ $5$	$5.000$ $1.414$
$1$ $3$ $4$ $5$ $4$ $6$ $4$ $7$	$1.000$
$2$ $4$ $0$ $1$ $0$ $-1$ $1$ $0$ $-1$ $0$ $3$ $8$ $9$ $0$ $1$ $14$ $14$	$1.414$ $11.314$
$3$ $2$ $1$ $1$ $1$ $2$ $5$ $8$ $6$ $3$ $3$ $4$ $1$ $7$ $7$ $5$ $0$ $3$ $1$ $1$ $1$ $3$ $2$ $5$	$1.000$ $5.657$ $2.000$

Code

#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int inf = 10000000;

struct node {
    int x;
    int y;
};

vector <node> cities;
int d [200];
void diikstra ( int n ){
    d[0] = 0;
    for (int i = 1; i < n; i++){
        d[i] = inf;
    }
    priority_queue < pair <int, int> > q;
    q.push({d[0], 0});
    while (!q.empty()) {
        int num_v = q.top().second;
        node cur = cities[num_v];
        int distv = -q.top().first;
        q.pop();
        for (int i = 0; i < n; i++) {
             int distance = max (distv, (cur.x - cities[i].x)*(cur.x - cities[i].x)+(cur.y - cities[i].y)*(cur.y - cities[i].y));
                     if(d[i] > distance){
                        d[i] = distance;
                        q.push ({-distance, i});
                    }
        }
            }
}
int main() {
    cout.precision(3);
    int q;
    cin >> q;
    for (int w = 0; w < q; w++){
        int n;
        cin >> n;
        for (int i = 0; i < n; i++){
            int a, b;
            cin >> a >> b;
            cities.push_back({a,b});
        }
        diikstra (n);
        for (int i = 0; i < n; i++){
            cities.pop_back();
        }
        cout << fixed << sqrt(d[1]) <<  endl;
        
        
    }
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

const int inf = 10000000;

struct node {

int x;

int y;

};

vector <node> cities;

int d [200];

void diikstra ( int n ){

d[0] = 0;

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

d[i] = inf;

}

priority_queue < pair <int, int> > q;

q.push({d[0], 0});

while (!q.empty()) {

int num_v = q.top().second;

node cur = cities[num_v];

int distv = -q.top().first;

q.pop();

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

int distance = max (distv, (cur.x - cities[i].x)*(cur.x - cities[i].x)+(cur.y - cities[i].y)*(cur.y - cities[i].y));

if(d[i] > distance){

d[i] = distance;

q.push ({-distance, i});

}

int main() {

cout.precision(3);

int q;

cin >> q;

for (int w = 0; w < q; w++){

int n;

cin >> n;

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

int a, b;

cin >> a >> b;

cities.push_back({a,b});

}

diikstra (n);

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

cities.pop_back();

}

cout << fixed << sqrt(d[1]) << endl;

}

return 0;

}

Solution

We can interpretate the set of the cities as weighted graph, which vertices represent cities and weight of each edge between two vertices is the gas volume required for passing the distance between corresponding cities.
The volume of truck’s gas container depends on the gas volume required for arrival to the each next station of the Umidsh’s way. The maximum between gas volume required to get to the city $A$ and gas volume required to pass the way from the city $A$ to the city $B$ represents the minimum necessary gas volume required to get to the city $B$ through the city $A$. So the volume of truck’s gas container would turn to minimum, when the maximum gas volume required for passing the distance between each two stations of his way would turn to minimum. Thus we could use modified Dijkstra’s algorithm to find the biggest value among the weights of an edges between each two stations of the way between vertice 0 and vertice 1.

References

The task at E-Olymp
My solution at ideone

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-olimp 1610. Зайцы в клетках

27/12/2017 by Бондаренко Кирилл

Зайцы в клетках

Всем известен, так называемый, принцип Дирихле, который формулируется следующим образом:

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

В данной задаче мы рассмотрим более общий случай этого классического математического факта. Пусть имеется [latex]n[/latex] клеток и [latex]m[/latex] зайцев, которых рассадили по этим клеткам. Вам требуется расcчитать максимальное количество зайцев, которое гарантированно окажется в одной клетке.

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

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 10^9)[/latex].

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

Максимальное количество зайцев, которое гарантированно окажется в одной клетке.

Тесты

Входные данные	Выходные данные
3 50	17
5 5	1
1070 589	1
34 49	2

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

#include <iostream>
using namespace std;

int main() {
    int n, m;
    double k;
    cin >> n >> m;
    k = m / n;
    if (k >= 1)cout << (m + n - 1) / n;
    else cout << 1;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

double k;

cin >> n >> m;

k = m / n;

if (k >= 1)cout << (m + n - 1) / n;

else cout << 1;

return 0;

}

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

Пусть [latex]n[/latex] — количество клеток, и [latex]m[/latex] — количество зайцев.
Найдем отношение [latex]\frac{m}{n}[/latex]. Если это отношение больше либо равно единице то [latex]{m}\geq{n}[/latex] и мы имеем ответ. [latex]\frac{(m+n-1)}{n}[/latex] — это формула выводит ответ в целом виде, если он целый, и округляет в большую сторону, если он дробный. Иначе [latex]{m}\leq{n}[/latex] и максимальное гарантированное количество зайцев в одной клетке равно единице. Это следует из условия задачи.

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

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:

A322. Максимальная сумма делителей

17/12/2016 by Валентина Андриеш

Задача. Найти натуральное число с максимальной суммой делителей на заданном промежутке.

Входные данные:
— [latex]n[/latex] — промежуток чисел(от 1 до [latex]n[/latex]);

Выходные данные:
— [latex]max[/latex] _ [latex]sum[/latex] — максимальная сумма делителей числа на этом промежутке;
— [latex]max[/latex] _ [latex]number[/latex] — натуральное число с этой суммой;

Тесты:

[latex]n[/latex]	[latex]max[/latex] _ [latex]number[/latex]	[latex]max[/latex] _ [latex]sum[/latex]
100	96	252
8743	8400	30752
23000	22680	87120

Код на языке C++:

#include <iostream>
#include <cmath>
using namespace std;
 
int sum_dividers(int n){
    int sum=0;
    for(int i=1; i<sqrt(n); i++){
        if((n%i)==0)sum+=i+(n/i);
    }
    int i=sqrt(n);
    if(i*i==n)sum+=i;
    return sum;
}
 
int main() {
    int n;
    cin>>n;
    int max_sum=0;
    int max_number=0;
    int j;
    for(j=1; j<=n; j++){
        int s=sum_dividers(j);
        if(max_sum<s){
            max_sum=s;
            max_number=j;
        }
    }
    cout<<max_number<<" "<<max_sum;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int sum_dividers(int n){

int sum=0;

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

if((n%i)==0)sum+=i+(n/i);

}

int i=sqrt(n);

if(i*i==n)sum+=i;

return sum;

}

int main() {

int n;

cin>>n;

int max_sum=0;

int max_number=0;

int j;

for(j=1; j<=n; j++){

int s=sum_dividers(j);

if(max_sum<s){

max_sum=s;

max_number=j;

}

cout<<max_number<<" "<<max_sum;

return 0;

}

Код на языке Java:

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

class Ideone
{
    static int sum_dividers(int n){
        int sum=0;
            for(int i=1; i<Math.sqrt(n); i++){
                    if((n%i)==0)sum+=i+(n/i);
            }
            double i=Math.round(Math.sqrt(n));
            if(i*i==n)sum+=i;
            return sum;
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int max_sum=0;
        int max_number=0;
        int j;
        for(j=1; j<=n; j++){
            int s=sum_dividers(j);
            if(max_sum<s){
                        max_sum=s;
                        max_number=j;
            }
        }
        System.out.println(max_number+" "+max_sum);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

static int sum_dividers(int n){

int sum=0;

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

if((n%i)==0)sum+=i+(n/i);

}

double i=Math.round(Math.sqrt(n));

if(i*i==n)sum+=i;

return sum;

}

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

{

Scanner in = new Scanner(System.in);

int n=in.nextInt();

int max_sum=0;

int max_number=0;

int j;

for(j=1; j<=n; j++){

int s=sum_dividers(j);

if(max_sum<s){

max_sum=s;

max_number=j;

}

System.out.println(max_number+" "+max_sum);

}

Решение задачи:
Для нахождения суммы делителей используется функция [latex]sum[/latex] _ [latex]dividers[/latex], которая в созданном цикле сначала находит все делители числа, а после суммирует их, присваивая значение переменной [latex]sum[/latex]. Создав в главной функции [latex]main[/latex] еще один цикл со счетчиком от 1 до [latex]n[/latex], подставляю в предыдущую функцию [latex]sum[/latex] _ [latex]dividers[/latex] все натуральные числа на выбранном промежутке. C помощью свободных переменных [latex]max[/latex] _ [latex]sum[/latex] и [latex]max[/latex] _ [latex]number[/latex] нахожу максимальное значение сумм и соответствующее ему натуральное число.

Код программы на C++: Ideone
Код программы на Java: Ideone
Условия задачи(стр.134): 322

Related Images:

ML39. Старинное окно

28/09/2016 by Тимур Фирсов

Задача

Окно в университетской аудитории имеет форму прямоугольника с присоединенным в верхней части полукругом. Периметр всего окна равен [latex]P[/latex]. Определить радиус полукруга [latex]R[/latex], при котором площадь окна максимальна.
Входные данные: Периметр окна [latex]P[/latex].
Выходные данные: Радиус полукруга [latex]R.[/latex]

Тесты

	Входные данные	Выходные данные
№	[latex]P[/latex]	[latex]R[/latex]
1	100	14.0025
2	73	10.2218
3	14	1.96035
4	0	0

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

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    double P, R;
    cin>>P;
    R=P/(4+M_PI);
    cout<<R;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double P, R;

cin>>P;

R=P/(4+M_PI);

cout<<R;

return 0;

}

Решение

Университетское окно

Обозначим боковую сторону окна [latex]b[/latex], а нижнюю [latex]a[/latex]. [latex]R=\frac { a }{ 2 } [/latex], тогда периметр окна [latex]P=a+2b+\frac { \pi a }{ 2 } [/latex], а площадь равна сумме площадей прямоугольника и полукруга [latex]S=ab+\frac { \pi { a }^{ 2 } }{ 8 } [/latex]. Выразим сторону [latex]b[/latex] через [latex]a[/latex] и периметр [latex]P[/latex] : [latex]b=\frac { 2P-2a-\pi a }{ 4 } [/latex], тогда [latex]S=\frac { 4Pa-4a^{ 2 }-\pi a^{ 2 } }{ 8 } [/latex]. Вычислим производную функции [latex]S(a)[/latex]. [latex]S'(a)=\frac { 2P-4a-\pi a }{ 4 } [/latex], затем найдем точки экстремума функции:
[latex]\frac { 2P-4a-\pi a }{ 4 } =0[/latex], тогда [latex]a=\frac { 2P }{ 4+\pi } [/latex].
Найдём область допустимых значений для [latex]a[/latex]. Наибольшего значения [latex]a[/latex] достигает при [latex]b=0[/latex], [latex]P=a+ \frac {\pi a}{2}[/latex], соответственно [latex]a=\frac { 2P }{ 1+\pi } [/latex]. Значит областью допустимых значений является отрезок [latex][0; \frac { 2P }{ 2+\pi } ] [/latex]. Поскольку [latex]0 < \frac { 2P }{ 4+\pi } < \frac { 2P }{ 2+\pi }[/latex] делаем вывод, что [latex]a=\frac { 2P }{ 4+\pi } [/latex] попадет в область допустимых значений. Найдём максимальное значение функции на отрезке:
[latex]S(0)=0[/latex].
[latex]S(\frac { 2P }{ 4+\pi })= \frac { 4P ^ {2} }{ 32 + 8 \pi } [/latex].
[latex]S( \frac { 2P }{ 2+\pi })= \frac { 4P ^ {2} }{ 16 + 8 \pi } \cdot \frac { \pi }{ 2+ \pi } [/latex].
[latex] \frac {S(\frac { 2P }{ 4+\pi })}{S( \frac { 2P }{ 2+\pi })} = \frac { 4+4\pi +{ \pi }^{ 2 } }{ 4\pi +{ \pi }^{ 2 } } [/latex].
Тогда [latex]S(0) < S(\frac { 2P }{ 2+\pi }) < S(\frac { 2P }{ 4+\pi }) [/latex].
Значит площадь окна [latex]S[/latex] достигает максимального значения при [latex]a=\frac { 2P }{ 4+\pi }[/latex], из чего следует [latex]R=\frac { P }{ 4+\pi }[/latex].

Ссылка на код

ideone

Related Images:

А291а

25/05/2016 by Андрей Яроцкий

Задача: А291а

Условие:

Даны действительные числа [latex]a_{1},\ldots,a_{30}.[/latex] Получить [latex]\max (a_{1}+ a_{30},a_{2}+a_{29},\ldots,a_{15}+a_{n}).[/latex]

Тесты:

№	Входные данные	Выходные данные
1	2 3 5 4	8
2	2 3 7 5 4	14
3	4.5 1.1 3 9.25 0.75	10.35
4	-4.5 -2 0 -7.1 5	0.5

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

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

bool f(double a, double b){ //Вспомогательная функция для сортировки вектора по убыванию
    return a>b;
}

int main() {
    vector<double> real;
    double value;
    while(cin >> value){
        real.push_back(value);
    }
    int size = real.size();
    int size_of_sum = ceil(size%2==0?size/2:size/2+1); //Размер вектора сумм
    vector<double> sum;
    for(int i = 0; i < size_of_sum; i++){
        if(i == size_of_sum-1 && size%2 != 0) sum.push_back(2*real[i]);// Средний элемент массива real при нечетном size
        else sum.push_back(real[i] + real[size - i - 1]);
    }
    sort(sum.begin(),sum.end(),f); // Сортировка по убыванию
    cout << sum[0];
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

using namespace std;

bool f(double a, double b){ //Вспомогательная функция для сортировки вектора по убыванию

return a>b;

}

int main() {

vector<double> real;

double value;

while(cin >> value){

real.push_back(value);

}

int size = real.size();

int size_of_sum = ceil(size%2==0?size/2:size/2+1); //Размер вектора сумм

vector<double> sum;

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

if(i == size_of_sum-1 && size%2 != 0) sum.push_back(2*real[i]);// Средний элемент массива real при нечетном size

else sum.push_back(real[i] + real[size - i - 1]);

}

sort(sum.begin(),sum.end(),f); // Сортировка по убыванию

cout << sum[0];

return 0;

}

Решение:

После считывания входного потока данных в вектор [latex]real[/latex] вещественных чисел, вычисляем размер вектора [latex]sum[/latex], равный половине количества элементов входного потока с округлением вверх. В случае нечетного количества элементов, последним элементом вектора [latex]sum[/latex] будет центральный элемент вектора [latex]real[/latex] увеличенный в два раза. Далее, после сортировки полученного вектора по убыванию, выводим первый элемент вектора.

Ссылки:

Задачник по программированию С. Абрамова.

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

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:

А406

18/12/2015 by Сабиров Ильдар

Задача

С помощью [latex]x_{ij}, i=1,2; j=1,\ldots,n.[/latex] — действительной матрицы на плоскости задано n точек так, что [latex]x_{1j}, x_{2j}[/latex] — координаты [latex]j[/latex] — точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n	Матрица [latex]x_{ij}, i=1,2.[/latex]	Длина наибольшего отрезка	Комментарий
3	2 8 4 9 1 5	10	Пройдено
4	6 14 2 1 9 3 8 0	13.3417	Пройдено
5	1 8 4 3 7 2 9 5 0 11	11.7047	Пройдено

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

#include <iostream>
#include <cmath>
using namespace std;
int main() 
{
	double max = 0;
	int K=2,L,x=0,y=1;
	cin >> L;
	int D[K][L];
	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j < L; j++)
		{
			cin>>D[i][j];
		}
	}
	for (int i = 0; i < L-1; i++)
	{
		for (int j = 0; j < L; j++)
		{
			double q=sqrt((D[x][i]-D[x][j])*(D[x][i]-D[x][j])+(D[y][i]-D[y][j])*(D[y][i]-D[y][j]));
			if(q>max)
			{
				max=q;
			}
		}
	}
	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j < L; j++)
		{
			cout<<D[i][j]<<" ";
		}
		cout<<"\n";
	}
	cout<<max;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double max = 0;

int K=2,L,x=0,y=1;

cin >> L;

int D[K][L];

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

{

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

{

cin>>D[i][j];

}

for (int i = 0; i < L-1; i++)

{

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

{

double q=sqrt((D[x][i]-D[x][j])*(D[x][i]-D[x][j])+(D[y][i]-D[y][j])*(D[y][i]-D[y][j]));

if(q>max)

{

max=q;

}

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

{

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

{

cout<<D[i][j]<<" ";

}

cout<<"\n";

}

cout<<max;

return 0;

}

Ход решения:

Вводим матрицу построчно (не очень удобно).
Находим длину наибольшего отрезка.
С помощью вложенных циклов мы находим длины всех отрезков по формуле
[latex] AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}). [/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;

}

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