đề thi hoc sinh giỏi

Së gi¸o dôc vµ ®µo t¹o §Ò thi chän häc sinh giái líp 12 THPT
TØnh ninh b×nh n¨m häc 2007 - 2008
M«n: Tin häc (Vßng 1)
Thêi gian lµm bµi: 180 phót (kh«ng kÓ thêi gian giao ®Ò)

§Ò thi gåm 03 bµi trong tæng sè 03 trang


Tªn bµi
Tªn file ch­¬ng tr×nh
File d÷ liÖu vµo
File kÕt qu¶

Bµi 1
DÞch cóm gia cÇm
H5N1.PAS
H5N1.INP
H5N1.OUT

Bµi 2
§ãng cöa sæ
WINDOWS.PAS
WINDOWS.INP
WINDOWS.OUT

Bµi 3
LÞch tr×nh xe buýt
ITINE.PAS
ITINE.INP
ITINE.OUT


Bµi 1 - H5N1 (8 ®iÓm):
H5N1 lµ mét lo¹i virus cóm ph¸t triÓn m¹nh trong c¸c ®µn gia cÇm (gµ, vÞt…) sau ®ã cã thÓ l©y lan sang ng­êi. Ph­¬ng ph¸p phæ biÕn hiÖn nay ®Ó ng¨n chÆn sù l©y lan cña H5N1 lµ tiªu huû gia cÇm ë n¬i cã ¶nh h­ëng cña dÞch vµ ®Ó ng¨n chÆn nguy c¬ t¸i ph¸t dÞch. Mét trong nh÷ng nguyªn t¾c tiªu huû gia cÇm lµ ph¶i tiªu huû toµn bé gia cÇm (nÕu tån t¹i, dï chØ mét con gia cÇm trong vïng th× còng coi nh­ viÖc tiªu huû lµ v« Ých).
C¶ n­íc cã N ®Þa ph­¬ng, c¸c ®Þa ph­¬ng ®­îc ®¸nh sè thø tù lÇn l­ît: 1, 2, 3,…N. Ban chØ ®¹o phßng chèng dÞch Trung ­¬ng ®· tÝnh to¸n ®­îc chi phÝ cÇn thiÕt cho viÖc dËp dÞch t¹i ®Þa ph­¬ng thø i lµ Ti.
Víi mét sè tiÒn K ®­îc nhµ n­íc cung cÊp, h·y chØ ra mét ph­¬ng ¸n gióp Ban chØ ®¹o phßng chèng dÞch Trung ­¬ng ph©n bæ sè tiÒn nµy cho c¸c ®Þa ph­¬ng cÇn dËp dÞch theo tÝnh to¸n trªn sao cho sè ®Þa ph­¬ng ®­îc nhËn tiÒn ®ñ ®Ó dËp dÞch lµ nhiÒu nhÊt.
D÷ liÖu vµo: File v¨n b¶n H5N1.INP:
Dßng thø nhÊt ghi sè nguyªn d­¬ng N (N ( 30000), vµ K ( K ( 2*109 ).
Trong N dßng tiÕp theo, dßng thø i ghi mét sè tù nhiªn Ti (Ti ( 50000). NÕu ®Þa ph­¬ng thø i kh«ng cÇn dËp dÞch th× Ti = 0.
D÷ liÖu ra: File v¨n b¶n H5N1.OUT:
Dßng ®Çu ghi mét sè nguyªn lµ sè ®Þa ph­¬ng nhiÒu nhÊt cã thÓ nhËn ®­îc tiÒn. NÕu kh«ng cã ®¸p ¸n ghi mét sè 0.
Dßng tiÕp theo ghi sè thø tù cña c¸c ®Þa ph­¬ng ®­îc nhËn tiÒn nÕu cã ®¸p ¸n. Hai sè c¹nh nhau ng¨n c¸ch b»ng mét ký tù c¸ch.
VÝ dô:
H5N1.INP
H5N1.OUT

4 10
8
9
1
2
2
1 3

Bµi 2 - §ãng cöa sæ (8 ®iÓm):
Trong giao diÖn ®å ho¹ cña mét hÖ ®iÒu hµnh, mµn h×nh ®­îc chia thµnh mét l­íi c¸c « vu«ng. Trªn l­íi, mét « vu«ng ®­îc ®Þnh vÞ b»ng to¹ ®é (x, y) : cét x, dßng y. Mét cöa sæ ®­îc ®Þnh nghÜa lµ mét tËp c¸c « vu«ng t¹o thµnh mét h×nh ch÷ nhËt. Cöa sæ ®­îc x¸c ®Þnh khi biÕt to¹ ®é (u, v) cña « gãc trªn bªn tr¸i vµ to¹ ®é (x, y) cña « gãc d­íi bªn ph¶i.
Cã thÓ më ®­îc nhiÒu cöa sæ trªn mµn h×nh, khi ®ã cöa sæ më sau cã thÓ sÏ che khuÊt mét phÇn cña c¸c cöa sæ më tr­íc. Ng­êi sö dông hÖ ®iÒu hµnh ®ãng mét cöa sæ b»ng c¸ch nh¸y chuét lªn « vu«ng gãc trªn bªn ph¶i cña cöa sæ, nh­ vËy mét cöa sæ chØ cã thÓ ®ãng l¹i ®­îc khi « vu«ng ë gãc trªn bªn ph¶i cña