Demiryolu - International Olympiad in Informatics

InternationalOlympiadinInformatics2014
13-20thJuly2014
Taipei,Taiwan
Day-1tasks
rail
Language:tr-TR
Demiryolu
Tayvan'daadanınbatıvedoğukıyılarınıbirbirinebağlayanuzunbirdemiryoluhattıvardır.Budemiryolu
hattı bloktanmeydanagelmektedir.Ardışıkbloklarbatıkıyısındandoğukıyısına 'dan
'e
numaralandırılmıştır.Herbirblokta,kuzeydedoğudanbatıyadoğrubirtekyönlühatvegüneydede
batıdandoğuyadoğrubirtekyönlühatbulunmaktadır.Bazıbloklardakuzeyvegüneyhatlarıarasında
tercihenbirtrenistasyonubulunabilir.
Üçtipblokvardır.Ctipindekibloklardasadecekuzeydengirilipgüneydençıkılabilenbiristasyon
bulunmaktadır.Dtipindekibloklardadasadecegüneydengirilipkuzeydençıkılabilenbiristasyon
bulunmaktadır.Boştipindekibloklardahiçistasyonbulunmamaktadır.Örnekvermekgerekirse,
aşağıdakişekilde0,4ve6.bloklarıntipiboş,1,2ve3.bloklarıntipiCveblok5'intipiD'dir.Bloklar
birbirlerinebağlantılarlabağlanmışlardır.Aşağıdakişekildebağlantılargridikdörtgenlerlegösterilmiştir.
Demiryolusisteminde 'dan
'ekadarnumaralandırılmış taneistasyonvardır.Herhangibir
istasyondanbaşkabiristasyonaraylarıtakipederekgitmeninmümkünolduğunuvarsayınız.
Örnekvermekgerekirse,istasyon0'danistasyon2'ye,2.bloktanbaşlayıpgüneydekiraylarla3.ve4.
bloklarıgeçipsonra1.istasyonüzerinden5.bloktangeçtiktensonra4.bloktangeçip,sonolarak3.
bloktaki2.istasyonagelerekulaşmakmümkündür.
İkiistasyonubağlayanbirdenfazlarotaolabileceğinden,biristasyondanbaşkabiristasyonaolan
mesafeenazbağlantıiçerenrotadakibağlantısayısıolaraktanımlanmıştır.Örnekolarak,0.
istasyondan2.istasyonaolanenkısarota2-3-4-5-4-3bloklarından5bağlantıkullanılarakoluştuğuiçin
mesafe5'tir.
Demiryolusisteminibirbilgisayarsistemiidareetmektedir.Neyazıkkibirelektrikkesintisisonucu,
bilgisayarartıkistasyonlarınneredeolduklarınıvebulunduklarıbloktipibilgilerinikaybetmiştir.
Bilgisayarıntekbildiği,0.istasyonunkaçıncıbloktaolduğuveobloğunherzamanCtipindeolduğudur.
Bilgisayarayrıcabiristasyondanbaşkabiristasyonaolanmesafeyisorgulayabilir.Örnekolarak,'0.
istasyondan2.istasyonaolanmesafenedir?'sorgusunuyapabilirvecevapolarak5'ibulabilir.
Görev
findLocationadında,herhangibiristasyonunkaçıncıbloktaolduğunuvebulunduğubloğuntipini
bulanbirfonksiyonyazmanızgerekmektedir.
1/3
findLocation(n,first,location,stype)
n:istasyonlarınsayısı.
first:0.istasyonunbulunduğubloknumarası.
location: uzunluğundabirdizi; .istasyonunbloknumarasınılocation[i]'ye
yazmalısınız.
stype: uzunluğundabirdizi; .istasyonunbloktipinistype[i]'yeyazmalısınız:Ctipi
için1veDtipiiçin2yazmalısınız.
İstasyonlarınyerlerinivetiplerinibulmadayardımcıolmakiçingetDistanceadlıfonksiyonu
çağırabilirsiniz.
getDistance(i,j)i.istasyondanj.istasyonaolanmesafeyidöner.getDistance(i,i)
0döner.getDistance(i,j)eğeriyadaj
sınırlarıiçindedeğilse-1
döner.
Altgörevler
Bütünaltgörevlerdebloksayısı 1,000,000'aeşityadadahaküçüktür.Bazıaltgörevlerde
getDistancefonksiyonunuçağırmasayısısınırlandırılmıştır.Sınıraltgörevdenaltgörevedeğişebilir.
Programınızfonksiyonçağırmasınırınıaşarsa'yanlışcevap'olarakdeğerlendirilecektir.
altgörev puan
getDistance
sayısı
1
8
sınırsız
2
22
sınırsız
3
26
ekbirsınıryoktur
4
44
ekbirsınıryoktur
not
istasyon0dışındakibütünistasyonlarD
tipindedir.
0.istasyonundoğusundakibütünistasyonlarD
tipibloklardadırve0.istasyonunbatısındaki
bütünistasyonlarCtipibloklardadır.
Gerçekleştirimdetayları
İsmirail.c,rail.cppyadarail.pasolanbirdosyagöndermelisiniz.BudosyafindLocation
fonksiyonunuaşağıdaverilenyapıdagerçekleştirir.C/C++programıiçinrail.hheaderdosyasını
eklemelisiniz.
C/C++programları
voidfindLocation(intn,intfirst,intlocation[],intstype[]);
Pascalprogramları
procedurefindLocation(n,first:longint;varlocation,
2/3
stype:arrayoflongint);
getDistancefonksiyonununyapısıaşağıdakigibidir.
C/C++programları
intgetDistance(inti,intj);
Pascalprogramları
functiongetDistance(i,j:longint):longint;
Örnekgrader
Örnekgradergirdi'yiaşağıdakiformattaokur:
satır1:altgörevnumarası
satır2:n
satır
,(
):stype[i](Ctipiiçin1veDtipiiçin2),location[i].
Örnekgrader,findLocationfonksiyonudöndüğündeeğerprogramınıztarafındanhesaplanan
location[0]..location[n-1]vestype[0]...stype[n-1]dizilerigirdiyleeşleşirseCorrect
yazar,eğereşleşmezseIncorrectyazar.
3/3