პოლიკარტეს ძალიან უყვარს გეომეტრიული პროგრესიები. იგი მხოლოდ 3 წლისაა, ამიტომაც ისეთი გეომეტრიული პროგრესიები უყვარს, რომელთა სიგრძეც სამია. მას ასევე აქვს საყვარელი მთელი რიცხვი K და N ცალი რიცხვისაგან შემდგარი მიმდევრობა A.
პოლიკარტეს აინტერესებს, რამდენი 3 სიგრძის ქვემიმდევრობის ამორჩევაა შესაძლებელი A-დან, ისე რომ ის გეომეტრიულ პროგრესიას ადგენდეს მნიშვნელით K.
3 სიგრძის ქვემიმდევრობა არის 3 ინდექსის i1, i2, i3 ისეთი კომბინაცია რომ 1 ≤ i1 < i2 < i3≤ N.
სხვა სიტყვებით რომ ვთქვათ, 3 სიგრძის ქვემიმდევრობა არის სამი ელემენტისგან შემდგარი ისეთი ჯგუფი, რომელშიც ელემენტები აუცილებლად თანმიმდევრობით არაა დალაგებული, მაგრამ მათი ინდექსები მკაცრად ზრდადია.
გეომეტრიული პროგრესია მნიშვნელით K არის რიცხვების ისეთი მიმდევრობა, რომელსაც აქვს შემდეგი ფორმა: b · k0, b · k1, ... , b · k r – 1.
პოლიკარტე მხოლოდ 3 წლისაა, შესაბამისად, მას არ შეუძლია ამ რიცხვის დათვლა. დაეხმარე მას ამის გაკეთებაში.
შემავალი მონაცემები:
შემავალი მონაცემების პირველი ხაზი წარმოადგენს ორ მთელ რიცხვს, N და K (1 ≤ n, k ≤ 2·105), რომლებიც უჩვენებენ თუ რამდენი რიცხვია პოლიკარტეს მიმდევრობაში და მის საყვარელ მთელ რიცხვს.
მეორე ხაზი კი N ცალი მთელი რიცხვია a1, a2, ... , an ( - 109 ≤ ai ≤ 109) – მიმდევრობის ელემენტები.
გამომავალი მონაცემები:
გამომავალი მონაცემი უნდა იყოს ერთი რიცხვი – რამდენნაირი 3 სიგრძის ქვემიმდევრობის არჩევაა შესაძლებელი, ისე რომ გეომეტრიულ პროგრესიას ადგენდეს მნიშვნელით K.
მაგალითები
შემავალი მონაცემები |
5 2 1 1 2 2 4 |
გამომავალი მონაცემები |
4 |
შემავალი მონაცემები |
3 1 1 1 1 |
გამომავალი მონაცემები |
1 |
შემავალი მონაცემები |
10 3 1 2 6 2 3 6 9 18 3 9 |
გამომავალი მონაცემები |
6 |
შენიშვნა
პირველ მაგალითში პასუხი არის 4, რადგან ქვემიმდევრობის პირველ ელემენტად ნებისმიერი 1-იანის არჩევა შეიძლება, მეორე ელემენტად ნებისმიერი 2-იანის და მესამე ელემენტი კი აუცილებლად 4 უნდა იყოს.
ამოცანის ამოსახსნელად განვიხილოთ პროგრესიის შუა ელემენტი. ეს ნიშნავს, რომ თუ დავაფიქსირებთ ai ელემენტს, მაშინ პროგრესია უნდა შედგებოდეს ai / K და ai · K ელემენტებისგან. ასე ვერ მოხდება, თუ თავად ai არ იყოფა K-ზე (ai mod K ≠ 0).
დაფიქსირებული შუა ელემენტისათვის შეგვიძლია ვიპოვოთ მიმდევრობათა რაოდენობა შემდეგნაირად: დავთვალოთ რამდენი ai / K ელემენტია მის მარცხნივ და რამდენი ai · 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;
}