РЕШУ ЕГЭ — информатика

Варианты заданий

Светлана составляет коды из букв своего имени. Код должен состоять из 8 букв, и каждая буква в нём должна встречаться столько же раз, сколько в имени Светлана. Кроме того, одинаковые буквы в коде не должны стоять рядом. Сколько кодов может составить Светлана?

Решение. Заметим, что алфавит состоит из 7 букв: С, В, Е, Т, Л, А, Н. Каждая буква должна встречаться в коде один раз, за исключением буквы А  — она может встречаться в коде два раза, но не должна стоять в коде рядом с другой буквой А.

Пусть одна буква А стоит на первом месте, а вторая буква А стоит на третьем месте, тогда всего таких кодов будет 1 · 6 · 1 · 5 · 4 · 3 · 2 · 1  =  720. Поскольку вторую букву А в этом случае можно разместить ещё на 5 других позициях, всего слов, в которых одна из букв А стоит на первом месте, будет 6 · 720  =  4320.

Пусть одна буква А стоит на втором месте, а вторая буква А стоит на четвёртом месте, тогда всего таких кодов будет 6 · 1 · 5 · 1 · 4 · 3 · 2 · 1  =  720. Поскольку вторую букву А в этом случае можно разместить ещё на 4 других позициях, всего слов, в которых одна из букв А стоит на втором месте, будет 5 · 720  =  3600.

Заметим, что передвигая первую букву А на следующую позицию, количество мест, на которых может стоять вторая буква А, уменьшается на 1. Тогда для случаев, когда буква А будет стоять на третьей, четвёртой, пятой и шестой позициях, количество кодов равно 720 · 4  =  2880, 720 · 3  =  2160, 720 · 2  =  1440 и 720 · 1  =  720 соответственно.

Таким образом, Светлана может составить 4320 + 3600 + 2880 + 2160 + 1440 + 720  =  15120 кодов.

Ответ: 15120.

Приведём другое решение на языке Python.

import itertools

alphabet = "СВЕТЛАНА"

ar = itertools.permutations(alphabet, 8) #Размещение

arl = []

for e in ar:

arl.append(list(e))

a = set()

for e in arl:

flag = True

s = ""

for i in range(len(e)-1):

s += e[i]

if e[i] == e[i + 1]:

flag = False

if flag:

a.add(s)

print(len(a))

Приведём другое решение на языке Python.

q = 0

sett = set()

for i1 in 'СВЕТЛАНА':

for i2 in 'СВЕТЛАНА':

for i3 in 'СВЕТЛАНА':

for i4 in 'СВЕТЛАНА':

for i5 in 'СВЕТЛАНА':

for i6 in 'СВЕТЛАНА':

for i7 in 'СВЕТЛАНА':

for i8 in 'СВЕТЛАНА':

a = i1+i2+i3+i4+i5+i6+i7+i8

if a.count('А') == 2 and a.count('С') == 1 and a.count('В') == 1 and a.count('Е') ==1 and a.count('Т')==1 and a.count('Л') == 1 and a.count('Н') == 1:

if i1 != i2 and i2 != i3 and i3 != i4 and i4 != i5 and i5 != i6 and i6 != i7 and i7 != i8 and (not(a in sett)):

sett.add(a)

q += 1

print(q)

Приведём решение Степана Козлова на языке Python.

from itertools import *

k = 0

d = set()

for i in product('СВЕТЛАНА', repeat = 8):

s = ''.join(i)

if len(set(s)) == 7 and 'АА' not in s and s.count('А') == 2:

d.add(s)

print(len(d))

Приведём решение Сергея Донец на языке PascalABC.NET.

begin
'СВЕТЛАНА'.Permutations(8).Distinct
.Count(s->s.Pairwise.All(\(pr,cr)->pr<>cr))
.Print;//15120
end.

Георгий составляет коды из букв своего имени. Код должен состоять из 7 букв, и каждая буква в нём должна встречаться столько же раз, сколько в имени Георгий. Кроме того, одинаковые буквы в коде не должны стоять рядом. Сколько кодов может составить Георгий?

Решение. Заметим, что алфавит состоит из 6 букв: Г, Е, О, Р, И, Й. Каждая буква должна встречаться в коде один раз, за исключением буквы Г  — она может встречаться в коде два раза, но не должна стоять в коде рядом с другой буквой Г.

Пусть одна буква Г стоит на первом месте, а вторая буква Г стоит на третьем месте, тогда всего таких кодов будет 1 · 5 · 1 · 4 · 3 · 2 · 1  =  120. Поскольку вторую букву Г в этом случае можно разместить ещё на 4 других позициях, всего слов, в которых одна из букв Г стоит на первом месте, будет 5 · 120  =  600.

Пусть одна буква Г стоит на втором месте, а вторая буква Г стоит на четвёртом месте, тогда всего таких кодов будет 5 · 1 · 4 · 1 · 3 · 2 · 1  =  120. Поскольку вторую букву Г в этом случае можно разместить ещё на 3 других позициях, всего слов, в которых одна из букв Г стоит на втором месте, будет 4 · 120  =  480.

Заметим, что передвигая первую букву Г на следующую позицию, количество мест, на которых может стоять вторая буква Г, уменьшается на 1. Тогда для случаев, когда буква Г будет стоять на третьей, четвёртой и пятой позициях, количество кодов равно 120 · 3  =  360, 120 · 2  =  240 и 120 · 1  =  120 соответственно.

Таким образом, Георгий может составить 600 + 480 + 360 + 240 + 120  =  1800 кодов.

Ответ: 1800.

Приведём другое решение на языке Python.

import itertools

alphabet = "ГЕОРГИЙ"

ar = itertools.permutations(alphabet, 7) #Размещение

arl = []

for e in ar:

arl.append(list(e))

a = set()

for e in arl:

flag = True

s = ""

for i in range(len(e)-1):

s += e[i]

if e[i] == e[i + 1]:

flag = False

if flag:

a.add(s)

print(len(a))

Приведём решение Ильи Андрианова на языке Python.

from itertools import permutations

count = set()

for s in permutations('георгий'):

slovo = ''.join(s)

if 'гг' not in slovo:

count.add(slovo)

print(len(count))

Приведём решение Сергея Донец на PascalABC.NET:

begin

'ГЕОРГИЙ'.Permutations(7).Distinct

.Where(s->s.Pairwise.All(\(pr,cr) -> pr<>cr))

.Count.Print;//1800

end.

№ п/п	№ задания	Ответ
1	40724	15120
2	40983	1800

Ключ