시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
7 초 | 256 MB | 492 | 127 | 117 | 32.773% |
린셰핑(Linköping)의 수도 시설은 복잡하다. 린셰핑 근교에는 지하수를 뽑는 수원지가 몇개 있다. 지하수는 파이프를 통해서 전달되는데, 파이프는 직선으로 한 수원지와 한 도시의 지점을 잇는다.
파이프의 지하 깊이는 모두 같아서. 두 파이프가 교차하면 교차점을 만든다. 교차점에서는 정확히 두개의 파이프만이 만남을 보장한다. 수원지는 교차점으로 치지 않으며, 수원지에서는 0개 이상의 파이프가 출발할 수 있다.
교차점에는 가끔 이물질이 막히는데, 이러한 이물질은 파이프에 큰 부담을 주어서 싱크홀 현상을 만든다. 최근 캠릿브지 대학의 연구에 의하면, 이러한 싱크홀을 본 린셰핑의 대학생들은 보통 인생의 회의를 느끼고, 공부를 그만두며, 결국 사회의 붕괴를 초래한다고 한다. 사회의 유지를 위해서, 린셰핑의 수도 시설 관리 기업인 Nordic Water Extraction and Redistribution Company (NWERC) 는 로봇을 설계했다. 로봇은 수원지에서 파이프로 집어넣을 수 있으며, 파이프를 한번 왔다갔다하면서 파이프에 있는 모든 교차점을 청소한다. 정부에서는, 교차점에서 로봇이 충돌하는 일을 막기 위해, 두 파이프가 만나는 교차점이 있다면, 오직 한 파이프만이 로봇을 포함할 수 있다는 규정을 만들었다.
파이프를 청소하는 동안에는 수도 시설이 닫힌다 (이것도 정부 규정이다). 고로, NWERC는 한번의 로봇 청소만으로 모든 파이프를 청소하고자 한다. 당신은, 어떠한 파이프의 부분집합에 동시에 로봇을 삽입해서, 로봇들이 모든 교차점을 청소하고, 두 로봇이 충돌하는 일이 없는지를 판별하여야 한다.
입력은 다음과 같다.
각각의 파이프는 1개의 수원지(=시작점) 만을 포함하며, 3개 이상의 파이프가 만나는 모든 점은 수원지다. 두 파이프는 많아야 1개의 교점을 가지며, 교점은 파이프의 끝점에 있을 수도 있다. 모든 파이프의 길이는 0 초과이다.
판별 결과에 따라 가능하면 "possible", 아니면 "impossible"을 출력한다.
3 3 0 0 0 2 2 0 1 2 3 2 2 2 3 0 3
impossible
2 3 0 0 0 10 1 5 15 1 2 15 2 10 10
possible
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2015 C번