Question

На с++(с комментариями) Максимальное время работы на одном тесте: 1 секунда На день рождения Пете подарили набор карточек с буквами. Теперь Петя с большим интересом составляет из них разные слова. И вот, однажды, составив очередное слово, Петя заинтересоваля вопросом: "А сколько различных слов можно составить из тех же карточек, что и данное?". Помогите ему ответить на этот вопрос. Входные данные Вводится слово, составленное Петей – строка из маленьких латинских букв не длиннее 15 символов. Выходные данные Выведите одно целое число – искомое количество слов. Примеры входные данные solo выходные данные 12

Answer 1

String line; getline(cin,line); //Можно и просто через cin..даже наверное лучше в данном случае именно через cin;
int count = 0;
sort(line.begin(),line.end());
do{
count++;
}while(next_permutation(line.begin(), line.end()));
cout<<count;
system("pause");

Где next_permutation - перебор всевозможных вариантов или делать, пока возможна перестановка.
sort() - функция сортировки. Так же есть более медленный qsort.

Answer 2

Для решения этой задачи можно воспользоваться подсчетом количества пермутаций для каждой буквы в слове и затем использовать формулу для подсчета общего числа пермутаций. Вот пример решения на C++ с комментариями:

cppCopy code
#include <iostream>
#include <string>
#include <algorithm>
#include <map>

using namespace std;

int factorial(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

int main() {
    string word;
    cin >> word;

    // Используем map для подсчета количества каждой буквы в слове
    map<char, int> letterCount;
    for (char letter : word) {
        letterCount[letter]++;
    }

    // Вычисляем общее количество пермутаций
    int totalPermutations = factorial(word.size());

    // Делим общее количество пермутаций на факториалы каждой буквы в слове
    for (const auto& pair : letterCount) {
        totalPermutations /= factorial(pair.second);
    }

    cout << totalPermutations << endl;
    
    return 0;
}

В этом коде сначала подсчитывается количество каждой буквы в слове с использованием std::map. Затем вычисляется общее количество пермутаций для введенного слова и делится на факториалы количества повторяющихся букв. Результат выводится на экран.

Пример работы программы:

makefileCopy code
Ввод: solo
Вывод: 12