No.3453 Crape Shop
タグ : / 解いたユーザー数 113
作問者 :
くらげ
/ テスター :
hikikomori
Problem Statement
You run a crepe shop.
The menu of this shop has $3$ kinds of crepes, crepe $1$ through crepe $3$. Crepe $1$ uses an apple, crepe $2$ uses a banana, and crepe $3$ uses both an apple and a banana, using $1$ of each required fruit.
At the time the shop opens today, there are $A$ apples and $B$ bananas in stock. Also, $N$ customers will visit today, and it is known that customer $i$ ( $1 \le i \le N$ ) will order crepe $p_i$.
Each customer orders $1$ crepe, and whenever an order is received, you always consume $1$ of each ingredient and make the ordered kind of crepe.
Determine which customer's arrival is the first time that "the ordered crepe cannot be made because there are not enough ingredients" occurs. If the crepes for all $N$ customers' orders can be made without running out of stock, print -1.
Here, being unable to make a crepe because of insufficient ingredients means that, at the time the order is received, the stock of an ingredient used in that crepe is $0$ or less. Ingredients other than apples and bananas are assumed to be unlimited.
Constraints
- $1 \le N \le 10 ^ 5$
- $1 \le A, B \le 10 ^ 5$
- $1 \le p_i \le 3$
- All inputs are integers.
Input
$N$ $A$ $B$ $p_1$ $p_2$ $\dots$ $p_N$
Output
Print on $1$ line the position of the customer whose arrival is when the ordered crepe cannot be made. If this never happens, print -1.
Sample
Sample 1
Input
6 2 4 1 3 2 2 3 1
Output
5
Initially there are enough apples for $2$ crepes, and $1$ apple each is used for the crepes ordered by customers $1$ and $2$. The next customer to order a crepe using an apple is customer $5$, and at this point the stock of apples is insufficient. In this case bananas never run short, so print 5.
Sample 2
Input
6 4 4 1 3 2 2 3 1
Output
-1
Sample 3
Input
10 6 3 1 3 2 1 3 3 1 1 3 2
Output
6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。