Задания
Версия для печати и копирования в MS Word
Тип 1 № 75238
i

На ри­сун­ке схема дорог изоб­ра­же­на в виде графа, в таб­ли­це со­дер­жат­ся све­де­ния о длине этих дорог в ки­ло­мет­рах.

 

П1П2П3П4П5П6П7П8П9
П138303426
П238312224
П3303132
П44028
П5222536
П624402537
П73236
П83435
П926283735

 

Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Из­вест­но, что до­ро­га КИ ко­ро­че до­ро­ги АГ. Опре­де­ли­те длину до­ро­ги ДЖ.

Спрятать решение

Ре­ше­ние.

На схеме толь­ко один на­се­лен­ный пункт сте­пе­ни 2 име­ю­щий общие до­ро­ги с пунк­та­ми сте­пе­ни 3. Это пункт И, ему со­от­вет­ству­ет пункт П7. Пункт Д един­ствен­ный пункт сте­пе­ни 4 у ко­то­ро­го есть общие до­ро­ги с двумя пунк­та­ми сте­пе­ни 3. Тогда пункт Д это на­се­лен­ный пункт П2. Пункт Ж может быть или пунк­том П3 или пунк­том П5.

Пред­по­ло­жим, что Ж это пункт П3. Тогда Г это пункт П1, К это пункт П5, а на­се­лен­ный пункт А это пункт П8. Тогда До­ро­га КИ дли­ною 36, а до­ро­га АГ дли­ною 34, что про­ти­во­ре­чит усло­вию, , что до­ро­га КИ ко­ро­че до­ро­ги АГ.

Пред­по­ло­жим, что Ж это пункт П5. Тогда Г это пункт П6, К это пункт П3, а на­се­лен­ный пункт А это пункт П4. Тогда До­ро­га КИ дли­ною 36, а до­ро­га АГ дли­ною 40, что под­хо­дит по усло­вию. Тогда длина до­ро­ги ДЖ(П2-П5) равна 22.

 

Ответ: 22.

 

При­ведём ре­ше­ние Юрия Кра­силь­ни­ко­ва на языке Python.

def ал­фа­вит(s): return ''.join(sorted(set(s.replace(' ',''))))

# ал­фа­вит - стро­ка из сим­во­лов стро­ки s в ал­фа­вит­ном по­ряд­ке (кроме про­бе­ла)

def дуги(s): return set(map(ал­фа­вит,s.split()))

# дуги - мно­же­ство дуг графа (пар сим­во­лов), каж­дая пара упо­ря­до­че­на по ал­фа­ви­ту

таб­ли­ца = '13 14 16 23 24 27 28 34 38 46 56 57 58 67 78' # дуги по таб­ли­це

граф = 'АБ АВ АГ АЖ БВ БД БИ ВД ГЕ ГЖ ДЕ ДИ ЕЖ ЕИ ЖИ' # дуги по схеме

# Не надо бо­ять­ся вклю­чить одну дугу два­жды (напр., БД и ДБ). Глав­ное - ни­че­го не про­пу­стить.

print(ал­фа­вит(таб­ли­ца)) # за­го­ло­вок

from itertools import permutations

for p in permutations(ал­фа­вит(граф)): # все воз­мож­ные пе­ре­ста­нов­ки бук­вен­ных обо­зна­че­ний

та­б­транс = str.maketrans(''.join(p),ал­фа­вит(таб­ли­ца)) # таб­ли­ца транс­ля­ции

if дуги(таб­ли­ца) == дуги(граф.translate(та­б­транс)): # если мно­же­ства дуг сов­па­да­ют

print(''.join(p),

'АБ -','АБ'.translate(та­б­транс),

'ЖИ -','ЖИ'.translate(та­б­транс),

'ВД -','ВД'.translate(та­б­транс))

 

В пер­вом ва­ри­ан­те до­ро­га КИ - это до­ро­га 57 дли­ной 36, а до­ро­га АГ - это до­ро­га 81 дли­ной 34, это про­ти­во­ре­чит усло­вию.

Во вто­ром ва­ри­ан­те до­ро­га КИ - это до­ро­га 37 дли­ной 32, а до­ро­га АГ - это до­ро­га 46 дли­ной 40, это со­от­вет­ству­ет усло­вию. Тогда до­ро­га ДЖ - это до­ро­га 25 дли­ной 22.


Аналоги к заданию № 75238: 75265 Все