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

Перегляд у форматі PDF
Надіслати розв'язок
Бали: 25,00 (partial)
Time limit: 2.0s
Memory limit: 64M
Author:
zvit
Problem type
Allowed languages
Assembly, Awk, Brain****, C, C++, Java, mono C#, Pascal, Perl, Python, Sed, Text, vb

Для даної послідовності ~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

Коментарі

Please read the guidelines before commenting.


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

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


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

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


      • 0
        hardLY  commented on Березень 23, 2022, 10:11 після полудня

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


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

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

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


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

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


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

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