Algorytm rozwiązujący zagadkę Opcje

[Fifi209]

Przeglądając forum, natknąłem na stary temat z zagadkami i jedną sobie skopiowałem:

Cztery osoby (nazwijmy je: Adam, Basia, Celina i Dorota) wybrały się samochodem na imprezę.
Rozpętała się burza, parking jest dość oddalony od domu, a okazało się, że w samochodzie jest tylko jeden parasol!
Adam idzie z parkingiu do domu - 1 minutę, Basia - 2, Celina - 5, a Dorota - 10.
Pod parasolem mieszczą się naraz dwie osoby, a gdy idą, szybsza dostosowuje swe tempo do wolniejszej (czyli Adam z Dorotą szliby 10 minut).
Aby nikt nie zmókł, wymyślili, że najpierw pójdzie Adam z Basią, Adam wróci z parasolem, potem Adam z Celiną, Adam wróci z parasolem, w końcu Adam z Dorotą. W sumie 2+1+5+1+10= 19 minut.
Sposób niezły, ale istnieje lepszy - da się to zrobić w 17 minut.
Pytanie: jak?

Z tekstu wynikają pewne założenia:

1. Prędkość osób
Adam - 1 minut
Basia - 2 minuty
Celina - 5 minut
Dorota - 10 minut

2. Parasol - mieszą się pod nim naraz maksymalnie dwie osoby
3. Miejsca:
a) Samochód
(IMG:style_emoticons/default/cool.gif) Dom

3. Osoba szybsza dostosowuje tempo do wolniejszej

Zadanie: Napisz program, który rozwiąże zagadkę korzystając z wytycznych.

Prosty zarys algorytmu jaki ja wymyśliłem:

[PHP] pobierz, plaintext 
$People = array(
	'Adam' => 1,
	'Basia' => 2,
	'Celina' => 5,
	'Dorota' => 10
);
[PHP] pobierz, plaintext 

Dwie tablice:

[PHP] pobierz, plaintext 
$Car = array();
$House = array();
[PHP] pobierz, plaintext 

Algorytm:
< Uruchomienie pętli >

• Przepisanie tablicy People do Car
• Wylosowanie dwóch osób, zapisanie ich imion do zmiennych pomocniczych i ich szybkości [i usunięcie ich z tablicy Car]
• Obliczenie, prędkości poruszania się osób - czyli sprawdzenie, która jest wolniejsza
• Dodanie czasu: prędkość wolniejszej osoby
• Dodanie osób do tablicy House
• Wylosowanie jednej osoby z tablicy House, która wróci do samochodu i dodanie jej do tablicy Car
• Dodanie czas: prędkość osoby wracającej
• Powtórzenie pętli, póki są osoby w samochodzie

Zapisanie kroków - kto i w jakiej kolejności
Porównanie czasu, jeżeli mniejszy od poprzedniego to przepisujemy kroki i zapisujemy czas
<Powrót do początku pętli>


Ja wymyśliłem taki algorytm... Jeszcze do końca nie wyszło mi napisanie tego, bo minimalny czas uzyskuję 19 minut - ale to błąd w moich wcześniejszych założeniach co do losowania.

Jestem ciekawy, czy można zrobić to jakoś bardziej optymalnie.

[!*!]

[PHP] pobierz, plaintext 
$inCar = array('Adam', 'Basia', 'Celina', 'Dorota');
$hexMap = array(0,1,2,3,4,5,6);
$items = array('parasol')
 
$run = new goHome($inCar);
$run->runCarHex($hextMap, 1, 1);
$run->removeUser(array('Basia', 'Celina', 'Dorota'));
$run->runCarHex($hextMap, 0, 0);
$run->getItems(1);
$run->runUserHex($hextMap, 1, 1);
echo $run->getTime();
[PHP] pobierz, plaintext 

Czas wykonania: 3 minuty, bo Adam nie był bucem i wysadził dziewczyny pod dom. (IMG:style_emoticons/default/biggrin.gif)

[thek]

Żaden problem... Adam odprowadza Basię (2), wraca (1) i mówi pozostałym, że mają iść same razem (10). Sam wraca bez parasola - bo facet nie z cukru (IMG:style_emoticons/default/biggrin.gif)

Wersja 2: Jedna z dziewczyn jest dziewczyną Adama. Pozostałe odprowadza, z dziewczyną zostają w samochodzie w celu wiadomym. Czas zakończenia - zależny od tego, która z dziewczyn jest dziewczyną Adama (IMG:style_emoticons/default/biggrin.gif)

A tak poważniej... Zadanie jest nieprecyzyjne, ponieważ nie określa czy wszyscy idą do tego samego domu choćby (IMG:style_emoticons/default/wink.gif)

[Fifi209]

Tak, idą do tego samego domu, dystans jest ten sam.

[foxbond]

Sposób niezły, ale istnieje lepszy - da się to zrobić w 17 minut.
Pytanie: jak?

Pewny jesteś, że istnieje sposób 17-sto minutowy? Chyba ze 4 opcje rozrysowałem na kartce i najszybszy 19min, najdłuższy 28min

[ADeM]

Thek podał rozwiązanie:
Żaden problem... Adam odprowadza Basię (2), wraca (1) i mówi pozostałym, że mają iść same razem (10). Sam wraca bez parasola - bo facet nie z cukru.

Na końcu Baśka wraca po niego (+4 minuty). Razem wychodzi 17.

[Fifi209]

@up
Dokładnie tak, ale chodzi mi o program/skrypt który tą zagadkę rozwiąże (IMG:style_emoticons/default/tongue.gif)

[Crozin]

Przeglądnij sobie zestawy zadań z ostatnich 2-4 lat potyczek algorytmicznych (raczej zadania z początkowych etapów). O ile dobrze pamiętam, w którymś zadaniu Bajtaraz musiał wykonać analogiczne zadanie.

Ten post edytował Crozin 18.03.2013, 12:35:43