Задача про сторожа и фонарик
vk f t

Задача про сторожа и фонарик

Ваша люби­мая зада­ча на пере­бор и логи­ку.

Про­грам­ми­сты обо­жа­ют подоб­ные зада­чи, пото­му что реше­ние таких штук (вро­де бы ото­рван­ных от реаль­но­сти) мощ­но про­ка­чи­ва­ет алго­рит­ми­че­ское мыш­ле­ние и пони­ма­ние абстракт­но­го мира машин. Попро­буй­те сна­ча­ла решить зада­чу само­сто­я­тель­но, а если упрё­тесь — смот­ри­те ответ.

Сто­рож про­ве­рял инвен­тарь и заме­тил, что у него не рабо­та­ет фона­рик. Он поша­рил в тум­боч­ке и выта­щил 8 бата­ре­ек. Насколь­ко он пом­нил, поло­ви­на из них — све­жие, пото­му что он совсем недав­но поку­пал в мага­зине бата­рей­ки по акции. А вот ещё четы­ре точ­но раз­ря­же­ны: сто­рож пла­ни­ро­вал их ути­ли­зи­ро­вать, но ока­за­лось, что сде­лать это в Рос­сии не так про­сто. В общем, теперь сто­ро­жу нуж­но вста­вить бата­рей­ки в фона­рик, что­бы про­ве­рить, какие из них заря­же­ны.

Что­бы фона­рик зара­бо­тал, в него долж­ны быть встав­ле­ны две заря­жен­ные бата­рей­ки. Сколь­ко мак­си­маль­но пар бата­ре­ек нуж­но пере­брать сто­ро­жу, что­бы фона­рик точ­но зара­бо­тал?

Реше­ние

Назо­вём каж­дую бата­рей­ку отдель­ной бук­вой — А Б В Г Д Е Ж З. Это поз­во­лит нам не пере­пу­тать бата­рей­ки, когда мы будем менять их места­ми друг с дру­гом.

Теперь разо­бьём бата­рей­ки на пары и про­ве­рим в фона­ри­ке каж­дую из них:

(А Б) (В Г) (Д Е) (Ж З) — это четы­ре пер­вые пары.

Если фона­рик зара­бо­тал на какой-то из них — отлич­но, мы нашли нуж­ную пару.

Если лам­поч­ка так и не заго­ре­лась, зна­чит, в каж­дой паре у нас ока­за­лась одна хоро­шая бата­рей­ка, и одна пло­хая. Давай­те поду­ма­ем, поче­му:

Если бы в одной паре было две нера­бо­чие бата­рей­ки, то на осталь­ные три пары при­хо­ди­лось бы две нера­бо­чие и четы­ре рабо­чие бата­рей­ки. Неиз­беж­но одна из пар подо­бра­лась бы с дву­мя рабо­чи­ми бата­рей­ка­ми.

Сле­до­ва­тель­но, раз ни одна из пар не вклю­чи­ла фонарь, в любой из них есть одна рабо­чая и одна нера­бо­чая бата­рей­ка.

Теперь возь­мём любые две пары — напри­мер, (А Б) и (В Г) — и поме­ня­ем в них пер­вые бата­рей­ки места­ми. Полу­чим:

(В Б) и (А Г) — в этот момент мы про­ве­ри­ли уже шесть пар.

Если фона­рик не зара­бо­тал и после этой пере­ста­нов­ки, зна­чит, мы поме­ня­ли места­ми оди­на­ко­вые бата­рей­ки: хоро­шую заме­ни­ли на хоро­шую, или плохую — на плохую. Выхо­дит, нуж­но взять вто­рую бата­рей­ку из пер­вой пары и поме­нять её с пер­вой бата­рей­кой из вто­рой пары:

берём пару (В Б), доста­ём отту­да вто­рую бата­рей­ку Б и ста­вим её на пер­вое место в паре (А Г), полу­ча­ем: (Б Г) — это седь­мая пара.

Если фона­рик заго­рел­ся, зна­чит, вто­рой мы поста­ви­ли хоро­шую бата­рей­ку. Если фона­рик всё ещё не све­тит, полу­ча­ет­ся, в этой паре у нас две пло­хих бата­рей­ки, а две хоро­ших оста­лись в дру­гой — (В А). Ста­вим их в фона­рик, и гото­во!

Полу­ча­ет­ся, что нам пона­до­бит­ся про­ве­рить мак­си­мум 7 пар.

Ещё по теме