e-olymp 7258. Числовые операции

Условие

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

Задание

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

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

Первая строка входного файла содержит число $T (1 \leqslant T < 10^4$), которое задает количество чисел во входном файле, для которых требуется найти ответ. В последующих T строках задано по одному натуральному числу $N_i$,$2\leqslant N_i < 10^9$, $1 \leqslant i \leqslant T$. Известно, что среди чисел $N_i, 1 \leqslant i \leqslant T$, нет одинаковых.

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

Выходной файл должен содержать $T$ чисел по одному в строке — в $i$-й строке должно быть записано наименьшее количество секунд, которое понадобится истратить Пете, чтобы, начав с единицы, записать на доске соответствующее число $N_i$.

Тесты

Ввод Вывод
1 3

3

955

21

1

48

12

2 4

137

318

3028

300
39

40

71

50

Код

Решение

Количество цифр в числе никогда не уменьшается, а может увеличиться только при добавлении к числу, состоящее только из девяток и единицы. Поэтому, для достижения числа $N$ сначала нужно дойти до числа $10$, потом до чисел $99$ и $100$ и т.д., пока кол-во цифр в числе не будет таким, как требуется.
Наименьшее кол-во операций,необходимое для того,чтобы перейти от числа $10^{n-1}$ до заданного $n$-значного числа $N=$:
1.Если число $N$ содержит хотя бы одну цифру, отличную от нуля, кроме первой, то кол-во операций можно посчитать по формуле summa(N) + nonzero(N) edinica(N)-1, где summa(N)-сумма цифр числа, nonzero(N)-кол-во цифр,отличных от нуля, на всех позициях числа $N$, кроме последней, edinica(N)-число,которое равно единице,если хотя бы на одной позиции числа $N$, кроме последней,есть единица, или равна нулю, если единиц на этих позициях нет.
2.Если все цифры числа $N$, кроме первой,нулевые,а первая цифра больше единицы, то кол-во операций можно посчитать по формуле summa(N-1)+nonzero(N-1) edinica(N-1).

Доказательство формул

Для дальнейшего удобства обозначим перестановку цифр числа через $\Rightarrow$.
Число $N$-заданное число, число $n$-кол-во цифр числа $N$. Если $n=1$,$N=7$,то для того,чтобы дойти от единицы до заданного числа,потребуется $N-1$ операций. В нашем случае 6 операций
($1+1=2,
2+1=3,

6+1=7$)
Если $n\geq2$,то для этого достаточно привести пример цепочки,подсчитывающая кол-во операций,которая число $10^{n-1}$ превращает в $N$. Но вместо прямого порядка действий будем делать обратный эквивалентный. То есть, $N \Rightarrow 10^{n-1}$: за одну операцию мы можем или уменьшить число на единицу, или переставить в нем цифры так,чтобы на первом месте оказался не нуль. Могут возникнуть следующие случаи:
1.Если $N=10^{n-1}$, то кол-во операций равно summa(N) + nonzero(N)-edinica(N)-1 $= $0.
Например, возьмем число $1000$. Сумма цифр $= 1$, количество ненулевых цифр $= 1$, количество единиц $= 1$, соответственно значение $= 1+1-1-1 =0$.

2.Если $N!=10^{n-1}$ и число первая цифра числа $N$ равна единица:
Сначала отнимаем от числа $N$ столько единиц, чтобы последняя цифра стала нулем,далее
Переставим местами последнюю цифру с какой-нибудь другой,отличной от нуля,кроме первой, и опять отнимем кол-во единиц,чтобы последняя цифра стала нулевой. Повторять будем до тех пор,пока все цифры,кроме первой,станут нулями.
Например,возьмем число $137$.
$137-1=136$, $136-1=135$, $135-1=134$, $134-1=133$ ,$133-1=132$ ,$132-1=131$, $131-1=130$ ,$130 \Rightarrow 103$ , $103-1=102$, $102-1=101$, $101-1=100$
Кол-во операций $= 11$. Проверяем по формуле. summa(137)=11, nonzero(137)=2, edinica(137)=1. Итого получаем $11+2-1-1=11$

3.Если первая цифра числа $N$ больше единицы, но хотя бы на одной позиции числа,кроме последней, есть единица, делаем:
Сначала уменьшаем последнюю цифру,пока она не станет нулем, затем переставляем цифры: поставим на место первой цифры единицу, а первую цифру сделаем последней, а нуль, который стоял в конце числа, поставим на место бывшей первой. После этого будем действовать согласно алгоритму пункта №2.
Например, число $318$.
$318-1=317$, $317-1=316$, $316-1=315$, $315-1=314$, $314-1=313$, $313-1=312$, $312-1=311$, $311-1=310$, $310 \Rightarrow 103$, $103-1=102$, $102-1=101$, $101-1=100$
Итого $12$ операций. Просчитываем по формуле summa(318)+nonzero(318)-edinica(318)-1.
Получаем $12+2-1-1=12$.

4.Если ни на одной из позиций числа $N$, кроме,возможно,последней, нет единиц, но в числе есть хотя бы одна ненулевая цифра,кроме первой, то делаем:
Последнюю цифру делаем нулевой, переставляем последний нуль с любой ненулевой цифрой,кроме первой, пока на последнем месте не окажется последняя ненулевая цифра (не считая первую), последнюю ненулевую уменьшаем не до нуля, а до единицы, переставим единицу с первой цифрой, новую последнюю цифру сделаем нулевой.
Например, число $3028$.
$3028-1=3027$, $3027-1=3026$, $3026-1=3025$, $3025-1=3024$, $3024-1=3023$, $3023-1=3022$, $3022-1=3021$, $3021-1=3020$, $3020 \Rightarrow 3002$, $3002-1=3001$, $3001 \Rightarrow 1003$, $1003-1=1002$, $1002-1=1001$, $1001-1=1000$
Получаем $14$ операций. Проверяем по формуле summa(3028)+nonzero(3028)-edinica(3028)-1 $= 13+2-0-1=14$.

5.Если первая цифра числа $N$ больше единицы, а все другие цифры-нулевые, то делаем:
Отнимем от числа $N$ единицу, а дальше будем использовать один из раннее алгоритмов в пунктах 2-4.
Например, число $300$.
$300-1=299$, $299-1=298$, $298-1=297$, $297-1=296$, $296-1=295$ $=$ … $291-1=290$, $290 \Rightarrow 209$, $209-1=208$ $=$ … $202-1=201$, $201 \Rightarrow 102$, $102-1=101$, $101-1=100$
Итого $22$ операции. summa(300-1)+nonzero(300-1)-edinica(300-1) $= 20+2-0=22$.

6.Подсчет операций от $1$ до $10^{n-1}$.
Для того,чтобы перейти от числа $10^{n-1}$ к $10^n$, понадобится число $10^n – 1$,которое равно $k$. По предыдущим алгоритмам, понадобится:
summa(k)+ nonzero(k) edinica(k) -1 $=$ $9 \cdot n + (n-1) -0 -1=10 \cdot n – 2$ операций, где b $>$ 1.
Если $n=1$, то кол-во операций $= 10 \cdot n – 2 =8$.

Кол-во операций можно посчитать по формуле $(5 \cdot n -1) \cdot (n – 1)$ ,где $n$- кол-во цифр заданного числа.

Ссылки

e-olymp 3738. Простая сортировка

Задача

Дан массив целых чисел.

Ваша задача — отсортировать его в порядке неубывания.

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

В первой строке входного файла содержится число N (1 ≤ N≤ 100000) — количество элементов в массиве. Во второй строке находятся N целых чисел, по модулю не превосходящих 109.

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

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

Тесты

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

10

1 8 2 1 4 7 3 2 3 6

1 1 2 2 3 3 4 6 7 8
2

9

7 39 8 1 4 2 65 10 5

1 2 4 5 7 8 10 39 65
3

12

-3 7 -7 -11 40 -30 25 30 2 7 -30 1

-30 -30 -11 -7 -3 1 2 7 7 25 30 40

Код

 

Решение

Для решения задачи используем функцию сортировки из библиотеки algorithm. Для начала создаем одномерный массив, потом с помощью цикла записываем значение в массив. С помощью функции sort, сортируем и записываем изменения в массив. Потом с помощью цикла выводим результат.

Ссылки

e-olymp 7241. Transit

Задача

Країна Ужляндія має вигідне географічне розташування – її територія знаходиться на перетині важливих торгівельних шляхів. Одним із таких є торгівельний шлях, яким сусідня братська держава доставляє свої унікальні обігрівачі до інших країн.

На кордоні Ужляндії та братської держави, де починається цей шлях, розташований спеціальний пропускний пункт, через який щодня проїжджає потяг із величезною кількістю обігрівачів. Зовсім недавно між урядами двох братських країн було погоджено нові правила транзиту обігрівачів через територію Ужляндії на найближчі $N$ днів. Згідно з новим договором має обратися певне число $m$ – максимальна кількість обігрівачів в одному потязі. Тоді з кожного потяга, що транспортує $A_i$ обігрівачів, буде відвантажено рівно $ A_i -m $ одиниць іноземної продукції (звичайно, якщо $A_i > m$ , інакше ж потяг рухатиметься без зупинок і нічого відвантажено не буде). Власне це й буде плата за проходження потяга територією Ужляндії, вона еквівалентна грошовим витратам на утримання залізничних колій. Сумарна кількість відвантажених в Ужляндії за $N$ днів обігрівачів повинна бути не менша $K$, інакше країна зазнає збитків.

Стала відома кількість обігрівачів у потязі в кожен із $N$ днів (ця інформація надається за умовами контракту). Знайдіть максимальне число $m$, при якому Ужляндія не зазнає економічних збитків.

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

В першому рядку записано два числа $N$, $K$ ($1 \leqslant N \leqslant 10^6$, $1 \leqslant K \leqslant 2 \cdot 10^9$). В наступному рядку задано $N$ чисел – кількість обігрівачів у потязі в кожен з $N$ днів, що не перевищує $10^9$.

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

В єдиному рядку виведіть одне число – відповідь на задачу, гарантується, що відповідь завжди існує.

Пояснення до прикладу

Всього територією Ужляндії пройде $4$ потяги з $11, 6, 1$ та $8$ обігрівачами відповідно. Щоби країна не знала збитків, потрібно відвантажити не менше $7$ обігрівачів. Очевидно, що максимальне можливе $m$, яке задовольнить цю умову, буде рівне $6$, тоді з потягів буде відвантажено відповідно $5, 0, 0, 2$ обігрівачів, що в сумі дорівнює $7$ і задовольняє умову.

Тести

Вхідні дані Вихідні дані
1 4 7
1 8 6 11
  6
2 10 20
1 8 6 11 16 14 21 10 13 4
  11
3 5 10
12 4 3 6 9
  5
4 6 11
5 8 6 9 4 7
  4
5 2 1
2 2
  1

Код

Рішення

Для знаходження числа $m$ я використовував бінарний пошук, перед цим зробивши сортування по зростанню елементів в масиві. Отже, вся задача зводиться до використання бінарного пошуку, та функції яка рахує $\sum\limits_{i=0}^{n-1} A_i — m$, при $A_i > m$ ($m$ — значення mid; $n$ — кількість елементів в масиві; $A_i$ — значення $i$-го елемента масиву). Далі ця сума порівнюється з $K$ для подальшої роботи пошуку та знаходження числа $m$. Якщо такого числа $m$ не існує ми шукаємо найближче, при якому країна не зазнає збитків.

Посилання

e-olymp 2691. Проходной балл

Задача

Дан список учащихся с указанием годовых оценок по всем предметам. Для поступления в Школу Одаренных Детей необходимо, чтобы средний балл по всем предметам был не ниже, чем $K$. Определите, кого из перечисленных ребят могут зачислить в эту школу.

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

В первой строке дано число $N$ ($1 \leqslant N \leqslant 10000$), количество учащихся в списке. Каждая из следующих $N$ строк имеет вид: фамилия и имя, затем число $M_i$ ($1 \leqslant M_i \leqslant 50$) — количество предметов, которые изучал ученик, а затем годовые оценки по каждому из этих предметов.
В последней строке дано единственное число $K$ — проходной балл. Фамилия и имя — строки, состоящие не более чем из $20$ латинских букв. Все числа во входном файле натуральные и не превышают $10^9$.

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

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

Тесты

Входные данные Выходные данные
1 3
Ivanov Ivan 2 7 9
Petrov Petr 1 7
Sidorov Sidor 2 10 8
4
Ivanov Ivan
Petrov Petr
Sidorov Sidor
2 1
Ivanov Ivan 1 6
5
Ivanov Ivan
3 4
Petrov Petr 10 1 2 3 4 5 6 7 8 9 10
Sidorov Sidor 5 8 8 8 4 4
Ivanov Ivan 0
Darienko Dasha 3 10 3 9
6
Sidorov Sidor
Darienko Dasha
4 2
Petrov Petr 10 1 2 3 4 5 6 7 8 9 10
Darienko Dasha 3 10 3 9
11
5 5
Petrov Petr 10 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000
Darienko Dasha 5 500000000 500000000 500000000 700000000 800000000
Sidorov Sidor 20 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000 500000000 500000000 500000000 700000000 800000000 500000000 500000000 500000000 700000000 800000000
Ivanov Ivan 8 600000000 600000000 600000000 800000000 200000000 1000000000 300000000 300000000
Sergeev Alexandr 1 700000000
600000000
Darienko Dasha
Sergeev Alexandr

Код

Оптимальное решение:

Более структурированное решение:

Решение

Введем данные в соответствующие структуры (см. комментарии в коде), вычислим средние баллы для каждого ученика и выведем фамилии и имена всех тех и только тех, чей средний балл выше проходного.
Т. к. все исходные данные натуральные и не превышают $10^9$ используем для их ввода тип int. При этом сумма оценок может выйти за пределы типа int ($50\cdot10^9 > 2 147 483 647$), поэтому для переменной sum используем тип long. Также заметим, что среднее арифметическое натуральных чисел может быть дробным числом, но в данном случаи средний проходной балл $K$ по условию являет натуральным числом, поэтому будет уместно отбросить дробную часть при сравнении, т. е. использовать целочисленных тип данных в вычислениях.

Ссылки

  • Задача на e-olymp
  • Код оптимального решения на ideone
  • Код решения со структурами на решения со структурами на ideone
  • Засчитанное оптимальное решение на e-olymp
  • Засчитанное структурированное решение на e-olymp
  • e-olymp 6253. Репликация вируса

    Задача

    Некоторые вирусы реплицируются путем замены фрагмента ДНК в живой клетке фрагментом ДНК, который вирус несет с собой. Это заставляет клетку создавать вирусы, идентичные оригинальной, зараженной клеткой. Группа биологов заинтересована в том, чтобы узнать, сколько ДНК вносит вирус в геном хозяина. Чтобы узнать об этом, они упорядочили полный геном здоровой клетки, а также идентичную клетку, инфицированную вирусом.

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

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

    Состоит из двух строк, содержащих последовательность ДНК до и после вирусной инфекции, соответственно. Последовательность ДНК задается как строка, содержащая от 1 до $10^5$ букв верхнего регистра из алфавита {AGCT}.

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

    Выведите одно целое число — минимальную длину ДНК, вставленную вирусом.

    Тесты

    Входные данные Выходные данные
    1 AAAAA
    AGCGAA
    3
    2 GTTTGACACACATT
    GTTTGACCACAT
    4
    3 SMMSMM
    SMAHMA
    4

    Код

    Решение

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

    В циклах for мы узнаём крайний слева и справа элемент обоих массивов, на которых буквы первой строки начинают не совпадать с буквами второй, s и e2 соответственно. Чтобы узнать результат необходимо проверить является ли l2 &gt; l1 и больше ли l2-l1 чем e2-s1+1.

    e-olymp 6941. Сумма НОД

    Задача

    Для заданных $n$ натуральных чисел найдите сумму НОД (наибольших общих делителей) всех возможных пар этих чисел.

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

    В первой строке задано количество тестов $n \ (1 < n < 100)$. Каждый тест состоит из одной строки и содержит количество входных чисел $m \ (1 < m < 100)$, за которым следуют $m$ натуральных чисел. Все входные числа натуральные, не превышающие $10^6.$

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

    Для каждого теста в отдельной строке вывести сумму $НОД$ всех возможных пар.

    Тесты

    Входные данные Выходные данные
    1 3
    4 10 20 30 40
    3 7 5 12
    3 125 15 25
    70
    3
    35
    2 2
    3 12 7 8
    4 5 14 25 11
    6
    10
    3 4
    4 5 6 7 8
    4 8 6 2 9
    3 2 15 6
    5 12 25 29 19 11
    7
    11
    6
    10

    Код

    Решение

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

    Ссылки

    E-Olymp 7029. Поликлиника

    Задача

    На прием к доктору каждый день приходит много людей. Каждый пациент находится на приеме целое число минут, однако разных пациентов доктор может принимать разное количество времени. Доктор начинает прием в момент времени $t_1$ минут и заканчивает прием в момент времени $t_2$ минут. Это означает, что любой пациент независимо от того, сколько времени его будет принимать доктор, может зайти на прием в моменты $t_1, t_1 + 1, …, t_2 − 1$. Заходить на прием к доктору в другое время или тогда, когда доктор принимает другого пациента, запрещено. Если пациент приходит в поликлинику в момент $t$, он ожидает первый момент времени $s ≥ t$ такой, что на этот момент доктор ведет прием, причем уже успел осмотреть всех пациентов, которые пришли в поликлинику раньше, то есть до момента $t$. Если доктор не успевает осмотреть всех до конца приема, то остаток пациентов должен прийти на следующий день.

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

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

    В первой строке приведено три числа: количество желающих попасть на прием n, время начала приема $t_1$ и время завершения приема $t_2$, больший чем $t_1$.

    Во второй строке перечислены $n$ чисел $a_1, a_2, …, a_n$ — время, когда в поликлинику зашли соответственно первый, второй, $…, n$-ый желающий попасть к доктору. Числа $a_1, a_2, …, a_n$ попарно различны и расположены в порядке возрастания.

    В третьей строке перечислены n чисел $b_1, b_2, …, b_n$ — время, необходимое доктору на осмотр соответственно первого, второго, $…, n$-го пациента.

    Все входные числа натуральные. Количество пациентов $n$ не больше $10^5$, остальные числа не превосходят $10^9$.

    Сутки на планете, где проживает Петя Пяточкин, длятся значительно дольше, чем на Земле, поэтому время начала приема $t_1$, время завершения приема $t_2$, а также числа $a_1, a_2, …, a_n$ и $b_1, b_2, …, b_n$ могут быть большими чем 1440 — количество минут в земных сутках.

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

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

    Тесты

    Входные данные Выходные данные
    1 3 10 20
    7 14 18
    5 2 1
    17
    2 5 10 20
    4 9 12 16 22
    4 10 10 9 2
    9
    3 1 10 20
    5
    15
    5

    Код

    Решение

    Создаём два массива, удовлетворяющих условия, a — время прихода пациентов и b — время на их приём. Инициализируем все необходимые переменные: t_1 и t_2 — время приёма, t — время в которое Петя должен прийти, n- кол-во пациентов, i и j — счётчики, l — время между приходом пациента и началом его приёма.

    Проверяем приходит ли первый пациент в самое начало приёма или после начала приёма, если в начало приёма — то приходим тогда.

    В цикле while определяем минимальное время, в которое Петя может прийти на приём к врачу. Проверяем приходит ли следующий пациент до завершения приёма предыдущего. Если приходит во время завершения, или через некоторое время, то заходим после приёма предыдущего. (Нам уступают) Если нет, цикл продолжается, проверяет, является ли разница между началом приёма следующего пациента и временем его прихода меньше, чем предыдущая зафиксированная разницы. Если да — записывает её и время прихода данного пациента, и переходит к следующему пациенту.       

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

    e-olymp 7095. Факторіали

    Задача

    Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.

    Знаючи пристасть майора до великих чисел, грабіжники переконані, що кодом є три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$. Наприклад:

    • при $N$ = $7$ кодом буде $504$, бо $7!$ = $5040$;
    • при $N$ = $17$ кодом буде $096$, бо $17!$ = $355687428096000$.

    За даним натуральним числом $N$ знайти три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$.

    Вхідні дані

    Вхідний файл містить єдине ціле число $N$. $(7 \leqslant N \leqslant 1000000000)$.

    Вихідні дані

    Вихідний файл має містити рівно три цифри — шуканий код.

    Тесты

    Входные данные Выходные данные
    1 7 504
    2 17 096
    3 50 512
    4 1000000000 144

    Код

    Решение

    Поскольку процесс расчёта факториала больших чисел занимает много времени, его можно ускорить использованием массива факториалов некоторых чисел. Полное значение факториала не нужно, поэтому массив содержит последние $8$ ненулевых цифр значений факториалов чисел, кратных $10000000$, которые можно получить с помощью следующего кода:

    Если на входе — число $N$, меньшее $10000000$, его факториал рассчитывается обычным циклом, попутно отбрасывая ненужные цифры высших разрядов. В конце выводятся искомые последние три цифры факториала числа $N$. Если на входе — число $N$, большее $10000000$, выбирается соответствующее значение из массива по индексу $N/10000000$, и далее с помощью цикла считается произведение оставшихся чисел из $N!$. С уменьшением кратности чисел, факториалы которых содержатся в массиве, увеличивается скорость выполнения программы.

    Ссылки

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

    Задача

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

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

    Степан дізнався, що кожен продавець продає один комп’ютер, і кожен покупець готовий купити рівно один комп’ютер. Всього на ринку торгують [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-му клієнту.

    Код

    Розв’язок

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

    Посилання

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

    e-olymp 399. Последствия гриппа в Простоквашино

    Задача

    ”Дорогой дядя Фёдор!

    После того, как мама испугалась, что ты можешь заболеть какой-то нечеловеческой болезнью и забрала тебя в город, Шарик видимо все-таки чем-то заболел, ибо его поступки я уже иначе объяснить не могу, как последствиями постоянного общения с Хрюшей.

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

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

    Дядя Фёдор, если тебе не трудно, напиши мне программу для подсчета этого количества, ибо из-за того, что Шарик задает мне свою непонятную задачу до 20 раз на день, у меня даже не остается времени ухаживать за моей любимой коровой.

    Всегда твой верный друг – кот Матроскин.”

    Помогите дяде Фёдору написать программу для Матроскина, иначе тот может остаться без молока.

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

    В первой строке задано число $n$ – количество заданий Шарика за день. В следующих $n$ строках задано по одному числу $k$ – количество выданных в очередной раз Матроскину квадратиков с изображением скобок. Квадратики Матроскин может переворачивать, получая при этом как открывающую, так и закрывающую скобку.

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

    Вывести в $n$ строках по одному числу – ответ на соответствующее задание Шарика.

    Тесты

    Входные данные Выходные данные
    1 3
    2
    3
    4
    1
    0
    2
    2 5
    3
    11
    7
    43
    27
    0
    0
    0
    0
    0
    3 6
    2
    28
    42
    14
    64
    0
    1
    2674440
    24466267020
    429
    55534064877048198
    1

    Код

    Решение

    Правильную скобочную последовательность можно построить лишь из четного количества скобок, т.е. для нечетного числа ответ заведомо $0$. А для $2m$ скобок ($m$ открывающих и $m$ закрывающих) ответ равен числу Каталана $C_m$. Для вычисления которого используется рекуррентное соотношение: $$C_m=\sum_{i=0}^{m-1} C_i \cdot C_{m-1-i}$$

    e-olimp 8536. Заповнення смуги $3 \times n$

    Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.

    Задача

    Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

    Вхідні дані

    Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.

    Вихідні дані

    Вивести кількість способів, якими можна заповнити смугу.

    Тести

    Вхідні дані Вихідні дані
    1 1
    5 4
    12 60
    50 122106097

    Код № 1

    Рішення 1

    Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

    Код № 2

    Рішення 2

    Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

    Посилання

    Умова задачі на E-Olymp
    Зараховане рішення № 1 на E-Olymp
    Зараховане рішення № 2 на E-Olymp
    Код задачі № 1 на Ideone
    Код задачі № 2 на Ideone

    e-olimp 8234. Сходинки

    Задача

    Скількома способами можна потрапити на $n$-ту сходинку, якщо можна ступати на наступну, переступати через одну і через дві сходинки.

    Вхідні дані

    Одне число $n$ — номер сходинки $(n \leqslant 60)$.

    Вихідні дані

    Вивести кількість способів, якими можна потрапити на $n$-ту сходинку.

    Тести

    Вхідні дані Вихідні дані
    0 1
    5 13
    15 5768
    32 181997601
    60 4680045560037375

    Код № 1

    Рішення

    Розіб’ємо задачу на декілька простих. Спочатку розрахуємо кількість способів для однієї сходинки (1 спосіб), потім для двох (2 способи: 0 $\rightarrow$ 1 $\rightarrow$ 2; 0 $\rightarrow$ 2) і також потрібно врахувати випадок, коли кількість сходинок дорівнює нулю (1 спосіб). Далі легко помітити, що кожне наступне значення дорівнює сумі трьох попередніх звідки і отримуємо формулу:
    arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
    Також цю задачу можна вирішити за допомогою рекурсії. Я використала рекурсію з запам’ятовуванням для того, щоб уникнути переповнення стеку викликів (загальна ідея така: при кожному виклику функції перевіряємо, чи маємо ми вже це значення, і якщо ні, рахуємо його. Таким чином ми будемо використовувати кожне значення лише один раз).

    Код № 2

    Посилання

    Умова задачі на E-Olymp
    Зараховане рішення № 1 на E-Olymp
    Зараховане рішення № 2 на E-Olymp
    Код задачі № 1 на Ideone
    Код задачі № 2 на Ideone

    e-olymp 236. Триомино

    Триомино

    Сколькими способами можно замостить прямоугольник $2 × n$ триоминошками? Триомино — это геометрическая фигура, составленная из трех квадратов, соединяющихся между собой вдоль полного ребра. Есть только две возможных триоминошки:

    Например, замостить прямоугольник $2 × 3$ можно только тремя различными способами. Поскольку ответ может быть достаточно большим, искомое количество способов следует вычислять по модулю $10^6$.

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

    Первая строка содержит количество тестов $t$ ($1 \leqslant  t \leqslant  100$). Каждая из следующих $t$ строк содержит значение $n$ ($0 < n < 10^9$).

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

    Для каждого теста в отдельной строке выведите количество способов, которыми можно замостить прямоугольник $2 × n$. Результат следует выводить по модулю $10^6$.

    Тесты

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

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

    1 3
    3
    4
    6
    3
    0
    11
    2 4
    12
    15
    21
    9
    153
    571
    7953
    41

    Код

    Решение

    Если n нацело не делится на $3$, то выводится ноль,в ином случае данная задача решается через рекуррентную формулу $a_n=4*a_{n-1}-a_{n-2}$. Но из-за слишком больших чисел мы не можем использовать данную формулу просто так, поэтому мы воспользуемся быстрым вычислением членов рекуррентной последовательности через матрицы. Надо умножать матрицу

    $\begin{pmatrix}
    4&-1 \\
    1&0 \\
    \end{pmatrix}$ в степени $p$(где $p$ равна двойке в степени номера единицы в двоичной записи числа ${{n}\over{3}}$) на матрицу $\begin{pmatrix}
    1\\
    1\\
    \end{pmatrix}$ каждый раз, когда встречается единица в двоичной записи числа ${{n}\over{3}}$. На выход подается первое число вектора $2 × 1$.

    Ссылки

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

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

    e-olymp 9066. Кружок стрельбы

    Задача

    После успешного обучения Атрея стрельбе из лука «Когтя» Фэй решила не останавливаться на достигнутом и открыть целый кружок стрельбы из лука.

    На занятие кружка пришли $n$ учеников. Фэй пронумеровала их целыми числами от $1$ до $n$. В начале занятия ученики встали вдоль координатной прямой, заблаговременно нарисованной на полу, причем i-й ученик стоял в точке с координатой $x_i$. Получилось так, что координаты учеников строго возрастали, то есть $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

    У каждого из учеников есть свой волшебный лук, который характеризуется своей дальностью $r_i$ и силой $c_i$. Оба параметра — целые положительные числа. Когда ученик совершает выстрел из лука, магический снаряд начинает лететь вдоль координатной прямой в сторону увеличения координаты. Снаряд летит до тех пор, пока его сила положительна. В момент выстрела сила заряда равна силе лука, из которого совершается выстрел. Каждый раз, когда снаряд пролетает очередные $r_i$ единиц расстояния вдоль прямой, он теряет одну единицу силы.

    Если ученик произвел выстрел, и снаряд, выпущенный им, достиг следующего по порядку вдоль прямой ученика, снаряд прекращает свой полет, а ученик, которого достиг снаряд, внезапно решает, что ему тоже надо произвести выстрел, и совершает его. Ученик совершит выстрел, даже если снаряд достиг его, имея силу $0$.

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

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

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

    Первая строка содержит количество учеников $n$ $(1 \leqslant n \leqslant 1000)$ на кружке Фэй.

    Каждая из следуюших $n$ строк содержит три целых числа $x_i$, $r_i$ и $c_i$ ($1 \leqslant x_i \leqslant 10^9$, $1 \leqslant r_i$, $c_i \leqslant 100$) — координату очередного ученика, а также дальность и силу его лука соответственно. Гарантируется, что $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

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

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

    Тесты

    ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
     1 5
    1 3 3
    5 1 2
    8 2 3
    10 1 2
    11 3 2
    2
    2 6
    1 3 5
    4 2 2
    7 4 3
    10 1 2
    11 3 2
    13 4 3
    1

    Код

    Решение

    Для решения задачи, мы должны найти расстояние между лучниками, то есть $x_{i+1}-x_i$, после чего найти максимальное расстояние, которое пролетит стрела у $x_{i}$ лучника умножив силу его лука $c_i$ и расстояние $r_i$, после чего сделать проверку, если расстояние между лучниками больше чем максимальное расстояние которое пролетит стрела, то мы дадим команду совершить ещё один выстрел.

    Ссылки

    • Условие задачи на e-olymp
    • Код на Ideone
    • Засчитанное решение на e-olymp 

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

    Задача

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

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

    Первая строка содержит число  $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

    Код

    Решение

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

    Ссылки

    e-olymp 8956. Вывести массив 4

    Задача

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

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

    Первая строка содержит число [latex]n (1 \leqslant n \leqslant 100)[/latex]. Во второй строке записаны [latex]n[/latex] целых чисел, каждое из которых не превышает по модулю [latex]100[/latex].

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

    В первой строке выведите количество отрицательных элементов массива. Во второй строке выведите сами отрицательные элементы в обратном порядке. Если отрицательных элементов в массиве нет, то выведите [latex]«NO»[/latex].

    Тесты

    # ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
    1 7
    -2 5 4 -3 7 -1 0
    3
    -1 -3 -2
    2 5
    2 1 0 1 5
    NO
    3 3
    -1 -2 -3
    3
    -3 -2 -1

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

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

    Для решения этой задачи, прежде всего, необходимо объявить две целочисленные переменные ― [latex]n[/latex] и [latex]count[/latex]. Переменная [latex]n[/latex] считывает первое число в строке ввода, и после объявления некоторого массива arr[n], она становится значением числа его элементов. Переменной [latex]count[/latex] обязательно присваиваем значение [latex]0[/latex], ведь именно она позднее будет отвечать за подсчет отрицательных элементов заданного массива.

    С помощью цикла for задаем массив, начиная с нулевого элемента и заканчивая [latex]n[/latex]-ым элементом (не включительно!). Внутри цикла размещаем условный оператор if, который прибавляет единицу к переменной count каждый раз, когда элемент массива отрицателен. После окончания цикла важно не забыть о еще одном условном операторе, который будет выводить [latex]«NO»[/latex] и заканчивать работу программы, если значение [latex]count[/latex] равно нулю (то есть именно в том случае, если в массиве не будет ни одного отрицательного элемента). Но если в массиве всё же есть отрицательные элементы, то программа должна продолжить работу, что мы и предусматриваем, выполняя все остальные операции в рамках оператора else. Отлично! Теперь полученное значение переменной [latex]count[/latex] (если оно больше нуля) можно вывести, однако это еще не конец, ведь также необходимо вывести все отрицательные элементы в обратном порядке, так что переходим на новую строку с помощью endl и продолжаем.

    Реализация подобной процедуры не так сложна, как кажется. Для этого необходимо создать еще один цикл for, перебирающий массив с конца (то есть от [latex]n-1[/latex] до [latex]0[/latex] включительно). Внутри цикла вновь создаем условный оператор if, который каждый раз выводит элемент массива (с пробелом), если он оказывается отрицательным. Не забываем закрыть скобку оператора else, ведь эта процедура также выполняется внутри условного оператора.

    Готово!

    e-olymp 2386. Следующая перестановка

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

    Найдите следующую перестановку. Тождественная перестановка является следующей для обратной.

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

    В первой строке записано количество элементов $n$ $\left(1\leqslant n\leqslant10^5\right)$ в перестановке. Во второй строке записана перестановка из $n$ чисел.

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

    Вывести $n$ чисел — искомую перестановку.

    Тесты

    Ввод Вывод
    1 3
    3 2 1
    1 2 3
    2 1
    9
    9
    3 5
    2 4 5 3 1
    2 5 1 3 4
    4 4
    3 5 4 1
    4 1 3 5
    5 2
    2 3
    3 2

    Алгоритм Нарайаны

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

    Решение

    Пусть $a$ — данная $n$-элементная перестановка $\left(a\;=\;\left[a_1,\;a_2,\;…,\;a_n\right]\right)$. Применяем алгоритм Нарайаны :

    • Находим наибольший номер $i$ (если он существует), такой, что $a_i<a_{i+1}$. Находим такой номер $j$, что число $a_j$ является наименьшим среди чисел $a_{i+1},\;a_{i+2},\;…,\;a_n$, превосходящим $a_j$. Меняем местами элементы $a_i$ и $a_j$ .
    • Если такого номера не существует, то $a$ — наибольшая $n$-элементная перестановка.
    • Изменяем порядок элементов, занимающих места с $\left(i+1\right)$-го по $n$-е, на противоположный.

    Полученная перестановка $\left[a_1,\;a_2,\;…,\;a_{i-1},\;a_j,\;a_n,\;a_{n-1},\;…,\;a_{j+1},\;a_i,\;a_{j-1},\;…,\;a_{i+1}\right]$  будет являться искомой перестановкой.

    Ссылки

     Функция next_permutation()

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

    Решение

    Применяем функцию next_permutation() , которая генерирует следующую лексиграфическую перестановку в диапазоне элементов.

    Ссылки

    e-olymp 1661. Рюкзак Алладина

    Условие

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

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

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

    Будем считать, что в пещере имеются предметы $n$ различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен $w$. Каждый предмет типа $i$ имеет вес $w_{i}$ и стоимость $v_{i}$ $(i = 1, 2, \ldots, n)$.

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

    В первой строке содержится два натуральных числа $w$ и $n$ $(1 \leqslant w \leqslant 250, 1 \leqslant n \leqslant 35)$ — максимальный вес предметов в рюкзаке и количество типов предметов. Следующие $n$ строк содержат по два числа $w_{i}$ и $v_{i}$ $(1 \leqslant w_{i} \leqslant 250, 1 \leqslant v_{i} \leqslant 250)$ — вес предмета типа $i$ и его стоимость.

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

    Выведите максимальную стоимость груза, вес которого не превышает $w$.

    Тесты

    Входные данные Выходные данные
    1 10 2
    5 10
    6 19
    20
    2 250 35
    187 100
    28 109
    245 142
    123 83
    237 78
    36 172
    15 248
    90 24
    181 137
    40 233
    8 99
    231 128
    79 132
    43 217
    156 104
    45 191
    130 113
    105 225
    206 5
    26 120
    26 119
    64 138
    23 147
    19 202
    79 54
    149 185
    158 79
    209 88
    110 133
    235 209
    188 230
    15 220
    107 164
    235 137
    60 167
    4067
    3 35 4
    20 4
    1 2
    10 8
    7 6
    70

    Программный код

    Решение

    Допустим $w = 9$, $n = 2$, первый предмет $w_{1} = 3$, $n_{1} = 4$, а второй предмет $w_{2} = 2$, $n_{2} = 1$. После того как считаем условие в два одномерных или один двумерный массив (как вам удобнее). Создадим одномерный массив в котором его размер будет равен $w$ и первый элемент будет равен 0, а остальные будут равны минус бесконечности или как в нашем случае (в коде) -1, как показано на (рис. 1). И дальше как показано на (рис. 2) начиная с элемента с номером веса предмета мы прибавляем его стоимость к стоимости предыдущей как показано в коде s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];, если прошлый не минус бесконечность. И так же со вторым элементом, когда они пересекаются с первым мы их сравниваем и вписываем в массив, больший. И в самом конце проходим заново массив и выбираем самый больший элемент, где бы он ни был как показано на (рис. 3). И таким образом на последних позициях которые равняются весу, будут записаны самые дорогие комбинации, благодаря записи самых дорогих элементов в ячейки.

    Ссылки:
    Задача на e-olymp
    Код на OnlineGDB
    Код на Ideone
    Засчитанное решение на e-olymp

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

    Условие

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

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

    В первой строке содержится количество элементов $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$.

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

    Ссылки

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

    e-olymp 8963. Наименьшие влево

    Условие

    Задан массив из [latex]n[/latex] целых чисел. Переместить все минимальные элементы в начало массива, не меняя порядок других.

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

    В первой строке записано натуральное число [latex]n[/latex]. В следующей строке записаны [latex]n[/latex] целых чисел. Все числа по модулю не превышают [latex]100[/latex].

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

    Выведите элементы обновленного массива.

    Тесты

    Ввод Вывод
    1 7
    6 -3 -7 4 -7 -4 5
    -7 -7 6 -3 4 -4 5
    2 2
    100 -100
    -100 100
    3 6
    -2 -2 7 3 99 -2
    -2 -2 -2 7 3 99
    4 5
    1 1 1 1 1
    1 1 1 1 1

    Решение

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

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

    Ссылки

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