Задача
Из слова «молоко» можно составить слово «коло». Сколько слов из заданного словаря можно составить, используя буквы заданного слова, причем каждую букву можно использовать не более одного раза.
Тесты
| Входные данные | Выходные данные |
| молоко 4 мило коло коліно око |
2 |
| приветствие 8 ветер треск спирт трепет перерыв север текст привести |
5 |
Код программы на С++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <vector> #include <string> using namespace std; int main() { string word; vector <int> D(256), U; int n; for (int i = 0; i < D.size(); i++) D[i] = 0; cin >> word; // ввод заданного слова; for (int i = 0; i < word.size(); i++) { D[word[i]+127]++; } cin >> n; // ввод количества слов в словаре; int rez = 0; for (int i = 0; i < n; i++) { cin >> word; // ввод слов со словаря; U = D; bool words = true; for (int j = 0; j < word.size(); j++) { U[word[j]+127]--; if (U[word[j]+127] < 0) { words = false; break; } } rez += words; } cout << rez << endl; // вывод количества слов, которые можно составить из заданного слова; return 0; } |
Код программы на Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); String word; String words[] = new String[256]; char table[] = new char[256]; int count[] = new int[256]; int tempcount[] = new int[256]; int templength,length,sum = 0,kilk,countwords = 0; int mem = 0, index = 0; word = in.nextLine(); kilk = in.nextInt(); for (int i = 0; i < kilk+1; i++) { words[i] = in.nextLine(); } length = word.length(); table[0] = word.charAt(0); for (int i = 1; i < length; i++) { for (int j = 0; j < i; j++) { if (word.charAt(i) == table[j]) mem = 1; } if (mem == 0) { index++; table[index] = word.charAt(i); } mem = 0; } mem = 0; for (int i = 0; i <= index; i++) { for (int j = 0; j < length; j++) { if (table[i] == word.charAt(j)) { mem++; } } count[i] = mem; mem = 0; } int mem2 = 0; for (int a = 0; a < kilk; a++) { templength = words[a].length(); mem = 0; for (int i = 0; i <= index; i++) { for (int j = 0; j < templength; j++) { if (table[i] == words[a].charAt(j)) mem++; } tempcount[i] = mem; mem = 0; } for (int i = 0; i <= index; i++) sum = sum + tempcount[i]; mem2 = 0; if (sum == templength) { for (int i = 0; i <= index; i++) { if (tempcount[i]>count[i])mem2++; } if (mem2 == 0) countwords++; } sum = 0; } System.out.println(countwords); } } |
Решение
Создаем вектор [latex]D[/latex], в котором будем хранить количество каждого символа в слове, и обнуляем его. Тип [latex]char[/latex] вмещает максимум [latex]256[/latex] значений (в диапазоне от [latex]-127[/latex] до [latex]126[/latex]). Класс [latex]string[/latex] состоит из символов типа [latex]char[/latex], поэтому для того, чтобы «вернуть» значения этих символов к положительным (в чём возникает необходимость при обращении к элементам вектора), к ним прибавляется [latex]127[/latex].
Потом считаем число каждого символа в слове. Создаем переменную, в которой будем хранить число слов из словаря, которое можно составить, используя символ первого входного слова. Предполагаем, что слово [latex]words[/latex] составить можно ([latex]words=true[/latex]). Считаем использованные символы из первой входной строки и, если вдруг число стало отрицательным, то слово составить нельзя, обнуляем переменную [latex]words[/latex] и останавливаем цикл. К переменной [latex]rez[/latex] прибавляем переменную [latex]words[/latex] и выводим [latex]rez[/latex].
Ссылки
Код на ideone.com (C++)
Код на ideone.com (Java)
Задача с сайта e-olymp.com.
Засчитанное решение.
Прошу рассмотреть задачу [latex]string [/latex].
Если есть возможность, [latex]c-string [/latex] я сделаю позже.
— Пояснительный текст нуждается в улучшении. Как понимать «Потом считываем число каждого символа в слове»? Вы не считываете чисел, кроме размера словаря.
— Что это за магическое число 256 по всей программе? Нужно объяснить.
— bool words = 1; Так лучше не делать. Если уж переменная логическая, то используйте true или false.
Исправила.
Я просил «Что это за магическое число 256 по всей программе? Нужно объяснить.»
Вы написали «Тип char вмещает в себе максимальное значение 256.»
Кроме того, что это неправда, это еще и не объясняет почему Вы завели массив на 512 элементов и почему добавляете 256 к коду букв.
Мне понятно, что Вы боритесь с символами кириллицы, но Вы этого не поясняете.
Проверьте, пожалуйста.
Проверил. Принято. Молодец. Вы всё хорошо объяснили.
Пожалуйста во второй версии просто используйте unsigned char, чтобы избежать этой проблемы.