Informatica Online Judge

  고사장 찾기 [2121 / 0849]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 7   Total Tried : 8


The Champion of this Problem (C++) : gs16106 - 0ms / 734byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16048]

Background

경곽이는 수능 공부를 하는 고등학교 3학년 학생이다.

경곽이가 사는 지역은 가로 N, 세로 M개의 구역으로 나누어져 있고, 각 구역마다 고사장이 한 개씩 있으며, 고사장마다 교실이 H개 있다.

경곽이는 원래 (1,1) 구역에 있는 수일여중에서 수능을 보기로 되어 있었다. 그런데 수능이 1주일 연기되면서 고사장이 바뀌었고, 경곽이는 연기된 1주일간 열심히 공부하느라 고사장이 바뀌었다는 소식을 듣지 못한 채 아침에 일어나 수일여중으로 갔다.

경곽이는 수일여중에 있는 모든 교실을 방문한 후에야 고사장이 바뀌었다는 사실을 깨닫고 패닉에 빠져 근처 학교들을 돌아다니며 자신의 고사장을 찾기 시작했다.

경곽이가 한 시간 안에 자신의 고사장을 찾지 못하면 수능을 보지 못할 때, 무사히 수능을 칠 수 있는 고사장의 개수를 구하고, 해당 고사장들에 가는데 걸리는 시간을 오름차순으로 모두 출력하시오.

한 고사장에서 경곽이는 교실 수만큼 시간을 보낸다. 즉, 만약 수일여중에 교실이 3개가 있다면 3분을 보낸 후 다음 고사장으로 이동할 수 있다.

각 학교간 거리는 너무 가까워서 학교 사이를 이동하는데 걸리는 시간은 무시할 수 있다.

학교 사이는 상하좌우로만 이동할 수 있다.

한번 방문한 학교를 다시 지나가는 것은 시간 낭비이기 때문에 지나가지 않는다.

모든 고사장엔 적어도 1개의 교실이 존재한다.

자신의 고사장을 찾으면 그곳에 있는 자신의 친구들이 바로 올바른 교실로 데려다 주므로 시간을 쓰지 않는다.

Input

첫째 줄에는 마을의 구역을 나타내는 n (1<=n<=100), m (1<=m<=100)이 주어진다.

이후 m개의 줄마다 n개의 교실 수 h (1<=h<=60)가 주어진다.

Output

첫째 줄에는 수능을 칠 수 있는 고사장의 수를 출력한다. (수일여중은 포함하지 않는다)

둘째 줄부터는 해당 고사장들에 가는데 걸리는 시간을 오름차순으로 출력한다.

IO Example

입력1
2 2
1 59
59 1


출력1
3
1
1
60



입력2
4 4
1 1 1 57
1 1 57 1
1 57 1 1
57 1 1 1


출력2
12
1
1
2
2
2
3
3
3
3
60
60
60

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]