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

10/02/2020 by Виктория Крачилова

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

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

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

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

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

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

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin>>n;
    int a[n]; // массив для перестановки из n чисел
    for (int i = 0; i < n; i++) cin>> a[i];
    for (int i = n - 2; i >= 0; i--) { 
        if (a[i] < a[i+1]){
            int min = i + 1; // индекс минимального элемента 
            for (int j = i + 2; j < n; j++) {
                if (a[j] > a[i] && a[j] < a[min]) min = j;
            }
            swap(a[i], a[min]);
            reverse(&a[i+1], &a[n]);
            break;
        }
        if (i == 0) reverse(&a[i], &a[n]);
    }
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n;

cin>>n;

int a[n]; // массив для перестановки из n чисел

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

for (int i = n - 2; i >= 0; i--) {

if (a[i] < a[i+1]){

int min = i + 1; // индекс минимального элемента

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

if (a[j] > a[i] && a[j] < a[min]) min = j;

}

swap(a[i], a[min]);

reverse(&a[i+1], &a[n]);

break;

}

if (i == 0) reverse(&a[i], &a[n]);

}

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

return 0;

}

Решение

Пусть $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()

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

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

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    next_permutation(a, a+n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n;

cin >> n;

int a[n];

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

next_permutation(a, a+n);

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

return 0;

}

Решение

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

Ссылки

Related Images:

e-olymp 1704. Умная черепашка

23/01/2020 by Виктория Крачилова

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

Имеется клетчатое поле размером $m\times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?

Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.

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

Два натуральных числа $m$ и $n$, не превышающие 30.

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

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

Тесты

№	Ввод	Вывод
1	4 5	10
2	3 14	105
3	11 17	5311735
4	20 21	68923264410
5	30 30	30067266499541040

Код программы (циклы)

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    if (m > n) swap(n, m);
    long long den = 1, ways = 1; // den - знаменатель, ways - количество способов.
    for (int i = 0; i < m - 1; i++) {
        ways *= n + i;
        if (ways % den == 0) {
            ways /= den;
            den++;
        }
    }
    cout << ways;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

if (m > n) swap(n, m);

long long den = 1, ways = 1; // den - знаменатель, ways - количество способов.

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

ways *= n + i;

if (ways % den == 0) {

ways /= den;

den++;

}

cout << ways;

return 0;

}

Решение

Для нахождения количества способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний, мы воспользуемся формулой из комбинаторики: $\frac{\left(n+m-2\right)!}{(n-1)!\times(m-1)!}$. Для того, чтобы избежать больших чисел, делим на наибольший множитель знаменателя (пусть это будет $\left(n-1\right)!$ ). Получаем: $ \frac{n\times(n+1)\times…\times(n+m-2)}{1\times2\times…\times(m-1)}$. Домножаем числитель, пока он не делится на очередной сомножитель знаменателя. Если делится, то делим и переходим к следующему сомножителю знаменателя.

Код программы (динамическое программирование)

#include <iostream>
#define N 30
int main() {
    // Создаем треугольную матрицу для хранения всех ответов
    long *x[N];
    for (int i=0; i < N; ++i) x[i] = new long[i+1];
    // Находим все ответы
    x[0][0] = 1;
    for (int i=1; i < N; ++i) {
        x[i][0] = 1;
        for (int j=1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1];
        x[i][i] = 2 * x[i][i-1];        
    }
    // Проходим все тесты
    int m, n; 
    std::cin >> m >> n;
    std::cout << x[std::max(n,m)-1][std::min(n,m)-1];
}

#include <iostream>

#define N 30

int main() {

// Создаем треугольную матрицу для хранения всех ответов

long *x[N];

for (int i=0; i < N; ++i) x[i] = new long[i+1];

// Находим все ответы

x[0][0] = 1;

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

x[i][0] = 1;

for (int j=1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1];

x[i][i] = 2 * x[i][i-1];

}

// Проходим все тесты

int m, n;

std::cin >> m >> n;

std::cout << x[std::max(n,m)-1][std::min(n,m)-1];

}

Решение

Заполним треугольную матрицу ответами для всех возможных значений $m$ и $n$ . Логика заполнения такая — если поле выглядит как полоска клеток, черепахе идти можно будет только вправо. Значит в первой строке (как и в столбце) будут все элементы равные 1. Поскольку в каждой клетке есть два варианта движения (вправо или вверх), остальные элементы будут заполняться как сумма ранее найденных значений для клеток справа текущей и над ней. Для диагональных элементов оба соседних расположены симметрично (то есть они равны), поэтому диагональный элемент будет равен удвоенному соседу справа. Решение намного быстрее, если нужно пройти много тестов, но тратит память на запоминание всех ответов.

Ссылки (циклы)

Ссылки (динамическое программирование)

Related Images:

e-olymp 7612. Алекс и квадраты оригами

04/12/2019 by Эвелина Алексютенко

Задача

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

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

В одной строке два целых числа [latex] h [/latex] и [latex] w [/latex] [latex] \left ( 1\leqslant h,w\leqslant 1000 \right ) [/latex] — высота и ширина куска бумаги.

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

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

Тесты

Входные данные	Выходные данные
30 11	10.0000
8 3	2.6667
210 297	105.0000
60 59	29.5000
250 100	83.3333

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

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

int main() {
    double h, w, ans = 0;
    cin >> h >> w;
    if (w < h) {
        swap (w, h);
    }
    ans = ( w >= 3 * h ? h : max (h / 2, w / 3) );
    cout << fixed << setprecision(4) << ans;
}

#include <iostream>

#include <algorithm>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double h, w, ans = 0;

cin >> h >> w;

if (w < h) {

swap (w, h);

}

ans = ( w >= 3 * h ? h : max (h / 2, w / 3) );

cout << fixed << setprecision(4) << ans;

}

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
 
int main() {
    double h, w, tmp = 0,  ans = 0;
    cin >> h >> w;
    if (w < h) {
        tmp = h;
        h = w;
        w = tmp;
    }
    if (w >= 3 * h) {
        ans = h;
    }
    else {
        ans = max (h / 2, w / 3);
    }
    cout << fixed << setprecision(4) << ans;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double h, w, tmp = 0, ans = 0;

cin >> h >> w;

if (w < h) {

tmp = h;

h = w;

w = tmp;

}

if (w >= 3 * h) {

ans = h;

}

else {

ans = max (h / 2, w / 3);

}

cout << fixed << setprecision(4) << ans;

}

Алгоритм решения

Допустим, что [latex] w [/latex] всегда больше чем [latex] h [/latex] . Из условия следует, что варианта расположения данных квадратов два:

В первом случае ответом будет [latex] \max\left ( \frac{h}{2}, \frac{w}{3} \right ) [/latex]. Во втором же, ответом будет [latex] h [/latex] .

Детали реализации

В первом коде программы используется используется библиотека
#include <algorithm> , которая включает в себя функцию swap() , так же, используется библиотека #include <cmath> , которая включает в себя функцию max() .
Для вывода ответа с точностью не меньше трех десятичных знаков используется библиотека
#include <iomanip> и манипуляторы fixed и setprecision() .

Ссылки :
Задача на e-olymp
Код № 1 на ideone
Код № 2 на ideone
Засчитанное решение № 1
Засчитанное решение № 2

Related Images:

АА13

14/03/2015 by Недомовний Владислав

Задача.

В заданной строке поменять местами рядом стоящие символы между собой (1 и 2, 3 и 4 и т.д., для строки нечетной длины, последний символ не менять).

Тесты.

Ввод	Вывод	Комментарий
123456	214365	Пройден
abcde	badce	Пройден

Код.

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

int main() {
	string s; 
	cin >> s; //ввод строки
	for (int i=1;i<s.length();i+=2)
	{
		swap(s[i-1],s[i]); //меняем местами соседние буквы
	}
	cout << s;
	return 0;
}