Štepi sa rozhodol pre nový koníček a začal stavať soľné stĺpy. Cez deň sa mu ich podarilo postaviť niekoľko vedľa seba do dlhého radu. Večer sa ale začalo zmrákať a Štepi sa bojí, že keď začne pršať, tak sa soľné stĺpy rozpustia. Chcel by ich preto prikryť plachtou.
Štepi má dlhý pás plachty, ktorý chce natiahnuť cez stĺpy tak, aby plachta všetky stĺpy zakrývala. Plachta je dostatočne široká, aby pokryla celý jeden stĺp, ale bude aj dosť dlhá, aby zakryla celý rad? Štepi by chcel zistiť, akú najmenej dlhú plachtu potrebuje, aby sa mu podarilo zakryť všetky stĺpy.
Štepi pripevní plachtu o vrchy niektorých stĺpov a medzi nimi ju natiahne, aby bola rovná. Plachta sa ale nemusí dotýkať všetkých stĺpov, stačí, aby boli všetky stĺpy pod ňou. Môže to vyzerať napríklad takto:
Na obrázku je plachta pripevnená o prvý, druhý a štvrtý stĺp, a tretí stĺp zakrýva tým, že je nad ním. Pre tieto stĺpy je to dokonca najkratší kus plachty, aký ich môže zakryť. Keby Štepi plachtu pripevnil napríklad aj o tretí stĺp, potreboval by dlhší kus plachty. Keby Štepi nepripevnil plachtu o druhý stĺp, ale len o prvý a štvrtý, tak by plachta nemohla ísť ponad druhý stĺp, takže by ho nezakrývala.
Predtým, než začne Štepi plachtu vešať, chcel by vedieť, kadiaľ ju má natiahnuť, aby jej minul čo najmenej. Stĺpy majú medzi sebou pravidelné rozostupy vždy 1 meter, a majú výšky postupne 1, 9, 7, 11, 8, 10, 10, 8, 5, 6, 2 a 1 meter. Šírka stĺpov je zanedbateľná.
Zisti, o ktoré stĺpy má Štepi plachtu pripevniť, aby keď ju potom natiahne, zakryl všetky stĺpy, a aby mu stačila plachta, ktorá je čo najkratšia.
Martinovi sa zapáčilo Štepiho hobby. “Aj ja chcem stavať šťĺpy!” povedal si a entuziasticky postavil na koniec stĺp výšky 4 metre a prikryl ho šplachtou. Kde majú pripevniť plachtu teraz, aby im stačila čo najkratšia? Ako vieme využiť predošlé výpočty z podúlohy A? Ako sa plachta posunula a kde sa nemenila?
Martin so Štepim stavajú ďalšie a ďalšie stĺpy. Po postavení každého z nich potrebujú vedieť povedať, o ktoré stĺpy majú plachtu pripevniť, aby im stačila čo najkratšia. Chceli by to urobiť len pomocou výpočtov alebo kreslenia na papieri, aby nemuseli reálne chodiť von a skúšať tú plachtu vešať. Okrem toho by chceli, aby keď pridajú nový stĺp, aby toho museli čo najmenej počítať, kresliť a skúšať nanovo.
Poraď im, ako to majú robiť. Ako si majú zapisovať riešenie, aby potom, keď pridajú ďalší stĺp, toho museli čo najmenej prepisovať?
Súťaž PRASK zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre stredoškolákov
Tímová matematicko-fyzikálna súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania