e-olymp 7240. Степан — бізнесмен

05/12/2020 by Валентина Михайліщук

Задача

Ужляндія, як відомо, країна з розвиненими торговими відносинами.

Степан вирішив спробувати зайнятися торгівлею і підзаробити собі на відпустку продажем комп’ютерної техніки. Для цього йому необхідно закуповувати техніку у інших продавців. Перш ніж почати роботу, він вирішив постежити за подіями на ринку Ужляндії і придумати, як отримувати найбільший прибуток.

Степан дізнався, що кожен продавець продає один комп’ютер, і кожен покупець готовий купити рівно один комп’ютер. Всього на ринку торгують [latex]N[/latex] продавців, вартість комп’ютера у [latex]i[/latex]-го з них дорівнює [latex]A_{i}[/latex] Ужляндських монет, причому ціни можуть відрізнятися у різних продавців. Крім того, він знайшов для себе [latex]M[/latex] потенційних покупців, кожен з яких хоче купити комп’ютер за [latex]B_{i}[/latex] монет. При цьому сам Степан може купити і продати будь-яку кількість комп’ютерів.

Степану необхідно отримати найбільший прибуток (вигідно купити і вигідно продати). Тому він звернувся за допомогою до Вас — кращому програмісту Ужляндії.

Формат вхідних даних

Перший рядок вхідного файлу містить розділення одиночним пропуском два цілих числа [latex]N, M (1 \leqslant N, M \leqslant 10^{5})[/latex] — кількість продавців на ринку Байтландіі і кількість потенційних покупців відповідно.
Другий рядок містить [latex]N[/latex] цілих чисел [latex]A_{i} (0 \leqslant A_{i} \leqslant 10^{9})[/latex] — вартості, за якими продавці готові продавати комп’ютери.
Третій рядок містить [latex]M[/latex] цілих чисел [latex]B_{i} (0 \leqslant B_{i} \leqslant 10^{9})[/latex] — суми, які потенційні покупці готові віддати при покупці комп’ютера.

Формат вихідних даних

Перший рядок вихідного файлу має містити одне ціле число [latex]S[/latex] — розмір максимальної вигоди в монетах, яку може отримати Степан.

Тести

№	Вхідні дані	Вихідні дані	Пояснення до прикладів
1	2 3 1 1 3 3 3	4	Степан купує комп’ютери у 1-го і 2-го продавців і продає їх будь-яким двом покупцям.
2	6 5 5 10 8 4 7 2 3 1 11 18 9	27	Степану найбільш вигідно купити комп’ютери у 1-го, 4-го і 6-го продавців і продати 3-му, 4-му і 5-му покупцям.
3	4 5 6 7 9 8 3 3 5 1 2	0	Степану невигідно закуповувати техніку, адже ціни продавців перевищують суми, які готові віддати покупці.
4	4 5 4 4 4 4 6 4 3 9 2	7	Степану байдуже в кого купувати комп’ютери, але продати вигідно їх він зможе лише 1-му і 4-му покупцям.
5	3 3 5 1 3 9 8 6	14	Степан купує всі комп’ютери, адже всіх їх він зможе вигідно продати.
6	4 1 2 5 4 6 8	6	Покупець лише один, тому Степан має купити комп’ютер тільки у 1-го продавця.
7	3 6 1 7 4 0 0 0 0 0 0	0	Клієнти є, але ніхто з них не збирається платити, тож Степан не отримає прибутку.
8	4 2 0 7 4 6 0 3	3	Перший продавець віддає свій комп’ютер безкоштовно, а другий покупець готовий заплатити. Отже, Степан може заробити.
9	1 5 5 5 7 9 3 4	4	Хоча покупців багато, але продавець лише один. Степан має продати комп’ютер 3-му клієнту.

Код

#include <iostream>
#include <algorithm>
using namespace std;
bool decrease(int a, int b) {
  return a > b;
}
int main() {
  int N, M, i = 0;
  cin >> N >> M;
  
  int * dealers = new int[N]; //створюємо масив  вартостей, за якими продавці готові продавати комп'ютери
  for (int i = 0; i < N; i++) {
    cin >> dealers[i];
  }
  int * clients = new int[M]; //створюємо масив сум, які покупці готові віддати при покупці комп'ютера
  for (int i = 0; i < M; i++) {
    cin >> clients[i];
  }
  sort(dealers, dealers + N); //відсортуємо масив за зростанням ціни
  sort(clients, clients + M, decrease); //відсортуємо масив за спаданням ціни
  long int S = 0;
  while (dealers[i] < clients[i] && i < N) {
    S += (clients[i] - dealers[i]); //розраховуємо вигоду
    i++;
  }
  cout << S;
  return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

bool decrease(int a, int b) {

return a > b;

}

int main() {

int N, M, i = 0;

cin >> N >> M;

int * dealers = new int[N]; //створюємо масив вартостей, за якими продавці готові продавати комп'ютери

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

cin >> dealers[i];

}

int * clients = new int[M]; //створюємо масив сум, які покупці готові віддати при покупці комп'ютера

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

cin >> clients[i];

}

sort(dealers, dealers + N); //відсортуємо масив за зростанням ціни

sort(clients, clients + M, decrease); //відсортуємо масив за спаданням ціни

long int S = 0;

while (dealers[i] < clients[i] && i < N) {

S += (clients[i] - dealers[i]); //розраховуємо вигоду

i++;

}

cout << S;

return 0;

}

Розв’язок

Щоб отримати маскимальну вигоду, Степан має купувати комп’ютери за найменшою ціною, а продавати якомога дорожче. Отже, потрібно створити масиви і відсортувати їх: масив вартостей, за якими продавці готові продавати комп’ютери — за зростанням; масив сум, які потенційні покупці готові віддати при покупці комп’ютера — за спаданням. Далі створюємо цикл, за допомогою якого розраховуємо вигоду від реалізації кожного комп’ютера. Оскільки масиви відсортовані, то, як тільки прибуток стане від’ємним або нульовим, можемо припинити розрахунки і вивести розмір максимальної вигоди.

Посилання

Код на ideone
Задача на e-olymp
Зарахований розв’язок на e-olymp

Related Images:

e-olymp 1462. Хитрая сортировка

25/02/2020 by Нина Хоробрых

Задача

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

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

Первая строка содержит число $n \ (1 \leqslant n \leqslant 1000)$, а вторая — сами натуральные числа, не превышающие $32000$.

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

Выведите последовательность чисел, упорядоченную согласно условию.

Тесты

№	Входные данные	Выходные данные
1	7 12 15 43 13 20 1 15	12 33 14 44 64 77
2	4 345 112 999 29	112 345 29 999
3	9 78 33 13 0 12 89 20 78 9990	0 20 9990 12 13 33 78 78 89

Код

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int mass[n];
    for (int i = 0; i < n; i++) {
        cin >> mass[i];
    }
    
    for (int i = 0; i < n; i++){
        for (int j = 1; j < (n - i);  j++) {
        if (mass[j] % 10 < mass[j-1] % 10) {
                swap (mass[j-1], mass[j]);
        } 
        else if ( mass[j] % 10 == mass[j-1] % 10 and mass[j] < mass[j-1]){
            swap (mass[j-1], mass[j]);
        }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << mass[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n;

cin >> n;

int mass[n];

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

cin >> mass[i];

}

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

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

if (mass[j] % 10 < mass[j-1] % 10) {

swap (mass[j-1], mass[j]);

}

else if ( mass[j] % 10 == mass[j-1] % 10 and mass[j] < mass[j-1]){

swap (mass[j-1], mass[j]);

}

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

cout << mass[i] << " ";

}

return 0;

}

Решение

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

Ссылки

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

Related Images:

e-olymp 2663. Сортировка пузырьком

28/01/2020 by Даниил Кадочников

Условие

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

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

В первой строке содержится количество элементов $n$ ($1 \leqslant n \leqslant 1000$) в массиве. Во второй строке — сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10$^$9$.

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

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

Тесты

№	Ввод	Вывод
1	3 1 3 2	1
2	2 2 1	1
3	4 4 1 5 3	3
4	5 5 4 1 100000 7	4
5	6 6 5 4 3 2 1	15

Решение

Используем простой алгоритм пузырьковой сортировки: проходим по массиву циклом, если два элемента стоят не в том порядке, то меняем их местами. Так как задача состоит в том, чтобы вывести число обменов, при каждом обмене прибавляем к счётчику $1$. При каждом выполнении цикла по j ставится на место хотя бы 1 элемент, поэтому с каждым полным проходом его длина сокращается на $1$.

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

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

int main() {
    cin >> n;
    int arr[n];

    for(int i=0; i<n; i++) cin >> arr[i];
    int counter=0;
    for(int u=0; u<n;u++) {
        for(int j=1; j<(n-u); j++) {
            if((arr[j]<arr[j-1])) {
                
                int prev;
                prev = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = prev;
                counter++;            
            }
        }
    }
    cout << counter;
    return 0;
}

#include <iostream>

using namespace std;

int n;

int main() {

cin >> n;

int arr[n];

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

int counter=0;

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

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

if((arr[j]<arr[j-1])) {

int prev;

prev = arr[j-1];

arr[j-1] = arr[j];

arr[j] = prev;

counter++;

}

cout << counter;

return 0;

}

Ссылки

решение на e-olymp
код на ideone

Related Images:

e-olymp 972. Сортировка времени

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

Задача

Отсортируйте время согласно заданному критерию

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

Сначала задано число $n\, \left ( 1\leqslant n\leqslant 100 \right )$, а затем n моментов времени. Каждый момент времени задается 3 целыми числами — часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60)

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

Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно)

Тесты

№	Входные данные	Выходные данные
1	[latex]\begin{matrix} 4 & & \\ 10 &20 &30 \\ 7 &30 &00 \\ 23&59 &59 \\ 13&30 &30 \end{matrix}[/latex]	[latex]\begin{matrix} 7 & 30 &00 \\ 10&20 &30 \\ 13&30 &30 \\ 23& 59 & 59 \end{matrix}[/latex]
2	$\begin{matrix} 6\\ 12 &55 &59 \\ 8 &33 &34 \\ 6 &56 &46 \\ 10 &23 &52 \\ 3 &20 &00 \\ 19 &31 &0\\ 10&23&52 \end{matrix}$	$\begin{matrix} 3 &20 &0 \\ 6 &56 &46 \\ 8 &33 &34 \\ 10 &23 &52 \\ 12 &55 &59 \\ 19 &31 &0 \end{matrix}$

#include <iostream>

#include <algorithm>

using namespace std;
int main() {
  int hours[100];
  int mins[100];
  int secs[100];
  int all_time[100];
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> hours[i] >> mins[i] >> secs[i];
    all_time[i] = hours[i] * 3600 + mins[i] * 60 + secs[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (all_time[i] > all_time[j]) {
        swap(hours[i], hours[j]); swap(mins[i], mins[j]);
        swap(secs[i], secs[j]); swap(all_time[i], all_time[j]);
      }
    }
  }
  for (int i = 0; i < n; i++) cout << hours[i] << " " << mins[i] << " " << secs[i] << endl;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int hours[100];

int mins[100];

int secs[100];

int all_time[100];

int n;

cin >> n;

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

cin >> hours[i] >> mins[i] >> secs[i];

all_time[i] = hours[i] * 3600 + mins[i] * 60 + secs[i];

}

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

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

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

swap(hours[i], hours[j]); swap(mins[i], mins[j]);

swap(secs[i], secs[j]); swap(all_time[i], all_time[j]);

}

for (int i = 0; i < n; i++) cout << hours[i] << " " << mins[i] << " " << secs[i] << endl;

}

Решение

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

Ссылки

e-olymp
ideone

Related Images:

e-olymp 396. Дождь

15/04/2018 by Мороз Дима

Задача

Капля дождя падает вертикально вниз с большой высоты на землю. На пути у капли могут встретиться препятствия, которые изменяют ее путь к земле.

Как это выглядит на координатной плоскости

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

Напишите программу, которая по координате $X$_$0$ точки появления капли над землей вычисляет координату $X$ точки соприкосновения капли с землей $(Y = 0)$.

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

Во входном файле в первой строке содержатся два целых числа через пробел – координата $X$_$0$ точки появления капли $(0 < X$_$0$ $< 10000)$ и количество отрезков-препятствий $N (0 ≤ N ≤ 100)$. Далее следует $N$ строк, каждая из которых содержит четыре разделенные пробелами числа $x$_$1$, $y$_$1$, $x$_$2$, $y$_$2$ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $0$ до $10000$, $x$_$1$ $ < x$_$2$, $y$_$1$ $≠$ $y$_$2$$)$. Отрезки не пересекаются и не соприкасаются.

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

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

Тесты

Входные данные	Выходные данные
30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19	18
12 5 12 9 13 5 17 8 19 5 13 10 10 7 6 17 4 12 13 4 5 12	13
40 3 12 30 21 39 41 5 45 70 20 30 25 35	40
70 6 45 75 598 37 489 48 726 47 673 873 46 36 60 735 373 762 483 73 364 59 462 375 583 457	726

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

#include <iostream>
using namespace std;
 
int main () 
{
    int x, n;
    cin >> x >> n;
    int N[n][4];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 4; j++)
            cin >> N[i][j];
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            for (int q = 0; q < 4; q++)
                if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) )
                    swap(N[i][q], N[j][q]);
    for (int i = 0; i < n; i++) {
        if (x >= N[i][0] && x <= N[i][2]) 
            N[i][1] < N[i][3] ? x = N[i][0] : x = N[i][2];
        for (int j = 0; j < 4; j++)
            N[i][j] = 0;
    }
    cout << x;
 
    return 0;
}

#include <iostream>

using namespace std;

int main ()

{

int x, n;

cin >> x >> n;

int N[n][4];

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

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

cin >> N[i][j];

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

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

for (int q = 0; q < 4; q++)

if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) )

swap(N[i][q], N[j][q]);

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

if (x >= N[i][0] && x <= N[i][2])

N[i][1] < N[i][3] ? x = N[i][0] : x = N[i][2];

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

N[i][j] = 0;

}

cout << x;

return 0;

}

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

Сортируем наш динамический массив по наибольшим координатам $y$ и, если $y$ равны, по координатам $x$.

Далее составим алгоритм решения задачи:

Если $X$ $ ∈ [x$_$1$$, x$_$2$$]$, то наша капля пересечется с данной прямой. В противном случае мы просто игнорируем данное препятствие.
Тогда мы сравниваем координаты $y$_$1$ и $y$_$2$, выбираем из них наименьшее и присваиваем соответствующую координату $x$_$1$ или $x$_$2$ координате нашей капли $X$.
Повторяем до тех пор, пока не будут обработаны все препятствия и выводим последнюю присвоенную координату $X$ нашей капли, так как она и будет координатой $x$ соприкосновения капли с зимой.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

Related Images:

Ю4.13

22/10/2014 by Осецимський Анатолій Вадимович

Задача. Дан массив [latex]A(n)[/latex]. Все положительные его элементы поместить в начало массива [latex]B(n)[/latex], а отрицательные элементы- в начало массива [latex]C(n)[/latex]. Подсчитать количество тех и других.

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

-1

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

#include <iostream>
using namespace std;

int main() {
    int n=0,otr=0,pol=0;
    scanf("%d",&n);//размеры массива
    double A[n],B[n],C[n];//создаем три массива
    for(int i=0;i<n;i++)// цикл для ввода значений массива и сортировки
    {
        cin >> A[i];
        A[i]>=0?B[pol++]=A[i]:C[otr++]=A[i];//В данной строке команда printf используется вместо двух ifов,чтобы было приятнее глазу, Если элемент из массива А положительный,то в массив В добавляем новый элемент и увеличиваем счетчик на 1, а если отрицательно, то в массив С
    }
	cout << "Negative " << otr << " Positive " << pol << endl;//выводим количество отрицательных и положительных чисел
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n=0,otr=0,pol=0;

scanf("%d",&n);//размеры массива

double A[n],B[n],C[n];//создаем три массива

for(int i=0;i<n;i++)// цикл для ввода значений массива и сортировки

{

cin >> A[i];

A[i]>=0?B[pol++]=A[i]:C[otr++]=A[i];//В данной строке команда printf используется вместо двух ifов,чтобы было приятнее глазу, Если элемент из массива А положительный,то в массив В добавляем новый элемент и увеличиваем счетчик на 1, а если отрицательно, то в массив С

}

cout << "Negative " << otr << " Positive " << pol << endl;//выводим количество отрицательных и положительных чисел

return 0;

}

Заводим счетчик для отрицательных и положительных чисел,а также переменную для количества элементов массива типа [latex]int[/latex]. Читаем количество элементов и создаем три массива типа [latex]double[/latex](вдруг нам буду вводить действительные числа). В цикле читаем элемент [latex]A[i][/latex] и условием определяем положительное число или нет, и увеличиваем соответствующий счетчик. Выводим полученные результаты.

Ссылка на программу.

Java

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), p = 0, o = 0;
		int[] A = new int[n], B = new int[n], C = new int[n];
		for(int i = 0; i < n; i++){
			A[i] = in.nextInt();
			if(A[i] >= 0) B[p++] = A[i]; else C[o++] = A[i];
		}
		System.out.println("Positive:"+p + " Negative:"+o);
	}
}