Given 3 characters a, b, c, find the number of strings of length n that can be formed from these 3 characters given that; we can use ‘a’ as many times as we want, ‘b’ maximum once, and ‘c’ maximum twice
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 08.11.2026 17:45:28 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Can you describe what is your approach to solve this problem?
I tried to solve it recursivly by generating all possible strings and then discarding those strings which doesn't follow above rule?
Can you tell me more efficient approach?
How about using permutaions?
Number of strings containing only a's.
Number of strings containing 1 b and rest a's.
Number of strings containing 1c and rest a's.
. . .
and add the sum of all the above points to get the final answer.
then how to print them in minimum complexity?
The best you can do is
where M is the number of possibilities. To do it efficiently, make some string of length n, and recursively fix the 
character. You'd do this from left to right, and your recursive function should pass down information on whether or not you've fixed the letter
b, and how manyc's you've fixed so far.thanks a lot sir.Can you write pseudo code?
Not too hard:
I assume you're solving this, since N<=20 you can use:
(cnk = number of combinations)
There aren't many possible cases if we care only about 'b' and 'c'. Let's focus only on placing 'b' and 'c', the remaining will be 'a':
1) no 'b' and 'c': 1 option.
2) only 1 'b': n options.
3) only 1 'c': n options.
4) 2 'c': n(n — 1) / 2 options.
5) 1 'b' and 1 'c': n(n — 1) options.
6) 1 'b' and 2 'c': n(n — 1)(n — 2) / 6 * 3 = n(n — 1)(n — 2) / 2 options.
so to sum it up, given n you need to output: 1 + 2n + 3n(n — 1) / 2 + n(n — 1)(n — 2) / 2.
this is O(1) which means it's slightly faster than an exponential complexity by using recursion.
Yes, constant time is indeed slightly faster than exponential time.