holiday Örnek

InternationalOlympiadinInformatics2014
13-20thJuly2014
Taipei,Taiwan
holiday
Day-2tasks
Language:tr-TR
Tatil
Jian-JiabirsonrakitatiliniTayvan'dageçirmekiçinplanyapmaktadır.Tatilisüresince,Jian-Jiaşehirler
arasındagezerekşehirlerdekieğlenceyerlerinigörmektedir.
Tayvan'datekbiryolüzerindebulunantoplam taneşehirvardır.Şehirlerardışıkolarak0ile
arasındanumaralandırılmıştır.Şehir için,
olmaküzere,komşuşehirler
ve
'dir.Şehir0'akomşuolantekşehir,Şehir1'dir.Şehir
'ekomşuolantekşehirde,Şehir
'dir.
Herbirşehirdebelirlisayıdaeğlenceyerleribulunmaktadır.Jian-Jia'nıntatili günlüktürveotatilinde
mümkünolanenfazlasayıdaeğlenceyerigörmekistemektedir.Jian-Jiatatilinebaşlayacağışehri
öncedenseçmiştir.Tatilininherbirgününde,Jian-Jia,yakomşubirşehregeçmektedir,yadabulunduğu
şehrintümeğlenceyerlerinigörmektedir,fakatherikisinibirdendeğil.Jian-Jiaaynışehirdenbirden
fazlageçsebile,oşehrineğlenceyerlerinihiçbirzamanikikezgörmeyecektir.Jian-Jia'nın
tatilindemümkünolduğuncaçoksayıdafarklıeğlenceyerlerinigörmesiiçinlütfenyardımediniz.
Örnek
Jian-Jia'nıntatili7günlükolsunveaşağıdakitablodaverildiğigibi5taneşehirbulunsun.Tatileşehir
2'denbaşlasın.İlkgünde,Jian-Jia,şehir2'deki20eğlenceyerinigörür.İkincigünde,şehir2'denşehir
3'egeçerveüçüncügündeşehir3'deki30eğlenceyerinigörür.Sonraki3günde,Jian-Jiaşehir3'den
şehir0'agiderveyedincigündeşehir0'daki10eğlenceyerinigörür.BuşekildeJian-Jia'nıngördüğü
eğlenceyerlerisayısı20+30+10=60olurkibusayıJian-Jia'nıntatilineşehir2'denbaşlamasıhalinde
7gündegörebileceğimaksimumeğlenceyerisayısıdır.
şehir
0
1
2
3
4
gün
1
2
3
4
5
6
7
eğlenceyerisayısı
10
2
20
30
1
faaliyet
şehir2'dekieğlenceyerlerinigör
şehir2'denşehir3'egit
şehir3'dekieğlenceyerlerinigör
şehir3'denşehir2'yegit
şehir2'denşehir1'egit
şehir1'denşehir0'agit
şehir0'dakieğlenceyerlerinigör
1/3
Görev
Jian-Jia'nıngörebileceğimaksimumeğlenceyerisayısınıhesaplayanfindMaxAttraction
fonksiyonunuyazınız.
findMaxAttraction(n,start,d,attraction)
n:şehirsayısı.
start:başlangıçşehrininnumarası.
d:Günsayısı
attraction: uzunluğundadizi;attraction[i]şehir 'dekieğlenceyerisayısıdır,
olmaküzere.
FonksiyonJian-Jia'nıngörebileceğimaksimumeğlenceyerisayısınıdöndürmelidir.
Altgörevler
Tümaltgörevlerde
veherbirşehirdekieğlenceyerisayısınegatifdeğildir.
Ekkısıtlar:
altgörev puan
şehirdekimaksimumeğlenceyerisayısı başlangıçşehri
1
2
3
4
1,000,000,000
100
1,000,000,000
1,000,000,000
7
23
17
53
kısıtyok
şehir0
kısıtyok
kısıtyok
Gerçekleştirimdetayları
İsmiholiday.c,holiday.cppveyaholiday.pasolantekbirdosyagöndermelisiniz.Budosya
yukarıdatanımlananveaşağıdaformatıverilenaltprogramıiçermelidir.C/C++programıiçin
holiday.hheaderdosyasınıdaeklemelisiniz.
Sonucunbüyükolabileceğinedikkatedin,vefindMaxAttractionfonksiyonunundönendeğerinintipi
64-bittamsayıdır.
C/C++program
longlongintfindMaxAttraction(intn,intstart,intd,
intattraction[]);
Pascalprogram
functionfindMaxAttraction(n,start,d:longint;
attraction:arrayoflongint):int64;
2/3
Örnekgrader
Örnekgradergirdiyiaşağıdakiformattaokur:
satır1:n,start,d.
satır2:attraction[0],...,attraction[n-1].
ÖrnekdeğerlendiricifindMaxAttraction'ındönendeğeriniyazacaktır.
3/3