Crazy numbers P37813


Statement
 

pdf   zip

html

Given three natural numbers b, d and n, let us say that a natural number x is crazy if x is a multiple of n, and x represented in base b

  • has exactly d digits (maybe with a leading zero),
  • and does not have two equal consecutive digits.

Given b, d and n, can you find all crazy numbers?

Input

Input consists of several cases, each one with b, d and n. You can assume 3 ≤ b ≤ 10, d ≥ 1, and n < bd ≤ 1017.

Output

For every case, print in order and with exactly d digits all crazy numbers in base b, followed by a line with ten dashes. All given cases are such that there are between 1 and 100 crazy numbers.

Observation

The expected solution requires less than 0.1 seconds to solve Sample input 2.





Public test cases
  • Input

    10 1 5
    10 9 123456789
    4 5 108
    5 24 98765432109876
    

    Output

    0
    5
    ----------
    123456789
    246913578
    370370367
    493827156
    617283945
    740740734
    864197523
    987654312
    ----------
    01230
    03120
    20130
    ----------
    032043431321202432312313
    121312313043034230314202
    142103021401412342123403
    320434313212024323123130
    430242010421032012421213
    ----------
    
  • Input

    3 35 959849555
    

    Output

    01010120212021021202102120121212021
    01010210202101210120212021012020212
    01012102010202121012121210121202120
    01020101012010120201210102120121012
    01020102102102021202101012010102120
    01020121021012102102120121010201012
    01202012120201210210120120210202101
    01202120210202102121012120210120102
    01202120212101202020210120120201212
    01212020210212010210201012021212020
    02010210102102120121010201020101202
    02010212020102120202120101021021202
    02012020120121010102012012101010201
    02020101020121201010120102121210120
    02020201012121201021201021012120201
    02021021201212010121012121010102010
    02102020201020101012012010201021021
    02120102012120101212021021212010120
    02121020120101020212102121210101012
    10101020212021012010210201010120201
    10101202120210212021021201212120210
    10102102021012101202120210120202120
    10201010120101202012101021201210120
    10201210210121021021201210102010120
    12010102012021201202012121210102101
    12010202120210121210202021201202021
    12020121202012102101201202102021010
    12021202102021021210121202101201020
    12021202121012020202101201202012120
    12101012101210210212012010201210202
    12102101212121020202010120120120212
    12121202020121010102101201201020212
    20101010212101201202101021012010101
    20102101021021201210102010201012020
    20102120201021202021201010210212020
    20120120102010102021020202010202102
    20120120121210202020101202101201212
    20120201201210101020120121010102010
    20120210202102020201212020212101021
    20121212102121201010201202102101212
    20201012120120120210120201201012121
    20202010121212010212010210121202010
    20212012121201010101010120120212102
    20212121201020201202020102020212121
    21012010202101020201202010210212021
    21020202010201010120120102010210210
    21020210120102021202021201020101201
    21021010212120120212120212101202021
    21021201021020202020201201202120202
    21201020202010210102102021202010212
    21210201201010202121021212101010120
    21210210101010101210102101210121012
    21212021202012012012012020210202102
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Dotzè Concurs de Programació de la UPC - Final
    Date
    2014-10-01