InternationalOlympiadinInformatics2014
13-20thJuly2014
Taipei,Taiwan
wall
Day-1tasks
Language:tk-TM
Wall(Diwar)
Jian-Jiameňzeşululykdakykerpiçleriüst-üstünegoýupdiwarýasaýar.Budiwarnsanykerpiç
sütündenybaratbolup,busütünlerçepdensaga0bilenn-1aralygyndabelgilenen.Sütünleriň
uzynlyklarybir-birindentapawutlybolupbilýär.Sütüniňuzynlygyonydüzýänkerpiçleriňsanydyr.
Jian-Jiadiwaryşuşekildedüzýär:Başdahiçbirsütündekerpiçýok.Soň,Jian-Jiaksanytapgyrdan
geçýär(kerpiçlerigoşmakýa-daaýyrmaktapgyry).Binanyňgurluşyhemmeksanytapgyrdan
geçilendensoňtamamlanýar.HertapgyrdaJian-Jianayzygiderlikerpiçsütünleriňaralygywebeýiklik
(h)beriler,weolşuproseduranyýerineýetirýär:
Goşmatapgyrynda,Jian-Jiaberilenaralykdakysütünlereh-denazkerpiçbarbolsa,huzynlygyna
deňbolýançakerpiçgoşýar.Egersütündehýa-dah-denköpkerpiçbolsahiçzatedenok.
Aýyrmatapgyrynda,Jian-Jiaberilenaralykdakysütünlerdeh-denköpkerpiçbolsa,uzunlykh
bolmasyüçinkerpiçaýyrýar.Kerpiçsanyhbolanýa-dah-denazbolansütünlerüçinhiçzat
edenok.
Siziňişiňizdiwaryňiňsoňundakyşekilinikesgitlemek.
Mysal
10kerpiçsütüniňwe6diwartapgyrynyňbardygynykabuledeliň.Aşakdakytablisadakyhemme
aralyklarhasabaalynýar.Herbirtapgyryňsoňundakydiwardiagrammalaryaşakdagörkezilen.
tapgyr
0
1
2
3
4
5
görüniş
goşmak
aýyrmak
aýyrmamk
goşmak
goşmak
aýyrmak
aralyk
1-8sütünaralygy
4-9sütünaralygy
3-6sütünaralygy
0-5sütünaralygy
2-njisütün
6-7sütünaralygy
beýiklik
4
1
5
3
5
0
Başdabütünsütünleremboşbolandygyüçin,0-njytapgyrdansoň1-8aralygyndakyherbirsütünde4
kerpiçbolar.0-njywe9-njysütünboşgalar.Birinjitapgyrda,4-8aralygyndakysütünlerdenbeýiklikleri
1bolýançakerpiçaýyrylar,we9-njysütünboşgalar.0-3aralygyndakysütünlerberilenaralygyň
daşyndabolanlygysebäpliüýtgemezler.ikinjitapgyrdahiçbirüýtgemebolmaz,sebäbi3-6aralygyndaky
sütünleriňhiçbirinde5-denköpkerpiçýok.Üçünjitapgyrdansoň0,4we5belgilisütünleriňbeýiklikleri
3bolar.Dördünjitapgyryňnetijesinde2-njisütüniňbeýikligi5bolar.Bäşinjitapgyr6-njywe7-njy
sütünleriňhemmekerpiçleriniaýyrar.
1/3
Ýumuş
berilenktapgyrlaryulanyp,herbirsütündäkikerpiçleriňsanynyhasaplaň(hemmetapgyrlargutarandan
soň).SizbuildWallfunksiýasynyýazmaly.(BuildWall,diwargurmakdiýmek.)
buildWall(n,k,op,left,right,height,finalHeight)
n:diwardakysütünleriňsany.
k:tapgyrlaryňsany.
op:kuzynlygandakymassiw;0<=i<=k-1üçinop[i]i-njitapgyryňgörnüşidir:goşmak
tapgyryüçin1weaýyrmaktapgyryüçin2.
left(çep)weright(sag):kuzynlygyndakymassiwler;0<=i<=k-1üçin,i-njitapgyrdaky
sütünaralygyleft[i]bilenbaşlaýarweright[i]bilengutarýar(left[i]we
right[i]aralygyňiçinealynýar).
height(beýiklik):kuzynlygyndakymassiw;0<=i<=k-1üçin,height[i]i-njitapgyrüçin
uzynlykparametiridir.
finalHeight(iňsoňkybeýiklik):nuzynlygyndakymassiw;0<=i<=k-1üçin,netijeleriňi,
ýagnyi-njisütündäkikerpiçleriňsanynyfinalHeight[i]-agoýupgaýtarmaly(return).
Subtask(ýumuşjyk)
Hemmeýumuşjyklarüçinbütintapgyrlaryňbeýiklikparametrleriotrisatelbolmadyk100,000-edeň
bolanýa-dakiçibolanbitinsanlardyr.
2/3
subtask ballar
subtask ballar
1
8
n
n
k
k
bellik
bellik
goşmaçaçäklendirmeýok
2
24
3
29
bütingoşmaktapgyrlarybütin
aýyrmaktapgyrlaryndanöň
goşmaçaçäklendirmeýok
4
39
goşmaçaçäklendirmeýok
Ýerineýetirmeaýratynlyklary
Diňewall.c,wall.cppýa-dawall.pasatlyýekejefaýlugradypbilýäňiz.Bufaýlýokardaky
programmajyklaryaşakdagörkezilişiýalyişlemeli.AýratynamsizC/C++programmalryüçinwall.h
headerinigoşmaly.
C/C++program
voidbuildWall(intn,intk,intop[],intleft[],intright[],
intheight[],intfinalHeight[]);
Pascalprogram
procedurebuildWall(n,k:longint;op,left,right,height:
arrayoflongint;varfinalHeight:arrayoflongint);
Mysalybahalandyrma
Grader(bahalandyryjy)girişiaşakdakyformatdaokaýar:
1-njisetir:n,k.
setir
(
):op[i],left[i],right[i],height[i].
3/3
Download

Wall (Diwar) - IOI 2014 in Taiwan