Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Có lẽ ai cũng biết chuyện ngụ ngôn một chị gà mái đang bới đất tìm giun cho đàn gà con bị gió thổi bay một sợi lông. Sự việc được kể từ tai này sang tai khác trở thành chuyện chị gà mái bị gió xoáy vặt trụi không còn chiếc lông nào! Các nhà xã hội học quyết định nghiên cứu một cách nghiêm túc sự biến đổi của các tin đồn. Người ta khảo sát nhiều người thuộc đủ các thành phần xã hội và ngành nghề khác nhau. Dựa vào các thông tin cá nhân người ta tính  Chỉ số lanh lợi SQ(Sagacious Quotient) cho mỗi người được khảo sát và chốt lại danh sách nngười có SQ là nguyên dương, khác nhau từng đôi một và không vượt quá n. 

Nội dung của công việc khảo sát là chọn một nhóm 4 người, cho người thứ nhất trong nhóm nghe một câu chuyện, sau đó người này phải kể lại cho người thứ 2 trong nhóm, người thứ 2 – kể lại cho người thứ 3 và người này kể lại cho người thứ tư. Các nhà nghiên cứu sẽ so sánh câu chuyên ban đầu với câu chuyện người thứ tư nghe được và rút ra các kết luận cần thiết. Để đề phòng sự phản đối có thể có của Hội bảo vệ quyền phụ nữ người ta quyết định chọn 2 loại nhóm – nhóm A và nhóm B theo các quy tắc sau:

• Quy tắc chọn nhóm A:

• Nếu người thứ i của nhóm có thứ tự pi trong danh sách thì p1<p2<p3<p4 

• Người thứ nhất và người thứ tư phải là nam giới, hai người kia là nữ, 

• Chỉ số SQ của người thứ nhất phải lớn hơn chỉ số SQ của người thứ tư.

• Quy tắc chọn nhóm B:

• Nếu người thứ i của nhóm có thứ tự pi trong danh sách thì p1<p2<p3<p4

• Người thứ nhất và người thứ tư phải là nữ, hai người kia là nam, 

• Theo giá trị tuyệt đối, chỉ số SQ của người thứ nhất phải nhỏ hơn chỉ số SQ của người thứ tư.

Yêu cầu:Cho n và các số nguyên ai , i= 1 ÷ n, trong đó nếu ai > 0 thì người thứ i là nam và có SQ  là ai , nếu  ai < 0 thì người thứ i là nữ và có SQ là –ai. Hãy xác định có thể chọn được bao nhiêu nhóm khác nhau. Hai nhóm gọi là khác nhau nếu khác nhau người thứ nhất hoặc khác nhau người thứ tư hay khác nhau cả 2 người thứ nhất và thứ tư. 

Dữ liệu:Vào từ file văn bản SQ.INP:

• Dòng đầu tiên chứa số nguyên n(4 ≤ n≤ 10^6),

• Dòng thứ 2 chứa nsố nguyên a1 , a2 , . . ., an

Kết quả:Đưa ra file văn bản SQ.OUT trên một dòng 2 số nguyên – số lượng nhóm A khác nhau có thể chọn và số lượng nhóm B khác nhau có thể chọn.

Ví dụ:

SQ.INP 

8

-2 6 -4 7 8 -3 1 5

SQ.OUT

2 1