COCI-09 (2009) - Γύρος #4 - 5 (Kaboom)

View as PDF

Submit solution

Points: 45 (partial)
Time limit: 0.3s
Memory limit: 32M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python
Kaboom

Ο Luka βρήκε μια ενδιαφέρουσα ταινία στο χημικό εργαστήριο. Η ταινία χωρίζεται σε N τμήματα ίσου μήκους και μπορεί εύκολα να κάμπτεται μεταξύ δύο τμημάτων, αλλά μόνο κατά 180 μοίρες ακριβώς.
Η μία πλευρά της ταινίας καλύπτεται πλήρως με μια πολύ ασταθή χημική ουσία. Αν το χημικό έρθει σε επαφή με τον εαυτό του, φτάνει σε κρίσιμη μάζα και εκρήγνυται.
Η άλλη πλευρά της ταινίας δεν έχει καλυφθεί ακόμη πλήρως. Μόνο τα πρώτα A τμήματα και τα B τελευταία τμήματα είναι καλυμμένα, με την ίδια ακριβώς χημική ουσία.

Γράψτε ένα πρόγραμμα που θα υπολογίζει τον αριθμό των διαφορετικών τρόπων με τους οποίους μπορεί να λυγίσει ο Luka ταινία χωρίς να εκραγεί. Μπορεί να λυγίσει αν θέλει την ταινία περισσότερες από μία φορές και δύο τρόποι είναι διαφορετικοί, εάν υπάρχει τουλάχιστον μία λοξότμηση μεταξύ των τμημάτων που δεν είναι λυγισμένη στον ένα και είναι λυγισμένη στον άλλο.
Επειδή η λύση μπορεί να είναι τεράστια, εκτυπώστε το modulo αποτελέσματος 10301.
Το παρακάτω παράδειγμα απεικονίζει τους 6 πιθανούς τρόπους για N=4, A=1 και B=1. Διασαφηνίζουμε ότι η ταινία είναι λυγισμένη μόνο 90 μοίρες στην εικόνα. Ο Luka στην πραγματικότητα θα τη λύγιζε 180 μοίρες.

coci09d5-figure.svg
Είσοδος

Η πρώτη και μοναδική γραμμή περιέχει τρεις φυσικούς αριθμούς: των συνολικό αριθμό τμημάτων N, των αριθμό καλυμμένων τμημάτων από το αριστερά A και τον B από τα δεξιά αντίστοιχα. (A > 0,\; B > 0,\; A + B \le N \le 1000).

Έξοδος

Η πρώτη και μοναδική γραμμή πρέπει να περιέχει τον αριθμό των πιθανών τρόπων κάμψης της ταίνίας modulo 10301.

Παραδείγματα

input

4 1 1

output

6

input

5 2 2

output

1

input

6 1 2

output

7

Comments

There are no comments at the moment.