Παρεμπιπτόντως να ο κώδιξ μου:
cocktails
[pastebin]
http://pastebin.com/Hi5G7dTm[/pastebin]
ΕΞΗΓΗΣΕΙΣ:
Πρώτα φτιάχνω ένα δισδιάστατο πίνακα με αναλογίες μεταξύ των υλικών.
Γνωρίζουμε ότι (Αα/Α0)*(Αβ/Αα)=(Αβ/Α0), όπου Αν η σχετική ποσότητα του ποτού ν που μας δίνεται.
Οπότε αν έχουμε τις αναλογίες μερικών ποτών σε σχέση με το ποτό 0, μπορούμε να αρχίσουμε να κατασκευάζουμε τον πίνακα Β, όπου Βν=(Αν/Α0).
Μετά κάνω μια BFS γιατί έτσι μου αρέσει να κάνω flood fill, και έχοντας τον πίνακα Β με ποσά ανάλογα των πραγματικών αναλογιών που χρησιμοποίησε αυτός ο μεθύστακας, εκτυπώνω το ποσοστό του κάθε ενός σε εκατοστά.
amplifiers
[pastebin]
http://pastebin.com/UXY3fmqq[/pastebin]
ΕΞΗΓΗΣΕΙΣ:
Αν κάτσεις να κάνεις ένα γράφημα των διαδοχικών τιμών του A, μπορείς να δεις ότι πρέπει να το πλακοστρώσεις με διαφόρων μεγεθών πλάκες.
Οι πλάκες που έβαλες σε μία γούβα δεν επηρεάζουν τις επόμενες γούβες ή τις πλάκες τους, οπότε μπορούμε να κάνουμε την πλακόστρωση άπληστα και σειριακά σε γραμμικό χρόνο.
Πρώτα απ'όλα χρειαζόμαστε μια στοίβα για να ξέρουμε μέχρι ποιό ύψος θα γεμίσουμε τη γούβα-δε θέλουμε να βάλουμε στην ίδια (υπο)γούβα δύο πλάκες στο ίδιο ύψος.
Η στοίβα κρατάει το τρέχον υψόμετρό μας στο γράφημα και ποιά σκαλοπάτια έχουμε κατέβει.
Για τον επόμενο αριθμό που θα διαβάσουμε υπάρχουν οι εξής περιπτώσεις:
1)Είναι μεγαλύτερος από το μεγαλύτερο υψόμετρο που έχουμε φτάσει.
Τότε πλακοστρώνουμε όλη τη διαφορά ύψους από εκεί που είμαστε ως εκεί που πρέπει να ανεβούμε και συνεχίζουμε με το Ai ως πλατύσκαλο.
2)Είναι μεγαλύτερος από το τρέχον υψόμετρό μας και μικρότερος από το πλατύσκαλο.
Τότε ανεβαίνουμε ένα ένα τα σκαλοπάτια πετώντας ενισχυτές πίσω μας, μέχρι να συναντήσουμε μεγαλύτερο σκαλοπάτι.
3)Είναι μικρότερος από το τρέχον υψόμετρό μας.
Άλλο ένα σκαλοπάτι κάτω δηλαδή, δε πετάμε ενισχυτές για τώρα.
Στο τέλος μπορεί να βρισκόμαστε πιο κάτω από το πλκατύσκαλο, οπότε αναπληρώνουμε τη διαφορά με μερικούς ενισχυτές και τελειώσαμε.
Χειρότερη περίπτωση:
Ν Ν-1 Ν-2...0 Ν
Πολυπλοκότητα χειρότερης περίπτωσης: 2Ν
Καλύτερη περίπτωση:
Όποια δε προϋποθέτει διαδοχικό ανέβασμα σκαλοπατιών.
Πολυπλοκότητα καλύτερης περίπτωσης:Ν
Αν το ανέβασμα σκαλοπατιών γινόταν με binary search η πολυπλοκότητα ίσως θα γινόταν ΝlogΝ.
Το να μη βάλω άπειρο ως πλατύσκαλο επιταχύνει αρκετά το πρόγραμμα, σε βάλος της αισθητικής.
Η γραμμή 44 είναι η μ@λ@κί@ του να ρίχνω πασιέντζες επί 1 ώρα αντί να κοιτάω τον κώδικά μου.
Αυτό το πρόβλημα πρέπει να είναι παραλλαγή ενός ασημί του USACO, αλλά δεν είναι τόσο εμφανής η λύση και οι πλάκες είναι ορθογώνιες.
rdigits
[pastebin]
http://pastebin.com/6CQWeeHv[/pastebin]
ΕΞΗΓΗΣΕΙΣ:
Ηλίθια λύση με δε ξέρω τι πολυπλοκότητα, αλλά θεωρητικά ορθή.
Τα ψηφία που έπρεπε να βγάλω τα σόρταρα επειδή είχα ένα προαίσθημα που τελικά...δεν έγινε ιδέα εγκαίρως.