Задача D. Спички (Школьный этап 2015 - 2016)

Товарищ A ждал товарища B недалеко от входа в парк и наблюдал за тем, как дедушка обучал внука счёту на спичках.

Конечно, когда одна спичка представляет собой одну единичку, то с помощью n спичек можно представить любое число от 1 до n, и только их. Разрешим «объединять» спички в любые числа, составленные из единиц: например, две спички, положенные рядом, будем считать обозначением числа 11, три спички — числа 111, и т.д. Тогда, например, с помощью десятка спичек мы сможем представить не только числа от 1 до 10, но и, например, число 14 (= 11 + 1 + 1 + 1; использовали 5 спичек), и 25 (= 11 + 11 + 1 + 1 + 1; использовали 6 спичек), и 112 (= 111 + 1; 4 спички). А вот, к примеру, число 38 уже так представить не получится: для этого понадобится 11 спичек.

Ваша задача — для заданного количества спичек n определить максимальное число m, такое, что все числа от 1 до m могут быть представлены с помощью n спичек, а число m + 1 с помощью n спичек представлено быть не может.