Hướng dẫn giải của TMP2526_CAU1
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho dãy là hoán vị của {1, ..., 8}. Xác định dãy đơn điệu tăng (ascending), đơn điệu giảm (descending) hay không đơn điệu (mixed).
Sub 1: Vét cạn — ~O(n^2)~
Với mọi cặp (i, j), i < j, kiểm tra có a[i] > a[j] (không tăng) hay a[i] < a[j] (không giảm). Nếu luôn đúng một chiều thì dãy đơn điệu. Với n = 8 chạy nhanh, đạt 12/12 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a[8];
for (int i = 0; i < 8; i++) cin >> a[i];
// Vét cạn: kiểm tra mọi cặp (i, j) với i < j
bool inc = true, dec = true;
for (int i = 0; i < 8; i++)
for (int j = i + 1; j < 8; j++) {
if (a[i] > a[j]) inc = false;
if (a[i] < a[j]) dec = false;
}
if (inc) cout << "ascending\n";
else if (dec) cout << "descending\n";
else cout << "mixed\n";
return 0;
}
Sub 2: So sánh các cặp liền kề — ~O(n)~
Vì dãy là hoán vị nên không có hai số bằng nhau. Dãy tăng khi mọi cặp liền kề a[i] < a[i+1], giảm khi mọi cặp liền kề a[i] > a[i+1]. Chỉ cần hai cờ inc, dec và một vòng lặp. Đạt 12/12 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a[8];
for (int i = 0; i < 8; i++) cin >> a[i];
// Dãy đơn điệu khi mọi cặp số liền kề cùng chiều (vì là hoán vị nên không có bằng nhau)
bool inc = true, dec = true;
for (int i = 0; i + 1 < 8; i++) {
if (a[i] > a[i + 1]) inc = false;
if (a[i] < a[i + 1]) dec = false;
}
if (inc) cout << "ascending\n";
else if (dec) cout << "descending\n";
else cout << "mixed\n";
return 0;
}
Bình luận