🐷大肚肚
CF-65B普及+/提高

修改日期

1.0s💾 256MB

📋 题目描述

给定 nn 个整数,表示 nn 个年份,请你更改一些数字,使年份按时间顺序排列,即 nn 个整数非递减排列,同时要求没有任何日期晚于 20112011 或早于 10001000 。对于每个日期,最多只能改动一个数字。

📥 输入格式

第一行一个整数 nn1n10001\le n\le 1000 ) 表示年份的个数,之后的 nn 行,每行仅有一个正整数,表示一个年份,保证所有年份的数都是一个没有前导零的四位数。

📤 输出格式

共有 nn 行,每行仅有一个正整数,为修改后的年份序列,如果有多种方案,输出任意一组符合要求的方案。如果没有满足题意的方案,输出 No  solutionNo\ \ solution

📝 样例 1

输入
3
1875
1936
1721
输出
1835
1836
1921

📝 样例 2

输入
4
9999
2000
3000
3011
输出
1999
2000
2000
2011

📝 样例 3

输入
3
1999
5055
2000
输出
No solution

📚 来源

💡 题目讲解

1

理解题意

nn 个四位数的年份。可以修改每个年份至多一个数字

修改后必须满足两个条件:

  • 每年 [1000,2011]\in [1000, 2011](不含前导零)
  • 序列非递减(年年 \ge 前一年)

无解输出 "No solution",有解输出任意一组


12001100 为例:1100 < 1200,需要改大。1100 改一位,能变哪些值?

改哪一位可能变成
千位0100(✗无前导零), 2100(>2011✗)
百位1000~1900
十位1100~1190
个位1100~1109

1200\ge 12002011\le 2011 的 → 1200~1900。选 1200(刚好等于前一个,非递减允许相等)。

1 / 5