1188 . 鬼腳圖

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

ck1090915

User's AC Ratio

100.0% (17/17)

Submission's AC Ratio

75.0% (21/28)

Tags

TIOJcon 2008-TIOJcon-1st

Description

大家有沒有遇過一群人無法馬上做下決定的事情呢？
例如今天晚餐要吃什麼、跨年要去哪裡狂歡、晚餐錢要誰出之類的問題…

猜拳已經落伍啦！現在最流行的(?)是鬼腳圖(好啦，其實大家一定玩過…)

曾經是高中同學的三毅、阿正、兩瑋、韋衖與小雷五個人，在美好的2007寒假，決定辦一個同學會。
但是需要進行的準備事項有五：場地、活動、聯絡、開會、茶點。
每個人做這五項工作都沒問題，但還是需要分配一下，於是他們畫了一張這樣的圖：



   1   2   3   4   5
   |   |   |   |   |
   +---+   +---+   |
   |   |   |   |   |
   |   +---+   |   |
   |   |   |   +---+
   +---+   |   |   |
   |   |   |   |   |
   +---+   |   |   |
   |   |   |   |   |
   A   B   C   D   E

五個人A,B,C,D,E沿著各自的線走，遇到岔路就一定要轉彎，而且不能往下走，最後一定會走到1,2,3,4,5五件工作其中之一。
阿正驚訝的發現五個人走到的五件工作都不會重複！

今年是2008年，這次的同學會由於擴大舉辦，總共有N個人要負責N件事情。
阿正如法炮製畫了一個類似的圖，但是由於太過複雜，阿正沒辦法確定到底每個人該做什麼事情，於是他請德育要求時弦麻煩球主商請阿棠請託蛋蛋有請川弘告訴…(族繁不急被宰)…蕃茄拜託你，來寫一個程式來求出每個人該負責的工作。

Input Format

輸入可能包含多筆測試資料，每筆測試資料的第一列有兩個正整數n(1<=n<=100)以及m(0<=m<=100,000)。
接下來有m列每列有4*n-3個字元，形成一個鬼腳圖。(為了方便起見，下面的入口由左而右依序是第1,2,...,n人，這樣就不必寫出這n個人的名字了，上面的終點依序代表編號1,2,...,n的工作，同樣的在輸入中也不會出現)

當n=m=0時代表輸入結束。

輸入的所有鬼腳圖不會有不合理的地方，所有的叉路都不會有猶豫不決的情況。

Output Format

對每一筆測試資料，請輸出一列，包含n個以一個空白間隔的數字，第i個數字代表第i個人分配到的工作編號。
注意不要輸出行尾的空白。

Sample Input 1

5 6
| | | | |
+---+ +---+ |
| | | | |
| +---+ +---+
| | | | |
| | | | |
1 0
2 1
+---+
0 0

Sample Output 1

2 4 1 5 3
1
2 1

Hints

可考慮使用gets()或cin.getline()一次輸入一列字元。

※2008/01/20題目修正：感謝jack。

Problem Source

原TIOJ1188 / TIOJ 2008例行賽01 (prob D)。Problem Setter：Tmt。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
Submit
Back to Top