시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 41 | 37 | 36 | 90.000% |
Kattis has many pairs of nice, warm, knit socks in her sock drawer that are perfect for the winter. These socks come in a wide range of colours and types, and have all been mixed together. Each morning Kattis needs to pick two matching socks.
To find matching socks, she simply randomly takes single socks out of the drawer until she has a matching pair. It may take a long time, for example when she keeps drawing right socks without a matching left one. How long does she need to keep drawing socks until she is guaranteed to have a pair to wear?
The input consists of:
left
, right
or any
, indicating whether the socks fit on the left foot, the right foot or any foot.A given fit of a given type of sock appears at most once in the input.
Output the minimum number of socks Kattis needs to draw to be guaranteed to get a matching pair. If it is not possible to get a matching pair at all, output impossible
.
3 fuzzy any 10 wool left 6 wool right 4
8
3 sports any 1 black left 6 white right 6
impossible
2 warm any 5 warm left 3
4
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2021 K번