#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <numeric>
// --- PARTE I: Contagem de Triplas Míticas (O(N^2) Solution) ---
/**
* Procedimento exigido para a Parte I: Contar o número de triplas míticas.
* Complexidade: O(N^2)
*
* @param H Array de alturas dos picos.
* @return O número total de triplas míticas.
*/
long long count_triples(std::vector<int> H) {
int N = H.size();
long long count = 0;
// A condição é que {H[i], H[j], H[k]} seja uma permutação de {d1, d2, d3},
// onde d1 = j-i, d3 = k-j, e d2 = d1 + d3.
// Otimizamos iterando sobre o índice central 'j' e a distância 'd1'.
// Iteração sobre o índice central 'j'
for (int j = 1; j < N - 1; ++j) {
// Iteração sobre a distância esquerda 'd1' (d1 = j - i).
// d1 >= 1.
for (int d1 = 1; d1 <= j; ++d1) {
int i = j - d1;
int hi = H[i];
int hj = H[j];
// Iteração sobre a distância direita 'd3' (d3 = k - j).
// d3 >= 1 e k < N, então d3 <= N - 1 - j.
for (int d3 = 1; j + d3 < N; ++d3) {
int k = j + d3;
int hk = H[k];
int d2 = d1 + d3;
// --- 3 Casos de Correspondência (d2 é o maior valor) ---
// Caso 1: H[i] = d2 (a maior altura é a primeira)
// H[j] e H[k] devem ser {d1, d3}
if (hi == d2) {
if ((hj == d1 && hk == d3) || (hj == d3 && hk == d1)) {
count++;
continue;
}
}
// Caso 2: H[j] = d2 (a maior altura é a central)
// H[i] e H[k] devem ser {d1, d3}
if (hj == d2) {
if ((hi == d1 && hk == d3) || (hi == d3 && hk == d1)) {
count++;
continue;
}
}
// Caso 3: H[k] = d2 (a maior altura é a última)
// H[i] e H[j] devem ser {d1, d3}
if (hk == d2) {
if ((hi == d1 && hj == d3) || (hi == d3 && hj == d1)) {
count++;
continue;
}
}
}
}
}
return count;
}
// --- PARTE II: Construção de Picos (Função Placeholder) ---
/**
* Procedimento exigido para a Parte II: Construir um array de picos.
* ESTA É UMA IMPLEMENTAÇÃO PLACEHOLDER (Para fins de compilação/teste de Part I).
* Para obter pontuações na Parte II, é necessária uma estratégia de construção otimizada.
*
* @param M O número máximo de picos.
* @param K O número desejado de triplas míticas.
* @return Um array H de alturas, onde 3 <= H.size() <= M, e 1 <= H[i] <= H.size() - 1.
*/
std::vector<int> construct_range(int M, int K) {
// A construção mais simples e válida. O tamanho mínimo é 3[cite: 48].
// N = 3. Alturas devem estar entre 1 e N-1 (ou seja, 1 e 2)[cite: 48].
// H = [1, 2, 1]. Esta configuração tem 1 tripla mítica: (0, 1, 2).
// Distâncias: {1, 2, 1}. Alturas: {1, 2, 1}. Match.
if (M >= 3) {
// Retorna N=3 com H=[1, 2, 1]
return {1, 2, 1};
}
// Caso M < 3 (não deve ocorrer, mas é uma contingência)
return {};
}
// --- FIM DOS PROCEDIMENTOS IOI ---
/*
// Exemplo de uso para um ambiente de teste local:
int main() {
// --- Teste da Parte I ---
std::cout << "--- Teste da Parte I: count_triples ---" << std::endl;
// Exemplo do enunciado: [4, 1, 4, 3, 2, 6, 1]
// Resultado esperado: 3 [cite: 34, 38]
std::vector<int> H_exemplo = {4, 1, 4, 3, 2, 6, 1};
std::cout << "Exemplo 1 (Resultado esperado: 3): " << count_triples(H_exemplo) << std::endl;
// Exemplo Simples (N=3, i=0, j=1, k=2)
// Distâncias: {1, 2, 1}. Alturas: {1, 2, 1}. Mítica.
std::vector<int> H_simples = {1, 2, 1};
std::cout << "Exemplo 2 ([1, 2, 1]): " << count_triples(H_simples) << std::endl;
// Exemplo Simples (N=4)
// H = [1, 1, 1, 1]. Triplas: (0, 1, 2), (1, 2, 3) (Míticas? Não. {1,2,1} vs {1,1,1})
// Triplas: (0, 1, 2) -> {1, 2, 1} vs {1, 1, 1} (Não)
// Triplas: (0, 2, 3) -> {2, 3, 1} vs {1, 1, 1} (Não)
// Triplas: (0, 1, 3) -> {1, 3, 2} vs {1, 1, 1} (Não)
std::vector<int> H_quatro = {1, 1, 1, 1};
std::cout << "Exemplo 3 ([1, 1, 1, 1] - esperado: 0): " << count_triples(H_quatro) << std::endl;
// --- Teste da Parte II (Placeholder) ---
std::cout << "\n--- Teste da Parte II: construct_range (Placeholder) ---" << std::endl;
int M_teste = 10;
int K_teste = 100;
std::vector<int> range = construct_range(M_teste, K_teste);
std::cout << "Array Construído (N=" << range.size() << "): ";
for (int h : range) {
std::cout << h << " ";
}
std::cout << std::endl;
return 0;
}
*/
