Матч 422, Мультичисло (MultiNumber)

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

Число называется мультичислом, если его десятичное представление можно разбить на две части, произведение цифр которых одинаково. Например, число 1221 можно разбить на 12 и 21, произведение цифр которых равно: 1 * 2 = 2 * 1. Число можно разбивать только на две непустые группы последовательно стоящих цифр. Например, 12345 можно разбиться на 1-2345, 12-345, 123-45, 1234-5. Вернуть “YES”, если number является мультичислом или “NO” в противном случае.

Класс: MultiNumber

Метод: string check(int number)

Ограничения: 1 £ number £ 2,147,483,647.

Вход. Натурвальное число number.

Выход. “YES” или “NO” в зависимости от того, является ли number мультичислом.

Пример входа

number

1

1221

4729382

42393338

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

“NO”

“YES”

“NO”

“YES”

РЕШЕНИЕ

перебор

Преобразуем число number в строку n. Будем разбивать число, записанное в строке n, на две части: от нулевой цифры до (i – 1) - ой и от i - ой до len - ой, где len – количество цифр в числе number. В переменной a подсчитываем произведение цифр первой части, а в b – второй. Если для какого-нибудь разбиения имеет место равенство a = b, то возвращаем “YES”, иначе “NO”.

ПРОГРАММА

#include <cstdio>

#include <string>

using namespace std;

char n[100];

class MultiNumber

{

public:

string check(int number)

{

int i, j, a, b, len = sprintf(n,"%d",number);

for(i = 1; i < len; i++)

{

a = b = 1;

for(j = 0; j < i; j++) a *= n[j] - '0';

for(j = i; j < len; j++) b *= n[j] - '0';

if (a == b) return "YES";

}

return "NO";

}

};