InternationalOlympiadinInformatics2014
13-20thJuly2014
Taipei,Taiwan
gondola
Day-2tasks
Language:tr-TR
Kayık
Mao-KongKayıklarıTaipei'deünlübireğlenceyeridir.Kayıksistemi,daireselbirraydanveburay
üzerindesabitbiryönde1'den 'ekadarnumaralandırılmış tanekayıktanoluşmaktadır. .kayık
istasyonugeçtiktensonraeğer
iseistasyonugeçenbirsonrakikayık
.kayıkoluryada
eğer
ise1.kayıkolur.
Kayıklarbazenbozulabilir.Neysekielimizde
,
,vedevamışeklindenumaralandırılmış
sonsuzsayıdayedekkayıkbulunmaktadır.Birkayıkbozulduğunda,bozukkayıkçıkarılarakbozuk
kayığınraydabulunduğuyeresıradakiilkuygunyedekkayık(yanienküçüknumaralıkullanılmamış
yedekkayık)yerleştirilir.Örnekolarak,eğerbeşkayıkvarsave1.kayıkbozulursa,1.kayığı6.kayık
iledeğiştiririz.
İstasyondaoturup,geçenkayıklarıseyretmeksevdiğinizaktivitelerdenbirisidir.Birkayıkdizisi
istasyondangeçen adetkayığınnumaralarınındizisidir.Sizkayıklarıizlemeyebaşlamadanöncebazı
kayıklarbozulmuşvedeğiştirilmişolabilir,amasizizlemeyebaşladıktansonrahiçbirkayıkbozulmaz.
Buarada,aynıkayıkkonfigürasyonunun,sizizlemeyebaşladığınızdaistasyondanilkgeçenkayığabağlı
olarak,birdenfazlakayıkdizisioluşturabileceğinedikkatedin.Örnekolarak,eğerhiçbirkayık
bozulmamışsahem(2,3,4,5,1)hemde(4,5,1,2,3)olasıkayıkdizileriolabilirler,fakat(4,3,2,5,1)
olasıbirkayıkdizisideğildir(çünkübudizidekayıklaryanlışsıradadır).
Eğer1.kayıkbozulursa,(4,5,6,2,3)kayıkdizisinigözlemleyebiliriz.Sonra4.kayıkbozulursa,onu7.
kayıkiledeğiştiririzve(6,2,3,7,5)kayıkdizisinigözlemleyebiliriz.Hemensonrasında7.kayık
bozulursa,onu8.kayıkiledeğiştiririzve(3,8,5,6,2)kayıkdizisinigözlemleyebiliriz.
bozukkayık
1
4
7
yenikayık
6
7
8
olasıkayıkdizisi
(4,5,6,2,3)
(6,2,3,7,5)
(3,8,5,6,2)
Birbozulmadizisi,bozulduklarısıraile,bozulankayıklarınnumaralarınınserisidir.Biröncekiörnekte
bozulmadizisi(1,4,7)'dir.Bir bozulmadizisi,eğerkayıklar 'debelirtilensıradabozulduğunda
gözlemlenebiliyorsa, kayıkdizisiniüretir.
KayıkDizisiKontrolü
İlküçaltgörevde,birgirdidizisininbirkayıkdizisiolupolamayacağınıkontroledeceksiniz.Aşağıdaki
tablodakayıkdizisiolanveolmayanörnekdizilergörebilirsiniz.validadındabirfonksiyon
gerçekleştirmelisiniz.
valid(n,inputSeq)
1/4
n:girdidizisininboyu.
inputSeq: uzunluğundabirdizi;inputSeq[i]girdidizisinin .elemanıdır,
.
Girdidizisibirkayıkdizisiisefonksiyon1,değilise0dönmelidir.
1,2,3no'luAltgörevler
altgörev puanı
inputSeq
1'den 'yekadarbütündeğerlertamolarakbirkere
dizidegeçer
1
5
2
5
inputSeq[i]
3
10
inputSeq[i]
Örnekler
altgörev
1
1
1
1
2
3
3
inputSeq
(1,2,3,4,5,6,7)
(3,4,5,6,1,2)
(1,5,3,4,2,7,6)
(4,3,2,1)
(1,2,3,4,5,6,5)
(2,3,4,9,6,7,1)
(10,4,3,11,12)
dönendeğer
1
1
0
0
0
1
0
not
1,5'tenhemenöncegelemez
4,3'tenhemenöncegelemez
numarası5olanikikayıkvar
bozulmadizisi(5,8)
4,3'tenhemenöncegelemez
BozulmaDizisi
Birsonrakiüçaltgörevde,verilenbirkayıkdizisiniüretebilecekolasıbirbozulmadizisioluşturmalısınız.
Verilenkayıkdizisiniüretebilenherhangibirbozulmadizisiçözümolarakkabuledilecektir.
replacementadındabirfonksiyongerçekleştirmelisiniz.
replacement(n,gondolaSeq,replacementSeq)
nkayıkdizisininboyudur.
gondolaSeq: uzunluğundadizi;gondolaSeq'indoğrubirkayıkdizisiolduğugarantidir,
vegondolaSeq[i]dizinin .elemanıdır,
.
Fonksiyon,bozulmadizisininuzunluğunu, 'yi,dönmelidir.
replacementSeq:bozulmadizisinintamamınıyerleştirebilecekbüyüklüktebirdizi;
bulduğunuzbozulmadizisinin .elemanıreplacementSeq[i]'deolacakşekilde
yerleştirmelisiniz,
.
2/4
4,5,6no'luAltgörevler
altgörev puan
gondolaSeq
4
5
gondolaSeq[i]
5
10
gondolaSeq[i]
6
20
gondolaSeq[i]
Örnekler
altgörev
4
4
5
gondolaSeq
dönendeğer replacementSeq
(3,1,4)
1
(5,1,2,3,4)
0
(2,3,4,9,6,7,1) 2
(2)
()
(5,8)
BozulmaDizileriniSayma
Birsonrakidörtaltgörevde,verilenbirdiziyi(doğrubirkayıkdizisiolabiliryadaolmayabilir)üretebilen
bütünolasıbozulmadizilerininsayısınımod1,000,000,009'dabulmalısınız.countReplacement
adındabirfonksiyongerçekleştirmelisiniz.
countReplacement(n,inputSeq)
n:girdidizisininboyu.
inputSeq: uzunluğundabirdizi;inputSeq[i]girdidizisinin .elemanıdır,
.
Eğergirdidizisibirkayıkdizisiise,bukayıkdizisiniüretebilecekbütünbozulmadizilerinin
sayısınıbulmalısınız(busayıçokçokbüyükolabilir),vebusayıyımod1,000,000,009'da
dönmelisiniz.Eğergirdidizisibirkayıkdizisideğilise,fonksiyonunuz0dönmelidir.Eğer
girdidizisibirkayıkdizisiisefakathiçbirkayıkbozulmamışise,ozamanfonksiyon1
dönmelidir.
7,8,9,10no'luAltgörevler
altgörev puan
inputSeq
7
5
8
15
9
15
inputSeq[i]
10
10
inputSeq[i]
inputSeq[i]
inputSeq[i]
,ve
enaz
tanesibozulmamıştır.
no'luilkkayıklardan
Örnekler
3/4
altgörev
inputSeq
dönendeğer
bozulmadizisi
7
8
(1,2,7,6)
2
(2,3,4,12,6,7,1) 1
(3,4,5)or(4,5,3)
(5,8,9,10,11)
9
(4,7,4,7)
0
10
(3,4)
2
inputSeqbirkayıkdizisideğildir
(1,2)or(2,1)
Gerçekleştirimdetayları
İsmigondola.c,gondola.cppyadagondola.pasolantekbirdosyagöndermelisiniz.Budosya,
yukarıdatanımlananüçfonksiyonunhepsini(altgörevlerdensadecebirkısmınıyapmışolsanızbile)
aşağıdakiformattagerçekleştirmelidir.C/C++gerçekleştirimlerigondola.hheaderdosyasınıinclude
etmelidir.
C/C++programları
intvalid(intn,intinputSeq[]);
intreplacement(intn,intgondolaSeq[],intreplacementSeq[]);
intcountReplacement(intn,intinputSeq[]);
Pascalprogramları
functionvalid(n:longint;inputSeq:arrayoflongint):integer;
functionreplacement(n:longint;gondolaSeq:arrayoflongint;
varreplacementSeq:arrayoflongint):longint;
functioncountReplacement(n:longint;inputSeq:arrayoflongint):
longint;
Örnekgrader
Örnekgradergirdiyiaşağıdakiformattaokur:
satır1:T,programınızınçözmesibeklenenaltgörevnumarası(
).
satır2:n,girdidizisininboyu.
satır3:EğerT4,5,yada6ise,busatırgondolaSeq[0],...,gondolaSeq[n-1]'iiçerir.Değil
isebusatırinputSeq[0],...,inputSeq[n-1]'iiçerir.
4/4
Download

Kayık - IOI 2014