Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1089
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1089
Musical Loop
By Ricardo Anido 
Brazil
Timelimit: 1
A musical loop is a small section of music composed to be played continuously (that is, the section is played again when it reaches the end), in a seamless way. Loops are used in many styles of popular music (hip hop, techno, etc), as well in computer games, especially casual games on the Internet.
Loops may be digitalized for example using PCM (Pulse Code Modulation), a technique for representing analog signals used extensively in digital audio. In PCM, the magnitude of the signal is sampled at regular intervals, and the values sampled are stored in sequence. To produce the sound for the sampled data, the procedure is applied in reverse (demodulation).
Fernanda works for a game software house, and composed a beautiful musical loop, coded in PCM. Analyzing the waveform of her loop in audio editing software, Fernanda became curious when she noticed the number of "peaks". A peak in a waveform is the value of a sample that represents a local maximum or minimum. The figure below illustrates (a) a waveform and (b) the loop formed with this waveform, containing 48 peaks.
Fernandinha is a dear friend of yours. She has asked your help to determine how many peaks exist in her musical loop.
Input
The input contains several test cases. The first line of a test case contains one integer N, representing the number of samples in the musical loop composed by Fernanda (2 ≤ N ≤ 104). The second line contains N integers Hi, separated by spaces, representing the sequence of magnitudes sampled (-104 ≤ Hi ≤ 104 for 1 ≤ i ≤ N, H1 ≠ HN and Hi ≠ Hi+1 for 1 ≤ i < N). Notice that H1 follows HN when the loop is played.
The end of the input is indicated by a line that contains only one zero.
Output
For each test case in the input your program must print a single line, containing one integer, the number of peaks that exist in the musical loop.
| Input Sample | Output Sample |
|
2 |
2 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
int main(int argc, char **argv)
{
int n, i, ans;
int ondas[10050];
while (scanf("%d", &n), n)
{
for (i = 0; i < n; ++i)
scanf("%d", &ondas[i]);
ans = 0;
for (i = 1; i < n - 1; ++i)
if ((ondas[i] - ondas[i - 1]) * (ondas[i] - ondas[i + 1]) > 0)
++ans;
if ((ondas[0] - ondas[n - 1]) * (ondas[0] - ondas[1]) > 0)
++ans;
if ((ondas[n - 1] - ondas[n - 2]) * (ondas[n - 1] - ondas[0]) > 0)
++ans;
printf("%d\n", ans);
}
return 0;
}
Input
1 -3
6
40 0 -41 0 41 42
4
300 450 449 450
0
Output
2
4
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, x, c;
while (1)
{
cin >> n;
if (n==0)
break;
c=0;
vector<int>v;
vector < char>s;
while (n--)
{
cin >> x;
v.push_back(x);
}
v.push_back(v[0]);
v.push_back(v[1]);
for (int i = 0; i < v.size()-1; ++i)
{
if (v[i] <= v[i+1])
s.push_back('u');
else
s.push_back('d');
}
for (int i = 0; i < s.size()-1; ++i)
{
if (s[i]!=s[i+1])
c++;
}
cout << c << endl;
}
return 0;
}
Input
1 -3
6
40 0 -41 0 41 42
4
300 450 449 450
0
Output
2
4
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const { readFileSync } = require("fs")
const input = readFileSync("/dev/stdin", "utf8").split("\n").map((line) => line.split(" "))
/**
* @param {string | any[]} arr
* @param {number} pos
*/
const at = (arr, pos) => arr[(arr.length + pos) % arr.length]
/** @param {number[]} nums */
function countInflections(nums) {
if (nums.length <= 1) return nums.length
let count = 0
let prevInflectionPoint = at(nums, -1)
nums.forEach((curr, index, arr) => {
const next = at(arr, index + 1)
// Ambos estão descendo ou subindo:
// 9 -> DESCEU -> 6 -> DESCEU -> 5
// PREV -> CURR -> NEXT
// INFLECÇÃO:
// 9 -> DESCEU -> 5 -> SUBIU -> 10
// PREV -> CURR -> NEXT
// prevInflectionPoint = curr
// CURR === NEXT <=> Não faz nada
// 5 -> DESCEU -> 10 -> IGUA -> 10
// PREV -> CURR -> NEXT
if (curr !== next) {
if (Math.sign(curr - prevInflectionPoint) != Math.sign(next - curr)) {
count += 1
prevInflectionPoint = curr
}
}
})
return count
}
function main() {
const responses = []
for (let index = 0; index < input.length; index += 2) {
const [N] = input[index]
if (N == "0") break
const nums = input[index + 1].slice(0, +N).map((n) => Number.parseInt(n, 10))
responses.push(countInflections(nums))
}
console.log(responses.join("\n"))
}
main()
Input
1 -3
6
40 0 -41 0 41 42
4
300 450 449 450
0
Output
2
4
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const { readFileSync } = require("fs")
const input = readFileSync("/dev/stdin", "utf8")
.split("\n")
.map(line => line
.split(" ")
.map(value => Number.parseInt(value, 10))
)
/** @param {number[]} nums */
function countInflections(nums) {
if (nums.length <= 1) return nums.length
let count = 0
let prevInflectionPoint = nums.at(-1)
nums.forEach((curr, index, arr) => {
const next = arr.at(index + 1)
if (curr !== next) {
if (Math.sign(curr - prevInflectionPoint) != Math.sign(next - curr)) {
count += 1
prevInflectionPoint = curr
}
}
})
return count
}
function main() {
const responses = []
for (let index = 0; index < input.length; index += 2) {
const [N] = input[index]
if (N === 0)
break
responses.push(
countInflections(input[index + 1].slice(0, N))
)
}
console.log(responses.join("\n"))
}
main()
Input
1 -3
6
40 0 -41 0 41 42
4
300 450 449 450
0
Output
2
4
#5 Code Example with Python Programming
Code -
Python Programming
while True:
n = int(input())
if n == 0: break
v = [int(x) for x in input().split()]
a = True if v[-1] < v[0] else False
p = 0
for i in range(1, n):
if v[i-1] < v[i]: s = True
else: s = False
if s != a: p += 1
a = s
if v[-1] < v[0]: s = True
else: s = False
if s != a: p += 1
print(p)
Input
1 -3
6
40 0 -41 0 41 42
4
300 450 449 450
0
Output
2
4