Задача D. Магiчнi послiдовностi
        
            Submit solution
        
    
    
    
    
    
    
    
    
    
                    
                
        
            
        
        Points:
        
                100        
    
    
        Time limit:
        1.0s
    
    
        Memory limit:
        256M
    
    
                        Author:
                        
                    
        
                    Problem type                
                
        
                Allowed languages
            
            
C++            
        Назвемо послiдовнiсть довжини \(N\) з двох чисел магiчною, якщо в нiй будь-яка пiдпослiдовнiсть з двох або бiльше однакових чисел має парну довжину.
Необхiдно порахувати кiлькiсть таких магiчних послiдовностей.
Обмеження:
- \(1 \le N\), \(A\), \(B \le 32\)
Формат входових даних:
Три цiлих числа: \(N\), \(A\), \(B\).
Формат виходових даних:
Одне цiле число --- кiлькiсть таких послiдовностей.
Приклад входових даних:
3 1 2Приклад виходових даних:
6Пояснення:
\(N=3\), а числа, якi можна використовувати: \(1\) та \(2\). Перелiчимо всi можливi послiдовностi та перевiримо їх:
- \([1, 1, 1]\) — Недопустимо (три одиницi поспiль).
- \([1, 1, 2]\) — Допустимо (двi одиницi, одна двiйка).
- \([1, 2, 1]\) — Допустимо (одиницi та двiйка поодинцi).
- \([1, 2, 2]\) — Допустимо (одиниця, двi двiйки).
- \([2, 1, 1]\) — Допустимо.
- \([2, 1, 2]\) — Допустимо.
- \([2, 2, 1]\) — Допустимо.
- \([2, 2, 2]\) — Недопустимо.
Загальна кiлькiсть допустимих послiдовностей: \(6\).
Comments