Ortaokul Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 5

[5-8 soruları için açıklama]
Ortaokul öğrencileri için düzenlenen bir yaz kampında öğrencilere spor öğretmenliği yapıyorsunuz. Spor programı kapsamında her öğrenci ilk olarak havuzda 10 tur yüzecek, sonrasında 5 km bisiklet sürecek, en son olarak da 2 km koşacaktır. Her öğrenci bu aktiviteleri verilen sırayla gerçekleştirecektir. Kampın güvenlik kuralları gereği aynı anda havuzda en fazla bir öğrenci bulunabilmektedir. Ancak aynı anda bisiklet sürebilecek ya da koşabilecek öğrenci sayısına ilişkin bir kısıt bulunmamaktadır. Havuzdan çıkan bir öğrenci hemen bisiklet sürmeye başlayacak ve aynı anda bir sonraki öğrenci yüzmeye başlayacaktır. Benzer şekilde bisiklet sürmesi biten öğrenci hemen koşmaya başlayacaktır.
Spor programı ilk öğrencinin havuza girmesiyle başlayıp koşusunu en son tamamlayan öğrencinin koşusunu tamamlamasıyla bitmektedir. Kamptaki n öğrencinin yüzme süreleri, bisiklet sürme süreleri ve koşma süreleri önceden bilinmektedir. Dikkat edilirse spor programının süresi öğrencilerin hangi sırayla havuza girdiklerine göre değişmektedir.
Örnek vermek gerekirse, \(n = 3\) öğrenci için yüzme süreleri, bisiklet sürme süreleri ve Koşma süreleri aşağıda verildiği gibi olsun.
<table><tr><td></td><td>Öğrenci 1</td><td>Öğrenci 2</td><td>Öğrenci 3</td></tr><tr><td>Yüzme süresi</td><td>3</td><td>6</td><td>8</td></tr><tr><td>Bisiklet süresi</td><td>4</td><td>8</td><td>6</td></tr><tr><td>Koşma süresi</td><td>6</td><td>4</td><td>5</td></tr></table>
Bu örnekte öğrenciler havuza 3, 1, 2 sırasıyla (ilk olarak 3. öğrenci, ardından 1. öğrenci ve son olarak da 2. öğrenci) girerlerse spor programı 29 birim zaman sürer. Ancak öğrenciler havuza 2, 3, 1 sırasıyla girerlerse spor programı 27 birim zaman sürmektedir.

---

Spor programını en kısa sürede tamamlamak için havuza ilk olarak hangi öğrenci girmelidir?

Şıklar:
A) Yüzme süresi en küçük olan | B) Bisiklet süresi en büyük olan | C) Yüzme, bisiklet ve koşma süreleri toplamı ortanca olan | D) Bisiklet ve koşma süreleri toplamı en büyük olan | E) Bisiklet süresi ile yüzme süresi arasındaki fark en fazla olan

Cevap: D Bisiklet ve koşma süreleri toplamı en büyük olan

Çözüm:
Spor programının en kısa sürede tamamlanması için öğrencilerin bisiklet ve koşma sürelerinin toplamına göre büyükten küçüğe sıralanmaları gerekmektedir. Bu çözümün optimal olduğunu şu şekilde ispatlayabiliriz. Öğrencilerin bisiklet ve koşma süreleri toplamına göre büyükten küçüğe sıRALI olmadıkları herhangi bir sıralama alalım. Bu sıralamada öyle ardışık iki öğrenci vardır ki önde olanın bisiklet ve koşma sürelerinin toplamı arkada olandan küçüktür. Bu iki öğrenciyi yer değiştirelim. Geri kalan öğrencilerin spor programını bitirdikleri zaman değişmeyecektir. Öne gelen öğrenci spor programını değişiklik öncesinden daha erken bitirecektir. Arkaya giden öğrenci ise daha önce arkada olan öğrenciden daha önce sporunu tamamlamış olacaktır. Böylelikle bu değişiklik sonrasında spor programının uzamadığını (muhtemelen kısaldığını) göstermiş olduk. Bu işlem bütün öğrenciler bisiklet ve koşma sürelerinin toplamına göre bu yükten küçüğe sıralanana kadar tekrarlanırsa başlangıçta hangi sıralama verilirse verilsin başlangıçta verilen sıralamadan daha kötü olmayan bir sıralama elde edildiğine göre öğrencilerin bisiklet ve koşma süreleri toplamı na göre büyükten küçüğe sıralanmaları spor programının toplam süresini eniyileyen sıralamadır. Bu yüzden