ამოცანის ამოსახსნელად განვიხილოთ პროგრესიის შუა ელემენტი. ეს ნიშნავს, რომ თუ დავაფიქსირებთ a_i ელემენტს, მაშინ პროგრესია უნდა შედგებოდეს a_i / K და a_i · K ელემენტებისგან. ასე ვერ მოხდება, თუ თავად a_i არ იყოფა K-ზე (a_i mod K ≠ 0).

 

დაფიქსირებული შუა ელემენტისათვის შეგვიძლია ვიპოვოთ მიმდევრობათა რაოდენობა შემდეგნაირად: დავთვალოთ რამდენი a_i / K ელემენტია მის მარცხნივ და რამდენი a_i · K ელემენტია მის მარჯვნივ. ამ რაოდენობათა ნამრავლი იქნება ამოცანის პასუხი.

 

მაგალითის დეტალური განხილვა

შემომავალი მონაცემები შევინახოთ მასივში.

გამოვყოთ პასუხისათვით განკუთვნილი ცვლადი answer, რომელიც შეინახავს სასურველი გეომეტრიული პროგრესიების რაოდენობას.

 

answer = 0

 

1

1

2

2

4

 

დამატებით შემოვიღოთ 2 Map (ასახვა) სტრუქტურა, რომელთა გასაღები (Key) იქნება შემომავალი მონაცემი, მნიშვნელობა (Value) კი - სიხშირე (რამდენჯერ გვხვდება იგი). თითოეული მომენტისათვის უნდა ვიცოდეთ მონაცემთა სიხშირე ყოველი დაფიქსირებული კურსორის მარცხნივ და მარჯვნივ. 2 Map სწორედ ამისთვის გვჭირდება.

 

მონაცემთა განხილვას ვიწყებთ მარცხნიდან მარჯვნივ, შესაბამისად, თავდაპირველად გვექნება ასეთი მდგომარეობა:

 

numsLeft = {}

numsRight = {1 : 2, 2 : 2, 4 : 1}

answer = 0

 

numsLeft
მნიშვნელობა	სიხშირე

 

numsRight
მნიშვნელობა	სიხშირე
1	2
2	2
4	1

 

დავიწყოთ მონაცემთა განხილვა.

 

1

1

2

2

4

1-იანი არ იყოფა 2-ზე, ეს რიცხვი ვერ იქნება სასურველი გეომეტრიული პროგრესიის შუა წევრი, ამიტომაც მხოლოდ სიხშირეები განვაახლოთ.

 

NumsLeft = {1 : 1}

numsRight = {1 : 1, 2 : 2, 4 : 1}

 

answer = 0

 

numsLeft
მნიშვნელობა	სიხშირე
1	1

 

 

numsRight
მნიშვნელობა	სიხშირე
1	1
2	2
4	1

 

 

გადავიდეთ შემდეგ მონაცემზე.

 

1

1

2

2

4

 

აქაც ანალოგიური შემთხვევა გვაქს, შევასრულოთ იგივე.

 

 

NumsLeft = {1 : 2}

numsRight = {2 : 2, 4 : 1}

 

 

answer = 0

 

numsLeft
მნიშვნელობა	სიხშირე
1	2

 

 

numsRight
მნიშვნელობა	სიხშირე
2	2
4	1

 

გადავიდეთ შემდეგ მონაცემზე.

 

1

1

2

2

4

 

 

2-იანი იყოფა 2-ზე, ამიტომ “მარცხენა” Map-ში ვნახოთ რამდენი ისეთი წევრი გვაქვს, რომელიც სასურველი გეომეტრიული პროგრესიის (ამ შემთხვევაში [1, 2, 4]) მარცხენა კიდურა წევრი იქნება.

 

მოვნახოთ 1-იანის სიხშირე და დავიმახსოვროთ.

NumsLeft[1] = 2

 

ახლა კი “მარჯვენა” Map-ში ვნახოთ რამდენი ისეთი წევრი გვაქვს, რომელიც სასურველი გეომეტრიული პროგრესიის (ამ შემთხვევაში [1, 2, 4]) მარჯვენა კიდურა წევრი იქნება.

 

მოვნახოთ 4-იანის სიხშირე და დავიმახსოვროთ.

NumsRight[4] = 1

 

ახლა კი answer ცვლადს დავუმატოთ დამახსოვრებულ მნიშვნელობათა ნამრავლი და განვაახლოთ სიხშირეები:

answer += 1 * 2

 

NumsLeft = {1 : 2, 2 : 1}

numsRight = {2 : 1, 4 : 1}

 

 

answer = 2

 

numsLeft
მნიშვნელობა	სიხშირე
1	2
2	1

 

numsRight
მნიშვნელობა	სიხშირე
2	1
4	1

 

 

გადავიდეთ შემდეგ მონაცემზე.

 

1

1

2

2

4

 

აქაც წინა სიტუაციის ანალოგიური მდგომარეობა გვაქვს.

 

NumsLeft[1] = 2

numsRight[4] = 1

 

answer += 1 * 2

 

განვაახლოთ სიხშირეები.

 

NumsLeft = {1 : 2, 2 : 2}

numsRight = {4 : 1}

 

 

answer = 4

 

numsLeft
მნიშვნელობა	სიხშირე
1	2
2	2

 

numsRight
მნიშვნელობა	სიხშირე
4	1

 

გადავიდეთ ბოლო მონაცემზე.

 

1

1

2

2

4

 

 

4-იანი იყოფა 2-ზე, ამიტომ “მარცხენა” Map-ში მოვნახოთ რამდენი ისეთი წევრი გვაქვს, რომელიც სასურველი გეომეტრიული პროგრესიის (ამ შემთხვევაში [2, 4, 8]) მარცხენა კიდურა წევრი იქნება.

 

NumsLeft[2] = 2

 

ახლა კი “მარჯვენა” Map-ში უნდა მოვნახოთ პროგრესიის მარჯვენა კიდურა წევრის სიხშირე, მაგრამ ცხადია ასეთი არ მოიძებნება.

 

NumsRight[8] = 0

 

answer ცვლადი განახლებისას არ შეიცვლება.

 

Answer += 0 * 2

 

განვაახლოთ სიხშირეები.

 

NumsLeft = {1 : 2, 2 : 2, 4 : 1}

numsRight = {}

 

 

answer = 4

 

numsLeft
მნიშვნელობა	სიხშირე
1	2
2	2
4	1

 

numsRight
მნიშვნელობა	სიხშირე

ყველა მონაცემის გადარჩევის შემდეგ დავბეჭდოთ answer ცვლადი.

 

ამოხსნის კოდი

#include <iostream>
#include <map>
using namespace std;

void SubsequencesOfLengthThree() {
  map <long long, long long> numsLeft;
  map <long long, long long> numsRight;
  long long N;
  long long K;
  long long sequence[300010];
  long long ans;

  scanf("%lld %lld", &N, &K);

  for (int i = 0; i < N; i++) {
      scanf("%lld", &sequence[i]);
      numsRight[sequence[i]]++;
  }

  for (int i = 0; i < N; i++) {
      long long elementsLeft = 0;
      long long elementsRight = 0;

      if (sequence[i] % K == 0) {
          elementsLeft = numsLeft[sequence[i] / K];
      }

      numsRight[sequence[i]]--;
      elementsRight = numsRight[sequence[i] * K];
      ans += elementsLeft * elementsRight;
      numsLeft[sequence[i]]++;
  }

  printf("%lldn", ans);
}

int main() {
  SubsequencesOfLengthThree();

  return 0;
}