Pewna czarownica omyłkowo odstawiła fiolkę z bardzo silną trucizną na półkę z innymi fiolkami i teraz nie pamięta, która z nich zawiera niebezpieczną substancję. Postanowiła ona przetestować fiolki za pomocą żabek, które są na truciznę odporne, ale u których po wypiciu trucizny następuje efekt uboczny w postaci zmiany koloru na fioletowy. Zmiana koloru następuje w ciągu 24 godzin. Czarownica musi wiedzieć w której fiolce znajduje się trucizna w przeciągu następnych d dni. Młoda adeptka magii do swojego eksperymentu chciałaby użyć jak najmniejszej liczby żabek. Wiedząc ile fiolek znajduje się na szafce, oblicz minimalną liczbę żabek potrzebnych do eksperymentu.
Rozmowę rekrutacyjną zacznijmy od pytań precyzujących zadanie:
Kandydat: Czy żabki stają się fioletowe po określonym czasie? Na przykład dokładnie po 10 godzinach?
Rekruter: Nie. Wiemy jedynie, że staną się fioletowe nie później niż po 24 godzinach. Każda żabka może stać się fioletowa w innym momencie, nawet jeśli wzięły one truciznę w tym samym czasie.
Jeśli odpowiedź na to pytanie byłaby twierdząca, to moglibyśmy użyć strategii w której jedną żabkę częstujemy każdą możliwą fiolką w odpowiednich odstępach czasu. Mierząc dokładnie w którym momencie żabka stała się fioletowa, moglibyśmy jednoznacznie określić która fiolka zawierała truciznę. Ponieważ jednak odpowiedź na to pytanie była negatywna – nie możemy tego uczynić.
Kandydat: Czy jednego dnia możemy poczęstować żabkę zawartością kilku fiolek? Co się dzieje w takiej sytuacji.
Rekruter: Tak. Każda żabka może otrzymać roztwór będący mieszaniną dowolnej liczby fiolek. Żabka stanie się wtedy fioletowa wtedy i tylko wtedy gdy roztwór zawierał w sobie truciznę.
Ponownie, gdyby odpowiedź rekrutera była odwrotna – zadanie byłoby dużo łatwiejsze. Gdyby każda żabka mogłaby spróbować zawartości tylko jednej fiolki, potrzebowalibyśmy tylu żabek ile wynosi iloraz liczby fiolek przez liczbę dni (zaokrąglony w górę do najbliższej liczby całkowitej).
Kandydat: Czy zawartość którejś z fiolek może nam się skończyć? Co wtedy?
Rekruter: Nie. Żabki są bardzo małe i potrzebują niewielkiej ilości roztworów.
Kandydat: Co się stanie gdy fioletowej żabce podamy truciznę?
Rekruter: Nic. Nie staje się “bardziej” fioletowa.
Kandydat: Czy fioletowa żabka może stać się na nowo zielona? Jeśli tak to w jaki sposób?
Rekruter: Nie. Żabki pozostają już fioletowe do końca świata.
Normalnie w zagadkach zakładamy takie rzeczy, ale podczas rozmowy rekrutacyjnej lepiej się o to zapytać, niż zakładać coś, czego nie było w treści zadania.
Zanim przejdziemy do rozwiązania tego zadania, zastanówmy się jaka jest najmniejsza liczba żabek, jakie potrzebujemy aby wykryć truciznę w ciągu jednego dnia, jeśli na półce znajdują się 4 fiolki. Okazuje się, że wystarczą 2 żabki. Pierwszej z nich podajemy płyn z drugiej i czwartej fiolki, a drugiej żabce podajemy płyn z trzeciej i czwartej. Jeśli po 24 godzinach pierwsza żabka będzie fioletowa, to trucizna znajduje się w drugiej fiolce. Jeśli druga żabka będzie fioletowa, to trucizna znajduje się w trzeciej fiolce. Jeżeli obie żabki będą fioletowe to trucizna znajduje się w czwartej fiolce, a jeśli żadna żabka nie stała się fioletowa to trucizna znajduje się w pierwszej fiolce.
Aby rozwiązać to zadanie, trzeba na nie popatrzeć trochę pod innym kątem. Zamiast zastanawiać się jaka jest minimalna liczba żabek dla określonej liczby dni oraz fiolek – zastanówmy się jaka jest maksymalna liczba fiolek jakie możemy sprawdzić dla określonej liczby żabek oraz dni.
Problem wciąż wydaje się zbyt trudny. Uprośćmy go i zastanówmy się co, jeśli czarownica ma tylko jeden dzień na odkrycie, która fiolka zawiera truciznę. Po przypadku z czterema fiolkami, który rozważyliśmy dwa akapity wyżej – możemy wysnuć przypuszczenie, że liczba fiolek jaką jesteśmy w stanie sprawdzić to dwa do potęgi liczby żabek. Po 24 godzinach każda z żabek będzie albo zielona, albo fioletowa. Możemy uzyskać zatem dwa do potęgi liczby żabek różnych wyników. Możemy tak przydzielić fiolki do żabek, aby zakodować w każdym wyniku jedną fiolkę.
Sytuacja się nieco komplikuje, gdy Czarownica ma więcej dni na rozpoznanie, która fiolka zawiera trującą substancję, bowiem po pierwszym dniu może nam zostać różna liczba zielonych żabek. Możemy się jednak posłużyć programowaniem dynamicznym.
Niech DP[i][j] oznacza jaka jest maksymalna liczba fiolek jakie da się sprawdzić za pomocą j żabek w i dni. Załóżmy, że z j zielonych żabek k pozostało zielonych. Mogło się to stać na j po k różnych sposobów (gdzie “j po k” oznacza dwumian newtona i jest równy j! / k! * (j – k)!). Wtedy nam zostaje k zielonych żabek oraz i – 1 dni. Wtedy możemy maksymalnie sprawdzić DP[i-1][k] różnych fiolek. Mnożąc tę wartość przez j po k, a następnie sumując po wszystkich możliwych k otrzymujemy nasz pożądany wynik.
int liczbaŻabek(int fiolki, int dni)
{
int DP[101][11]; // DP[i][j] = maksymalna liczba fiolek jakie da się
// sprawdzić za pomocą j żabek w i dni.
// W ciągu dnia liczba fiolek jakie da się sprawdzić to potęga dwójki.
int j = 0;
DP[1][0] = 1;
while (DP[1][j] < fiolki)
{
j++;
DP[1][j] = 2 * DP[1][j-1];
}
// Dla kolejnych dni używamy programowania dynamicznego
for (int i = 2; i <= dni; i++)
{
j = 0;
vector<int> dwumian; // Dwumian newtona liczony dynamicznie
dwumian.push_back(1);
DP[i][0] = 1;
while (DP[i][j] < fiolki)
{
j++;
// Liczymy dwumian
for (int k = dwumian.size()-1; k >= 1; k--)
dwumian[k] += dwumian[k-1];
dwumian.push_back(1);
DP[i][j] = 0;
for (int k = 0; k < dwumian.size(); k++)
DP[i][j] += dwumian[k] * DP[i-1][k];
}
}
// W j zapamiętaliśmy najmniejszy indeks dla którego DP[dni][j] był większy
// od fiolek. Zmienna j jest zatem rozwiązaniem naszego problemu.
return j;
}Aby otrzymać lepszy algorytm, trzeba zrobić jedną z trzech rzeczy:
Po pierwsze, możemy wypisać wartości tablicy DP na ekranie i zauważyć zaskakującą(?) zależność:
| żabki\dni | 1 | 2 | 3 | 4 | 5 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 4 | 9 | 16 | 25 | 36 |
| 3 | 8 | 81 | 64 | 125 | 216 |
| 4 | 16 | 279 | 256 | 625 | 1296 |
Po drugie, możemy sobie przypomnieć ze szkoły średniej, że zachodzi:
Podstawiając za y wartość 1, szybko zauważymy że prawa strona to tak naprawdę to co liczymy w naszym programie, zatem z każdym dniem, liczymy potęgi coraz to większej podstawy.
Po trzecie, możemy na problem spojrzeć inaczej. Zamiast dzień po dniu tak jak to zrobiliśmy wcześniej – możemy popatrzeć “żabka po żabce”. Każda żabka może stać się fioletowa w którymś dniu, albo może zostać zielona do końca eksperymentu. Czyli dla przykładu jeśli eksperyment trwał trzy dni, to żabka mogła zostać fioletowa w pierwszym dniu, w drugim dniu, w trzecim dniu albo pozostać zielona przez cały eksperyment. Mamy zatem (dni + 1) różnych opcji dla każdej z żabek. Zatem mamy (dni + 1) do potęgi liczby żabek różnych wyników eksperymentu. Każdej z nich można przypisać inną fiolkę.
Wiedząc już o tym, możemy nasz program napisać prościej:
int liczbaŻabek(int fiolki, int dni)
{
int zabki = 0;
int maks = 1; // ile maksymalnie fiolek jestesmy w stanie sprawdzic
// za pomocą zabki żabek w dni dni.
while (maks < fiolki)
{
zabki++;
maks *= (dni + 1);
}
return zabki;
}Czarownica kategorycznie zaprzecza aby kręciła się z fiolkami w pobliżu Odry pod koniec lipca tego roku.
