Υπάρχουν δύο κλεψύδρες: η μία τρέχει εντελώς σε \(4\) λεπτά, η άλλη σε \(7\) λεπτά. Πώς μετράτε ακριβώς \(9\) λεπτά όταν η μέτρηση πρέπει να ξεκινήσει την πρώτη φορά που ξεκινούν τα ρολόγια; Δεν επιτρέπονται άλλο ρολόι, μέτρηση δευτερολέπτων και εικασίες. Το μόνο που έχετε να κάνετε είναι να αναποδογυρίσετε τις κλεψύδρες και να παρακολουθήσετε πότε ο πάνω θάλαμος είναι άδειος. Η περιστροφή δεν πρέπει να πάρει χρόνο. Αυτό που αναζητούμε είναι μια διαδικασία κατά την οποία το τέλος της επιθυμητής χρονικής περιόδου μπορεί να αναγνωριστεί αποκλειστικά από τις κλεψύδρες.
Ονομάζουμε το ρολόι με \(4\) λεπτά \(A\) και αυτό με \(7\) λεπτά \(B\) . Αρχικά όλη η άμμος βρίσκεται στο κάτω μέρος. Ξεκινάμε και τα δύο ρολόγια ταυτόχρονα αναποδογυρίζοντάς τα. Από αυτή τη στιγμή και μετά μετράνε τα \(9\) λεπτά που αναζητήσατε. Μετά από αυτό, μπορείτε πάντα να κάνετε συναλλαγές όταν ένα ρολόι στην κορυφή αδειάσει. Δεν μπορείτε να αναποδογυρίσετε το ένα, το ένα ή και τα δύο ρολόγια, ακόμη και ένα που λειτουργεί ακόμα. Περιμένεις μέχρι την επόμενη φορά που θα τελειώσει. Η στάση και η σήμανση δεν επιτρέπονται. ένα άδειο ρολόι μπορεί να παραμείνει όρθιο. Η λύση μοιάζει με αυτό:
- Στο λεπτό ξεκινούν \(0\) \(A\) και \(B\) .
- Στο λεπτό \(4\) \(A\) είναι κενό και αναποδογυρίζεται. \(B\) συνεχίζει να λειτουργεί αμετάβλητο.
- Στο λεπτό \(7\) \(B\) είναι κενό και αναποδογυρίζεται. Απομένει ακόμα \(1\) λεπτό στο \(A\) .
- Στο λεπτό \(8\) \(A\) είναι κενό. Στο \(B\) η άμμος έτρεξε για ακριβώς \(1\) λεπτό. επομένως \(B\) αναποδογυρίζεται αμέσως ξανά.
- Στο λεπτό \(9\) \(B\) είναι κενό. Η ώρα που αναζητούσατε έχει φτάσει.
Στο λεπτό \(8\) αναποδογυρίζουμε το ρολόι \(B\) το οποίο εξακολουθεί να λειτουργεί. Από την επανεκκίνησή τους στο λεπτό \(7\) , έχει κυλήσει ακριβώς τόση άμμος όση θα χωρούσε μέσα από το σημείο συμφόρησης σε \(1\) λεπτό. Μετά το γύρισμα, μόνο αυτή η μικρή ποσότητα είναι από πάνω. Τώρα χρειάζεται \(1\) λεπτό για να ρίξει ξανά. Επομένως, το ρολόι αδειάζει στο λεπτό \(9\) , όχι μετά από μια άλλη πλήρη εκτέλεση. Μετράμε λοιπόν το τελευταίο λεπτό με άμμο που έχει ήδη περάσει. Το κινούμενο σχέδιο δείχνει αυτή την κίνηση:
Το χτύπημα μιας κλεψύδρας είναι επίσης χρήσιμο για τη γενική λύση. Με τον όρο υπολειπόμενος χρόνος εννοούμε τον χρόνο που χρειάζεται ακόμα να ρέει η άμμος στον επάνω θάλαμο. Εάν το πλήρες ρολόι έχει τον χρόνο λειτουργίας \(c\) και ο χρόνος που απομένει είναι \(r\) , τότε η ποσότητα άμμου στο κάτω μέρος αντιστοιχεί στη διάρκεια \(cr\) . Όταν το αναποδογυρίζετε, αυτό ακριβώς το ποσό έρχεται στην κορυφή. Εάν ο επάνω θάλαμος είναι γεμάτος εκ των προτέρων, θα αδειάσει μετά και το αντίστροφο. Για ένα ρολόι που εκτελείται μερικώς, ο νέος χρόνος λειτουργίας που απομένει είναι \(r'\):
$$r'=c-r.$$
Προηγουμένως, η μέτρηση ξεκινούσε με την πρώτη στροφή. Αυτό σημαίνει «χωρίς χρόνο παράδοσης»: κάθε λεπτό από την έναρξη μετράει. "Με προκαταβολή" σημαίνει, από την άλλη, ότι μπορείτε να προετοιμάσετε πρώτα τα ρολόγια και η επιθυμητή χρονική περίοδος αρχίζει αργότερα. Για παράδειγμα, ξεκινάμε και τα δύο ρολόγια και αναποδογυρίζουμε \(A\) στο λεπτό \(4\) . Εάν \(B\) αδειάσει στο λεπτό \(7\) , ξεκινά η μέτρησή μας. Εάν \(A\) γίνει κενό στο λεπτό \(8\) , τελειώνει. Μετρήσαμε \(1\) λεπτό. τα προηγούμενα \(7\) λεπτά δεν μετράνε.
Τώρα εξετάζουμε αυθαίρετες κλεψύδρες με θετικούς ακέραιους χρόνους λειτουργίας \(a\) και \(b\) . Ονομάζουμε την επιθυμητή διάρκεια \(T\) . Ποιοι χρόνοι μπορούν να μετρηθούν με αυτό εάν επιτρέπεται η προετοιμασία; Και εδώ η αρχή και το τέλος πρέπει να είναι αναγνωρίσιμα από έναν κενό χώρο. Επομένως, δεν πρέπει να αρχίσετε να μετράτε κάποια στιγμή με βάση το συναίσθημά σας. Οι λαβές παραμένουν οι ίδιες όπως στο πραγματικό παζλ. Πρώτα δείχνουμε ποιοι χρόνοι εξαιρούνται. τότε θα σας δείξουμε πώς να μετρήσετε πραγματικά όλα τα υπόλοιπα.
Πρώτα ας πάρουμε ρολόγια με \(6\) και \(10\) λεπτά. Και οι δύο χρόνοι λειτουργίας διαιρούνται με \(2\) . Επομένως, η άμμος μπορεί να χωριστεί διανοητικά σε μέρη, καθένα από τα οποία χρειάζεται \(2\) λεπτά για να περάσει. Όταν το αναποδογυρίζετε ή περιμένετε μέχρι την επόμενη φορά που θα αδειάσει, δημιουργούνται ξανά μόνο ολόκληρα τμήματα. Όλοι οι παρατηρήσιμοι άδειοι χρόνοι απέχουν επομένως ζυγό αριθμό λεπτών. Δεν μπορείτε να το χρησιμοποιήσετε για να μετρήσετε διάρκεια \(3\) λεπτών, ακόμα κι αν προετοιμάσετε τα ρολόγια για όσο χρόνο θέλετε εκ των προτέρων.
Γενικά, έστω \(g=\gcd(a,b)\) ο μεγαλύτερος κοινός διαιρέτης των χρόνων εκτέλεσης. Αρχικά και οι δύο υπόλοιποι όροι είναι πολλαπλάσια του \(g\) . Όταν περιστρέφεται \(r\) γίνεται είτε \(ar\) είτε \(br\) ; και τα δύο παραμένουν διαιρούμενα με το \(g\) . Κατά την αναμονή, παρέρχεται ο μικρότερος θετικός χρόνος που απομένει, ο οποίος είναι επίσης πολλαπλάσιο του \(g\) . Αυτό σημαίνει ότι όλοι οι κενοί χρόνοι και οι αποστάσεις τους παραμένουν πολλαπλάσια του \(g\) . Μια μετρήσιμη διάρκεια πρέπει επομένως να ικανοποιεί \(g\mid T\) : \(T\) πρέπει να διαιρείται με το \(g\) . Το αν αυτό είναι αρκετό μένει να φανεί.
Για να γίνει αυτό, αφήνουμε και τα δύο ρολόγια να λειτουργούν ξανά και ξανά και αναποδογυρίζουμε το καθένα μόλις αδειάσει. Το πρώτο στη συνέχεια γίνεται άδειο μετά \(a,2a,3a,\ldots\) μονάδες χρόνου, το δεύτερο μετά \(b,2b,3b,\ldots\) . Αναζητούμε μια ώρα \(mb\) του δεύτερου ρολογιού και μια μεταγενέστερη ώρα \(na\) του πρώτου, μεταξύ της οποίας βρίσκεται ακριβώς \(T\) . Το λήμμα του Bézout εγγυάται την αντιστοίχιση ακεραίων \(n,m\) εάν \(T\) είναι θετικό πολλαπλάσιο του \(g\) . Η σχέση που αναζητάτε είναι::
$$na-mb=T.$$
Οι αριθμοί \(n,m\) που παρέχονται από την Bézout μπορεί αρχικά να είναι αρνητικοί. Δεν μπορούν να πραγματοποιηθούν αρνητικές διαδρομές. Ωστόσο, μπορεί κανείς να αυξήσει και τους δύο αριθμούς χωρίς να αλλάξει το χρονικό διάστημα: τους αντικαθιστούμε με \(n+kb/g\) και \(m+ka/g\) , όπου \(k\) είναι ένας αρκετά μεγάλος θετικός ακέραιος αριθμός. Επομένως και οι δύο χρόνοι μετατοπίζονται κατά το ίδιο ποσό \(kab/g\) ; η διαφορά τους παραμένει \(T\) . Έτσι και οι δύο αριθμοί γίνονται θετικοί και οι απαιτούμενοι χρόνοι είναι στην πραγματικότητα μετά την έναρξη των ρολογιών.
Τώρα μετράτε τους πλήρεις κύκλους κάθε ρολογιού. Όταν το \(m\) ρολόι αδειάσει, αρχίζει η μέτρηση. τελειώνει όταν το πρώτο ρολόι αδειάσει για την \(n\) -η φορά. Υπάρχουν ακριβώς \(T\) μονάδες χρόνου ενδιάμεσα. Η προετοιμασία μπορεί να διαρκέσει πολύ. Η απόδειξη δεν υπόσχεται μια ιδιαίτερα σύντομη διαδικασία. Για \(T=0\) η αρχή και το τέλος συμπίπτουν. Αυτό αποδεικνύεται για όλους τους μη αρνητικούς ακέραιους στόχους: Με την προετοιμασία, μια διάρκεια μπορεί να μετρηθεί εάν και μόνο εάν τη διαιρέσει ο μεγαλύτερος κοινός διαιρέτης:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Αυτός ο κανόνας δεν ισχύει απαραίτητα για την έναρξη των μετρήσεων από την πρώτη εκκίνηση. Για παράδειγμα, με \(4\) και \(7\) λεπτά \(g=1\) , αλλά μετά από \(1\) λεπτό κανένα ρολόι δεν είναι κενό. Έτσι δεν μπορείτε να δείτε το τέλος αυτού του λεπτού. Η μέτρηση από το λεπτό \(7\) έως \(8\) που περιγράφεται παραπάνω λειτουργεί μόνο επειδή η προετοιμασία δεν μετράει. Η απόδειξη απαντά έτσι στο ερώτημα τι είναι δυνατό μετά την προετοιμασία. Αν ψάχνετε για μια επιτρεπόμενη διαδικασία με ή χωρίς προετοιμασία, η παρακάτω συστηματική αναζήτηση θα σας βοηθήσει.
Το σενάριο PHP θυμάται τόσο τους υπόλοιπους χρόνους εκτέλεσης όσο και τον χρόνο που έχει παρέλθει από την έναρξη της μέτρησης. Για κάθε τέτοια κατάσταση, δοκιμάστε τα όλα \(4\) Δυνατότητες: χωρίς ρολόι, μόνο το πρώτο, μόνο το δεύτερο ή αναποδογυρίστε και τα δύο. Στη συνέχεια, περιμένει μέχρι την επόμενη φορά που θα αδειάσει. Η αξία \(-1\) υποδεικνύει προετοιμασία. την είσοδο start ρυθμίζει το χρόνο μέτρησης \(0\). Οι γνωστές συνθήκες δεν θα διερευνηθούν εκ νέου. Η αλληλουχία που βρέθηκε λαμβάνεται μέσω των προκατόχων της. wait αναφέρεται μόνο στην απόσταση από το επόμενο άδειασμα, όχι σε πρόσθετη μέτρηση χρόνου:
<?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;
}
Η αναζήτηση βρίσκει ή επιστρέφει μια επιτρεπόμενη διαδικασία null, αν δεν υπάρχει κανένα. Καλύπτει όλες τις επιτρεπόμενες συνέχειες και απαιτεί μέγιστη προετοιμασία \((a+1)(b+1)(T+2)\) Κράτη. Επομένως, οι μεγάλες είσοδοι απαιτούν πολλή μνήμη. Ο αριθμός των μεταβάσεων αναζήτησης ελαχιστοποιείται, όχι ο χρόνος προετοιμασίας. Οι ορθολογικοί χρόνοι εκτέλεσης και στόχοι μετατρέπονται σε ακέραιους αριθμούς χρησιμοποιώντας έναν κοινό παρονομαστή. Για χρόνους εκτέλεσης χωρίς κοινή μονάδα χρόνου, για παράδειγμα \(1\) και \(\sqrt{2}\), Αυτή η αναζήτηση πεπερασμένου ακέραιου αριθμού δεν είναι κατάλληλη.