İki kum saati vardır: biri tamamen \(4\) dakikada, diğeri \(7\) dakikada tamamlanır. Saatler ilk başlatıldığında ölçümün başlaması gerektiğinde tam olarak \(9\) dakikayı nasıl ölçersiniz? Başka bir saate, saniye saymaya ve tahmin etmeye izin verilmez. Tek yapmanız gereken kum saatini ters çevirip üst bölmenin ne zaman boşaldığını izlemek. Geri dönmek hiç zaman almamalı. Aradığımız, istenilen sürenin sonunun yalnızca kum saatinden anlaşılabileceği bir süreçtir.
\(4\) dakikalı saati \(A\) ve \(7\) dakikalık olanı \(B\) olarak adlandırırız. Başlangıçta kumun tamamı alttadır. Her iki saati de ters çevirerek aynı anda çalıştırıyoruz; Bu andan itibaren aranan \(9\) dakika sayılır. Bundan sonra, üstteki saat boşaldığında her zaman işlem yapabilirsiniz. Saatlerden birini, birini veya her ikisini, hatta hala çalışıyor olsa bile, çeviremezsiniz. Bir dahaki sefere bitene kadar beklersiniz. Durdurmaya ve işaretlemeye izin verilmez; boş bir saat ayakta kalabilir. Çözüm şuna benziyor:
- Dakikada \(0\) \(A\) ve \(B\) başlatılır.
- Dakikada \(4\) \(A\) boştur ve ters çevrilir. \(B\) değişmeden çalışmaya devam eder.
- Dakikada \(7\) \(B\) boştur ve ters çevrilir. \(A\) 'da hala \(1\) dakika kaldı.
- Dakikada \(8\) \(A\) boştur. \(B\) de kum tam olarak \(1\) dakika boyunca aktı; dolayısıyla \(B\) hemen tekrar ters çevrilir.
- Dakikada \(9\) \(B\) boş. Aradığınız saate ulaşıldı.
\(8\) dakikada hâlâ çalışmakta olan \(B\) saatini ters çeviriyoruz. \(7\) dakikada yeniden başladıklarından bu yana, darboğazdan \(1\) dakikada geçebilecek miktarda kum aşağı doğru aktı. Döndürdükten sonra sadece bu küçük miktar üstte kalır. Şimdi tekrar aşağıya damlaması \(1\) dakika sürüyor. Bu nedenle saat, başka bir tam koşudan sonra değil, \(9\) dakikada boşalır. Yani son dakikayı zaten geçmiş olan kumla ölçüyoruz. Animasyon bu hareketi gösteriyor:
Çalışan bir kum saatini çevirmek de genel çözüm açısından faydalıdır. Kalan süre derken kumun üst haznede akmaya devam etmesi gereken süreyi kastediyoruz. Tam saatin çalışma süresi \(c\) varsa ve kalan çalışma süresi \(r\) ise, o zaman alttaki kum miktarı \(cr\) süresine karşılık gelir. Ters çevirdiğinizde tam olarak bu miktar en üste çıkıyor. Üst bölme önceden doluysa daha sonra boş olacaktır ve bunun tersi de geçerlidir. Kısmen çalışan bir saat için kalan yeni çalışma süresi \(r'\):
$$r'=c-r.$$
Daha önce ölçüm ilk dönüşle başlıyordu. Bu, "tedarik süresi olmadan" anlamına gelir: Başlangıçtan bu yana geçen her dakika önemlidir. “Önceden” ise saatleri önce hazırlayabileceğiniz ve istediğiniz zaman diliminin daha sonra başlayacağı anlamına gelir. Örneğin, her iki saati de başlatıyoruz ve \(4\) dakikada \(A\) yı ters çeviriyoruz. Eğer \(B\) \(7\) dakikada boşalırsa ölçümümüz başlar. Eğer \(A\) \(8\) dakikada boşalırsa biter. \(1\) dakikayı ölçtük; önceki \(7\) dakika sayılmaz.
Şimdi pozitif tamsayı çalışma süreleri \(a\) ve \(b\) olan rastgele kum saatlerini ele alıyoruz. İstenilen süreye \(T\) diyoruz. Hazırlığa izin veriliyorsa bununla hangi zamanlar ölçülebilir? Burada da başlangıç ve bitişin boşlukla tanınabilmesi gerekir. Bu nedenle bir noktada hislerinize dayanarak ölçüm yapmaya başlamamalısınız. Tutamaçlar gerçek bulmacadakiyle aynı kalır. Öncelikle hangi zamanların hariç tutulduğunu gösteriyoruz; sonra size geri kalan her şeyi nasıl ölçeceğinizi göstereceğiz.
Öncelikle \(6\) ve \(10\) dakikalık saatleri alalım. Her iki çalışma süresi de \(2\) ile bölünebilir. Bu nedenle kum, zihinsel olarak her birinin geçmesi \(2\) dakika süren kısımlara bölünebilir. Ters çevirdiğinizde veya bir dahaki sefere kadar boşalıncaya kadar beklediğinizde, yalnızca tam porsiyonlar yeniden oluşturulur. Bu nedenle gözlemlenebilir tüm boş zamanlar, çift sayıda dakikalık aralıklara sahiptir. Saatleri önceden istediğiniz süreye hazırlasanız bile \(3\) dakikalık bir süreyi ölçmek için kullanamazsınız.
Genel olarak, çalışma sürelerinin en büyük ortak böleni \(g=\gcd(a,b)\) olsun. Başlangıçta kalan terimlerin her ikisi de \(g\) nin katıdır. Döndürüldüğünde \(r\) \(ar\) veya \(br\) olur; her ikisi de \(g\) ile bölünebilir kalır. Beklerken, \(g\) nin katı olan en küçük pozitif kalan süre geçer. Bu, tüm boş zamanların ve mesafelerinin \(g\) nin katları olduğu anlamına gelir. Bu nedenle ölçülebilir bir sürenin \(g\mid T\) yi karşılaması gerekir: \(T\) \(g\) ile bölünebilir olmalıdır. Bunun yeterli olup olmadığı görülecektir.
Bunu yapmak için her iki saati de tekrar tekrar tamamen çalıştırıyoruz ve boşalır boşalmaz her birini çeviriyoruz. İlki \(a,2a,3a,\ldots\) zaman biriminden sonra, ikincisi ise \(b,2b,3b,\ldots\) 'dan sonra boşalır. İkinci saatin zamanını \(mb\) ve birinci saatin daha sonraki bir zamanını \(na\) arıyoruz, bu arada tam olarak \(T\) bulunur. Bézout'un lemması, eğer \(T\) \(g\) 'nin pozitif katı ise \(n,m\) tamsayılarının eşleşmesini garanti eder. Aradığınız ilişki::
$$na-mb=T.$$
Bézout'un sağladığı \(n,m\) sayıları başlangıçta negatif olabilir. Negatif çalıştırmalar gerçekleştirilemez. Bununla birlikte, zaman aralığını değiştirmeden her iki sayı da artırılabilir: bunları \(n+kb/g\) ve \(m+ka/g\) ile değiştiririz; burada \(k\) yeterince büyük bir pozitif tam sayıdır. Dolayısıyla her iki zaman da aynı miktarda \(kab/g\) kaydırılır; farkları \(T\) olarak kalır. Yani her iki sayı da pozitif oluyor ve gerekli zamanlar aslında saatler başladıktan sonra oluyor.
Artık her saatin tam döngülerini sayarsınız. \(m\) saat boşaldığında ölçüm başlar; ilk saat \(n\) -inci kez boşaldığında sona erer. Arada tam olarak \(T\) zaman birimi vardır. Hazırlık uzun zaman alabilir. Kanıt özellikle kısa bir süreç vaat etmiyor. \(T=0\) için başlangıç ve bitiş çakışır. Bu, negatif olmayan tüm tamsayı hedefleri için kanıtlanmıştır: Hazırlıkla, bir süre ancak ve ancak en büyük ortak bölenin onu bölmesi durumunda ölçülebilir:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Bu kural ölçümlerin ilk başlangıçta başlatılması için mutlaka geçerli değildir. Örneğin, \(4\) ve \(7\) dakika \(g=1\) ile, ancak \(1\) dakikadan sonra hiçbir saat boş değildir. Yani bu dakikanın sonunu göremezsiniz. Yukarıda açıklanan \(7\) ile \(8\) dakikaları arasındaki ölçüm yalnızca hazırlık sayılmadığından işe yarar. Kanıt böylece hazırlıktan sonra neyin mümkün olduğu sorusunu yanıtlar. Hazırlıklı veya hazırlıksız, izin verilen bir süreç arıyorsanız, aşağıdaki sistematik arama yardımcı olacaktır.
PHP betiği hem kalan çalışma sürelerini hem de ölçümün başlangıcından bu yana geçen süreyi hatırlar. Bu tür her durum için hepsini deneyin \(4\) Olasılıklar: saat yok, yalnızca birincisi, yalnızca ikincisi veya her ikisini de ters çevirin. Daha sonra bir sonraki boşalıncaya kadar bekler. Değer \(-1\) hazırlığı belirtir; giriş start ölçüm süresini ayarlar \(0\). Bilinen durumlar yeniden araştırılmayacaktır. Bulunan dizi öncülleri aracılığıyla elde edilir. wait ek bir zaman ölçümü değil, yalnızca bir sonraki boşaltmaya kadar olan mesafeyi ifade eder:
<?php
declare(strict_types=1);
function hourglass(int $a, int $b, int $target, bool $prepare = false): ?array
{
if ($a <= 0 || $b <= 0 || $target < 0) {
throw new InvalidArgumentException('Positive capacities, nonnegative target required.');
}
$root = [0, 0, $prepare ? -1 : 0];
$key = static fn(array $s): string => implode(',', $s);
$queue = new SplQueue();
$queue->enqueue($root);
$previous = [$key($root) => null];
$enqueue = static function (array $next, array $from, array $action)
use ($queue, &$previous, $key): void {
$k = $key($next);
if (!array_key_exists($k, $previous)) {
$previous[$k] = [$key($from), $action];
$queue->enqueue($next);
}
};
while (!$queue->isEmpty()) {
$state = $queue->dequeue();
[$x, $y, $elapsed] = $state;
if ($elapsed === $target) {
$path = [];
for ($k = $key($state); $previous[$k] !== null;) {
[$k, $action] = $previous[$k];
$path[] = $action;
}
return array_reverse($path);
}
if ($elapsed === -1) {
$enqueue([$x, $y, 0], $state, ['start' => true]);
}
for ($mask = 0; $mask < 4; ++$mask) {
$u = ($mask & 1) ? $a - $x : $x;
$v = ($mask & 2) ? $b - $y : $y;
if ($u === 0 && $v === 0) {
continue;
}
$wait = $u === 0 ? $v : ($v === 0 ? $u : min($u, $v));
$nextTime = $elapsed < 0 ? -1 : $elapsed + $wait;
if ($nextTime > $target) {
continue;
}
$enqueue(
[max(0, $u - $wait), max(0, $v - $wait), $nextTime],
$state,
['flip' => $mask, 'wait' => $wait]
);
}
}
return null;
}
foreach ([[4, 7, 9, false], [4, 7, 1, false], [4, 7, 1, true],
[6, 10, 3, true], [5, 5, 10, false], [4, 7, 0, false]] as $case) {
echo json_encode($case), ': ', json_encode(hourglass(...$case)), PHP_EOL;
}
Arama, izin verilen bir işlemi bulur veya döndürür null, eğer hiçbiri yoksa. İzin verilen tüm devamları kapsar ve maksimum hazırlık gerektirir \((a+1)(b+1)(T+2)\) Devletler. Bu nedenle büyük girişler çok fazla bellek gerektirir. Hazırlık süresi değil, arama geçişlerinin sayısı en aza indirilir. Rasyonel koşu ve hedef süreleri ortak bir payda kullanılarak tam sayılara dönüştürülür. Örneğin ortak bir zaman birimi olmayan çalışma süreleri için \(1\) ve \(\sqrt{2}\), bu sonlu tamsayı araması uygun değildir.