Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Краљица Дидо, такође позната и као Елиза, је у страху од свог немилосрдног брата, Пигмалиона, побегла у северозападну Африку. Ту је одлучила да оснује своје краљевство, древни град Картагу. То ће урадити тако што ће оградити неки део земље и унутар њега основати краљевство.
Северозападна Африка се може представити као део координатне равни изнад \(x\)-осе. Дидо је већ изградила део ограде од тачке \((0,0)\) до \((W,0)\) и тренутно се налази у тачки \((0,0)\). Како има ограничено много материјала за ограду, остатак ограде не сме бити дужи од \(L\) јединица дужине. У једном потезу, Дидо може да изгради сегмент ограде од тренутне тачке до неке друге тачке тако да се \(x\) и \(y\) координате промене за највише \(1\) (за шта постоји 8 могућности). Дидо хоће да се нови део ограде заврши у тачки \((W,0)\) како не би било делова ограде који су бескорисни. Због тога што Дидо хоће да оснује моћно краљевство, површина ограђена оградом треба да буде што већа. Ограда (рачунајући и нов и већ изграђени део) не сме да има самопресецања.
Помозите Дидо и реците јој двоструку највећу површину које њено краљевство може да има.
Потребно је да имплементирате функцију
где је \(W\) \(x\)-координатa другог краја ограде, а \(L\) максимална дужина новог дела ограде. Функција треба да врати двоструку највећу површину краљевства.
Нека је \(W=1\) и \(L=6\),
Тада је највећа могућа површина \(3\) (функција треба да врати двоструку највећу површину тј. \(6\)), и један начин да се добије та површина је следећи:
\((0,0) \rightarrow (-1,1) \rightarrow (0,2) \rightarrow (1,2) \rightarrow (1,1) \rightarrow (1,0)\)
Укупна дужина ограде је \(5.8284271247\dots\)
Тест примери су подељени у \(5\) подзадатка: - [21 поена]: \(W, L \leq 5\) - [16 поена]: \(W, L \leq 10\) - [18 поена]: \(W, L \leq 40\) - [22 поена]: \(W, L \leq 70\) - [23 поена]: Нема додатних ограничења
Потребно је да пошаљете тачно један фајл dido.cpp који
имплементира поменуту функцију. Осим тражене функције, ваш фајл може
садржати и додатне глобалне променљиве, помоћне функције и додатне
библиотеке.
Ваша функција мора бити следећег облика:
int Dido(int W,int L);
Вашим програмима је дозвољено да мењају садржај низова/матрица, али не смеју да приступају ван граница датих низова.
Уз задатак, обезбеђен вам је “template” фајл code.cpp
које можете користити и мењати по потреби. Такође вам је обезбеђен
програм grader.cpp који служи да лакше тестирате кодове.
Овај програм учитава са стандардног улаза следеће податке:
Затим овај програм зове вашу функцију и штампа број који врати функција.