POSPROD - Tích dương
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho một dãy số nguyên ~A_1, A_2, . . . , A_N~. Bạn có thể thực hiện phép biến đổi sau với số lần tùy ý (có thể không thực hiện lần nào):
- Chọn một vị trí ~i~ từ ~1~ đến ~N~, và đảo dấu ~A_i~ (tức là thay thể ~A_i~ bởi ~−A_i~)
Hãy cho biết số phép biến đổi ít nhất cần thực hiện, để dãy thu được thỏa mãn tính chất sau:
- Tích của hai phần tử bất kì trong dãy đều là số nguyên dương (nói cách khác, với mỗi cặp ~(i, j)~ thỏa ~1 ≤ i < j ≤ N~, ta có ~A_i × A_j > 0~).
Input
- Dòng đầu tiên gồm số nguyên ~N~ ~(2 ≤ N ≤ 100)~ - số phần tử của dãy ~A~.
- Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, . . . , A_N~ ~(−1000 ≤ A_i ≤ 1000)~ - mô tả dãy ~A~.
Output
- In ra một số nguyên duy nhất là số phép biến đổi ít nhất cần thực hiện. Trong trường hợp không có cách biến đổi, hãy in ra ~-1~.
Sample
Input #1
5
10 -20 -30 40 50
Output #1
2
Input #2
4
9 7 2 3
Output #2
0
Input #3
3
0 0 0
Output #3
-1
Hint
- Trong ví dụ thứ nhất, ta sẽ lần lượt thực hiện phép biến đổi với vị trí ~2~ và ~3~. Khi đó, dãy ~A~ trở thành ~[10, 20, 30, 40, 50]~.
Problem source: Kc97ble - Free Contest
Bình luận
Giải quyết đề bài:
như đề bài đã nói tích hai phần tử "bất kì" phải là số nguyên dương:
từ đó ta phải biến đổi làm sao để số lần biết đổi nhanh nhất:
vd ta có một list a =[10 -20 -30 40 50]
ta cần phải biến đổi làm sao tích hai phần tử bất kì phải là số dương
nếu ta cho tất cả phần tử trong list đều là số âm thì ta cần biến đổi 3 số 10,40,50
từ đó ta có thể thõa mãn tính chất của đề bài là tích hai phần tử phải là số nguyên dương:
tuy nhiên ta có thể làm biến đổi nhanh hơn bằng cách cho tất cả các phần tử đều là số nguyên dương tức là biến đổi 2 số -20,-30:
tử đó ta thõa mản tính chất:
nhưng đề bài lại muốn ta tìm số lần biến đổi nhanh nhất vậy ở ta thấy ở phàn biến đổi số lần âm thì số lần biến đổi là 3
mà số lần biến dổi ở phần dương là 2
vậy đáp chính là 2
tuy nhiên nếu phần tử xuất hiện một số 0 hoặc nhiều số 0 thì tích một phần tử bất kì không phải là số nguên dương được
vd 1*0 = 0 mà 0 thi không phải số nguyên dương
bài này đơn giản chỉ cần tìm xem có số lượng số âm và dương cái nào lớn hơn thì cout số ít hơn là ra, nếu có một giá trị bằng 0 thì cout -1
Nếu vậy chỉ qua được 4 case đầu