Tiếp tục "tài lanh", Another xin tham kiến quý vị.
Trước hết cần lưu ý yêu cầu đề bài ("số lần biến đổi ít nhất" chứ không phải "dãy sau khi biến đổi"). Vậy nên chúng ta không cần quá nhiều chất xám để nghĩ thuật toán (dĩ nhiên là ngoại trừ mấy thanh niên khối 10 chưa đủ chất xám và "thò lò mũi xanh" như bọn em).
Lưu ý 1: trong bài sử dụng mảng a có kiểu giá trị "int" làm ví dụ.
Thuật toán và tư duy:
-
B1: Trước hết, ta phải khai báo mảng a có ít nhất 100 phần tử và n là số phần tử tương ứng sẽ có trong dãy số a
-
B2: Tạo 2 biến đếm, dùng để đếm số phần tử dương, đếm số phần tử âm
-
B3: Tiếp theo, nhập khi chạy i từ 1 đến n (hoặc từ 0 đến n-1)
-
- Nếu thì tăng , và ngược lại, tăng nếu
-
- Nếu gặp phần tử thì gán , phá lặp
- B4 :In ra biến đếm nhỏ nhất bằng cách sử dụng min(,)
*Lưu ý 2: bước phá lặp trong trường hợp không ảnh hưởng đến việc nhập giá trị (nếu các phần tử chỉ cách nhau bởi 1 dấu cách), tuy nhiên nếu muốn an toàn thì không nên phá lặp, có thể theo hướng dẫn trong phần "Giải thích".
Giải thích: Hết sức đơn giản, vì nếu muốn tích của 1 cặp số bất kỳ trong mảng lớn hơn 0 thì buộc tất cả các phần tử trong mảng đều phải có cùng dấu (cùng âm, hoặc cùng dương). Bản chất đề bài muốn ta phải biến đổi tất cả các phần tử trong dãy số về các phần tử có cùng dấu.
Có 1 trường hợp đặc biệt: Xuất hiện phần tử 0!
Phần tử 0 không thể coi là âm hay dương, nghĩa là không có dấu và không thể biến đổi. Trường hợp gặp 0 thì đơn giản chỉ còn cách "bó tay chịu trận", nghĩa là in ra "-1". Vậy ý nghĩa của việc phá lặp đã rõ: để bảo toàn biến (nếu có thêm 1 số dương nữa thì sẽ tăng, và dĩ nhiên là kết quả thay đổi). Tuy nhiên việc phá lặp sẽ ảnh hưởng tới việc nhập dữ liệu (nếu dữ liệu vào không đầy đủ thì ảnh hưởng tới kết quả).
Trong trường hợp đó, ta có thể tạo biến có kiểu bool (lấy ví dụ là biến ) có giá trị khởi tạo là (hoặc ) và gán thành (hoặc ) khi gặp giá trị bất kỳ bằng . Sau khi nhập xong, xét biến . Nếu bằng (hoặc ) thì in ra -1, nếu bằng (hoặc ) thì in ra min(cnt1, cnt2).
Các test trong bài khá yếu (với và ) nên đây là phương pháp khả thi. Tuy nhiên nếu có giá trị lớn thì nên khai báo thành kiểu xâu (ví dụ xâu s) và làm theo thuật toán trong bài #605 (DEMSO). Giá trị N cũng nên khai báo thành kiểu long long.
Tham khảo thuật toán đếm số lớn tại đây:
Thuật toán và tư duy đơn giản bài #605 (DEMSO)
Tham khảo code của Aki (Python 3) tại đây:
n = int(input())
Aki = [int(i) for i in input().split()]
cnt1 = cnt2 = 0
for i in Aki:
cnt1 += (i < 0)
cnt2 += (i > 0)
print(cnt1,cnt2)
Tham khảo code của Another tại đây:
#include <bits/stdc++.h>
#define f(a, b, c) for (long long c = a; c <= b; c++)
#define maxn 1000001
#define mirota cin
#define nonomiya cout
#define Mirota_Nonomiya main
#define effective \
ios::sync_with_stdio(0); \
mirota.tie(0); \
nonomiya.tie(0);
using namespace std;
int Mirota_Nonomiya() {
effective
int n, res1=0, res2=0;
string s;
mirota >> n;
while (mirota >> s) {
if (s[0]=='-') res1++;
if (s[0]>='1' && s[0]<='9') res2++;
}
nonomiya << res1 << " " << res2;
}
Cảm ơn đã dành time đọc bài "tài lanh" của Another.
Tạm biệt và hẹn gặp lại -.-
-Another-