[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Bài 1: Cow Baseball (6 điểm)
Nông dân John (FJ) có N con bò đang đứng trên một hàng, mỗi con đứng ở một vị trí khác nhau trên trục số. Chúng đang luyện tập ném trái bóng chày vòng vòng để chuẩn bị cho một trận thi đấu quan trọng với những con bò láng giềng.
Khi FJ theo dõi, ông ta nhận ra một nhóm có ba con bò (X,Y,Z) hoàn thành hai cú ném. Con bò X ném trái bóng cho con bò Y ở bên phải cô ta, và con bò Y ném trái bóng cho con bò Z ở bên phải cô ta. FJ để ý rằng lần ném thứ hai có độ dài không quá hai lần so với lần ném đầu tiên. Hãy giúp FJ đếm xem có bao nhiêu bộ ba các con bò (X,Y,Z) mà FJ có thể theo dõi.
INPUT
Dòng 1: Số lượng các con bò là N (3 <= N <=1000).
Dòng 2..1+N: Mỗi dòng chứ một số tự nhiên là vị trí của một con bò (các số tự nhiên nằm trong khoảng 0..100,000,000).
OUTPUT
Dòng 1: Số lượng bộ ba con bò (X,Y,Z), trong đó con bò Y nằm bên phải con bò X, con bò Z nằm bên phải con bò Y, và khoảng cách giữa Y và Z nằm giữa XY và 2XY (bao gồm cả giá trị này), trong đó XY là khoảng cách của X đến Y.
BASEBALL.inp
5
3
1
10
7
4
BASEBALL.out
4
• 50% test có n <= 500
Giải thích : Có bốn bộ ba con bò ở các vị trí 1-3-7, 1-4-7, 4-7-10, 1-4-10.
Bài 2: Balanced Cow Subsets (7 điểm)
Nông dân John (FJ) có N con bò (2 <= N <= 20), trong đó con bò thứ I sản xuất được M(i) đơn vị sữa một ngày (1 <= M(i) <= 100,000,000). FJ muốn sắp xếp quá trình lấy sữa của ông ta hàng ngày, vì vậy ông ta thêm vào máy vắt sữa mới trong nhà kho. Tuy nhiên, nó chỉ hoạt động nếu như sản lượng sữa ở bên trái nhà kho bằng sản lượng sữa ở bên phải.
Chúng ta gọi tập các con bò là “cân bằng” nếu như ta có thể chia chúng thành hai nhóm có sản lượng sữa là ngang nhau. Vì vậy, FJ muốn biết có bao nhiêu tập các con bò thỏa mãn điều kiện khi chia chúng ra thì hai nhóm có sản lượng sữa là bằng nhau.
INPUT
*Dòng 1: Số tự nhiên N.
*Dòng 2..1+N: Dòng thứ i+1 chứa số M(i).
OUTPUT
*Dòng 1: Số tập cân bằng của các con bò.
SUBSETS.inp SUBSETS.out
4
1
2
3
4
SUBSETS.out
3
• 30 % test có n <= 10
Giải thích : Có 3 tập cân bằng: Tập {1,2,3} có thể chia ra thành {1,2} và {3}, tập {1,3,4} chia ra thành {1,3} và {4}, tập {1,2,3,4} có thể chia ra thành {1,4} và {2,3}
Nông dân John (FJ) có N con bò đang đứng trên một hàng, mỗi con đứng ở một vị trí khác nhau trên trục số. Chúng đang luyện tập ném trái bóng chày vòng vòng để chuẩn bị cho một trận thi đấu quan trọng với những con bò láng giềng.
Khi FJ theo dõi, ông ta nhận ra một nhóm có ba con bò (X,Y,Z) hoàn thành hai cú ném. Con bò X ném trái bóng cho con bò Y ở bên phải cô ta, và con bò Y ném trái bóng cho con bò Z ở bên phải cô ta. FJ để ý rằng lần ném thứ hai có độ dài không quá hai lần so với lần ném đầu tiên. Hãy giúp FJ đếm xem có bao nhiêu bộ ba các con bò (X,Y,Z) mà FJ có thể theo dõi.
INPUT
Dòng 1: Số lượng các con bò là N (3 <= N <=1000).
Dòng 2..1+N: Mỗi dòng chứ một số tự nhiên là vị trí của một con bò (các số tự nhiên nằm trong khoảng 0..100,000,000).
OUTPUT
Dòng 1: Số lượng bộ ba con bò (X,Y,Z), trong đó con bò Y nằm bên phải con bò X, con bò Z nằm bên phải con bò Y, và khoảng cách giữa Y và Z nằm giữa XY và 2XY (bao gồm cả giá trị này), trong đó XY là khoảng cách của X đến Y.
BASEBALL.inp
5
3
1
10
7
4
BASEBALL.out
4
• 50% test có n <= 500
Giải thích : Có bốn bộ ba con bò ở các vị trí 1-3-7, 1-4-7, 4-7-10, 1-4-10.
Bài 2: Balanced Cow Subsets (7 điểm)
Nông dân John (FJ) có N con bò (2 <= N <= 20), trong đó con bò thứ I sản xuất được M(i) đơn vị sữa một ngày (1 <= M(i) <= 100,000,000). FJ muốn sắp xếp quá trình lấy sữa của ông ta hàng ngày, vì vậy ông ta thêm vào máy vắt sữa mới trong nhà kho. Tuy nhiên, nó chỉ hoạt động nếu như sản lượng sữa ở bên trái nhà kho bằng sản lượng sữa ở bên phải.
Chúng ta gọi tập các con bò là “cân bằng” nếu như ta có thể chia chúng thành hai nhóm có sản lượng sữa là ngang nhau. Vì vậy, FJ muốn biết có bao nhiêu tập các con bò thỏa mãn điều kiện khi chia chúng ra thì hai nhóm có sản lượng sữa là bằng nhau.
INPUT
*Dòng 1: Số tự nhiên N.
*Dòng 2..1+N: Dòng thứ i+1 chứa số M(i).
OUTPUT
*Dòng 1: Số tập cân bằng của các con bò.
SUBSETS.inp SUBSETS.out
4
1
2
3
4
SUBSETS.out
3
• 30 % test có n <= 10
Giải thích : Có 3 tập cân bằng: Tập {1,2,3} có thể chia ra thành {1,2} và {3}, tập {1,3,4} chia ra thành {1,3} và {4}, tập {1,2,3,4} có thể chia ra thành {1,4} và {2,3}