Πρόβλημα κουπονιών στο διαγωνισμό IEEE Xtreme

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
StamPapEce
Δημοσιεύσεις: 1
Εγγραφή: Παρ Ιαν 24, 2020 4:02 pm

Πρόβλημα κουπονιών στο διαγωνισμό IEEE Xtreme

Δημοσίευση από StamPapEce »

Μπορεί κάποιος να βοηθήσει στο παρακάτω πρόβλημα?
https://csacademy.com/ieeextreme-practi ... upon-codes
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Πρόβλημα κουπονιών στο διαγωνισμό IEEE Xtreme

Δημοσίευση από Κηπουρίδης »

Για ευκολία θα υποθέσω ότι έχουμε τρεις μόνο χαρακτήρες. Έχουμε πχ τις λέξεις
ΑΒΑ
ΑΡΑ
1ΡΑ

Η απάντηση θα ήταν 2, επειδή το ΑΡΑ μπορεί με μία αλλαγή να γίνει ΑΒΑ, και μπορεί και με μία αλλαγή να γίνει 1ΡΑ, αλλά το 1ΡΑ δεν μπορεί με μια αλλαγή να γίνει ΑΒΑ.

Αυτό που μπορείς τώρα να κάνεις είναι για κάθε λέξη να γεννήσεις 3 βοηθητικές λέξεις:
ΑΒΑ -> *ΒΑ, Α*Α, ΑΒ*
ΑΡΑ -> *ΡΑ, Α*Α, ΑΡ*
1ΡΑ -> *ΡΑ, 1*Α, 1Ρ*

Βλέπουμε ότι το ΑΒΑ και το ΑΡΑ έχουν κοινή την βοηθητική λέξη Α*Α, το ΑΡΑ και το 1ΡΑ έχουν κοινή την βοηθητική λέξη *ΡΑ, ενώ το ΑΒΑ και το 1ΡΑ δεν έχουν καμμία κοινή βοηθητική λέξη.

Σταματάω εδώ για να το σκεφτείς, κι αν χρειαστείς κι άλλη βοήθεια μας ρωτάς.

Καλώς ήρθες στο forum!
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Απάντηση