Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
正整数 x が美しい整数であるとは,x が 9 桁の整数であり,その 10 進法表記 S_1\ldots S_9 (S_i は x の 10 進法表記の i 文字目)が以下の条件をすべて満たすことをいいます:
- S_1 は
0
ではない - S_1 = S_2
- S_5 = S_6
- S_7 = S_9
例えば 998244353 や 333333333 は美しい整数です.111112222 は S_5 \neq S_6 であるため美しい整数ではありません.
正の整数 N が与えられます.小さい方から数えて N 番目の美しい整数を答えてください.
制約
- N は正の整数
- 美しい整数が N 個以上存在する
入力
入力は以下の形式で標準入力から与えられます.
N
出力
小さい方から数えて N 番目の美しい整数を出力してください.
入力例 1
3
出力例 1
110000020
美しい整数を小さい順に並べると,110000000, 110000010, 110000020, \ldots となります.
入力例 2
882436
出力例 2
998244353
入力例 3
2023
出力例 3
110200222
Score : 300 points
Problem Statement
A positive integer x is said to be a beautiful integer if and only if x is a 9-digit integer whose decimal notation S_1\ldots S_9 (S_i is the i-th character) satisfies all of the following conditions:
- S_1 is not
0
, - S_1 = S_2,
- S_5 = S_6, and
- S_7 = S_9.
For instance, 998244353 and 333333333 are beautiful integers, while 111112222 is not, since S_5 \neq S_6.
You are given a positive integer N. Print the N-th smallest beautiful integer.
Constraints
- N is a positive integer.
- There are at least N beautiful integers.
Input
The input is given from Standard Input in the following format:
N
Output
Print the N-th smallest beautiful integer.
Sample Input 1
3
Sample Output 1
110000020
The beautiful integers in ascending order are 110000000, 110000010, 110000020, \ldots.
Sample Input 2
882436
Sample Output 2
998244353
Sample Input 3
2023
Sample Output 3
110200222