P7412 [USACO21FEB] Year of the Cow S

Farmer John’s cows are very excited to learn that the Year of the Ox is being celebrated recently. The Year of the Ox is always the cows’ favorite. We know that in the Chinese calendar, the zodiac animal for each year follows a 12-year cycle: Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat, and then back to Ox. A lesser-known fact is that whenever the Year of the Ox arrives, a mysterious time portal opens, allowing the cows to travel through time to any past or future Year of the Ox. Bessie the cow wants to use the time portal opened this year to visit $N$ famous ancestors who lived long ago, where $1 \leq N \leq 0x10000$ (it seems fitting to express the range of $N$ in hexadecimal in the Year of the Ox; $0x10000$ equals $65536$). Unfortunately, too much time travel makes Bessie dizzy, so she wants to travel through the portal at most $K$ times ($1 \leq K \leq N$). Please help Bessie find the minimum number of years she must spend to visit all her ancestors and return to the current year, if she uses the portal at most $K$ times. If, in some Year of the Ox, Bessie does not want to use the time portal, she may choose not to. The time portal connects the first day of each Year of the Ox. Therefore, for example, if Bessie goes to some portal year and then waits until the next portal 12 years later, she spends exactly 12 years during that process. Bessie starts her trip on the first day of the current year, so she can time travel immediately. None of Bessie’s ancestors lived in a Year of the Ox.

The first line contains $N$ and $K$. The next $N$ lines contain $N$ distinct integers in the range $1 \ldots 10^9$, where each integer represents how many years ago one of Bessie’s ancestors lived.

Output the minimum number of years Bessie needs to spend to visit all ancestors and return to the current year.

One way for Bessie to visit all ancestors and return within 36 years is as follows: - Enter the time portal and go back to 48 years ago. - Wait 12 years, then enter the portal from 36 years ago and go back to 108 years ago. - Wait 24 years, then enter the portal from 84 years ago and return to the current year. Problem by: Brian Dean, David Yang. Translated by ChatGPT 5