2137: Магічні послідовності

Перегляд у форматі PDF
Надіслати розв'язок
Бали: 15,00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
zvit
Problem type

Назвемо послідовність довжини ~N~ з двох цілих чисел ~A~ і ~B~ магічною, якщо в ній будь-яка підпослідовність з двох або більше однакових чисел має парну довжину.

Необхідно порахувати кількість таких магічних послідовностей.

Обмеження

- ~1 \le N, A, B \le 32~

Input

Три цілих числа: N, A, B

Output

Одне ціле число — кількість таких послідовностей.

Sample Input 1

3 1 2

Sample Output 1

6

Notes

~N~=3, числа, які можна використовувати: 1 та 2.

Перелічимо всі можливі послідовності та перевіримо їх:

  • [1, 1, 1] — Недопустимо (три одиниці поспіль).
  • [1, 1, 2] — Допустимо (дві одиниці, одна двійка).
  • [1, 2, 1] — Допустимо (одиниці та двійка поодинці).
  • [1, 2, 2] — Допустимо (одиниця, дві двійки).
  • [2, 1, 1] — Допустимо.
  • [2, 1, 2] — Допустимо.
  • [2, 2, 1] — Допустимо.
  • [2, 2, 2] — Недопустимо.

Загальна кількість допустимих послідовностей — 6.

Коментарі

Please read the guidelines before commenting.


  • 0
    Folela  commented on Жов. 8, 2025, 6:24 після полудня

    A може дорівнювати B?


    • 0
      judge  commented on Жов. 9, 2025, 7:52 до полудня

      так


  • 0
    pcheloveks69  commented on Жов. 8, 2025, 8:42 до полудня
    1. Чи потрібно робити обчислення по модулю? 2. Як тут визначається підпослідовність? 3. A, B представляють собою допустимі в послідовності числа?

    • 0
      judge  commented on Жов. 8, 2025, 10:07 до полудня
      1. ні
      2. Підпослідовність це люба довжина послідовності від 1 до максимальної довжини.
      3. так

      • 0
        pcheloveks69  commented on Жов. 8, 2025, 10:39 до полудня

        То підпослідовність тут — це послідовність, яку можна отримати видаленням деяких довільних елементів без зміни порядку інших, чи послідовність, яку можна отримати видаленням елементів лише з початку та кінця?


        • 0
          judge  commented on Жов. 8, 2025, 11:27 до полудня

          Підпослідовність це видалення елементів з початку та кінця


          • 0
            zhukso  commented on Жов. 16, 2025, 4:23 після полудня ← відректований

            Але ж.. Загальновживаний термін підпослідовність - це будь-яка підмножина без зміни порядку ¯\(ツ)/¯


            • 0
              judge  commented on Жов. 17, 2025, 4:50 до полудня ← відректований

              Так, це вірно. Попередній пост - це відповідь на запитання. Окремо це твердження немає змісту.


              • 0
                zhukso  commented on Жов. 19, 2025, 7:54 після полудня

                Або я все ж таки щось не бачу в умові, або щось не те з тестами 6 і 9 :) Бо я вже три розв'язки звірив і навіть з брутом на додачу, на всіх N від 1-32 співпадає результат :)

                Про всяк випадок, перепитаю, чи я правильно розумію: для визначення магічності порівнюються саме числа, не цифри (тобто їх або один або два види - A і B). Підрядок (те що в умові підпослідовність) - довільний, що складається з однакових чисел (тобто тільки AAAA чи тільки BBBB якщо A!=B) а не тільки участки з однакових елементів. (тобто в 12 22 12 12 12 12 22 22 є підрядки з 1, 2, 3 і 4 однаковими елементами тому послідовність не є магічною, а наприклад послідовність 12 22 - магічна)


                • 0
                  judge  commented on Жов. 20, 2025, 6:50 до полудня

                  Ваш приклад 12 22 12 12 12 12 22 22 є магічною послідовністю, і в умові завдання немає вимоги, що A!=B. Тест №6: 6 1 1


                  • 0
                    zhukso  commented on Жов. 22, 2025, 11:02 до полудня

                    Мені вже незручно забирати час... але ж в {12 22 12 12 12 12 22 22} є підрядок з трьома (непарною кількістю) однакових елементів наприклад з 2 (1-based) по 5: {22 12 12 12} Відповідно будь-яка послідовність довжини більше 2, що складається з однакових (тест 6 1 1) чисел не є магічною, адже в ній існує підрядок з однакових елементів непарної довжини.

                    Гіпотезу, що в умові мається на увазі "усі участки послідовності, на яких числа не змінюються, мають парну довжину або довжину 1"? я перевіряв :), там ще більше тестів не пройшло (4,7,8,10), тому я її відкинув. Хіба що для a=b та a!=b інтерпретація умови має бути різною.

                    PS. "пофікшений" варіант, в якому для різних a!=b вважається, що будь-яка послідовність з трьома і більше однаковими елементами поспіль немагічна, для a=b вважається, що якщо вона парної довжини, то вона магічна, заходить на 100% ¯\(ツ)/¯


                    • 0
                      judge  commented on Жов. 22, 2025, 2:32 після полудня

                      {12 22 12 12 12 12 22 22} Розбиваємо на підпослідовності, які складаються з однакових чисел 1) 12 2) 22 3) 12 12 12 12 4) 22 Кожна з цих підпослідовностей має довжину 1 або парну довжину. Тому дана послідовність магічна


                      • 0
                        zhukso  commented on Жов. 22, 2025, 8:25 після полудня

                        Так, проблема в тому, що я таку інтерпретацію перевіряв :) Схоже, що вона така для тестів з A==B. Але або проблема з тестами або солюшеном для A!=B. (я все ж пропихнув розв'язок на 100% в дорішці і він "гібридний" - по одній інтерпретації для A==B і по іншій в A!=B). Я не наполягаю, для обох варіантів я написав брутфорсний варіант по всіх двійкових векторах і порівняв для усіх n 1..32, все співпало. Інтерпретації починають розходись для A!=B починаючи з n=5. тест, умовно, 5 1 0 дає 20 в одній інтерпретації і 16 в іншій по першій інтерпретації "магічні", зокрема {10000, 00001, 11110, 00001}, а по іншій - ні. (ви стверджуєте, що перша інтерпретація правильна, але по тестам заходить друга)

                        PS. якщо я надаю тут надто багато інформації по задачі, можете стерти цей коментар, зі мною зв'язатись можна по емейлу s.o.zhuk.rl{ет}gmail.com або через месенджер. Ще раз вибачайте за занудство :)


                        • 0
                          zvit  commented on Жов. 23, 2025, 5:54 до полудня

                          Ні, інформація ця корисна. Вітаю з успішною здачею!


          • -2
            misahko  commented on Жов. 8, 2025, 7:45 після полудня

            Якщо підпослідовність це видалення елементів лише з кінця або початку, то чому 1 2 1 підходить? Якщо видаляти числа лише з кінця або початку ми не отримаємо парну послідовність однакових чисел.


            • 0
              judge  commented on Жов. 9, 2025, 7:09 до полудня ← відректований

              Видаляти маємо право як окремо з країв так і одночасно. Парна підпослідовність вважається такою, що підряд йдуть однакові числа і їх кількість парна (це правило тільки стосується де підпослідовність 2 і більше підряд чисел, якщо числа чергуються по одному разу то це також підходить). Дивіться уважно пояснення з прикладами.