各位数字全不同的最近一天（MM/DD/YYYY）

Distinct Date II

专题: Algorithmic Programming / 算法编程
难度: L4
来源: QuantQuestion

题目详情

找“最近（最晚）的一天”的日期，使得按 $MM/DD/YYYY$ 表示时出现的所有数字都互不相同。

例如 $01/23/4567$ 是合法的。用 $MMDDYYYY$ 的形式给出答案。

Find the most recent date where all of the digits, when expressed in the form $MM/DD/YYYY$ are distinct. For example, $01/23/4567$ would be a valid date. Express your answer in the form $MMDDYYYY$ .

解析

要尽量晚，年份应尽量大且仍在过去。

分析可知年份必须以 1 开头；为最大化年份，取 $1987$ 。

此时月份首位只能是 0，选最大的可用月份为 06；再选可行的最大日期为 25。

因此日期为 $06/25/1987$ ，答案为

06251987.

Original Explanation

Our goal now is to maximize the year to make it as close as possible to our present date. The biggest thing to first note is that the year must start with a $1$ . Suppose that it started with a $2$ . We know that the first $M$ is either a $0$ or $1$ . If it is a $0$ , then the day either starts with a $1$ or is $31$ . Note that the other $M$ can't be a $1$ in this case; otherwise, that would eliminate the day possibilities. If the month starts with a $1$ , then the day either contains $0$ or is $30$ . However, since the $0$ is already used in the $MMDD$ part, regardless of what we start with, we can't get a year that is in the past.

Therefore, the year must start with a $1$ . To maximize the year, we can just fix the rest as the three largest integers. Namely, $987$ , so our year is $1987$ . Since the year starts with $1$ , the month must start with $0$ . Then, we choose the largest month integer remaining, which is $6$ . Then, we must pick the largest possible day among the integers remaining. We can see that $25$ is the largest possible day, as anything starting with $3$ is not possible. Therefore, our date is $06/25/1987$ .