Bài tập đồ thị Pascal Tin học lớp 9 - Võ Trí Viết

Baøi taäp Thöïc haønh:
Baøi 1. Vieát moät chöông trình tìm caùc thaønh phaàn lieân thoâng cuûa ñoà thò
+ Yeâu caàu:
- Xaùc ñònh tính lieân thoâng
- Caùc thaønh phaàn lieân thoâng
- Minh hoïa baèng ñoà hoïa
döõ lieäu vaøo: laø töø file text coù teân DOTHI.INP
	-haøng ñaàu ghi soá N (soá ñænh ñoà thò), vaø soá K (soá caïnh cuûa ñoà thò).
	-K haøng tieáp theo haøng thöù i chöùa 2 soá ui vaø vi moâ taû caïnh thöù i töông öùng vôùi ñænh ui vaø vi cuûa ñoà thò.
Keát quûa : Ra maøn hình nhö sau :
-Doøng ñaàu : Soá thaønh phaàn lieân thoâng.
-Caùc doøng tieáp theo:
+Thaønh phaàn thöù 1: x1 x2 .....
+Thaønh phaàn thöù 2: x1 x2 .....
+........................
Baøi 2.
	Coù N thaønh phoá ñaùnh soá thöù töï töù 1 ñeán N, giöõa caùc thaønh phoá coù theå coù hoaëc khoâng coù ñöôøng ñi. Ñöôøng ñi coù theå laø moät chieàu hoaëc hai chieàu. Tìm taát caû ñöôøng ñi töø thaønh phoá x ñeán thaønh phoá y cho tröôùc.
döõ lieäu vaøo: laø töø file text coù teân THPHO.INP
	-haøng ñaàu ghi soá N (soá thaønh phoá), vaø soá K (soá ñöôøng ñi tröïc tieáp giöõa 2 thaønh phoá).
	- Doøng thöù hai ghi hai soá x vaø y
	-K haøng tieáp theo haøng thöù i chöùa 2 soá ui vaø vi moâ taû ñöøng thöù i töông öùng noái hai thaønh phoá ui vaø vi .
	Keát quûa: Ra maøn hình
	-Doøng ñaàu toång soá ñöôøng ñi.
	-Caùc doøng tieáp theo, moãi doøng laø danh saùch caùc ñænh treân ñöôøng ñi, baét ñaàu töø x keát thuùc taïi y. 
Baøi 3. “ Otomat”. Moät maùy ñoåi theû giaûi trí töï ñoäng coù m cöûa duøng ñeå ñoåi theû. Coù caùc theû maõ soá töø 1 ñeán n. Neáu ta boû theû coù maõ i vaøo 1 cöûa naøo ñoù thì maùy thu theû ñoù vaø cho ra 1 theû coù maõ soá trong khoaõng 1 ... n. Ngöôøi ta tieát loä cho baïn bieát raèng maùy haønh ñoäng theo thoâng tin ghi trong teäp vaên baûn coù teân OTOMAT.INP nhö sau:
- Caùc giaù trò n m (doøng ñaàu tieân)
- Moät baûng kích thöôùc n x m (n doøng m coät)
phaàn töû naèm treân doøng i, coät j cuûa baûng naøy laø phaàn töû maùy seõ cho ra neáu ta boû theû maõ i vaøo cöûa j.
Yeâu caàu:
a- Vôùi moãi theû soá hieäu x cho tröôùc haõy tìm caùch nhanh nhaát ñeå thu ñöôïc theû coù soá hieäu lôùn nhaát.
b- Vôùi moãi caëp theû x, y cho tröôùc haõy tìm caùch nhanh nhaát (coù theå neáu ñöôïc) ñeå duøng theû x thu ñöôïc theû y.
Lôøi giaûi caàn hieån thò treân maøn hình theo maãu sau:
Boû theû x vaøo cöûa y seõ thu ñöôïc theû z
Boû theû z vaøo cöûa .....
Baøi 4. Maïng maùy tính:
Moät maïng maùy tính goàm n maùy ñaùnh soá töø 1 ñeán n, vaø m keânh truyeàn tin moät chieàu giöõa moät soá caëp maùy ñöôïc ñaùnh soá töø 1 ñeán m. Maïng maùy tính laø thoâng suoát (nghóa laø töø moät maùy baát kyø coù theå truyeàn tin ñeán taát caû caùc maùy coøn laïi hoaëc laø theo keânh noái tröïc tieáp hoaëc thoâng qua caùc maùy trung gian). Moät maùy trong maïng ñöôïc goïi laø maùy chaún (maùy leû) neáu soá keânh truyeàn tin tröïc tieáp töø ñoù ñeán caùc maùy khaùc trong maïng laø soá chaún (soá leû).
Giaû söû S vaø T laø hai maùy leû trong maïng. Baèng caùch ñaûo ngöôïc höôùng truyeàn tin moät soá keânh trong maïng, haõy bieán ñoåi maïng ñaõ cho thaønh maïng (khoâng nhaát thieát phaûi thoâng suoát) maø trong ñoù 2 maùy S vaø T trôû thaønh maùy chaún maø khoâng thay ñoåi tính chaún leû cuûa caùc maùy khaùc.
Döõ lieäu vaøo ñöôïc cho trong file kieåu Text coù teân NET.INP theo qui caùch:
- Doøng ñaàu tieân chöùa 2 soá n, m ñöôïc ghi caùch nhau bôûi daáu caùch ( n < 1 0 1 )
- Doøng thöù hai chöùa 2 soá nguyeân döông S T ñöôïc ghi caùch nhau bôûi daáu caùch laø chæ soá cuûa 2 maùy leû trong maïng.
- Doøng thöù i trong soá m doøng tieáp theo ghi 2 soá nguyeân Ui , Vi cho bieát keânh thöù i truyeàn tröïc tieáp töø maùy Ui ñeán maùy Vi ( i = 1, 2, ... , m )
Keát quaû ghi ra maøn hình vaø ra file kieåu Text vôùi teân NET.OUT theo qui caùch:
- Doøng ñaàu ghi soá löôïng keânh caàn thay ñoåi höôùng truyeàn q 
- Moãi doøng trong soá q doøng tieáp theo ghi chæ soá cuûa keânh caàn ñaûo ngöôïc höôùng truyeàn tin.
Ví duï: 
NET.INP
NET.OUT
6
9
3
1
6
1
1
2
7
2
3
9
3
4
4
1
4
6
6
3
2
5
5
3
5
6
Baøi 5. “Löôùi ñen traéng”
Cho 1 löôùi caùc oâ vuoâng, moãi oâ coù maøu ñen hoaëc traéng. Cho moät maãu caét hình chöõ nhaät laø moät phaàn cuûa löôùi naøy. Maãu caét goàm m doøng vaø n coät (m, n < 100) Haõy cho bieát:
a- Soá vuøng maøu ñen, soá vuøng maøu traéng coù trong maãu caét. Bieát raèng 2 oâ coù chung caïnh vaø cuøng maøu laø naèm trong moät vuøng.
b- haõy ñoåi maøu (ñen thaønh traéng hoaëc traéng thaønh ñen) cho 1 vuøng naøo ñoù ñeå sau khi ñoåi ta coù vuøng môùi vôùi dieän tích lôùn nhaát .
Keát quaû ghi ra maøn hình.
döõ lieäu vaøo: laø töø file Text LUOI.INP coù caáu truùc:
- Doøng ñaàu laø hai soá nguyeân döông m, n. Töø doøng thöù hai trôû ñi ñeán doøng m+1, moãi doøng chöùa n soá (0 hoaëc 1) caùch nhau bôûi ít nhaát 1 kyù töï traéng. Soá 0 töông öùng cho oâ maøu ñen, soá 1 töôïng tröng cho oâ maøu traéng.
VD:
LUOI.INP
Döõ lieäu ra: ghi leân maøn hình
5
5
Soá vuøng maøu traéng: 2
0
1
0
1
0
Soá vuøng maøu ñen: 3
0
0
0
1
1
Sau khi ñoåi maøu 1 vuøng
1
1
1
1
1
Dieän tích vuøng lôùn nhaát ñaït ñöôïc: 24
0
0
0
0
0
Maøn cuûa vuøng lôùn nhaát: Ñen.
0
0
0
0
0
Baøi 6. “ Maïng ñöôøng saét”
	Do nhu caàu caáp baùch trong xaây döïng kinh teá cuûa moät quoác gia, ngöôøi ta caàn söûa chöõa gaáp ruùt laïi moät maïng löôùi ñöôøng saét ( hai chieàu) ñaõ coù saún löu thoâng giöõa N thaønh phoá ( ñaùnh soá thöù töï 1,2,...,N). Bieát raèng chi phí cho söõa chöõa chæ phuï thuoäc vaøo chieàu daøi cuûa ñoaïn ñöôøng cuû. Haõy tìm moät phöông aùn söõa chöõa ít toán keùm nhaát maø vaãn ñaûm baûo laø chæ söû duïng ñöôøng môùi söõa maø vaãn löu thoâng giöõa caùc thaønh phoá nhö tröùôc khi söûa.
döõ lieäu vaøo: laø töø file text coù teân DUONGSAT.INP
	-haøng ñaàu ghi soá N (soá thaønh phoá), vaø soá K (soá ñöôøng noái tröïc tieáp giöõa hai thaønh phoá).
	-K haøng tieáp theo haøng thöù i chöùa 3 soá ui , vi vaø di moâ taû coù ñöôøng noái thöù i giöõa 2 thaønh phoá ui vaø vi vôùi chieàu daøi laø di.
	Keát quûa: Ra maøn hình.
	-Doøng tieân laø toång soá chieàu daøi caàn söûa chöõa.
	-Caùc doøng tieáp theo laø chæ soá cuûa caùc ñöôøng caàn söûa.
Baøi 7.
Cho moät baûng N doøng, M coät caùc soá nguyeân khoâng aâm. Töø moät oâ (i,j) ta coù theå ñi sang oâ chung caïnh neáu giaù trò cuûa oâ naøy khoâng lôùn hôn giaù trò cuûa oâ (i,j). Moät ñöôøng ñi töø oâ (i,j) tôùi oâ (k,l) theo caùch ñi treân goïi laø moät ñöôøng ñi xuoáng. Haõy laäp trình giaûi quyeát caùc baøi toaùn sau:
1. Cho tröôùc hai oâ (i,j) vaø (k,l). Haõy tìm moät ñöôøng ñi xuoáng töø oâ (i,j) tôùi oâ (k,l) (neáu coù) vôùi toång giaù trò T caùc oâ treân ñöôøng ñi laø beù nhaát.
2. Cho tröôùc oâ (i,j) haõy chæ ra moät ñöôøng ñi xuoáng qua nhieàu oâ nhaát xuaát phaùt töø oâ (i,j).
Döõ lieäu trong file TEXT coù teân BANG.INP vôùi caáu truùc nhö sau:
	- Doøng ñaàu laø hai soá N, M (beù hôn hay baèng 100)
	- N doøng tieáp theo, doøng thöù i chöùa töông öùng doøng thöù i cuûa baûng.
	- Doøng tieáp theo chöùa 4 soá i, j, k vaø l töông öùng vôùi döõ lieäu caâu 1.
	- Doøng cuoái chöùa 2 soá i vaø j töông öùng vôùi döõ lieäu caâu 2.
Keát quaû ghi ra file TEXT coù teân BANG.OUT vôùi caáu truùc nhö sau:
	- Doøng ñaàu laø: “KET QUA CAU 1:”
	- Doøng thöù 2 ghi giaù trò T.
	- Doøng thöù 3 ghi “KHONG” neáu khoâng coù ñöôøng ñi xuoáng töø oâ (i,j) tôùi oâ (k,l), ngöôïc laïi ñöa ra daõy caùc oâ treân ñöôøng ñi baét ñaàu tö oâ (i,j) vaø keát thuùc taïi oâ (k,l).
	- Doøng thöù 4 ghi ra: “KET QUA CAU 2”
	- Doøng thöù 5 ghi ra ñöôøng ñi tìm ñöôïc quy caùch nhö doøng thöù 3.
Caùc soá treân cuøng moät doøng trong caùc file BANG.INP vaø BANG.OUT caùch nhau bôûi ít nhaát moät khoaûng traéng.
Baøi 8.
Cho moät löôùi caùc oâ vuoâng maø toïa ñoä goùc traùi döôùi laø (0,0), toïa ñoä goùc phaûi treân laø (100,100) goàm 10.000 oâ vuoâng. Trong löôùi naøy ta ñaët N hình vuoâng khaùc nhau kích thöôùc ñeàu baèng 5x5, caùc ñænh cuûa caùc hình vuoâng naøy coù toïa ñoä nguyeân vaø caùc caïnh hình vuoâng song song vôùi caùc truïc toïa ñoä vaø hai caïnh song song cuûa hai hình vuoâng khaùc nhau caùch nhau ít nhaát 1 ñôn vò. Ñeå ñi töø ñieåm (0,0) ñeán ñieåm (100,100), coù theå coù hai caùch ñi:
	- Caùch thöù nhaát: ñi theo caùc caïnh cuûa caùc oâ cuûa löôùi, caùc moác ñi qua laø caùc ñænh.
	- Caùch thöù hai: ñi theo caùc ñænh cuûa löôùi, töø moät ñænh naøy ñeán moät ñænh khaùc theo ñoaïn noái hai ñænh ñoù.
Ñöôøng ñi töø oâ (0,0) ñeán oâ (100,100) chæ ñöôïc chung vôùi N hình vuoâng ñaõ cho nhieàu nhaát 1 ñieåm.
Döõ lieäu ñöôïc cho bôûi file TEXT coù teân INPUT.DAT trong ñoù doøng thöù nhaát ghi soá N, caùc doøng tieáp theo moãi doøng ghi hai soá x vaø y maø (x,y) laø toïa ñoä cuûa ñænh traùi döôùi cuûa hình vuoâng, 0 £ x,y £ 95.
1. Tìm ñöôøng ñi ngaén nhaát töø (0,0) ñeán (100,100) theo caùch thöù nhaát. Keát quaû thoâng baùo ra file TEXT coù teân KQ2.DAT caùc ñænh laàn löôït treân haønh trình trong moät doøng, doøng tieáp theo thoâng baùo ñoä daøi.
2. Tìm ñöôïc ñi ngaén nhaát töø (0,0) ñeá (100,100) theo caùch thöù hai. Keát quaû thoâng baùo tieáp ra file TEXT coù teân KQ1.DAT caùc ñænh laàn löôït treân haønh trình trong moät doøng, doøng tieáp theo thoâng baùo ñoä daøi.
Baøi 9. “Laäp lòch bay”
Coù N thaønh phoá (N £ 50). Haøng ngaøy töø thaønh phoá i ñeán thaønh phoá j coù caùc chuyeán bay vaøo caùc giôø naøo ñoù, caùc giôø naøy tính thoáng nhaát theo moät ñoàng hoà chung cho caû N thaønh phoá. Taïi thaønh phoá i, neáu ôû laïi ñoù moät giôø thì toán moät löôïng tieàn naøo ñoù. Moät ngöôøi muoán bay töø thaønh phoá u ñeán thaønh phoá v vaø khôûi haønh vaøo giôø T. Thôøi gian chuyeån maùy bay xem nhö khoâng ñaùng keå.
Döõ lieäu ñöôïc cho bôû file TEXT coù teân MB.DAT trong ñoù doøng thöù nhaát ghi caùc soá N, u, v, T. Vôùi 1 £ i,j £ N, doøng thöù (i-1)N+j+1 ghi nhö sau:
	- Neáu i¹j thì soá ñaàu tieân laø thôøi gian bay töø i ñeán j, soá thöù hai laø giaù veù bay töø i ñeán j, tieáp theo laø caùc giôø coù chuyeán bay töø i ñeán j, neáu doøng naøy roãng coù nghóa laø khoâng coù ñöôøng bay töø i ñeán j.
	- Neáu i=j thì ghi chi phí cho 1 giôø taïi i. 
Taát caû caùc soá ñeàu nguyeân döông, soá chæ giôø tính töø 1 ñeán 24
Haõy tìm cho ngöôøi ñoù moät haønh trình töø u ñeán v theo caùc yeâu caàu sau ñaây:
	1. Thôøi gian bay nhanh nhaát. Keát quaû thoâng baùo ra file TEXT vôùi teân KQ.DAT, caùc doøng ñaàu ghi haønh trình, moãi doøng moät chaëng theo quy caùch nhö sau (quy öôùc ngaøy 1 laø ngaøy khôûi haønh):
	...........................
	4 ® 3 ñi 5 giôø ngaøy 6 ñeán 7 giôø ngaøy 8.
	3 ® 10 ñi 11 giôø ngaøy 8 ñeán 15 giôø ngaøy 8.
	...........................
doøng tieáp theo thoâng baùo giôø bay töø u, giôø ñeán v, thôøi gian bay (chuù yù raèng haønh trình coù theå keùo daøi nhieàu ngaøy).
2. Chi phí ít nhaát. Keát quaû thoâng baùo tieáp ra file KQ2.DAT, caùc doøng cho haønh trình töông töï nhö treân, doøng tieáp theo ghi chi phí, giôø bay töø u, giôø ñeán v, thôøi gian bay.
Baøi 10. “Veõ Ñöôøng”
Moät löôùi giao thoâng ñöôøng hai chieàu giöõa n ñòa ñieåm ñöôïc cho bôûi ma traän A[i,j] trong ñoù A[i,j] =1 neáu ñòa ñieåm i noái vôùi ñòa ñieåm j, coøn A[i,j] =0 trong tröôøng hôïp ngöôïc laïi. Treân moãi ñoaïn ñöôøng coù vaïch ôû giöõa ñeå phaân caùch. Ngöôøi ta caàn veõ laïi vaïch naøy treân moãi ñoaïn ñöôøng baèng caùc xe veõ vaïch, moãi ñoaïn moät laàn. Moãi moät xe khi ñaõ baét ñaàu veõ vaïch khoâng naâng ñöôïc caàn leân cho ñeán khi keát thuùc. Moãi moät xe chæ söû duïng moät laàn.
Haõy laäp trình xaùc ñònh soá löôïng ít nhaát caùc xe phaûi söû duïng ñeå veõ laïi vaïch cho taát caû ñoaïn ñöôøng, moãi xe haõy chæ ra loä trình maø noù phaûi thöïc hieän.
Döõ lieäu cho trong File Text coù teân nhaäp töø baøn phím, trong ñoù doøng ñaàu laø n, n doøng tieáp theo laø chöùa baûng A. Keát quaû ñöa ra maøn hình (Quy caùch ñöa keát quaû ra tuøy choïn).
Baøi 11. “Toâ Maøu”.
	Cho moät baûng goàm caùc hình vuoâng, kích thöôùc MxN (M,N<=100). Trong ñoù coù moät soá oâ ñen, coøn laïi laø oâ traéng. Haõy toâ maøu taát caû caùc oâ traéng baèng hai maøu xanh vaø ñoû sao cho treân moãi doøng cuõng nhö treân moãi coät soá löôïng caùc oâ maøu xanh vaø soá löôïng caùc oâ maøu ñoû cheânh leäch nhau khoâng quaù 1. 
	Döõ lieäu vaøo: laø file Text TOMAU.INP coù caáu truùc nhö sau:
	- Doøng ñaàu tieân laø 2 soá M, N
	- M doøng tieáp theo moãi doøng goàm N soá (0 hoaëc 1)
	Doøng thöù i coät j moâ taû cho oâ vuoâng ôû haøng i coät j. Soá 0 töông öùng cho oâ traéng, soá 1 töông öùng cho oâ ñen.
	Keát quaû: file TOMAU.OUT hoaëc maøn hình
	Caáu truùc nhö sau:
	Moät baûng soá goàm M doøng vaø N coät. Soá ôû haøng i coät j moâ taû cho oâ töông öùng (i,j). Soá 2 töông öùng cho maøu xanh, soá 3 töông öùng cho maøu ñoû. (coù theå cho hieån thò treân maøn hình ñoà hoïa baûng maøu töông öùng).
	Ví duï:
ñ
x
x
ñ
x
ñ
x
x
ñ
x
ñ
TOMAU.INP
TOMAU.OUT
6 4
3 1 2 1
0 1 0 1 
2 1 1 1
0 1 1 1 
1 3 1 2
1 0 1 0
3 2 1 1
0 0 1 1
1 2 1 3
1 0 1 0
2 1 3 1
0 1 0 1
Baøi 12. Laâu ñaøi.
	Hình beân döôùi laø löôùi oâ vuoâng kích thöôùc MxN (M=4, N=7) bieåu dieãn moät laâu ñaøi. 
Ta goïi moät phoøng laø goàm 1 hoaëc nhieàu oâ vuoâng chung caïnh ñöôïc bao chung quanh bôûi caùc böùc töôøng.Haõy vieát chöông trình tính :
1. Laâu ñaøi coù bao nhieâu phoøng ?
2. Phoøng lôùn nhaát laø bao nhieâu oâ vuoâng ?
3. Böùc töôøng naøo caàn loaïi boû ñeå coù moät phoøng caøng nhieàu oâ vuoâng caøng toát.
1
2
3
4
5
6
7
(Muõi teân trong hình chæ böùc töôøng bò loaïi boû)
1
2
3
4
->
Döõ lieäu vaøo: File text teân LAUDAI.INP coù caáu truùc nhö sau:
-Doøng ñaàu tieân laø hai soá M,N (0<M,N<50).
-M doøng tieáp theo, moãi doøng laø N soá , soá thöù j cuûa doøng thöù i laø soá pij nhaèm moâ taû caùc böùc töôøng taïi oâ haøng i coät j. Caùch thöù moâ taû nhö sau : pij laø toång cuûa caùc soá sau:
	1: neáu oâ(i,j) coù böùc töôøng phía Taây (beân traùi);
	2: neáu oâ(i,j) coù böùc töøng phía Baéc (beân treân);
	4: neáu oâ(i,j) coù böùc töøng phía Ñoâng (Beân phaûi);
	8: neáu oâ(i,j) coù böùc töøng phía Nam (Beân döôùi);
	Caùc böùc töôøng beân trong coù theå ñöôïc xaùc ñònh hai laàn trong hai oâ 
Keát Quûa : Ra Maøn hình nhö sau: Vieát treân 3 doøng:
+ Doøng thöù nhaát vieát soá löôïng phoøng.
+ Doøng tieáp theo vieát dieän tích (toång soá oâ) cuûa phoøng lôùn nhaát.
+ Doøng thöù cuoái cuøng vieát hai soá ñaàu chæ haøng vaø coät cuûa oâ chöùa böùc töôøng bò loaïi boû, sau ñoù laø moät soá chæ böùc töôøng töông öùng bò boû (1:Taây;2:Baéc;4:Ñoâng;8:Nam);
Ví duï :
LAUDAI.INP
Maøn hình
4 7
5
11 6 11 6 3 10 6
9
7 9 6 13 5 15 5 
4 1 4
1 10 12 7 13 7 5
13 11 10 8 10 12 13
Baøi 13. Meâ Cung.
	Moät vöông quoác noï, nhaø vua coù N cung ñieän ñaùnh soá laø 1,2,...,N, giaønh cho K Cung Phi kyù hieäu laø 1,2,...,K. Moãi Cung Phi ôû rieâng moät cung ñieän . Moät hoâm nhaø vua muoán tìm caùc ñi thaêm moät soá Cung Phi. Bieát raèng giöõa caùc cung ñieän vôùi nhau coù theå coù hoaëc khoâng coù ñöôøng ñi qua laïi (hai chieàu) vôùi nhau.
Yeâu caàu :
a. Haõy giuùp cho nhaø Vua caùch baét ñaàu töø Cung ñieän No ñi thaêm caøng nhieàu caøng toát caùc Cung Phi maø khoâng phaûi qua Cung ñieän khoâng ngöôøi vaø moãi nôi chæ thaêm moät laàn.
b. Haõy giuùp nhaø Vua töø cung ñieän No ñi thaêm caøng nhieàu caøng toát caùc Cung Phi roài sau ñoù trôû veà nôi xuaát phaùt maø khoâng phaûi ñeán cung khoâng ngöôøi vaø moãi nôi chæ ñeán moät laàn.
Döõ lieäu Nhaäp: Cho trong File Text teân laø CUNGDIEN.INP nhö sau :
+ Doøng ñaàu tieân laø boán soá : N,K,E,No. (E laø soá ñöôøng ñi tröïc tieáp giöõa hai Cung ñieän).
+ doøng thöù hai, chöù K soá n1,n2, . . . .,nk , soá thöù j moâ taû Cung Phi j ôû cung ñieän nj
+ E doøng tieáp theo, moåi doøng thöù j laø hai soá uj, vj moâ taû ñöôøng ñi tröïc tieáp thöù j noái giöõa hai cung ñieän uj vaø vj.
Keát Quûa: Ra Maøn hình nhö sau :Goàm 4 doøng:
Trong hai doøng ñaàu laø keát quaû caâu a. Doøng thöù nhaát laø toång soá Cung Phi ñöôïc thaêm, Doøng thöù hai laàn löôït laø chæ soá cuûa caùc Cung phi theo thöù töï ñöôïc thaêm baét ñaàu töø Cung phi ôû Cung ñieän No neáu coù.
Trong Hai doøng sau : Doøng ñaàu laø Toång soá Cung ñieän ñaõ ñi qua keå caû Cung ñieän No.
Doøng tieáp theo laø caùc chæ soá cung ñieän laàn löôït ñöôïc nhaø vua ñi qua baét ñaàu töø Cung ñieän No vaø keát thuùc laø No.
Ví duï :
CUNGDIEN.INP
Maøn Hình
7 7 8 5
7
2 6 4 5 1 7 3
4 3 5 7 1 6 2
1 3
7
7 6
5 4 1 3 2 7 6 5
3 2
7 2
4 5
1 4
5 6
2 5
Baøi 14. Maïng maùy tính cuïc boä.
	Xeùt moät maïng maùy tính cuïc boä coù N maùy tính (ñöôïc ñaùnh soá 1,2, . . .,N) (0<N<101) bao goàm 1 maùy chuû heä thoáng vaø caùc maùy laøm vieäc. Maùy chuû heä thoáng goïi laø maùy ôû möùc 0 (vaø ñöôïc ñaùnh soá 1). Caùc maùy ñöôïc noái vôùi maùy chuû ñöôïc goïi laø maùy ôû möùc 1. Caùc maùy ñöôïc noái vôùi maùy ôû möùc 1 ñöôïc goïi laø maùy ôû möùc 2. ......... Moãi maùy ôû möùc i (tröø maùy chuû heä thoáng ôû möùc 0) ñöôïc noái vôùi ñuùng moät maùy ôû möùc i-1 (i=1, 2, .....) goïi laø maùy chuû tröïc tieáp cuûa maùy ôû möùc i. Khoâng coù hai maùy naøo ôû cuøng möùc ñöôïc noái vôùi nhau, ñoàng thôøi töø maùy chuû heä thoáng coù theå truyeàn tin tôùi baát kì maùy laøm vieäc naøo trong maïng (hoaëc laø tröïc tieáp hoaëc laø thoâng qua moät soá maùy trong maïng).
	Thoâng tin ñöôïc truyeàn töø maùy chuû heä thoáng ñeán caùc maùy laøm vieäc theo qui taéc sau: Khi nhaän ñöôïc thoâng tin töø maùy ôû möùc nhoû hôn chuyeån ñeán, moãi maùy (tröø caùc maùy khoâng coù maùy con) phaûi ghi laïi thoâng tin vôùi thôøi gian g, sau ñoù laàn löôït truyeàn thoâng tin nhaän ñöôïc cho caùc maùy con cuûa noù. Thôøi gian truyeàn thoâng tin töø moät maùy naøy cho ñeán maùy con cuûa noù laø t.
Yeâu caàu:
1. Haõy xaùc ñònh xem heä thoáng boàm bao nhieâu möùc vaø moãi möùc goàm nhöõng maùy naøo.
2. Ñoái vôùi moãi maùy haõy xaùc ñònh maùy naøo trong maïng laø maùy con cuûa noù.
3. Neáu taïi thôøi ñieåm 0 maùy chuû heä thoáng caàn truyeàn thoâng tin xuoáng taát caû caùc maùy con cuûa noù trong maïng, haõy xaùc ñònh trình töï truyeàn tin giöõa caùc maùy trong maïng sao cho vieäc truyeàn tin ñöôïc hoaøn thaønh sôùm nhaát.
Döõ lieäu vaøo : File vaên baûn MMT.INP
+Doøng ñaàu tieân laø 3 soá N,g,t vieát caùch nhau ít nhaát moät kyù töï traéng.
+ Doøng thöù hai ghi N soá nguyeân, soá ñaàu tieân laø soá 0, soá nguyeân thöù j cho bieát chæ soá cuûa maùy chuû tröïc tieáp cuûa maùy j (caùc soá caùch nhau ít nhaát moät kyù töï traéng).
Keát quûa: Ra File vaên baûn MMT.OUT
+Doøng ñaàu ghi soá möùc cuûa heä thoáng.
+Doøng thöù hai goàm N soá ghi caùch nhau bôûi daáu caùch, soá nguyeân thöù i ghi chæ soá möùc cuûa maùy i (i=1,2,....,N).
+ Moãi doøng thöù j (j=1,2,...,N) trong N doøng tieáp theo ghi chæ soá cuûa caùc maùy con cuûa maùy j (qui öôùc 0 neáu maùy j khoâng coù maùy con)
+ Moãi doøng thöù k (k=1,2,....,N) trong soá N doøng tieáp theo ghi chæ soá cuûa caùc maùy con cuûa maùy k theo trình töï truyeàn tin töø maùy k ñeán chuùng (qui öôùc ghi soá 0 neáu maùy k khoâng coù maùy con)
+Doøng cuoái cuøng ghi thôøi ñieåm sôùm nhaát tìm ñöôïc.
Baøi 15. Laùt Gaïch.
	Cho löôùi NxN oâ vuoâng coù ñoä daøi caïnh baèng moät ñôn vò (N<11). Ngöôøi ta phuû löôùi naøy baèng NxN hình vuoâng coù ñoä daøi caïnh baèng 1 ñôn vò thuoäc moät trong boán daïng (ñaùnh soá töø 1 ñeán 4) moâ taû trong hình 1. Moät caùch phuû ñöôïc goïi laø ñuùng ñaén neáu nhö khoâng coù 2 tam giaùc cuøng maøu naøo laïi coù chung caïnh.
Hình 1
4
3
2
1
Ví duï : Hình 2 laø moät caùch phuû ñuùng ñaén. Hình 3 laø caùch phuû khoâng ñuùng ñaén.
Hình 3
Hình 2
Yeâu caàu: Cho tröôùc moät caùch phuû, caàn kieåm tra xem noù laø ñuùnh ñaén hay khoâng. Trong tröôøng hôïp caâu traû lôøi laø khoâng, haõy tìm caùch ñoåi laïi caùch phuû cuûa moät soá ít nhaát oâ ñeå noù bieán thaønh moät caùch phuû ñuùng ñaén.
	Trong ví duï treân ta caàn ñoåi laïi caùch phuû cuûa oâ (1,2) ñeå thu ñöôïc caùch phuû hoaøn haûo.
Döõ lieäu Vaøo: Trong file vaên baûn teân LATGACH.INP, trong ñoù :
+Doøng ñaàu tieân ghi soá nguyeân döông N.
+Doøng thöù i trong N doøng