iktk   2년 전

문제

당신은 항공사 Fly Away Air의 직원이다. Fly Away Air는 타 항공사들과는 다르게 고객이 예약 없이 방문하면 항공편을 자동으로 매칭해 주는 혁신적인 시스템을 도입하였다. 당신은 상사로부터 회사에서 낭비되고 있는 돈이 있는지 확인하라는 임무를 받았고, 모든 항공편이 빈 좌석 없이 운행될 수 있는지 확인하고자 한다.

$n$일에 걸친 $k$개의 공항의 비행 스케줄이 주어진다. 어느 두 공항 간의 노선에도 하루에 두 편 이상 운행하는 경우는 없으며, 승객들은 도착한 날부터 항공기에 탑승할 때까지 무한정 기다린다.

승객들은 하루에 비행기를 한번만 탈 수 있으며, 두 편 이상 타면 멀미를 한다. 또한, 각 승객이 원하는 행선지는 없으며, 아무 비행기나 자유롭게 탑승할 수 있다. 심지어 원래 있던 곳으로 돌아오는 노선에도 탑승할 수 있다.

모든 항공편의 빈 자리가 없도록 할 수 있는지 확인해보자.

입력

첫 번째 줄에는 세 개의 정수 $k$, $n$, $m$이 공백으로 구분되어 주어진다. $k$($2\le k\le 12$)는 공항의 수, $n$ ($1\le n\le 8$)는 분석 대상 일수, $m$ ($1\le m\le k\cdot (k − 1)\cdot n$) 는 항공편의 수를 나타낸다.

두 번째 줄부터 $m$개의 행은 각각 하나의 항공편을 나타내는 4개의 정수 $u$, $v$, $d$, $z$가 공백으로 구분되어 주어진다. $u$는 출발하는 공항 번호 ($1\le u\le k$), $v$는 도착하는 공항 번호 ($1\le v\le k$, $u \ne v$), $d$는 항공편이 운행하는 날짜 ($1\le d\le n$), $z$는 해당 항공편의 좌석 수($1\le z\le 30\,000$)를 나타낸다. $m$개의 행 중 $u$,$v$,$d$가 모두 같은 행은 최대 1개만 주어진다.

그 다음 줄부터 $kn$개 행에는 승객들의 정보가 주어진다. 각 행에는 세 개의 정수 $a$, $b$, $c$가 주어지는데, $a$는 공항 번호 ($1\le a\le k$), $b$는 승객이 공항에 도착하는 날짜 ($1\le b\le n$), $c$는 승객의 수 ($1\le c\le 30\,000$)를 나타낸다. $c$에는 다른 공항으로부터 비행기를 타고 도착한 승객이 포함되어 있지 않다. 특정한 ($a$, $b$)값의 쌍은 정확히 한 번씩만 나타난다.

출력

모든 항공편의 빈 자리가 없도록 승객을 태울 수 있다면 optimal, 그렇지 않다면 suboptimal을 출력한다.

모든 승객을 항공편에 탑승시켜야 하는 것이 아님에 유의하라.

댓글을 작성하려면 로그인해야 합니다.