Задача

Анаграммой слова называется любая перестановка всех букв слова. Например, из слова SOLO можно получить 12 анаграмм: SOLO, LOSO, OSLO, OLSO, OSOL, OLOS, SLOO, LSOO, OOLS, OOSL, LOOS, SOOL.

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

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

Слово, количество букв в котором не превышает 14.

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

Количество различных анаграмм.

Тесты

№	Ввод	Вывод
1	SOLO	12
2	ANAGRAM	840
3	PERMUTATION	19958400
4	AAAAA	1
5	AABBBCCC	560

Код (string)

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

int main() {
    string s;
    map <char, int> m;
    cin >> s;
    int l = s.size(), count = 1;
    long long fact[15];
    fact[1] = 1;
    for (int i = 2; i <= l; i++) //заполняем массив факториалов
        fact[i] = fact[i - 1] * i;
    for (int i = 0; i < l; i++) //подсчитываем повторения
        ++m[s[i]];
    for (auto it = m.begin(); it != m.end(); it++) 
        if (it -> second > 1) count *= fact[it -> second];
    cout << fact[l] / count; 
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

string s;

map <char, int> m;

cin >> s;

int l = s.size(), count = 1;

long long fact[15];

fact[1] = 1;

for (int i = 2; i <= l; i++) //заполняем массив факториалов

fact[i] = fact[i - 1] * i;

for (int i = 0; i < l; i++) //подсчитываем повторения

++m[s[i]];

for (auto it = m.begin(); it != m.end(); it++)

if (it -> second > 1) count *= fact[it -> second];

cout << fact[l] / count;

return 0;

}

Код (c-string)

#include <iostream>
#include <cstring>
#include <map>
using namespace std;
 
int main() {
    char s[15]; //равносильно char * s = new char [15], где 15 - максимальный размер строки
    map <char, int> m;
    cin >> s;
    int l, count = 1;
    l = strlen(s);
    long long fact[15];
    fact[1] = 1;
    for (int i = 2; i <= l; i++) //заполняем массив факториалов
        fact[i] = fact[i - 1] * i;
    for (int i = 0; i < l; i++) //подсчитываем повторения
        ++m[s[i]];
    for (auto it = m.begin(); it != m.end(); it++) 
        if (it -> second > 1) count *= fact[it -> second];
    cout << fact[l] / count; 
    return 0;
}

#include <iostream>

#include <cstring>

#include <map>

using namespace std;

int main() {

char s[15]; //равносильно char * s = new char [15], где 15 - максимальный размер строки

map <char, int> m;

cin >> s;

int l, count = 1;

l = strlen(s);

long long fact[15];

fact[1] = 1;

for (int i = 2; i <= l; i++) //заполняем массив факториалов

fact[i] = fact[i - 1] * i;

for (int i = 0; i < l; i++) //подсчитываем повторения

++m[s[i]];

for (auto it = m.begin(); it != m.end(); it++)

if (it -> second > 1) count *= fact[it -> second];

cout << fact[l] / count;

return 0;

}

Решение

Данная задача решается с помощью единой формулы \begin{equation} N_s =\frac {length!}{p_1! × p_2! × \ldots\ × p_n!}\end{equation} где $ length$ — длина строки, а $p_i$ — количество повторений одной буквы $(i = 1, 2, \ldots\ , n$, $ n$ — количество различных букв). Буквы, повторяющиеся один раз, можем опустить, так как их факториал даст единицу, что никак не повлияет на результат.
Длину строки найдем с помощью метода size()(или strlen()), а количество повторений для удобства будем подсчитывать в контейнере map.

Ссылки

Задача 390 на e-olymp

Код на Ideone (string)

Код на Ideone (c-string)

Related Images:

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

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

Данную задачу можно найти здесь.

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

Последовательность действительных чисел [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{2n}[/latex].

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

Последовательность действительных чисел [latex]a_{1}[/latex], [latex]a_{2n}[/latex], [latex]a_{2}[/latex], [latex]a_{2n-1}[/latex], [latex]a_{3}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex], [latex]a_{n+1}[/latex] .

Тесты

№	Входные данные	Выходные данные
1	1 2 3 4 5 6	1 6 2 5 3 4
2	0 0 0 0 0 1	0 1 0 0 0 0
3	3 12 42 -6 15 0 0 0 501 20 20 20	3 20 12 20 42 20 -6 501 15 0 0 0
4	42 0 17 -2.6 -54 41888 0.25 13 1.3333 -284.73	42 -284.73 0 1.3333 17 13 -2.6 0.25 -54 41888
5	0 1 -1 0 1 -1 97 113 -7.777 0 48 -69	0 -69 1 48 -1 0 0 -7.777 1 113 -1 97

Код

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector <double> sequence, result_sequence;
    double term_of_sequence;
    while (cin >> term_of_sequence){
        sequence.push_back(term_of_sequence);
    }
    for (int i = 0; i < sequence.size() / 2; i++){
        result_sequence.push_back(sequence[i]);
        result_sequence.push_back(sequence[sequence.size() - 1 - i]);
    }
    for (int i = 0; i < result_sequence.size(); i++){
        cout << result_sequence[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> sequence, result_sequence;

double term_of_sequence;

while (cin >> term_of_sequence){

sequence.push_back(term_of_sequence);

}

for (int i = 0; i < sequence.size() / 2; i++){

result_sequence.push_back(sequence[i]);

result_sequence.push_back(sequence[sequence.size() - 1 - i]);

}

for (int i = 0; i < result_sequence.size(); i++){

cout << result_sequence[i] << " ";

}

return 0;

}

Код на ideone можно найти здесь.

Ход решения

Считываем все числа из входного потока и записываем их в вектор исходной последовательности sequence. Результатом работы нашей программы должна быть новая последовательность действительных чисел result_sequence, которая задаётся по следующему правилу: первый член новой последовательности совпадает с первым членом исходной, второй член новой последовательности является последним членом исходной, третий – второй член исходной и так далее до исчерпания чисел. Иными словами, новая последовательность из [latex]2n[/latex] чисел на нечётных номерах имеет члены исходной последовательности (от первого и до [latex]n[/latex]-го включительно), чётным же номерам новой последовательности соответствуют члены исходной с номерами от [latex]n+1[/latex] до [latex]2n[/latex] включительно, записанные в обратном порядке.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: перестановка

e-olymp 390. Анаграммы

Задача

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

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

Тесты

Код (string)

Код (c-string)

Решение

Ссылки

Related Images:

А282б

Related Images: