← 返回题目列表

AtCoder · agc066_b

B. 减少数字和

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

对于正整数 x,让 f(x) 表示其数字之和。例如, f(331)=3+3+1=7, f(2024)=2+0+2+4=8,和 f(1)=1.

给你一个正整数 N。打印一个正整数 x 满足以下所有条件:

  • 1\leq x< 10^{10000}
  • f(2^{i-1}x)>f(2^ix) 对于所有整数 1\leq i\leq N.

约束

  • 1\leq N\leq 50

输入

输入由标准输入按以下格式给出:

N

输出

打印一个正整数 x 满足条件。如果有多个正整数 x 满足条件,其中任何一个都将被接受。


示例输入 1

3

示例输出 1

89

对于 x=89,它来自 f(x)=17, f(2x)=16, f(4x)=14,和 f(8x)=10 那 f(x)>f(2x)>f(4x)>f(8x),满足条件。

满足条件的其他一些整数是 x=539 和 x=890.