Hướng dẫn giải của Dãy số (đề HSG 12 Phú Thọ 2025-2026)
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 một hoán vị 8 số của tập {1..8}, xác định dãy là đơn điệu tăng (ascending), đơn điệu giảm (descending) hay không đơn điệu (mixed).
Chỉ viết một sub: bài chỉ cần kiểm tra các cặp số liền kề, lời giải này đã là cách trực tiếp và không có cách vét cạn khác đáng kể để so sánh.
Sub 1: Kiểm tra các cặp liền kề — ~O(1)~
Dãy tăng nếu mọi a[i] < a[i+1]; dãy giảm nếu mọi a[i] > a[i+1]; còn lại là không đơn điệu. Vì dãy chỉ có 8 phần tử nên chạy rất nhanh.
Kết quả chấm: đạt 12/12 test
#include <bits/stdc++.h>
using namespace std;
// Bài này chỉ có một cách hợp lý: kiểm tra từng cặp liền kề, không có lời giải vét cạn khác đáng kể
// nên chỉ viết một sub (lời giải đầy đủ).
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
}
int a[8];
for (int i = 0; i < 8; i++) cin >> a[i];
bool tang = true, giam = true;
for (int i = 0; i + 1 < 8; i++) {
if (a[i] >= a[i + 1]) tang = false; // không tăng nghiêm ngặt
if (a[i] <= a[i + 1]) giam = false; // không giảm nghiêm ngặt
}
if (tang) cout << "ascending\n";
else if (giam) cout << "descending\n";
else cout << "mixed\n";
return 0;
}
Bình luận