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 9036. Комбинация игральных костей

10/12/2019 by Алина Зозуля

Задача

Подсчитайте количество способов, которыми можно получить сумму $n$ бросая игральный кубик один или несколько раз. Каждый бросок дает результат между 1 и 6.

Например, если $n = 3$, то имеется 4 способа:
1 + 1 + 1
1 + 2
2 + 1
3

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

Одно целое число $n$ $(1 \leqslant n \leqslant 10^6)$.

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

Выведите количество способов по модулю $10^9+7$.

Тесты

№	Входные данные	Выходные данные
1	1	1
2	3	4
3	5	16
4	6	32
5	8	123

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

Первый способ (выполняется быстрее, но использует больше памяти)

#include <iostream>
using namespace std;

int main() {
    int n;
    int ans;
    cin >> n; //считываем сумму, для которой будем считать количество перестановок
    long long a[n+1]; //создаем массив
    if (n == 1) ans = 1;
    if (n == 2) ans = 2;
    if (n == 3) ans = 4;
    if (n == 4) ans = 8;
    if (n == 5) ans = 16;
    if (n == 6) ans = 32;
    // частные случаи
    
    if (n > 6)
    {
        a[1] = 1; 
        a[2] = 2; 
        a[3] = 4; 
        a[4] = 8;
        a[5] = 16; 
        a[6] = 32; 
        for (int i = 7; i < n + 1; i++)
        {
            a[i]=0;
            for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы
                a[i] = ( a[i] + a[i-j] ) % 1000000007;
        }
        ans = a[n];
    }
    
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

int ans;

cin >> n; //считываем сумму, для которой будем считать количество перестановок

long long a[n+1]; //создаем массив

if (n == 1) ans = 1;

if (n == 2) ans = 2;

if (n == 3) ans = 4;

if (n == 4) ans = 8;

if (n == 5) ans = 16;

if (n == 6) ans = 32;

// частные случаи

if (n > 6)

{

a[1] = 1;

a[2] = 2;

a[3] = 4;

a[4] = 8;

a[5] = 16;

a[6] = 32;

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

{

a[i]=0;

for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы

a[i] = ( a[i] + a[i-j] ) % 1000000007;

}

ans = a[n];

}

cout << ans;

return 0;

}

Второй способ (использует меньше памяти, но выполняется дольше)

#include <iostream>
using namespace std;

int main() {
    int a[6]={1, 2, 4, 8, 16, 32}; //создаём массив на 6 элементов и заполняем для n от 1 до 6
    int n, quantity, counter = 6;
    cin >> n; //считываем сумму
    if (n > 6)
    {
        while (counter < n)
        {
            counter++; //счетик, значение которого - сумма, для которой мы ищем количество способов
            quantity = 0;
            for (int j = 1; j < 7; j++) //подсчет количества способов для k-ой суммы
                quantity = (quantity + a[6-j]) % 1000000007;
                
            for (int i = 0; i < 5; i++)  
                a[i] = a[i+1];
            a[5] = quantity;
        }
        cout << a[5];
    }
    else cout << a[n-1];
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a[6]={1, 2, 4, 8, 16, 32}; //создаём массив на 6 элементов и заполняем для n от 1 до 6

int n, quantity, counter = 6;

cin >> n; //считываем сумму

if (n > 6)

{

while (counter < n)

{

counter++; //счетик, значение которого - сумма, для которой мы ищем количество способов

quantity = 0;

for (int j = 1; j < 7; j++) //подсчет количества способов для k-ой суммы

quantity = (quantity + a[6-j]) % 1000000007;

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

a[i] = a[i+1];

a[5] = quantity;

}

cout << a[5];

}

else cout << a[n-1];

return 0;

}

Решение

Создадим массив на $n+1$ элемент. В который мы сразу запишем количество перестановок для сумм 1,2..,6. Для остальных случаев, когда $n>7$ воспользуемся следующей идеей. Будем вычислять количество перестановок для сумм, начиная с 7 до тех пор, пока не дойдем до заданного нам $n$. Будем делать это по такой формуле $a_{i}=a_{i-1}+a_{i-2}+a_{i-3}+a_{i-4}+a_{i-5}+a_{i-6}$ . Для первых шести сумм вычисляем по этой же формуле, с учетом, что $0 < i-k \; (1 \leqslant k \leqslant 6)$ и добавляя еще 1 перестановку, так как мы можем получить сумму ( $i$ ), подбросив кубик 1 раз. Рассмотрим для $n=7$. Чтобы получить 7 достаточно подбросить кубик ещё один раз, так как мы знаем количество для $n$ от 1 до 6. Если выпадет 1, то остается $a_{6}$ возможных перестановок, если выпадет 2, то остается $a_{5}$ и так далее. Затем нам требуется просуммировать, так как кубик может выпасть 6 способами, как было сказано ранее. Соответственно для $n=8$ количество комбинаций увеличится на $a_{7}$ и уменьшится на $a_{1}$, так как кубик имеет только 6 граней.

Ссылки

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

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

Related Images:

e-olymp 407. Обмін

26/12/2018 by Владислав Шеванов

Задача

У різдвяний вечір у віконці стояло три квіточки, зліва на право: герань, крокус та фіалка. Кожен ранок Маша витирала віконце і міняла містами стоявшу праворуч квіточку з центральною кввточкою. А Таня кожен вечір поливала квіточки і міняла місцями ліву та центральну квіточку. Потрібно визначити порядок квітів вночі після того, як пройде $k$ днів.

Вхідні дані

Перший рядок містить кількість тестів $t$ [latex](1 \leq t \leq 12)[/latex]. В кожному з наступних $t$ рядків знаходиться кількість днів $k$ [latex](k \leq 1000)[/latex].

Вихідні дані

Вивести $t$ рядків, що містять по три латинських літери: «G», «C» и «V» (великі літери без пропусків), які описують порядок квітів на вікні по закінченню $k$ днів (зліва направо). Позначення: G – герань, C – крокус, V – фіалка.

Тести

№	Вхідні дані	Вихідні дані
1	2 1 5	VGC CVG
2	6 1 2 3 4 5 6	VGC CVG GCV VGC CVG GCV
3	3 3 6 9	GCV GCV GCV

Код програми

#include <iostream>
using namespace std;

int main() {
    int n, day;
    cin >> n;
    while (n--) {
        cin >> day;
        if (day % 3 == 1)
            cout<<"VGC"<<endl;
        else if (day % 3 == 2)
            cout<<"CVG"<<endl;
        else
            cout<<"GCV"<<endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, day;

cin >> n;

while (n--) {

cin >> day;

if (day % 3 == 1)

cout<<"VGC"<<endl;

else if (day % 3 == 2)

cout<<"CVG"<<endl;

else

cout<<"GCV"<<endl;

}

return 0;

}

Розв’язок

Якщо кожного вечора звертати увагу на те, як Маша і Таня міняють місцями квіти, то можна помітити, що їх перестановки періодично повторюються кожні три дні. Цим я скористався для розв’язку задачі. Достатньо лише задати ці три перестановки і брати залишок від ділення на три для визначення конкретної.

Посилання

e-olymp
ideone.com

Related Images:

e-olymp 6. Путёвки

21/12/2015 by Александр Коломеец

Постановка задачи

e-olymp 6. Путёвки

Туристическая фирма не успела из-за больших морозов продать [latex]n[/latex] ([latex]n < 15[/latex]) путёвок на горнолыжные базы, срок действия которых уже наступил. С целью уменьшения убытков, было решено с 1 февраля все такие путёвки, которым осталось [latex]d_k[/latex] ([latex]d_k \le 30[/latex]) дней, продавать по номинальной стоимости – по [latex]c_k[/latex] ([latex]c_k \le 100[/latex]) грн за день только за те дни, что остались со дня продажи ([latex]k = 1..n[/latex]).

На какую наибольшую сумму можно реализовать эти путёвки, если каждый день продавать по одной путёвке?

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

Первая строка содержит количество путёвок [latex]n[/latex]. Каждая из следующих [latex]n[/latex] строк содержит два числа – количество дней [latex]d_k[/latex] и стоимость дня [latex]c_k[/latex].

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

Максимальная сумма прибыли.

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

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

Первая путёвка

срок действия: 2
номинальная стоимость: 13

Вторая путёвка

срок действия: 1
номинальная стоимость: 33

Третья путёвка

срок действия: 3
номинальная стоимость: 7

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

Путевки	Перебор всех возможных вариантов
	Вариант 1		Вариант 2
	Очередность	Результат	Очередность	Результат
Первая	1	20	1	20
Вторая	2		3
Третья	3		2
	Вариант 3		Вариант 4
	Очередность	Результат	Очередность	Результат
Первая	2	53	2	20
Вторая	1		3
Третья	3		1
	Вариант 5		Вариант 6
	Очередность	Результат	Очередность	Результат
Первая	3	40	3	7
Вторая	1		2
Третья	2		1

Теперь очевидно, что максимальная сумма прибыли равна 53. Таким образом можно решить данную задачу при любых входных данных. Но возникает проблема, когда путевок слишком много (или даже не очень). Количество перестановок для [latex]n[/latex] элементов равно [latex]n![/latex]. Это значит, что при количестве путевок, равном [latex]14[/latex] (максимальное возможное количество в данной задаче), количество перестановок равно [latex]14! = 87178291200[/latex], а ведь для каждой необходимо подсчитать сумму за реализованые путевки. Современные компьютеры не могут справиться с этой задачей за короткий промежуток времени, поэтому явным решением является оптимизация программы.

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

Тесты

Входные данные	Выходные данные
4 2 37 3 45 1 46 4 30	232
3 1 1 2 2 3 3	11
4 1 2 3 4 5 6 7 8	84

Реализация

ideone: ссылка
Засчитаное решение: ссылка

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

struct ticket {
	int id, validity, price;
};

int cutDown(ticket tickets[], int count) {
	for(int validity = 0; validity <= min(30, count - 1); validity++) {
		int ticketsCount = 0;
		for(int i = 0; i < count; i++) {
			if(tickets[i].validity == validity) {
				ticketsCount++;
			}
		}
		while(ticketsCount > validity) {
			int cheapestTicketPosition = -1;
			int cheapestTicketPrice = 101;
			for(int i = 0; i < count; i++) {
				if(tickets[i].validity == validity && tickets[i].price < cheapestTicketPrice) {
					cheapestTicketPrice = tickets[i].price;
					cheapestTicketPosition = i;
				}
			}
			tickets[cheapestTicketPosition] = tickets[--count];
			ticketsCount--;
		}
	}
	return count;
}

bool comparator(const ticket t1, const ticket t2) {
	return t1.id < t2.id;
}

int main() {
	int count;
	cin >> count;
	ticket tickets[count];
	for(int i = 0; i < count; i++) {
		tickets[i].id = i;
		cin >> tickets[i].validity >> tickets[i].price;
	}
	count = cutDown(tickets, count);
	sort(tickets, tickets + count, comparator);
	int maxProfit = 0;
	do {
		int profit = 0;
		for(int i = 0; i < count; i++) {
			profit += tickets[i].validity > i ? tickets[i].price * (tickets[i].validity - i) : 0;
		}
		maxProfit = max(profit, maxProfit);
	} while(next_permutation(tickets, tickets + count, comparator));
	cout << maxProfit << endl;
	return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

struct ticket {

int id, validity, price;

};

int cutDown(ticket tickets[], int count) {

for(int validity = 0; validity <= min(30, count - 1); validity++) {

int ticketsCount = 0;

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

if(tickets[i].validity == validity) {

ticketsCount++;

}

while(ticketsCount > validity) {

int cheapestTicketPosition = -1;

int cheapestTicketPrice = 101;

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

if(tickets[i].validity == validity && tickets[i].price < cheapestTicketPrice) {

cheapestTicketPrice = tickets[i].price;

cheapestTicketPosition = i;

}

tickets[cheapestTicketPosition] = tickets[--count];

ticketsCount--;

}

return count;

}

bool comparator(const ticket t1, const ticket t2) {

return t1.id < t2.id;

}

int main() {

int count;

cin >> count;

ticket tickets[count];

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

tickets[i].id = i;

cin >> tickets[i].validity >> tickets[i].price;

}

count = cutDown(tickets, count);

sort(tickets, tickets + count, comparator);

int maxProfit = 0;

do {

int profit = 0;

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

profit += tickets[i].validity > i ? tickets[i].price * (tickets[i].validity - i) : 0;

}

maxProfit = max(profit, maxProfit);

} while(next_permutation(tickets, tickets + count, comparator));

cout << maxProfit << endl;

return 0;

}

Related Images:

А1033

17/06/2015 by Марченко Філіп Олександрович

Условие

Получить все размещения из [latex]9[/latex] элементов [latex]\left\{1,2, \ldots, 9\right\}[/latex] по [latex]5[/latex] элементов в каждом.

Код на С++

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;


int a1[6]; int a2[6]; int cnt=0;


//генерация перестановок
void permut (int m){
	for (int j=1; j<=m; j++) a2[j]=a1[j];
	int i = 1;
	int j;
	while (i != 0){
		for (int i=1; i<=m; i++) cout << a2[i];
		cout << endl;
		i=m-1;
		while (a2[i]>a2[i+1]) i--;
		j=m;
		while (a2[j]<a2[i]) j--;
		swap (a2[j],a2[i]);
		int k=i+1;
		int kk=i+floor((m-i)/2);
		while (k<=kk){
			swap(a2[k],a2[m-k+i+1]);
			k++;
		}
		cnt++;
	}
}

int main() {
    int n=9, k=5;
	int p=k;
        //генерация размещений
	for (int i=1; i<=k; i++) a1[i]=i;
	while(p>=1){
        permut(k);
		if (a1[k]==n)
			p-=1;
		else
			p=k;
		if (p>=1)
			for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1;
	}
        //проверка количества размещений
	cout << cnt << endl;
	return 0;
}

#include <iostream>

#include <algorithm>

#include <math.h>

using namespace std;

int a1[6]; int a2[6]; int cnt=0;

//генерация перестановок

void permut (int m){

for (int j=1; j<=m; j++) a2[j]=a1[j];

int i = 1;

int j;

while (i != 0){

for (int i=1; i<=m; i++) cout << a2[i];

cout << endl;

i=m-1;

while (a2[i]>a2[i+1]) i--;

j=m;

while (a2[j]<a2[i]) j--;

swap (a2[j],a2[i]);

int k=i+1;

int kk=i+floor((m-i)/2);

while (k<=kk){

swap(a2[k],a2[m-k+i+1]);

k++;

}

cnt++;

}

int main() {

int n=9, k=5;

int p=k;

//генерация размещений

for (int i=1; i<=k; i++) a1[i]=i;

while(p>=1){

permut(k);

if (a1[k]==n)

p-=1;

else

p=k;

if (p>=1)

for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1;

}

//проверка количества размещений

cout << cnt << endl;

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class A {
	public static int cnt = 0;
	public static void Permutation (int m, int[] a1, int[] a2){
		for (int j=1; j<=m; j++) a2[j] = a1[j];
		int j;
		int i = 1;
		while (i != 0){
			//for (i=1; i<=m; i++) System.out.print(a2[i]);
			//System.out.print("\n");
			i=m-1;
			while (a2[i]>a2[i+1]) i--;
			j=m;
			while (a2[j]<a2[i]) j--;
			int tmp = a2[j];
			a2[j] = a2[i];
			a2[i] = tmp;
			int k=i+1;
			int kk=i + (m-i)/2;
			while (k<=kk){
				tmp = a2[k];
				a2[k] = a2[m-k+1+i];
				a2[m-k+1+i] = tmp;
				k++;
			}
			cnt++;
		}
	}
	public static void main (String[] args) {
		int[] a1; int[] a2;
		a1 = new int [6];
		a2 = new int [6];
		int n=9, k=5;
		int p=k;
		for (int i=1; i<=k; i++) a1[i]=i;
		while(p>=1){
	        Permutation(k, a1, a2);
			if (a1[k]==n)
				p-=1;
			else
				p=k;
			if (p>=1)
				for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1;
		}
		System.out.println(cnt);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class A {

public static int cnt = 0;

public static void Permutation (int m, int[] a1, int[] a2){

for (int j=1; j<=m; j++) a2[j] = a1[j];

int j;

int i = 1;

while (i != 0){

//for (i=1; i<=m; i++) System.out.print(a2[i]);

//System.out.print("\n");

i=m-1;

while (a2[i]>a2[i+1]) i--;

j=m;

while (a2[j]<a2[i]) j--;

int tmp = a2[j];

a2[j] = a2[i];

a2[i] = tmp;

int k=i+1;

int kk=i + (m-i)/2;

while (k<=kk){

tmp = a2[k];

a2[k] = a2[m-k+1+i];

a2[m-k+1+i] = tmp;

k++;

}

cnt++;

}

public static void main (String[] args) {

int[] a1; int[] a2;

a1 = new int [6];

a2 = new int [6];

int n=9, k=5;

int p=k;

for (int i=1; i<=k; i++) a1[i]=i;

while(p>=1){

Permutation(k, a1, a2);

if (a1[k]==n)

p-=1;

else

p=k;

if (p>=1)

for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1;

}

System.out.println(cnt);

}

Решение

При решении этой задачи мне понадобились 2 источника информации:

Там были приведены алгоритмы генерирования перестановок («Комбинаторные алгоритмы», стр. 27-29) и генерирования сочетаний («Комбинаторика для программистов», стр. 39-41).
Размещения я получал следующим образом:

Посчитал кол-во всевозможных размещений по формуле [latex]A^{k}_{n}=\frac{n!}{(n-k)!}=\frac{9!}{4!}=15120[/latex];
Заметил, что размещения — это перестановки всех уникальных комбинаций из 5 чисел (т.е сочетаний);
Поскольку кол-во перестановок [latex]P_{k}=k![/latex], а кол-во сочетаний — [latex]C_{n}^{k}=\frac{n!}{k!(n-k)!}[/latex], то кол-во размещений [latex]A_{n}^{k}=P_{k}\times{C_{n}^{k}}=\frac{n!k!}{k!(n-k)!}=\frac{n!}{(n-k)!}=15120[/latex];

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

Related Images:

A1031

06/06/2015 by Денисова Ольга

Задача. Получить все перестановки элементов 1, …, 6.

Решение

Все перестановки считаются и выводятся с помощью рекурсивной функции perestanovka().

Когда в ней складывается новый набор элементов, проверяем что бы в нем не было повторяющихся значений (считаем факториал и сумму, они должны совпадать со стандартом (6! = 720, 1+2+3+4+5+6 = 21) и тогда выводим.

Что бы убедиться, что выведено правильное количество перестановок, выводим в конце значение счетчика cnt (находится внутри функции perestanovka()) и требуемое значение перестановок ( 6! = 720). Эти значения совпадают.

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

const int n = 6;
int cnt = 0;
int a[n]; 
int ft, sum;

unsigned int fact(unsigned int n) { return ( ! n || n == 1 ) ? 1 : n * fact(n - 1); }
unsigned int summa(unsigned int n) { return ( ! n || n == 1 ) ? 1 : n + summa(n - 1); }

void perestanovka(int k) { 
	int pr, sm; 
	for ( a[k] = 1; a[k] <= n; a[k]++) { 
		if ( k == n-1) {
			pr = 1; 
			sm = 0; 
			for ( int i = 0; i < n; i++) {
				pr = pr*a[i];
				sm += a[i]; 
			}
			if ( (ft == pr) && (sum == sm) ){
				for ( int i = 0; i < n; i++) cout << a[i];
				cout << endl ;
				cnt++;
			} 
		} 
		else perestanovka(k+1);
	}
	return;
}

int main() { 
	ft = fact(n);
	sum = summa(n);
	perestanovka(0);
	cout << endl << cnt << "/" << fact(n) << endl;
}

#include <iostream>

#include <stdio.h>

using namespace std;

const int n = 6;

int cnt = 0;

int a[n];

int ft, sum;

unsigned int fact(unsigned int n) { return ( ! n || n == 1 ) ? 1 : n * fact(n - 1); }

unsigned int summa(unsigned int n) { return ( ! n || n == 1 ) ? 1 : n + summa(n - 1); }

void perestanovka(int k) {

int pr, sm;

for ( a[k] = 1; a[k] <= n; a[k]++) {

if ( k == n-1) {

pr = 1;

sm = 0;

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

pr = pr*a[i];

sm += a[i];

}

if ( (ft == pr) && (sum == sm) ){

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

cout << endl ;

cnt++;

}

else perestanovka(k+1);

}

return;

}

int main() {

ft = fact(n);

sum = summa(n);

perestanovka(0);

cout << endl << cnt << "/" << fact(n) << endl;

}

А на Java решение выглядит так:

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

class a1031 {

	static int n;
	static int cnt ; // Количество возможных перестановок
	static int a[]; // Массив чисел с которыми делаются перестановки 
	
	static void transposition(int k) { 
		boolean flag ; 
		boolean b[] = new boolean[n]; // Массив индикаторов повторов
		
		// Для элемента k перебираются все числа
		for ( a[k] = 1; a[k] <= n; a[k]++) { 
			if ( k == n-1) { //Если элемент последний
				flag = false;
				for ( int i = 0; i < n; i++) b[i] = false; // Массиву индикаторов повторов присваивается False
				for ( int i = 0; i < n; i++) { 
					if ( b[a[i]-1] == true ) { // Проверка на повторы
						flag= true ; // Если повтор то флаг = true
						break;
					}
					else b[a[i]-1] = true; 
				}
				if ( flag == false ) { // если повторов не было то печать
					for ( int i = 0; i < n; i++) System.out.print(a[i]);
					System.out.println();
					cnt++;
				} 
			} 
			else transposition(k+1); // если не последний элемент то перебирается для следующего k
		}
		return;
	}
	
	public static void main(String[] args) { 
		n = 6;
		cnt = 0;
		a = new int[n];
		transposition(0);
		System.out.println(cnt);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class a1031 {

static int n;

static int cnt ; // Количество возможных перестановок

static int a[]; // Массив чисел с которыми делаются перестановки

static void transposition(int k) {

boolean flag ;

boolean b[] = new boolean[n]; // Массив индикаторов повторов

// Для элемента k перебираются все числа

for ( a[k] = 1; a[k] <= n; a[k]++) {

if ( k == n-1) { //Если элемент последний

flag = false;

for ( int i = 0; i < n; i++) b[i] = false; // Массиву индикаторов повторов присваивается False

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

if ( b[a[i]-1] == true ) { // Проверка на повторы

flag= true ; // Если повтор то флаг = true

break;

}

else b[a[i]-1] = true;

}

if ( flag == false ) { // если повторов не было то печать

for ( int i = 0; i < n; i++) System.out.print(a[i]);

System.out.println();

cnt++;

}

else transposition(k+1); // если не последний элемент то перебирается для следующего k

}

return;

}

public static void main(String[] args) {

n = 6;

cnt = 0;

a = new int[n];

transposition(0);

System.out.println(cnt);

}

Related Images:

e-olimp 4475. Часы

03/04/2015 by Іванов Вячеслав Володимирович

4475. Часы

Постановка задачи

Ученые разработали часы, которые могут налаживаться для отсчета времени на любой планете. Они состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.

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

Во входном потоке содержится количество секунд в минуте [latex]S[/latex], минут в часе [latex]M[/latex], часов в сутках [latex]H[/latex] и число шариков [latex]K[/latex].

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

Интуитивно понятно, что положение шариков в очереди ежесуточно изменяется по одному и тому же закону, в силу однообразия процесса. Отыскать конкретный вид перестановки можно прямым моделированием часов, используя дек для описания лотка и стеки — каждой из чаш (у очереди задействованы оба конца, у чаш — только один).
Определить порядок суточной перестановки можно и возведением её в степень, но это нерациональный способ. Используя теорему о разложении перестановки в композицию циклов (к слову, непересекающихся), можно заметить, что порядок каждого из циклов равен его длине. Если мысленно представить перестановку в виде ориентированного графа, то процесс поиска циклов сведётся к поиску в глубину: обойти каждую компоненту связности, зафиксировать число входящих в неё вершин (на илл.)
[latex]\scriptsize \begin{pmatrix} 1 & 2 & 3 & 4 & 5 &6 & 7 & 8 & 9 & 10\\ 1 & 5 & 8 & 2 & 4 & 3 &7 & 9 & 6 & 10 \end{pmatrix}[/latex]
Зная длины всех циклов, нетрудно заметить, что задача сводится к поиску НОК полученной последовательности длин. Обосновать такой переход можно индуктивно: порядок перестановки, представимой в виде композиции двух циклов, равен НОК их длин, а случай большего количества циклов в разложении сводится к рассмотренному последовательным рассмотрением пар циклов (результат не зависит от порядка рассмотрения в силу ассоциативности композиции).

Реализация:

ideone: http://ideone.com/nz2JlG
Засчитанное решение: http://www.e-olimp.com/solutions/1937971

#include <iostream>
    #include <iomanip>  //cout.setprecision(), cout.fixed
    #include <deque>
    #include <stack>
    #include <cmath>    //floor()
    #include <map>
    using namespace std;

    //НОД
    long double gcd(long double a, long double b){
       while(b){
           a = a - b*floor(a/b);
           swap(a, b);
       }
       return a;
    }

    //НОК
    long double lcm(long double a, long double b){
       return a*(b/gcd(a,b));
    }

    int main()
    {
        int S, M, H, K;
        cin >> S >> M >> H >> K;

        //инициализация очереди
        deque<int> clock;
        for(int i = 1; i <= K; i++)
           clock.push_back(i);

        //моделирование суточного цикла
        stack<int> s, m, h;
        while(h.size() != H){
           s.push(clock.front());  //первый шарик очереди падает
           clock.pop_front();           //на секундную чашу
           if(s.size() == S){           //при переполнении чаши
               m.push(s.top());   //последний упавший шарик
               s.pop();            //переходит на минутную чашу
               while(!s.empty()){       //остальные шарики
                   clock.push_back(s.top());   //переходят в конец очереди
                   s.pop();                //в обратном порядке
               }
               if(m.size() == M){               //аналогично при переполнении
                   h.push(m.top());       //минутной чаши
                   m.pop();
                   while(!m.empty()){
                       clock.push_back(m.top());
                       m.pop();
                   }
               }
           }
        }

        while(!h.empty()){
           clock.push_back(h.top());
           h.pop();
        }

        //суточная перестановка
        //1  2  3  4  5  6  ... K
        //a1 a2 a3 a4 a5 a6 ... ak
        int* permutation = new int[K+1];
        for(int i = 1; i <= K; i++){
           permutation[i] = clock.front();
           clock.pop_front();
        }

        //разложение перестановки в композицию непересекающихся циклов
        bool *used = new bool[K+1]; //метки на посещенных элементах
        long double permutation_order = 1; //порядок перестановки
        for(int i = 1; i <= K; i++){
           if(!used[i]){ //если элемент не принадлежит ни одному из обследованных циклов
               long double cycle_length = 1;  //найти длину его цикла
               for(size_t x = i; permutation[x] != i; x = permutation[x]){
                   used[x] = true;
                   cycle_length++;
               }
               //и воспользоваться тем, что порядок перестановки -
               //произведение длин циклов из его разложения
               permutation_order = lcm(permutation_order, cycle_length);
           }
        }
        cout << setprecision(0) << fixed << permutation_order << endl;
        return 0;
    }

#include <iostream>

#include <iomanip> //cout.setprecision(), cout.fixed

#include <deque>

#include <stack>

#include <cmath> //floor()

#include <map>

using namespace std;

//НОД

long double gcd(long double a, long double b){

while(b){

a = a - b*floor(a/b);

swap(a, b);

}

return a;

}

//НОК

long double lcm(long double a, long double b){

return a*(b/gcd(a,b));

}

int main()

{

int S, M, H, K;

cin >> S >> M >> H >> K;

//инициализация очереди

deque<int> clock;

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

clock.push_back(i);

//моделирование суточного цикла

stack<int> s, m, h;

while(h.size() != H){

s.push(clock.front()); //первый шарик очереди падает

clock.pop_front(); //на секундную чашу

if(s.size() == S){ //при переполнении чаши

m.push(s.top()); //последний упавший шарик

s.pop(); //переходит на минутную чашу

while(!s.empty()){ //остальные шарики

clock.push_back(s.top()); //переходят в конец очереди

s.pop(); //в обратном порядке

}

if(m.size() == M){ //аналогично при переполнении

h.push(m.top()); //минутной чаши

m.pop();

while(!m.empty()){

clock.push_back(m.top());

m.pop();

}

while(!h.empty()){

clock.push_back(h.top());

h.pop();

}

//суточная перестановка

//1 2 3 4 5 6 ... K

//a1 a2 a3 a4 a5 a6 ... ak

int* permutation = new int[K+1];

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

permutation[i] = clock.front();

clock.pop_front();

}

//разложение перестановки в композицию непересекающихся циклов

bool *used = new bool[K+1]; //метки на посещенных элементах

long double permutation_order = 1; //порядок перестановки

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

if(!used[i]){ //если элемент не принадлежит ни одному из обследованных циклов

long double cycle_length = 1; //найти длину его цикла

for(size_t x = i; permutation[x] != i; x = permutation[x]){

used[x] = true;

cycle_length++;

}

//и воспользоваться тем, что порядок перестановки -

//произведение длин циклов из его разложения

permutation_order = lcm(permutation_order, cycle_length);

}

cout << setprecision(0) << fixed << permutation_order << endl;

return 0;

}

Примечания

Экспериментально выяснено, что только тип long double является достаточно вместительным для избежания переполнения.
Операция взятия остатка для чисел с плавающей точкой не определена аппаратно, так что алгоритм Евклида вычисления НОД реализован в соответствии с его математическим описанием.
Модификатор fixed используется для предотвращения вывода чисел в научном формате (с использованием степеней десятки).

Related Images:

Ю12.19

24/11/2014 by Марченко Філіп Олександрович

Задача: В имеющемся словаре найти группы слов, записанных одними и теми же буквами и отличающиеся только их порядком, то есть перестановкой, например, (КОРМА, КОМАР).

Код:

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>

using namespace std;
int count_words (string s) //функция подсчитывает слова в строке
{
    s+=' ';
    int a = 0;
    for (size_t i=0; i<s.length(); i++)
        if (s[i]==' ') a++;
    return a;
}
string * cut_words (string s) //функция разрезает строку на слова и возвращает массив
{
    s+=' ';
    int c = 0;
    int p = 0;
    int i=0;
    string *s_return = new string [count_words(s)];
    while (s.length() != 0)
        {
            if (s[i] != ' ')
            {
                c++;
                i++;
            }
            else
            {
                i=0;
                s_return[p] = s.substr(0, c);
                s.erase(0, c+1);
                c = 0;
                p++;
            }
        }
   return s_return;
}

int main ()
{
    string s;
    getline (cin, s);
	string *s_return;
	s_return = cut_words(s);
	for (int i=0; i<count_words(s); i++)
    {
    	string s_tmp = s_return[i];
        if (s_tmp.empty())					//если ячейка пуста, то продолжаем дальше
            {
                continue;
            }
        else				//а если нет, то ищем перестановки.
        {
        	int p = 0;
            for (int j=i+1; j<count_words(s); j++)
            {
                if ( is_permutation (s_tmp.begin(), s_tmp.end(), s_return[j].begin()))	//если перестановка
                    if (s_tmp.length() == s_return[j].length())		//и если одинаковая длина слов
                    {
                        cout<<s_return[j]<<endl;		//выводим на экран
                        s_return[j].clear(); //очищаем строку
                        p++;
                    }
            }
            if (p>=1) cout<<s_tmp<<endl;	
        }
    }
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <string>

using namespace std;

int count_words (string s) //функция подсчитывает слова в строке

{

s+=' ';

int a = 0;

for (size_t i=0; i<s.length(); i++)

if (s[i]==' ') a++;

return a;

}

string * cut_words (string s) //функция разрезает строку на слова и возвращает массив

{

s+=' ';

int c = 0;

int p = 0;

int i=0;

string *s_return = new string [count_words(s)];

while (s.length() != 0)

{

if (s[i] != ' ')

{

c++;

i++;

}

else

{

i=0;

s_return[p] = s.substr(0, c);

s.erase(0, c+1);

c = 0;

p++;

}

return s_return;

}

int main ()

{

string s;

getline (cin, s);

string *s_return;

s_return = cut_words(s);

for (int i=0; i<count_words(s); i++)

{

string s_tmp = s_return[i];

if (s_tmp.empty()) //если ячейка пуста, то продолжаем дальше

{

continue;

}

else //а если нет, то ищем перестановки.

{

int p = 0;

for (int j=i+1; j<count_words(s); j++)

{

if ( is_permutation (s_tmp.begin(), s_tmp.end(), s_return[j].begin())) //если перестановка

if (s_tmp.length() == s_return[j].length()) //и если одинаковая длина слов

{

cout<<s_return[j]<<endl; //выводим на экран

s_return[j].clear(); //очищаем строку

p++;

}

if (p>=1) cout<<s_tmp<<endl;

}

return 0;

}

Тесты:

Исходный словарь	Обработанный словарь
the and a to I is of have you he it in not was that his do on with she at say her for as are we but can him they up what out me go get this from be look my there know all one no see will back into like if were then an come think so down your them would about man take just by am now over make been or time when hand who want here tell off right their turn two through eye head other how some more around door room face day where way night well thing open away give only something ask move stand good find again little try too still hear walk before leave sit let long call feel close very why which car any hold work run never start even light than after put yes stop old watch first may talk another cut mean pull behind smile our toward towards much its house keep place begin nothing year woman side because three seem wait need moment himself stare arm use voice last late across sure front sound big really name should new anything against guy kill point small happen wall black step window life maybe fall own far under boy	no on three there own now how who thing night its sit name mean
Все слова

Алгоритм:

Для решения данной задачи я воспользовался возможностью, которую мне предоставляет библиотека <algorithm> . Поскольку мне надо было проверить, являются ли строки перестановками строки s_tmp, которую я ставлю в роли исходной с каждой итерацией, я воспользовался функцией is_permutation . Если некая строка является перестановкой, то она выводится на экран и стирается. С последующими итерациями будет проводится проверка на наличие на том или ином месте строки. Если строки обнаружено не будет, программа перейдёт к следующей итерации.

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

UPD: Поскольку я понял, что вводить вначале количество слов неудобно, я решил написать функцию, которая сама создаст массив из введённой мной строкой.