시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB944100.000%

문제

Quido has lunch in Hugo’s restaurant every day. He likes the restaurant because all of its prices are expressed as integers, and for each possible price (i.e. \$1, \$2, \$3, etc.) there is at least one beverage and at least one main dish on the menu. Every day there are three entries printed on Quido’s lunch bill: the beverage price, the main dish price, and the total price. Hugo knows of Quido’s interest in computational problems and he offered Quido a free dessert each time his lunch bill meets the following three constraints:

  • the bill is not identical to any of Quido’s previous bills,
  • the price of the beverage is less than the price of the main dish, and
  • the prices listed on the bill cannot mutually use the same digit. In essence, any digit which occurs in any of the entries (beverage, main dish, total) must be different from any of the digits of the other two entries.

Quido is on a budget and he pays the same price for his lunch every day. How many times can he have a free dessert?

입력

The input consists of a single line with one integer representing the price P which Quido pays for each lunch. The value of P is positive and less than 1018.

출력

Output the maximum number of times Quido can have a free dessert at Hugo’s restaurant, provided that the price of his lunch is always P. Next, the possible bills which result in a free dessert are listed in ascending order with respect to the beverage price. Each bill consists of the price of the beverage followed by the price of the main dish. For simplicity, the value P, which is always the same, is not included in the bill.

If there are more than 5 000 possible bills, then output only the first 5 000 bills (but still report the total number of possible bills before the list of bills).

예제 입력 1

37

예제 출력 1

4
8 29
9 28
11 26
15 22

예제 입력 2

30014

예제 출력 2

7
85 29929
88 29926
785 29229
788 29226
7785 22229
7788 22226
7789 22225

예제 입력 3

202020202020202058

예제 출력 3

3
7676767676767667 194343434343434391
37373737373737397 164646464646464661
67676767676767667 134343434343434391

출처

ICPC > Regionals > North America > North America Qualification Contest > ACM-ICPC North America Qualifier 2016 F번

  • 문제를 만든 사람: Marko Berezovsky