1685: Красиві трійки

Перегляд у форматі PDF

Надіслати розв'язок

Бали: 25
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Для даної послідовності \(a\), яка містить \(n\) цілих чисел у зростаючому порядку, трійка чисел (\(a_i, a_j, a_k\)) є красивою, якщо:

  • \(i < j < k\)

  • \(a_j - a_i = a_k - a_j = d\)

Підрахуйте кількість красивих трійок у послідовності \(a\).

Формат вхідних даних

Перший рядок вхідного потоку містить два цілі числа \(n,d\) (\(1 \le n \le 10^4\), \(1 \le d \le 20\)).

Наступний рядок містить елементи послідрвності \(a_i\) (\(0 \le a_i \le 2 \times 10^4\))

Формат вихідних даних

У вихідний потік вивести кількість красивих трійок.

Примітка

Красиві трійки: (1, 4, 7), (4, 7, 10), (2, 5, 8)

Приклад вхідних даних

7 3
1 2 4 5 7 8 10

Приклад вихідних даних

3

Коментарі


  • 2
    hardLY  commented on Березень 22, 2022, 5:51 після полудня відректований

    Добро дня. У мене є запитання та зауваження по цій задачі. Перше, ліміт на викнання одного блоку тестів - 1с. У задачі 8 блоків тестів, отже максимальний час виконання задачі - 8с. Але якщо відкрити "Кращі відправки", то можна побачити, що у користувача "Даринка" задача працює 8,01с, і вона зарахована. Чому так? Друге, я написав програму яка правильно рахує, але три останні блоки не проходила через ліміт часу, я її максимально оптимізував, і навіть переписав програму на C++, але все одно не проходить. Перевірте буль ласка тести починаючи із шостого. Дякую


    • 0
      Dead_Moroz  commented on Березень 23, 2022, 4:38 після полудня

      Троє людей здало її на С++ і одна на Пайтоні. Правильно написане рішення чудово поміщається в обмеження. Проблема не в тестах)


      • 0
        hardLY  commented on Березень 24, 2022, 12:11 до полудня

        Ти не зрозумів що я писав про того хто здав на Пайтоні, перечитай.


        • 1
          zvit  commented on Березень 24, 2022, 9:34 до полудня редагувати 3

          Time limit 1 с виділяється системою для роботи одного тесту для більшості мов програмування. Для Пайтона інколи ми окремо виділяємо більший час для тестування.

          ps Зараз час для одного тесту 2 с і твій розв'язок отримує TL


          • 0
            hardLY  commented on Березень 24, 2022, 9:45 до полудня відректований

            Але в мене перші п'ять тестів працюють 0,005 с, чому починаючи із шостого вони не проходять?


            • 0
              zvit  commented on Березень 24, 2022, 12:06 після полудня редагувати 2

              Реалізований алгорит не приводить до повного розв'язку цієї задачі. Необхідно шукати метод розв'язання за меншу кількість проходів послідовності.