Hướng dẫn giải của [Beginner Free Contest 05] POSIPROD
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 N số nguyên (N ≤ 100, |A_i| ≤ 1000). Mỗi lần được đảo dấu một phần tử. Tìm số lần đảo ít nhất để tích của mọi cặp phần tử đều dương, hoặc in -1 nếu không làm được.
Sub 1: Thử hai dấu đích, lật rồi kiểm tra từng cặp — ~O(n^3)~
Tích mọi cặp đều dương nghĩa là mọi phần tử khác 0 và cùng dấu. Ta thử hai khả năng: tất cả đều dương hoặc tất cả đều âm. Với mỗi khả năng, lật các phần tử sai dấu, rồi kiểm tra bằng vòng lặp O(n^2) xem mọi cặp có tích dương không. Lấy số lần lật nhỏ nhất trong các khả năng hợp lệ. Đạt 10/10 test vì N nhỏ.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
// Sub 1: thu ca hai dau cuoi (+ va -), lat dau moi phan tu sai dau,
// roi kiem tra lai bang vong lap O(n^2) xem moi cap co tich > 0 khong.
int best = -1;
for (int s = -1; s <= 1; s += 2) {
vector<int> b = a;
int cnt = 0;
bool hasZero = false;
for (int i = 0; i < n; i++) {
if (b[i] == 0) { hasZero = true; break; }
if ((b[i] > 0) != (s > 0)) { b[i] = -b[i]; cnt++; }
}
if (hasZero) continue;
bool ok = true;
for (int i = 0; i < n && ok; i++)
for (int j = i + 1; j < n && ok; j++)
if ((long long)b[i] * b[j] <= 0) ok = false;
if (ok && (best == -1 || cnt < best)) best = cnt;
}
cout << best << endl;
return 0;
}
Sub 2: Đếm số dương và số âm — ~O(n)~
Nếu có số 0 thì không bao giờ đảo được thành số dương, nên tích với số 0 luôn bằng 0: in -1. Nếu không có số 0, đưa cả dãy về cùng dấu dương cần đảo số lượng số âm, còn đưa về cùng dấu âm cần đảo số lượng số dương. Đáp án là min của hai số này. Đạt 10/10 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int pos = 0, neg = 0, zero = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > 0) pos++;
else if (x < 0) neg++;
else zero++;
}
// Muon tich moi cap > 0 thi moi phan tu khac 0 va cung dau.
// Neu co so 0 thi khong bao gio doi duoc -> -1.
if (zero > 0) {
cout << -1 << endl;
return 0;
}
// Cung dau duong: can doi cac so am (neg phep). Cung dau am: can doi cac so duong (pos phep).
cout << min(pos, neg) << endl;
return 0;
}
Bình luận