하이쿠

면접 대비

시간 제한1초메모리 제한512 MB

요약
주어진 음절 목록을 사용해 세 개의 구절을 각각 음절로 나눌 때 음절 수가 5, 7, 5가 되는 분해가 존재하는지 판정한다.
난이도

보통10점 중 6점

유형
동적 계획법, 문자열, 해시맵, 트라이
정답자
아직 제출이 없습니다

문제

하이쿠는 일본의 시 형식으로, 각각 55, 77, 55개의 음절로 이루어진 세 개의 구로 구성된다.

HiQ는 매년 직원들이 최고의 시를 제출하는 하이쿠 대회를 연다. 제출된 시는 다음과 같은 다양한 측면에서 심사된다.

  • 창의성
  • 단순함
  • 아름다움
  • 제출된 시가 실제로 하이쿠인지

마지막 항목은 심사위원들에게 상당히 어려운 문제였다. 심사위원 절반은 음절을 00부터 세고 나머지 절반은 11부터 세면서 많은 문제가 생겼다.

음절 집합이 주어졌을 때, 제출된 시가 하이쿠인지 판별하도록 심사위원들을 도와줄 수 있는가? 시에 있는 한 단어를 음절로 나누는 방법이 여러 가지일 수 있다. 이 경우 어떤 분해가 하이쿠인지 판별해야 한다.

입력

첫째 줄에는 음절의 수 1≤S≤1001 \le S \le 100이 주어진다. 다음 줄에는 SS개의 음절이 공백으로 구분되어 주어진다. 각 음절은 최대 77개의 소문자 a-z로 이루어진다.

그다음 세 줄에 시가 주어진다. 각 줄은 공백으로 구분된 비어 있지 않은 단어 목록이며, 하나의 구를 나타낸다. 단어는 소문자 a-z로만 이루어진다. 각 줄의 길이는 공백을 포함해 최대 100100자이다.

주어진 시를 주어진 음절로 분해하는 방법이 적어도 하나 존재함이 보장된다.

출력

주어진 시가 하이쿠이면 "haiku"를, 아니면 "come back next year"를 출력한다. 따옴표는 출력하지 않는다.

예제3

  1. 예제 1

    입력
    20
va
fi
ve
mor
lling
spe
in
i
sh
ti
hard
cov
ear
fe
red
ja
ry
need
ly
ning
spelling very hard
early in morning tired
i need covfefe
    예상 출력
    haiku

  2. 예제 2

    입력
    22
q
c
da
plus
to
the
e
thee
un
late
ci
a
shall
by
com
i
ru
pare
temp
ble
hi
de
shall i compare thee
to a c plus plus template
undecidable
    예상 출력
    haiku

  3. 예제 3

    입력
    19
ju
win
soft
it
east
sun
and
light
der
the
is
through
li
but
yon
what
breaks
et
dow
but soft what light through
yonder window breaks it is
the east and juliet is the sun
    예상 출력
    come back next year