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


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
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.

Ż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

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

A tak poważniej... Zadanie jest nieprecyzyjne, ponieważ nie określa czy wszyscy idą do tego samego domu choćby

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

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

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.

@up
Dokładnie tak, ale chodzi mi o program/skrypt który tą zagadkę rozwiąże

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.