Матч 22, Парковка машин (CarParking)

В городе улицы пронумерованы от 1 до streets. Вы находитесь на улице с номером now. Вы хотите припарковаться на ближайшей улице, номер которой является палиндромом. Если таких улиц несколько, то вернуть номер наименьшей.

Класс: CarParking

Метод: int closestShed(int now, int streets)

Ограничения: 1 £ streets £ 2147483647, 1 £ now £ streets.

Вход. Номер улицы now, на которой Вы находитесь и количество улиц в городе streets.

Выход. Номер ближайшей улицы, являющийся палиндромом.

Пример входа

now	streets
19	22
19	21
1234567	12345678

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

22

11

1234321

РЕШЕНИЕ

элементарные вычисления

Функция IsPal(i) проверяет, является ли число i палиндромом. Для этого запоминаем его в дополнительной переменной ii, ищем обращение i в переменной j, и сравниваем ii с j. Если числа равны, исходное i является палиндромом. Во избежание переполнения следует работать с 64 битовым целым типом.

Номера улиц могут быть 9 значные, следовательно до ближайшего палиндрома от любого числа будет не более 10⁵ чисел. Перебираем числа now – i и now + i (i = 0, 1, 2, 3, …), проверяя, являются ли они палиндромами. Каждый раз следует проверять, не больше ли now + i числа улиц в городе. В цикле for сначала проверяем на палиндром число now – i, а потом now + i. Этим самым мы обеспечим тот факт, что если существует несколько улиц - палиндромов на одинаковом расстоянии от now, то первым будет найден меньший номер.

ПРОГРАММА

#include <stdio.h>

int IsPal(long long i)

{

long long ii = i, j;

for(j = 0; i > 0; i /= 10) j = 10 * j + i % 10;

return (ii == j);

}

class CarParking

{

public:

int closestShed(int now, int streets)

{

for(int i = 0; ; i++)

{

if (IsPal(now - i)) return now - i;

if ((now + i <= streets) && (IsPal(now + i))) return now + i;

}

}

};