THMMY.gr

Το πρόβλημα είναι απλό, αλλά σίγουρα θα έχει απασχολήσει τους χρήστες Η/Υ τουλάχιστον 1 φορα:

Θα το διατυπώσω στην πιο απλή μορφή του.
Θέλω να γεμίσω ένα κείμενο με έναν χαρακτήρα. Π.χ. κατι σαν αυτό:

ggggggggggggggggggggggggg
ggggggggggggggggggggggggg
ggggggggggggggggggggggggg
κτλ κτλ.

Ο απλός (μη βέλτιστος) τρόπος είναι να κρατώ συνεχώς πατημένο το αντίστοιχο πλήκτρο. Αυτό ισχύει για έναν μικρό αριθμό χαρακτήρων.
ΑΝ θέλω όμως έναν μεγάλο αριθμό Ν, έστω Ν=10^6, τότε συμφέρει να αρχίσω το copy-paste.
Δηλαδή έχοντας συμπληρώσει έναν αριθμό m1  χαρακτήρων ξεκινώ και κάνω copy-paste αυτούς.
Κατόπιν  έχοντας συμπληρώσει έναν αριθμό m2 χαρακτήρων m2>>m1 (?) ξεκινώ και κάνω copy-paste αυτούς.
κτλ κτλ.

Όλοι θα έχουμε δοκιμάσει να βρούμε τους βέλτιστους αριθμούς m1,m2,m3 διαισθητικά.
έχει σκεφτεί κανείς να βρει την ακριβή λύση του προβλήματος μαθηματικά;
Καμιά ιδέα;

Θεωρούμε το "κόστος" του copy-paste =2 χαρακτήρες ή και 3 αν προτιμάτε.
Η λύση του προβλήματος έχει ενδιαφέρον και μπορεί εύκολα να επεκταθεί και για κάποια φράση,pattern σε σχεδιαστικό πρόγραμμα και πολλές ακόμη εφαρμογές.

Πάρα πολύ ενδιαφέρον! Αν βρω λίγο χρόνο θα προσπαθήσω να το λύσω!

Μια διευκρίνηση... επιτρέπεται να ξεπεράσουμε τον αριθμό Ν ή να κάνουμε copy ένα τμήμα του κειμένου ώστε να φτάσουμε ακριβώς το Ν;

Αν επιτρέπεται να ξεπεράσουμε το Ν νομίζω βρήκα τη λύση (για κόστος 2 των copy-paste), αλλά είναι πολύπλοκη και έχει διάφορες περιπτώσεις. Αν μιλούσαμε για κάποια φράση ή κάποιο pattern το οποίο θέλουμε να αναπαράγουμε τότε είναι απλούστερο. Όμως με τους απλούς χαρακτήρες μπλέκεται και το πόσους χαρακτήρες θα πληκτρολογήσεις στην αρχή χωρίς copy-paste, που "κοστίζουν" το 1/2 ή το 1/3 από το κάθε copy ή paste.
Θέλω αρκετή ώρα να διατυπώσω τη λύση, μάλλον θα κάτσω αύριο. Να τη στείλω σε κάποιο mail σου fugitive για να μην τη δημοσιεύσω εδώ;

Αλέξης Γελαστόπουλος, υποψήφιος συμφοιτητής σας ;)

Ωραίο το πρόβλημά σου fugitive, προτείνω όμως αντί μαθηματικής λύσης λαμβάνοντας υπόψιν το κόστος που ανέφερες, να ψάξουμε για την καλύτερη δυνατή προγραμματιστική λύση με κριτήριο το χρόνο εκτέλεσης του προγράμματος.

ΥΓ: Χαιρετίσματα στον υποψήφιο συμφοιτητή

Ψάξε μήπως βγάλεις άκρη με την εντολή του word: =rand(a,b) όπου α ο αριθμός παραγράφων και όπου b ο αριθμός των σειρών ανά παράγραφο.

Τώρα πως θα αλλάξει το κείμενο της παρουσίασης των γραμματοσειρών σε κάτι άλλο ... είναι ένας "γρίφος"

Εξάλλου θέλει αρετή και τόλμη η Ελευθερία!!!

Αποποίηση ευθύνης:
δεν είμαι υπεύθυνος αν κάποιος γράψει =rand(200,99) ή περισσότερο και κολήσει το pc του...  :D

Ναι μπορείς να το ξεπεράσεις. Μετά θα χρειαστείς απλώς 1-2 εντολές Delete.

Καλως ήρθες στην κοινότητα του ΤΗΜΜΥ.gr

ΥΓ: Πώς μας ανακάλυψες;

Έστειλα τη λύση στο email σου fugitive


Έψαχνα πληροφορίες για τη σχολή, πριν και μετά το μηχανογραφικό. Δε θυμάμαι που βρήκα το link, αλλά αμέσως έκανα bookmark τη σελίδα.

Εμείς δεν θα μάθουμε?  :P

Κ.Ι.Σ.

Kallis καλύτερα τώρα? (http://www.thmmy.gr/index.php?option=com_smf&Itemid=41&?topic=2110.from1124568325;topicseen#msg12005)
:P :P :P

Ευτυχώς που υπάρχει και η νοικοκυρά μας (ή μήπως e-κοκυρά) εδώ πέρα και τακτοποιεί αμέσως τις συζητήσεις "εντός θέματος"...  :D :D :D    :P

Κ.Ι.Σ.

Επειδή το ζήτησε ο Καλ.
και για να μη χαρακτηριστώ "μοναχοφάης" κάνω....
copy-paste απο το μαιλ μου

Γεια χαρά,
Ορίστε η λύση του γρίφου. Εϊναι λίγο δύσκολο να την παρακολουθήσεις, δεν
μπορούσα να τα γράψω πιο απλά... Ελπίζω να τα καταφέρεις!

Έστω ότι αρχικά γράφουμε ακριβώς α χαρακτήρες χωρίς copy-paste. Το κόστος
μέχρι εδώ είναι α χαρακτήρες.
Κάθε φορά για να διπλασιάσουμε το κείμενο που έχουμε γράψει πρέπει να
κάνουμε μία φορά copy και μία φορά paste. Αυτό θα μας κοστίσει συνολικά 4
χαρακτήρες. Αν θέλαμε να τριπλασιάσουμε το κείμενο θα κάναμε μία φορά copy
και 2 φορές paste, που θα κόστιζε 6 χαρακτήρες. Γενικά για να
πολλαπλασιάσουμε το κείμενο που έχουμε γράψει με τον αριθμό n, μας κοστίζει
2n χαρακτήρες: 2 για το copy και 2n-2 για τα paste. Θα αποδείξουμε ότι το
μόνο που συμφέρει να κάνουμε είναι να διπλασιάζουμε ή να τριπλασιάζουμε
(κατά περίσταση) το κείμενό μας.
Πράγματι, για να τετραπλασιάσουμε το κείμενο απαιτούνται 8 χαρακτήρες. Αλλά
με το ίδιο κόστος μπορούμε να το διπλασιάσουμε δύο φορές και έτσι να έχουμε
το ίδιο αποτέλεσμα. ʼρα δε θα χρειαστεί ποτέ να τετραπλασιάσουμε. Για να
πενταπλασιάσουμε κοστίζει 10 χαρακτήρες, αλλά με τους ίδιους χαρακτήρες
μπορούμε να διπλασιάσουμε και να τριπλασιάσουμε οπότε έχουμε 6 φορές το
κείμενο. ʼρα δε συμφέρει να πενταπλασιάσουμε. Κάθε αριθμός μεγαλύτερος του 5
γράφεται στη μορφή 3κ, 3κ+1 ή 3κ+2, με κ μεγαλύτερο ή ίσο του 2. Για να
πολλαπλασιάσουμε το κείμενό μας με τον αριθμό 3κ ή 3κ+1 ή 3κ+2 μας κοστίζει
2*(3κ) ή 2*(3κ+1) ή 2*(3κ+2) χαρακτήρες. Όμως, με 2*3 χαρακτήρες μπορούμε να
τριπλασιάσουμε το κείμενο και αν επαναλάβουμε κ φορές θα έχουμε 3^κ φορές το
κείμενο με κόστος 2*3*κ χαρακτήρες. Με μαθηματική επαγωγή εύκολα
αποδεικνύεται ότι για κ μεγαλύτερο ή ίσο του 2 ισχύει 3^κ > 3κ+2 > 3κ+1 >
3κ. ʼρα με ίδιο ή μικρότερο κόστος μπορούμε να έχουμε περισσότερες φορές το
κείμενο τριπλασιάζοντας διαδοχικά αντί να πολλαπλασιάσουμε με 3κ ή 3κ+1 ή
3κ+2, κ μεγαλύτερο ή ίσο του 2.
ʼρα δε συμφέρει να τετραπλασιάσουμε, να πενταπλασιάσουμε, να εξαπλασιάσουμε
κλπ το κείμενο. Αυτό πρακτικά σημαίνει ότι μεταξύ δύο copy θα κάνουμε μόνο
ένα ή δύο paste.
Έστω ότι τους αρχικούς α χαρακτήρες τους διπλασιάσαμε λ φορές και τους
τριπλασιάσαμε μ φορές. Το συνολικό κόστος σε χαρακτήρες είναι α + 4*λ + 6*μ
και τελικά έχουμε α*2^λ*3^μ χαρακτήρες. Θα προσπαθήσουμε να βρούμε το
ελάχιστο κόστος που μπορεί να δώσει Ν ή περισσότερους χαρακτήρες, δηλαδή τα
α, λ, μ για τα οποία α*2^λ*3^μ μεγαλύτερο ή ίσο του Ν και α + 4*λ + 6*μ
ελάχιστο. Για να το βρούμε αυτό θα βρούμε πρώτα το μέγιστο α*2^λ*3^μ που
μπορεί να δώσει κάθε σταθερό άθροισμα α + 4*λ + 6*μ, και στη συνέχεια από τα
μέγιστα που ξεπερνάν το Ν θα πάρουμε αυτό που έχει το ελάχιστο άθροισμα α +
4*λ + 6*μ.

Έστω ότι για κάποια α, λ, μ έχουμε κόστος α + 4*λ + 6*μ. Θα προσπαθήσουμε να
βρούμε άλλους α, λ, μ ώστε το κόστος να είναι ίδιο και οι χαρακτήρες που
γράφουμε περισσότεροι.
Αν λ > 2, τότε ελαττώνοντας το λ κατά 3 και αυξάνοντας το μ κατά 2, το
κόστος παραμένει το ίδιο, αφού α + 4*(λ-3) + 6*(μ+2) = α + 4*λ � 12 + 6*μ +
12 = α + 4*λ + 6*μ, ενώ οι χαρακτήρες που παίρνουμε αυξάνονται, αφού
α*2^(λ-3)*3^(μ+2) = α*2^λ*3^μ*9/8. ʼρα, κάθε φορά που λ > 2 μπορούμε να
ελαττώσουμε το λ κατά 3 και να αυξήσουμε το μ κατά 2 και να έχουμε
περισσότερους χαρακτήρες με το ίδιο κόστος. Επομένως για κάθε κόστος ο
μέγιστος αριθμός χαρακτήρων που μπορούμε να γράψουμε είναι για λ=0 ή λ=1 ή
λ=2.

Τώρα θα προσπαθήσουμε να περιορίσουμε τις τιμές του α.
Θα πάρουμε αρχικά την περίπτωση που μ > 0. Αν ελαττώσουμε το μ κατά 1, για
να διατηρηθεί το άθροισμα α + 4*λ + 6*μ πρέπει το α να αυξηθεί κατά 6. Όμως
επειδή με τη μείωση του μ, το α*2^λ*3^μ διαιρείται με το 3, για να μας
συμφέρει η ελάττωση του γ και η αύξηση του α θα πρέπει η αύξηση του α να
συνεπάγεται πολλαπλασιασμό του α*2^λ*3^μ με αριθμό μεγαλύτερο του 3, δηλαδή
(α+6) > 3α ή α < 3. Έτσι, αν α < 3 αυξάνουμε το α κατά 6 και ελαττώνουμε το
μ κατά 1. Βλέπουμε ότι το α δε χρειάζεται να αυξηθεί αν είναι μεγαλύτερο ή
ίσο του 3. Την περίπτωση που α < 3 και μ = 0 θα την εξετάσουμε ξεχωριστά στο
τέλος.
Εδώ μπορούμε να θεωρήσουμε το α μεγαλύτερο ή ίσο του 3 (αφού αν α < 3 το
αυξάνουμε κατά 6 και ελαττώνουμε το μ κατά 1)

Θα δοκιμάσουμε τώρα πότε μας συμφέρει να αυξήσουμε το μ κατά 1 και να
ελαττώσουμε το α κατά 6, ώστε το α + 4*λ + 6*μ να διατηρηθεί σταθερό. Η
αύξηση του μ συνεπάγεται πολλαπλασιασμό του α*2^λ*3^μ με το 3. ʼρα αυτή η
κίνηση μας συμφέρει αν α-6>α/3 δηλαδή α>9, ενώ είναι ουδέτερη αν α=9, οπότε
γίνεται α=3. Αφού η κίνηση μας συμφέρει (ή είναι ουδέτερη) για α >= 9
μπορούμε να θεωρήσουμε α <= 8.
Επομένως α=3 ή α=4 ή α=5 ή α=6 ή α=7 ή α=8.
Στην περίπτωση που α=8, μπορούμε να κάνουμε το α ίσο με 4 και να αυξήσουμε
το β κατά 1, οπότε το άθροισμα α + 4*λ + 6*μ και το γινόμενο α*2^λ*3^μ
παραμένουν σταθερά. Οπότε για κάθε κόστος ο μέγιστος αριθμός χαρακτήρων που
μπορούμε να γράψουμε είναι για α=3 ή α=4 ή α=5 ή α=6 ή α=7.

Έστω τώρα ότι 3^γ<Ν<=3^(γ+1). Για κάθε ζεύγος α, λ υπάρχει μοναδικός αριθμός
μ που εξαρτάται από το γ τέτοιος ώστε 3^γ < α*2^λ*3^μ <= 3^(γ+1). Οι τριάδες
α, λ, μ δίνουν ένα άθροισμα α + 4*λ + 6*μ. Από τις τριάδες που έχουν ίδιο
άθροισμα α + 4*λ + 6*μ θα επιλέξουμε εκείνη με το μεγαλύτερο γινόμενο
α*2^λ*3^μ, για την οποία γνωρίζουμε ότι θα είναι μία από αυτές που 0 <= λ <=
2 και 3 <= α <= 7 και έτσι θα έχουμε βρει το μεγαλύτερο αριθμό χαρακτήρων
(γινόμενο α*2^λ*3^μ) που μπορούμε να γράψουμε για κάθε συγκεκριμένο κόστος,
ξεκινώντας από το κόστος που μόλις μπορεί να ξεπεράσει τους 3^γ χαρακτήρες
και σταματώντας σε αυτό που φτάνει ή ξεπερνάει τους 3^(γ+1) χαρακτήρες.
Έπειτα θα επιλέξουμε το ελάχιστο κόστος που δίνει χαρακτήρες που φτάνουν ή
ξεπερνούν το Ν.
Στον παρακάτω πίνακα για κάθε δυνατό ζεύγος α, λ βρίσκουμε το μ, το κόστος
(α + 4*λ + 6*μ) και τους χαρακτήρες (α*2^λ*3^μ) συναρτήσει του γ.

α   λ   μ      κόστος   χαρακτήρες (*3^(γ-2))
3   0   γ      6γ+3       27   *
3   1   γ-1   6γ+1      18
3   2   γ-2   6γ-1       12
4   0   γ-1   6γ-2       12   *
4   1   γ-1   6γ+2      24   *
4   2   γ-2   6γ          16   *
5   0   γ-1   6γ-1      15    *
5   1   γ-2   6γ-3      10    *
5   2   γ-2   6γ+1      20
6   0   γ-1   6γ          15
6   1   γ-2   6γ-2      12
6   2   γ-2   6γ+2      24
7   0   γ-1   6γ+1      21   *
7   1   γ-2   6γ-1       14
7   2   γ-3   6γ-3      28/3

Οι μόνοι τρόποι για να έχουμε κάποιο κόστος από τα 6γ-2, 6γ-1,�, 6γ+2 με 0
<= λ <= 2 και 3 <= α <= 7 είναι αυτοί που εμφανίζονται στον πίνακα, αφού σε
οποιοδήποτε ζεύγος α, λ αν αυξήσουμε το μ κατά 1 το κόστος γίνεται 6γ+3 ή
παραπάνω, ενώ αν το μειώσουμε κατά 1 το κόστος γίνεται 6γ-3 ή λιγότερο. ʼρα
ο μέγιστος αριθμός χαρακτήρων που μπορούμε να γράψουμε με κάθε κόστος από
6γ-2 έως 6γ+2 είναι ο μεγαλύτερος από αυτούς που εμφανίζονται στον πίνακα
για το συγκεκριμένο
 κόστος.

Για να έχουμε κόστος 6γ-3 με 0 <= λ <= 2 και 3 <= α <= 7 οι μόνοι τρόποι
είναι αυτοί που εμφανίζονται στον πίνακα καθώς και αν α = 3, λ = 0 και μ =
γ-1, που προκύπτει αν στην πρώτη γραμμή του πίνακα ελαττώσουμε το μ κατά 1.
Όμως σε αυτή την περίπτωση οι χαρακτήρες δεν ξεπερνούν το 10*3^(γ-2) που
δίνονται από την 8η γραμμή του πίνακα. ʼρα με κόστος 6γ-3 μπορούμε να έχουμε
μέχρι 10*3^(γ-2) χαρακτήρες.

Έστω ότι υπάρχει κόστος μικρότερο από 6γ-3 τέτοιο ώστε να δίνει
περισσότερους από 3^γ χαρακτήρες. Τότε με το ίδιο κόστος μπορούμε να έχουμε
τους ίδιους ή περισσότερους χαρακτήρες για 0 <= λ <= 2 και 3 <= α <= 7. Αφού
το κόστος είναι μικρότερο από 6γ-3 και τα α, λ είναι ίδια με κάποιο ζεύγος
στον πίνακα, συμπεραίνουμε ότι το μ είναι μικρότερο από το αντίστοιχο στον
πίνακα. Αν αυξήσουμε το μ κατά 1, τότε το μ θα είναι μικρότερο ή ίσο με αυτό
του πίνακα και θα δίνει περισσότερους από 3^(γ+1) χαρακτήρες, δηλαδή με ίδια
α, λ και μικρότερο ή ίσο μ θα έχουμε μεγαλύτερο γινόμενο α*2^λ*3^μ, που
είναι άτοπο.
ʼρα για 3^γ χαρακτήρες το κόστος είναι τουλάχιστον 6γ-3.

3^(γ+1) χαρακτήρες μπορούμε να έχουμε με κόστος 6γ+3 και όχι μικρότερο, όπως
προκύπτει από τον πίνακα.

Οπότε για κάθε κόστος ο μέγιστος αριθμός χαρακτήρων είναι ο εξής (αστερίσκος
στον πίνακα):
<6γ-3:    < 3^γ
6γ-3:      10*3^(γ-2)
6γ-2:      12*3^(γ-2)
6γ-1:      15*3^(γ-2)
6γ:         16*3^(γ-2)
6γ+1:     21*3^(γ-2)
6γ+2:     24*3^(γ-2)
6γ+3:     >= 27*3^(γ-2) = 3^(γ+1)


Επομένως,
αν 3^γ             < Ν <= 10*3^(γ-2)  τότε α=5, λ=1, μ=γ-2
αν 10*3^(γ-2)  < Ν <= 12*3^(γ-2)  τότε α=4, λ=0, μ=γ-1
αν 12*3^(γ-2)  < Ν <= 15*3^(γ-2)  τότε α=5, λ=0, μ=γ-1
αν 15*3^(γ-2)  < Ν <= 16*3^(γ-2)  τότε α=4, λ=2, μ=γ-2
αν 16*3^(γ-2)  < Ν <= 21*3^(γ-2)  τότε α=5, λ=2, μ=γ-2
αν 21*3^(γ-2)  < Ν <= 24*3^(γ-2)  τότε α=4, λ=1, μ=γ-1
αν 24*3^(γ-2)  < Ν <= 3^(γ+1)      τότε α=3, λ=0, μ=γ

Τώρα θα εξετάσουμε την περίπτωση που μ = 0 και α < 3.
Επειδή λ <= 2, α <=2 και μ = 0, ισχύει α*2^λ*3^μ <= 8. Δηλαδή μας ενδιαφέρει
η περίπτωση που Ν <= 8. Αλλά για Ν <= 8 εύκολα βρίσκεται ότι έχουμε το
μικρότερο κόστος όταν δεν κάνουμε κανένα copy-paste, δηλαδή όταν α = Ν.

Τα προηγούμενα επομένως ισχύουν αν Ν > 8.

Βρίσκουμε τα Μ1, Μ2, Μ3 κλπ
Μ1 = α

Αν λ = 0,               Μ2 = 3*Μ1
Αν λ = 1 ή λ = 2,   Μ2 = 2*Μ1

Αν λ = 0 ή λ = 1,    Μ3 = 3*Μ2
Αν λ = 2,                Μ3 = 2*Μ2

Για ν >= 4 Μν = 3*Μ(ν-1)

Σταματάμε στον ελάχιστο αριθμό ν για τον οποίο Μν >= Ν

Αλέξης Γελαστόπουλος

Καταρχήν ευχαριστούμε τον υποψήφιο συνάδελφο για τη λύση.
Ομολογώ ότι δεν τη διάβασα διεξοδικά λόγω μεγάλου μεγέθους κειμένου και μικρής ποσότητας ελεύθερου χρόνου αυτή τη στιγμή.
Με... διαγώνια ανάγνωσηπου έκανα φαίνεται πολύ καλά μελετημένη και τεκμηριωμένη.
Όταν βρω χρόνο θα παραθέσω και τη δική μου λύση, που ενδεχομένως τελικά να συμπίπτει με του υποψήφιου συναδέλφου.

Το μόνο που μου φαίνεται λίγο παράδοξο θα έλεγα είναι το

Εκφράζοντας τον δεκαδικό αριθμό των ζητούμενων χαρακτήρων στο δυαδικό σύστημα παρατήρησα πως μπορούμε εύκολα να δούμε πόσα copy-paste θα χρειαστούμε για να τον εκφράσουμε ακριβώς εισάγοντας μόνο ένα χαρακτήρα. Έγραψα μια εκδοχή της λύσης αυτού του προβλήματος σε κώδικα και σας το παραθέτω. Αν και δεν έχει πολλή σχέση με το αρχικό πρόβλημα που έθεσε ο fugitive, είναι αρκετά ενδιαφέρον. Είναι λίγο πρόχειρος ο κώδικας, αλλά δίνει μια εικόνα του συλλογισμού χωρίς πολλά λόγια.

Το πρόγραμμα μπορεί να γίνει πιο αποτελεσματικό με διαφορετική δομή και δυναμική δέσμευση μνήμης για να υποστηρίζει μεγαλύτερους αριθμούς. Τώρα που το ξαναβλέπω μου φαίνεται πως θα ήταν πολύ καλύτερα να δουλεύει εντελώς αντίστροφα :P . Εν πάσει περιπτώσει, ήταν μια πρώτη σκέψη.

Λοιπόν παραθέτω και τη δική μου "λύση" ή καλύτερα προσπάθεια επίλυσης.
Είναι γενική ώστε να μην περιλαμβάνει μόνο χαρακτήρες αλλά και οποιοδήποτε pattern.
Έχουμε λοιπόν:
Αρχικά γράφουμε Κ1 χαρακτήρες (ή patterns στο εξής θα αναφέρονται με την κοινή ονομασία χαρακτήρες).
Κατόπιν κάνουμε αυτούς copy-paste (CP) Κ2 φορές.
Επομένως τώρα έχουμε Κ1*Κ2 χαρακτήρες.
Κάνουμε αυτό το σύνολο τώρα CP Κ3 φορές οπότε και έχουμε τώρα Κ1*Κ2*Κ3 χαρακτήρες.
Κατά τον ίδιο τρόπο συνεχίζουμε φτάνοντας έναν αριθμό Μ>Ν=ζητούμενο,
όπου Μ ο αριθμός χαρακτήρων που για πρώτη φορά θα υπερβεί το Ν.
Επομένως έχουμε Μ=Κ1*Κ2*...*Κν
και ζητούμε τα Ki τέτοια ώστε
P=K1+K2+K3+....+Kn να είναι ελάχιστο.

Εάν θεωρήσουμε αρχικά αμελητέο το κόστος σε εντολές του CP τότε η λύση είναι μάλλον απλή
αφού αυτό το άθροισμα γίνεται ελάχιστο όταν κάθε όρος από αυτούς γίνει ελάχιστος
και μετά από λίγες πράξεις καταλήγουμε ότι K1=K2=...Kn=2.
(το ένα απορρίπτεται αυφού δεν αυξάνει το γινόμενο)
Π.χ. για Ν=100 έχουμε
P=K1+K2+...K7=2*7=14.
ενώ αν K1=K2=10 έχουμε P=20.


Λοιπόν παραθέτω και τη δική μου "λύση" ή καλύτερα προσπάθεια επίλυσης.
Είναι γενική ώστε να μην περιλαμβάνει μόνο χαρακτήρες αλλά και οποιοδήποτε pattern.
Έχουμε λοιπόν:
Αρχικά γράφουμε Κ1 χαρακτήρες (ή patterns, στο εξής θα αναφέρονται με την κοινή ονομασία χαρακτήρες).
Κατόπιν κάνουμε αυτούς copy-paste (CP) Κ2 φορές.
Επομένως τώρα έχουμε Κ1*Κ2 χαρακτήρες.
Κάνουμε αυτό το σύνολο τώρα CP Κ3 φορές οπότε και έχουμε τώρα Κ1*Κ2*Κ3 χαρακτήρες.
Κατά τον ίδιο τρόπο συνεχίζουμε φτάνοντας έναν αριθμό Μ>Ν=ζητούμενο,
όπου Μ ο αριθμός χαρακτήρων που για πρώτη φορά θα υπερβεί το Ν.
Επομένως έχουμε Μ=Κ1*Κ2*...*Κν
και ζητούμε τα Ki τέτοια ώστε
P=K1+K2+K3+....+Kn να είναι ελάχιστο.

το άθροισμα γίνεται ελάχιστο όταν κάθε όρος από αυτούς γίνει ελάχιστος
και μετά από λίγες πράξεις καταλήγουμε ότι K1=K2=...Kn=2.
(το ένα απορρίπτεται αυφού δεν αυξάνει το γινόμενο)

Π.χ. για Ν=100 έχουμε
P=K1+K2+...K7=2*7=14.
ενώ αν K1=K2=10 έχουμε P=20.

Μέχρι τώρα, σιωπηρά υποθέσαμε ότι το κόστος σε εντολές του CP είναι αμελητέρο κάτι όμως που δεν ισχύει στην πραγματικότητα. Αυτό που πραγματικά συμβαίνει, είναι ότι σε κάθε copy θα μπορούσαμε να γράφαμε άλλον έναν χαρακτήρα, ομοίως και σε κάθε paste.
Εδ'ω μπλέκεται λίγο το θέμα.
Νέες ιδέες;

Πιο αναλυτικά θα έγραφα το εξής:

Άρα δε συμφέρει να τετραπλασιάσουμε, να πενταπλασιάσουμε, να εξαπλασιάσουμε
κλπ το κείμενο. Επομένως, το μόνο που θα κάνουμε είναι να διπλασιάζουμε ή να τριπλασιάζουμε το κείμενο που έχουμε κάθε φορά. Αυτό πρακτικά σημαίνει ότι μεταξύ δύο copy θα κάνουμε μόνο
ένα ή δύο paste.

Σημείωση: Για να διπλασιάσουμε το κείμενο κάνουμε copy, μετά μία φορά paste και μετά ξανακάνουμε copy όλο μαζί (εκτός αν έχουμε φτάσει το Ν). Για να τριπλασιάσουμε κάνουμε copy, δύο φορές paste και μετά πάλι copy όλο μαζί. Άρα μεταξύ δύο copy κάνουμε ένα ή δύο paste.


 :???: Ομολογώ πως αυτό δεν το έλαβα υπόψη. Έτσι όμως μπλέκεται πάάάάάρα πολύ το θέμα  :-\

Αν βγάλουμε μια συνάρτηση πολλών μεταβλητών απο το όλο θέμα και βρούμε το ολικό ελάχιστο?

Χωρίς να έχω εμπειρία από συναρτήσεις πολλών μεταβλητών, δε νομίζω ότι γίνεται αυτό για τους εξής λόγους:
1) Δε μας ενδιαφέρει να έχουμε ακριβώς Ν χαρακτήρες αλλά μπορούμε να έχουμε και περισσότερους, οπότε μας λείπει μια ισότητα
2) Η συνάρτηση που ψάχνουμε θα ορίζεται στους φυσικούς, που σημαίνει ότι δε θα είναι συνεχής κλπ κλπ (σύμφωνα με αυτά που μάθαμε στη γ' λυκείου... δεν ξέρω αν υπάρχει κανένα άλλο κόλπο για να βρεις ολικό ελάχιστο σε ακολουθία)

Στη δικιά μου "λύση" έψαχνα την ελάχιστη τιμή του (α+4λ+6μ), ώστε α*(2^λ)*(3^μ) >= Ν, όπου α,λ,μ φυσικοί. Μπορεί να εφαρμοστεί τίποτα εδώ για να βρεθεί η ελάχιστη τιμή; Εγώ χρησιμοποίησα μπακάλικες μεθόδους, γι' αυτό και η "λύση" που έγραψα είναι τόσο μεγάλη (τα 2/3 αφορούν το συγκεκριμένο πρόβλημα)

Νομίζω ότι αν πάρουμε υπόψη και αυτό που ανέφερε ο fugitive (χαρακτήρες μεταξύ των copy-paste) θα έχουμε ένα παρόμοιο πρόβλημα αλλά πολύ πιο πολύπλοκο.

Κατ' αρχας να καλωσορισω κι εγω το φιλο Junior στο forum και να του ευχηθω καλα αποτελεσματα! Ειναι 4:40, σε λιγοτερο απο 5,5 ωρες απο τωρα, ευχομαι να μπορεσουμε να τον καλωσορισουμε και στο τμημα!

Κρατα γερα συναδελφε! Αλλα ακομα κι αν δεν περασεις, μην σε παρει απο κατω... Κι εγω με τη δευτερη μπηκα, και μαλιστα ξεκινησα να διαβαζω Μαρτιο για τη δευτερη φορα ;)


Λοιπον, ωρα να επανελθουμε στην ταξη. Μετα απο 4 ωρες εξαντλητικων υπολογισμων, το προβλημα λυθηκε!
Επισυναπτω pdf με τη λυση.

Αν δεν μπορειτε να το διαβασετε με τα βρωμοwindows σας, πειτε μου να το ανεβασω και σε doc... Αν και παλι δεν μπορεσετε, τον πουλο, παρτε mac ή μεινετε στο σκοταδι και στερηθειτε τη λυση μου  ;D

Ελπιζω να μην εκανα καμια χοντραδα στη λυση...

 :P Εγώ δεν πήρα το p σταθερό! Μάλιστα στην αρχή της λύσης έδειξα ότι το p είναι πάντοτε 2 ή 3, αλλιώς βγαίνουν πάντα ίσα ή περισσότερα κλικ


Τελικά είναι πιο απλό από ότι φαίνεται... Το να προσθέσουμε ένα χαρακτήρα μετά από κάποιο copy ή paste κοστίζει όσο το να προσθέσουμε ένα χαρακτήρα στην αρχή, πριν κάνουμε το πρώτο copy. Μάλιστα αν τον προσθέσουμε στην αρχή, θα τον κάνουμε paste περισσότερες φορές από ότι αν τον προσθέσουμε κάπου στη μέση, οπότε δεν υπάρχει τέτοιο θέμα... Τελικά λειτουργείς χίλιες φορές καλύτερα με καθαρό μυαλό... ;D


Το άθροισμα P=K1+K2+K3+....+Kn δε γίνεται ελάχιστο όταν κάθε όρος γίνει ελάχιστος, αφού τότε έχουμε περισσότερους όρους!

Ενδεικτικά, για N=100 μια καλύτερη λύση είναι:
Κ1 = 4, Κ2 = 3, Κ3 = 3, Κ4 = 3
P=Κ1+Κ2+Κ3+Κ4 = 4+3+3+3 = 13 και Μ=Κ1*Κ2*Κ3*Κ4 = 4*3*3*3=4*27=108

Αξίζει να σημειώσουμε ότι η δική σου λύση αφορά την περίπτωση που κάθε copy και κάθε paste κοστίζει όσο ένας χαρακτήρας, ενώ εγώ πήρα να κοστίζει όσο 2 χαρακτήρες.

έχεις απόλυτο δίκιο!
Ευτυχώς δηλαδή γιατί αλλιώς θα ήμασταν μπροστά στο παράδοξο του απλού διπλασιασμού.

Εκείνο που έρχεται σε αντίθεση με τη διαίσθηση, αλλά φυσικά εμείς σαν μηχανικοί δε μασάμε, και είναι άξιο σχολιασμού είναι ότι δεν παίζει ρόλο η σειρά χ-σιασμού.
Ο απλός χρήστης ίσως θα περίμενε ότι η βέλτιστη σειρά είναι 3--3-3-4, (το μεγαλύτερο στο μεγαλύτερο τμήμα)
και η χείριστη 4-3-3-3

Καλά, σε μένα γιατί δε δίνει κανείς σημασία? :P Διαφωνείτε πλήρως με την ιδέα της μετατροπής του δεκαδικού σε δυαδικό? Εξηγούμαι καλύτερα: Έστω ότι χρειαζόμαστε 100 χαρακτήρες (δηλ. τον αριθμό 01100100). Ξεκινώντας από τα αριστερά προς τα δεξιά, προσπερνούμε το 0 και προχωρούμε στον πρώτο άσσο (2ο ψηφίο). Παρατηρούμε ότι το 2ο ψηφίο μπορεί να προκύψει από το διπλασιασμό του 3ου ψηφίου. Προχωρούμε στο 3ο ψηφίο. Παρατηρούμε ότι μπορεί να προκύψει από τον διπλασιασμό του 6ου ψηφίου, copy-paste του αποτελέσματος (πάμε στο 5ο ψηφίο) και μετά ξανά copy-paste του αποτελέσματος (πάμε στο 4ο ψηφίο), προχωρούμε στον επόμενο άσσο που είναι το 6ο ψηφίο κλπ.

Ενδεικτική έξοδος του προγράμματος:

integer: 100

0000000001100100

+ copy-paste 2 fores 32 xaraktires
+ copy-paste 1 fora 16 xaraktires
+ copy-paste 1 fora 8 xaraktires
+ copy-paste 2 fores 4 xaraktires
+ copy-paste 1 fora 2 xaraktires
+ copy-paste 1 fora 1 xaraktira
+ eisagwgi enos xaraktira

+ sinolika exoun ginei 8 copy-paste