Восстановление IP-адреса
Вася записал IP-адрес на лист бумаги, и случайно постирал штаны в которых оставил данный лист. После стирки Вася нашел 4 фрагмента данного листа.
Помогите Васе по фрагментам восстановить полный IP адрес, который был записан на листе.
Решение полным перебором
Попробуем решить задачу перебором. Возьмем первый фрагмент, и допустим, что именно он должен стоять на первом месте и попробуем поставить на второе место остальные фрагменты.
1) Допишем к "3.212" фрагмент "21", получается "3.21221" - это не подходит, т.к. 21221>255.
2) Допишем к "3.212" фрагмент "2.12", получается "3.2122.12" - это не подходит, т.к. 2122>255.
3) Допишем к "3.212" фрагмент ".42" получается "3.212.42" - это подходит, т.к. все числа меньше чем 256.
3.1) Допишем к "3.212.42" фрагмент "21" получается "3.212.4221" - это не подходит, т.к. 4221>255.
3.2) Допишем к "3.212.42" фрагмент "2.12" получается "3.212.422.12" - это не подходит, т.к. 422>255.
Т.к. все возможные варианты завели нас в тупик, попробуем в качестве первого фрагмент использовать не "3.212", а "21".
1) Допишем к "21" фрагмент "3.212" получается "213.212" - это подходит, т.к. все числа меньше чем 256.
1.1) Допишем к "213.212" фрагмент "2.21" получается "213.2122.21" - это не подходит, т.к. 2122>255.
1.2) Допишем к "213.212" фрагмент ".42" получается "213.212.42" - это подходит, т.к. все числа меньше чем 256.
1.2.1) Допишем к "213.212.42" фрагмент "2.21" получается "213.212.422.21" - это не подходит 422>256.
2) Допишем к "21" фрагмент "2.12" получается "212.12" - это подходит, т.к. все числа меньше чем 256.
2.1) Допишем к "212.12" фрагмент "3.212" получается "212.123.212" - это подходит, т.к. все числа меньше чем 256.
2.1.1) Допишем к "212.123.212" фрагмент ".42" получается "212.123.212.42" - это подходит, т.к. все числа меньше чем 256.
Получается изначально на листе был записан IP-адрес 212.123.212.42.
Более аналитическое решение
Также эту задачу можно решить более осознанно, не полным перебором.
1) Заметим, что ".42" может стоять только в конце, т.к. любой фрагмент, который мы поставим после, даст число не меньшее чем 420 (в теории можно было бы поставить фрагмент, который начинается с точки, но таких фрагментов кроме самого ".42" у нас нет).
2) Заметим, что "3.212" может столько только перед фрагментом, начинающимся с точки, т.к. фрагмент начинающийся с числа даст результат не меньше чем 2120, следовательно, "3.212.42" конец нашего IP-адреса.
3) Посмотрим на фрагменты "21" и "2.12" их можно расположить только как "212.12", т.к. если мы их расположим как "2.1221" получим число 1221>255.
В результате получается, что у нас 2 фрагмента "212.12" и "3.212.42" склеиваем их и получаем "212.123.212.42".
Ответ: 212.123.212.42