201530: [AtCoder]ARC153 A - AABCDDEFE

Memory Limit：1024 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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

Input

题意翻译

我们定义一个 $9$ 位的正整数（设这个正整数从高位到低位的第 $i$ 位的数是 $S_i$，如 $143,446,709$，其中 $S_3 = 3$）是**美丽的正整数**，当且仅当满足：$S_1 \neq 0, S_1 = S_2, S_5 = S_6, S_7 = S_9$。 举个例子，$998244353$ 是美丽的正整数，但 $111112222$ 不是，因为 $S_5 \neq S_6$。 现在给你一个正整数 $N$，请输出第 $N$ 小的美丽的正整数。 输入保证答案一定存在。换句话说，一定存在第 $N$ 小的美丽的正整数。

Source/Category

加入题单

算法标签：