USACO 2019 February Contest Gold Problem 2 Dishwashing

Bessie and Elsie are helping Farmer John wash the dishes, a more complicated process than one might think due to their lack of opposable thumbs.

The two cows decide that Bessie will apply soap, and Elsie will rinse. Bessie is given a dirty stack of plates labeled 11 through NN (1≤N≤1051≤N≤105) Elsie has an empty stack, where clean plates will go. There is a counter in between Bessie and Elsie for soapy stacks.

At each step, either:

• Bessie takes a plate from the top of the dirty stack, applies soap, and then places it on the counter. When placing a soapy plate on the counter, Bessie must either (i) place the plate on top of an existing non-empty soapy stack or (ii) create a new soapy stack to the right of all existing soapy stacks.
• Elsie takes a plate from the top of the leftmost soapy stack. Elsie rinses the plate, then places it on top of the clean stack.

The goal is for the clean stack to have all plates in order, with the smallest label on the bottom and the largest label on the top. It may not be possible for the cows to achieve this goal for the entire stack of plates, so please determine the length of the largest prefix of the input ordering for which the goal is achievable.

OUTPUT FORMAT (file dishes.out):

Please output the length of the longest prefix of the input stack that can be successfully washed so that the plates end up ordered properly in the clean stack.

SAMPLE INPUT:

5 4 5 2 3 1

SAMPLE OUTPUT:

4

Problem credits: George Xing

以上就是关于【USACO 2019 February Contest Gold Problem 2 Dishwashing】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

5金3银！2026 IOAI国际人工智能奥赛收官！中国队取得历史性突破！

AI奥赛2026国家队名单公布！ 新赛季翰林助力直通IOAI全球总决赛！