Demiryolu - International Olympiad in Informatics
Transkript
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