Следующую задачу предлагалось решить на математической олимпиаде:
Приведите пример четырехзначного числа, первая цифра которого равна количеству нулей в этом числе, вторая цифра равна числу единиц, третья — числу двоек, четвертая — числу троек.
Более прикольная вариация от dalex: найдите десятизначное число, где первая цифра — количество нулей, вторая — количество единиц, ... последняя — количество девяток
А вы можете придумать такое число в уме? Надеюсь, получите удовольствие от решения :)
Прячьте свои ответы под спойлеры — пишите комментарий и сразу же редактируйте его, чтобы ответ остался в предыдущей правке. Или просто напишите программу и проверьте себя самостоятельно! (с)
[спойлер]
<спойлер>
{спойлер}
спойлер
<спойлер>
спойлер, опоздал
<спойлер> Теги порадовали :))
Если что, это не мой тег
<спойлер>
[спойлер]
спойлер: как проще перебрать.
Решил за О(1), ответ в первой правке :)
Все потому, что встречался с другой, более интересной, версией этой задачи: найдите десятизначное число, где первая цифра — количество нулей, вторая — количество единиц, ... последняя — количество девяток.
Вообще, рекомендую сразу решать эту версию, для вашего же удовольствия
спойлер для случая с 10
ans? В первой правке. Интересно, кстати, но мозгом судя по всему решать быстрее, чем полным перебором.
спойлер
Можно обощит на n-значное число. Предлагалось на IMO 2001 USA.Тут английское оффициальное решение: Clearly, all terms in the sequence are nonnegative integers. x0 = 0 gives a contradiction, so we have x0 > 0. Now let m be number of positive terms in x1, x2, ..., xn. Since xi counts the terms equal to i, x1 + x2 + ... + xn counts the total number of positive terms in the sequence, which is m + 1. For this to be possible, we must have m - 1 of these terms equal to 1, one of the terms equal to 2, and the rest equal to 0. Thus, only x0 can be greater than 2, so only one of x3, x4, ..., xn can be positive, with the positive term corresponding to the value of x0. This implies that m ≤ 3. We now casework the values of m: m = 1: x1 = 2 is impossible, so x2 = 2. This gives us x0 = 2, leading to the sequence (2, 0, 2, 0). m = 2: Either x1 = 2, or x2 = 2. These give (1, 2, 1, 0), (2, 1, 2, 0, 0). m = 3: We have xk > 0 for some k > 2. Then x0 = k, and xk = 1. x1 = 1 then is impossible, so x1 = 2, leading to x2 = 1. These are all the positive terms in the sequence, so we end up with (k, 2, 1, 0, 0, ..., 0, 1, 0, 0, 0), where there are k - 3 zeroes in the middle.