Attention
시간 제한1초메모리 제한512 MB
0부터 N-1까지의 두 순열이 주어질 때, 두 순열 모두에서 증가하는 부분 수열이 되는 세 원소 조합의 개수를 세고, 없으면 없음을 판정한다.
문제
You and me, 내 맘이 보이지
한참을 쳐다봐, 가까이 다가가, you see?
Ayy-yeah, you see? Ayy, ayy, ayy, ayy
One, two, three, 용기가 생겼지
이미 아는 네 눈치 고개를 돌려 천천히, 여기
You see? 여기 보이니?
Looking for attention, 너야겠어
확실하게 나로 만들겠어
산지니는 새내기를 좋아한다. 새내기가 쿠키를 좋아한다는 것을 알게 된 산지니는 새내기가 좋아하는 맛의 쿠키를 선물해 관심을 끌고자 한다.
하나의 쿠키는 정확히 가지 재료를 통해 만들 수 있으며, 각 재료는 정수로 표현된다.
새내기의 취향을 조사한 결과, 부터 까지의 정수로 표현된 재료들이 나열된 어떠한 레시피 북에서 쿠키의 재료의 위치가 증가하는 수열인 쿠키를 좋아한다는 것을 알게 되었다.
산지니는 시행착오 끝에 새내기가 좋아하는 것으로 의심되는 레시피 북 개를 찾았다.
정확한 레시피 북은 알 수 없기에, 산지니는 새내기의 관심을 확실히 끌기 위해 개의 레시피 북에서 공통으로 위치가 증가하는 수열을 구성하는 쿠키의 재료들로 쿠키를 만들어 선물하고자 한다.
산지니가 새내기의 관심을 받기 위해서 만들어야 하는 쿠키의 개수를 알아보자.
A-T-T-E-N-T-I-ON
Attention is what I want
A-T-T-E-N-T-I-ON
You got me looking for attention
입력
첫째 줄에 레시피 북의 길이를 나타내는 정수 이 주어진다.
이어서 둘째 줄과 셋째 줄에 각 레시피 북에 나열된 쿠키의 재료들이 순서대로 나열된다.
각 레시피북에는 부터 까지의 정수로 표현되는 쿠키의 재료들이 정확히 번 나열된다.
출력
산지니가 처음 만든 레시피와 수정한 레시피 중에 새내기의 attention을 받을 수 있는 쿠키가 있으면
첫째 줄에 "My heart has gone to paradise"를 출력하고 둘째 줄에 만들어야 하는 쿠키의 개수를 출력한다.
확실히 attention을 받을 수 있는 쿠키를 찾지 못한다면 "Attention is what I want"를 출력한다.
힌트
예제 2에서 만들어야하는 쿠키들의 레시피 7개는 다음과 같이 구성된다.
1 2 3
1 2 0
1 2 4
1 3 0
1 3 4
2 3 0
2 3 4