Матч 210, IP преобразователь (IPConverter)

Дивизион 1, Уровень 1

IP адрес представляет собой строку из четырех чисел, разделенных точками. Имеется строка, состоящая из последовательности цифр. Необходимо расставить между цифрами три точки так, чтобы строка содержала реальный IP адрес. Числа в IP адресе могут принимать значения от 0 до 255. Ведущих нулей в числах быть не может. Например, адрес “0.90.24.26” является допустимым, а “19.02.4.26” нет.

Во входной строке цифр ambiguousIP необходимо найти все такие расстановки трех точек между цифрами, для которых получаются реальные IP адреса.

Класс: IPConverter

Метод: vector<string> possibleAddresses(string ambiguousIP)

Ограничения: строка ambiguousIP содержит от 0 до 50 символов, ‘0’ £ ambiguousIP[i] £ ‘9’.

Вход. Строка ambiguousIP.

Выход. Массив, содержащий все возможные строки с реальными IP адресами, которые можно получить из ambiguousIP вставкой трех точек. Строки в массиве должны быть отсортированы лексикографически по возрастанию.

Пример входа

ambiguousIP

“1902426”

“0186290”

“3082390871771742784899852251737850570843857369760”

Пример выхода

{"1.90.24.26",

"1.90.242.6",

"19.0.24.26",

"19.0.242.6",

"190.2.4.26",

"190.2.42.6",

"190.24.2.6"}

{"0.18.62.90", "0.186.2.90", "0.186.29.0"}

{}

РЕШЕНИЕ

перебор

Лексикографически наибольшим IP адресом является адрес 255.255.255.255, наименьшим 0.0.0.0. Если входная строка содержит более 12 или менее 4 цифр, то из нее вставкой символов ‘.’ невозможно получить допустимый IP адрес. Иначе совершаем перебор позиций, в которые можно вставить символы ‘.’ при помощи тройного вложенного цикла. Для каждой расстановки точек проверям, являются ли четыре числа адреса допустимыми (они не должны начинаться с нуля если число состоит из более чем одной цифры, а также числа должны лежать в промежутке от 0 до 255). Если адрес является допустимым, заносим его в результирующий массив.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

using namespace std;

int isCorrect(string s)

{

if ((s[0] == '0') && (s.size() > 1)) return 0;

int n = atoi(s.c_str());

return (n <= 255);

}

class IPConverter

{

public:

vector<string> possibleAddresses(string ambiguousIP)

{

vector<string> res;

string a, b, c, d;

int i, j, k;

if ((ambiguousIP.size() > 12) || (ambiguousIP.size() < 4)) return res;

for(i = 0; i < 3; i++)

for(j = i + 1; j < i + 4; j++)

for(k = j + 1; k < j + 4; k++)

{

if (k >= ambiguousIP.size() - 1) break;

a = ambiguousIP.substr(0,i+1);

b = ambiguousIP.substr(i+1,j-i);

c = ambiguousIP.substr(j+1,k-j);

d = ambiguousIP.substr(k+1);

if (isCorrect(a) && isCorrect(b) && isCorrect(c) && isCorrect(d))

res.push_back(a + '.' + b + '.' + c + '.' + d);

}

return res;

}

};