Az I. 666. feladat (2025. május)

I. 666. Egy digitális óceánon egyenes vonalban helyezkedik el a Bitek-sziget­csoport. A szigetek kiterjedése a közöttük lévő távolságokhoz képest elhanyagolható. Ha két szomszédos sziget legföljebb \(\displaystyle H\) távolságra van egymástól, akkor közöttük hajóval lehet közlekedni, de az ennél nagyobb távolságra lévő szomszédos szigetek között csak repülővel lehet megtenni az utat. Fontos, hogy a szigetcsoport bármelyik szigetéről bármelyik másik szigetére el lehessen jutni a fenti közlekedési eszközök alkalmazásával. A szigetek közötti hajó- és repülőjáratok oda-vissza közlekednek, a repülők a szigetcsoport két legtávolabbi szigete közötti utat is képesek megtenni.

A repülőjáratok üzemeltetése meglehetősen költséges és nem környezetbarát – még akkor is, ha a repülőgépek két szomszédos sziget között közlekednek –, ezért a szigetcsoport közlekedési minisztere azon töpreng, hogyan csökkentse a repülőjáratok számát. Kérdés, hogy legalább hány repülőjáratnak kell közlekednie, hogy bármelyik szigetről bármely szigetre el lehessen jutni.

Készítsünk programot i666 néven, amely megadja a választ a miniszter kérdése, tehát kiszámolja a szigetek összeköttetéséhez szükséges legkevesebb repülőjárat számát.

A program standard bemenetének első sorában a szigetek \(\displaystyle N\) száma (\(\displaystyle 10\leq N\leq 500\)), majd a hajóval megtehető legnagyobb \(\displaystyle H\) távolság (\(\displaystyle 1\leq H\leq 10\)) szerepel. A következő sorban \(\displaystyle N-1\) pozitív egész szám áll: a szigetek távolsága a Bitek-szigetcsoport bal szélső szigetétől (nem feltétlenül távolság szerinti sorrendben).

A program a standard kimenet első sorába írja ki a szükséges repülőjáratok minimális számát.

Példa:

Magyarázat: A szélső szigettől a 10 és 14 távolságra lévő, a 20 és 26 távolságra lévő, valamint a 28 és 33 távolságra lévő szigetek között szükséges repülőjáratokat fenntartani.

Beküldendő egy tömörített i666.zip állományban a program forráskódja és rövid dokumentációja, amely megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2025. június 16-án LEJÁRT.

Mintamegoldások:

Rajtik Sándor Python nyelvű programja: i666.py

Ali Vilmos C++ nyelvű munkája: i666.cpp

a Felhő csapat C# nyelvű megoldása: i666.cs

Statisztika:

14 dolgozat érkezett.
10 pontot kapott:	Ali Vilmos, Fajszi Karsa, Gyönki Dominik, Nagy 292 Korina, Rajtik Sándor Barnabás, Szabó Imre Bence, Szekeres Linda, Tóth Marcell Domonkos.
9 pontot kapott:	Kelemen András.
8 pontot kapott:	1 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	1 dolgozat.

A KöMaL 2025. májusi informatika feladatai