CF-65B普及+/提高
修改日期
⏱ 1.0s💾 256MB
📋 题目描述
给定 个整数,表示 个年份,请你更改一些数字,使年份按时间顺序排列,即 个整数非递减排列,同时要求没有任何日期晚于 或早于 。对于每个日期,最多只能改动一个数字。
📥 输入格式
第一行一个整数 ( ) 表示年份的个数,之后的 行,每行仅有一个正整数,表示一个年份,保证所有年份的数都是一个没有前导零的四位数。
📤 输出格式
共有 行,每行仅有一个正整数,为修改后的年份序列,如果有多种方案,输出任意一组符合要求的方案。如果没有满足题意的方案,输出 。
📝 样例 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
📚 来源
Problem:CF-65B
Contest:Codeforces Beta Round #60
💡 题目讲解
1
理解题意
有 个四位数的年份。可以修改每个年份至多一个数字。
修改后必须满足两个条件:
- 每年 (不含前导零)
- 序列非递减(年年 前一年)
无解输出 "No solution",有解输出任意一组。
以 1200 和 1100 为例:1100 < 1200,需要改大。1100 改一位,能变哪些值?
| 改哪一位 | 可能变成 |
|---|---|
| 千位 | 0100(✗无前导零), 2100(>2011✗) |
| 百位 | 1000~1900 |
| 十位 | 1100~1190 |
| 个位 | 1100~1109 |
取 且 的 → 1200~1900。选 1200(刚好等于前一个,非递减允许相等)。
1 / 5