Lucka 9

Lösning presenteras imorgon kl 08:00

Tumult har uppstått bland tomtenissarna. Nissen Fräkniga Fatima har tröttnat på sina grannar och hon har bestämt sig för att flytta. Att flytta tillhör inte vanligheterna bland nissarna, men när dom väl flyttar, så väljer dom alltid att byta boende med varandra.

Nissarna bor på en gata uppe på nordpolen. Det är en mycket, mycket, mycket lång gata, eftersom nissarna är så pass många i tomteverkstaden. Och tur är väl det! Annars skulle det bli svårt för tomten att hinna fixa alla julklappar för jul.

Tomtenissarna är ett väldigt givmilt folk, och gillar att dela med sina närmsta grannar. Fräkniga Fatimas favorit under jul är pepparkakor. Hon tänker att om hon flyttar in mellan två grannar som har väldigt många pepparkakor så är chansen stor att hon blir bjuden på en!

Fräkniga Fatima har gått längs hela gatan och frågat alla nissarna hur många pepparkakor de har hemma, för att kunna välja vem hon ska byta boende med (alltså var hon ska flytta in). Hon har sedan sammanställt en lista, där antalet pepparkakor i varje hus är i ordning efter gatunummer (som går från 0 till 499).

Nu ska vi hjälpa Fräkniga Fatima att hitta det optimala boendet, där hon har störst chans att få bli bjuden på pepparkakor!

Om listan skulle se ut enligt följande:
12, 27, 52, 1, 92
…så skulle det innebära att på gatunummer 0 så finns det 12 pepparkakor, på gatunummer 1 så finns det 27 pepparkakor, och på gatunummer 2 så finns det 52 pepparkakor, osv. Den optimala platsen att flytta in på i detta fall skulle vara på gatunummer 3 eftersom det där finns chans att bli bjuden på 52+92 pepparkakor. Eftersom den nisse som bor i huset nu tar med sin pepparkaka när Fräkniga Fatima flyttar in i så är det endast själva grannarna som Fräkniga Fatima bryr sig om.

Grannarna delar endast med sina närmsta grannar. En granne på gatunummer 100 delar bara med sina grannar på gatunummer 99 och 101.

Vilket gatunummer ska Fräkniga Fatima flytta in på för att ha chans att bli bjuden på så många pepparkakor som möjligt? Hon bor i dagsläget på gatunummer 2.

Du kan ladda ner listan på antal pepparkakor i varje hus en färdig lista i Python, eller som en txt-fil:
Som lista i Python
Som txt-fil

Unga Programmerare håller kurser i programmering för barn och ungdomar. Unga Programmerare startades av studenter från Chalmers Tekniska Högskola.

Följ oss

Nyhetsbrev