PROBLEM LINK:
Author: Alexey Zayakin
Tester: Hanlin Ren
Editorialist: Hanlin Ren
DIFFICULTY:
CAKEWALK
PREREQUISITES:
None
PROBLEM
We’re given the price of a phone over N days. Everyday we considers the price good if it’s strictly smaller than all the prices during previous five days. If on some day (before the first day) we didn’t record the price, we assume the price is infinite. Find the number of days with a good price.
EXPLANATION:
We simply iterate through the array, and for each index we check if it’s good. If it’s good, then we increase our answer. Pseudocode:
ans = 0
for i = 1 to N :
Check whether day i is good
if day i is good then
ans = ans + 1
print ans
Now we still need to check whether an index i is good. We can use a for-loop to iterate through its previous 5 indices.
Pseudocode:
for j = 1 to 5 :
if i-j > 1 then // if i-j>1, then the day i-j is valid, we need to check if its price is higher than the price in day i.
if P[i-j] < P[i] then day i is bad
return day i is good
Let’s put them together. We use a variable good to denote whether the i-th day is good. Initially we set good to be True, and when we find day i is bad, we set it to be False.
Pseudocode:
ans = 0
for i = 1 to N :
//Check whether day i is good
good = True
for j = 1 to 5 :
if i-j > 1 then // if i-j>1, then the day i-j is valid, we need to check if its price is higher than the price in day i.
if P[i-j] < P[i] then good = False
if good then
ans = ans + 1
print ans
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int MX = 100;
int a[MX];
int main() {
int T;
ignore = scanf("%d", &T);
while (T--) {
int n;
ignore = scanf("%d", &n);
for (int i = 0; i < n; i++) ignore = scanf("%d", a + i);
int ans = 0;
for (int i = 0; i < n; i++) {
bool ok = true;
for (int j = max(i - 5, 0); j < i; j++) {
ok = ok && a[i] < a[j];
}
if (ok) ans++;
}
printf("%d\n", ans);
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int n, p[2000];
void doit() {
int i, j, ans = 0;
cin >> n;
for (i = 1; i <= n; i++) cin >> p[i];
for (i = 1; i <= n; i++) {
for (j = max(1, i - 5); j < i; j++)
if (p[i] >= p[j]) break;
if (j == i) ans++;
}
cout << ans << endl;
}
int main() {int t; cin >> t; while (t--) doit(); return 0;}
