Để thư giãn sau những buổi học căng thẳng, An đã chơi một trò chơi như sau: An đặt 3 chiếc cốc úp trên bàn theo hàng ngang, được đánh số từ 1 đến 3 theo thứ tự từ trái sang phải.

Ban đầu, một quả bóng nhỏ được đặt dưới cốc số 1.

Sau đó, An thực hiện liên tiếp một số thao tác đổi chỗ giữa hai cốc. Mỗi thao tác được ký hiệu bởi một trong ba chữ cái sau:

• A: đổi chỗ cốc 1 và cốc 2

• B: đổi chỗ cốc 2 và cốc 3

• C: đổi chỗ cốc 1 và cốc 3

Yêu cầu: Bạn hãy viết chương trình giúp An xác định sau khi thực hiện xong toàn bộ các thao tác, quả bóng nằm dưới cốc số mấy.

Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím)

Gồm một dòng duy nhất chứa một xâu ký tự có độ dài không quá 50, chi gồm các chữ cái A, B, C, mô tả lần lượt các thao tác đổi chỗ.

Kết quả: Ghi ra thiết bị chuẩn (màn hình): Một số nguyên là chỉ số của chiếc cốc đang chứa quả bóng sau khi thực hiện xong tất cả các thao tác.

Ví dụ:

Input:

AB

Output:

3

Giải thích:

Ban đầu quả bóng ở dưới cốc 1.

• Sau thao tác A, cốc 1 và cốc 2 đổi chỗ nên bóng chuyển sang cốc 2;

• Sau thao tác B, cốc 2 và cốc 3 đổi chỗ nên bóng chuyển sang cốc 3.

Vì vậy kết quả cần in ra là 3.

Ràng buộc

• 30% số điểm thỏa mãn xâu ký tự chỉ gồm chữ cái A

• 30% số điểm thỏa mãn xâu ký tự có độ dài không quá 3

• 40% số điểm còn lại không có ràng buộc gì thêm

Nhà An có một mảnh đất có dạng hình tam giác trên mặt phẳng tọa độ. Trên khu đất và khu vực xung quanh có N cây táo. Biết tọa độ ba đỉnh của tam giác biểu diễn mảnh đất và tọa độ của tất cả các cây táo. An cần xác định:

• Diện tích mảnh đất.

• Số cây táo nằm bên trong hoặc trên biên mảnh đất đó.

Diện tích tam giác có ba đỉnh A(XA, YA), B (XB, YB), C (XC, YC) được tính theo công thức:

Yêu cầu: Bạn hãy lập trình giải bài toán trên giúp An nhé.

Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím)

• Ba dòng đầu tiên, mỗi dòng chứa hai số nguyên dương là tọa độ một đỉnh của tam giác.

• Dòng thứ tư ghi số nguyên N (1 ≤ N ≤ 100), số cây táo.

• Mỗi dòng trong số N dòng sau chứa tọa độ của một cây táo.

Tất cả các tọa độ là các cặp số nguyên dương nhỏ hơn 1000, được phân tách bằng dấu cách.

Kết quả: Ghi ra thiết bị chuẩn (màn hình)

• Dòng thứ nhất ghi diện tích mảnh đất của nhà An, với đúng một chữ số sau dấu phẩy;

• Dòng thứ hai ghi số lượng cây táo nằm trong hoặc trên biên của mảnh đất hình tam giác đó.

Ví dụ:

Input:

1 1
5 1
3 3
4
3 1
3 2
3 3
3 4

Output:

4.0
3

Ràng buộc:

• 20% số điểm thỏa mãn tất cả các điểm đều nằm ngoài mảnh đất.

• 20% số điểm thoa mãn tất cả các điểm đều nằm trong mảnh đất.

• 60% số điểm còn lại không có ràng buộc gì thêm.

Tại Trung tâm Tình nguyện quốc gia, An đang cùng các tình nguyện viên phân phối nước sạch cho người dân ở một vùng hạn hán. Trước mặt họ là N chiếc can nhựa chứa nước, được đánh số từ 1 đến N. Mỗi chiếc can có dung tích tối đa và một lượng nước hiện có khác nhau. Các tình nguyện viên đang suy nghĩ để tối ưu việc vận chuyển đến các điểm cấp phát, cụ thể họ muốn làm rỗng càng nhiều can càng tốt (để mang đi lấy nước mới), bằng cách rót nước giữa các can với nhau, sao cho không làm đổ nước ra ngoài. Họ có thể rót nước giữa các can thoải mái, bao nhiêu lần cũng được, miễn là không vượt quá dung tích tối đa của mỗi can.

Yêu cầu: Bạn hãy giúp An cùng đội tình nguyện tìm ra số lượng lớn nhất các can có thể làm rỗng.

Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím)

• Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 1000) - số lượng can.

• Mỗi dòng trong N dòng tiếp theo chứa hai số nguyên Wi và C:

• Wi (0 ≤ Wi ≤ 10^9): lượng nước hiện có trong can thứ i.

• C (1 ≤ Ci ≤ 10^9): dung tích tối đa của can thứ i.

Dữ liệu đảm bảo rằng Wi ≤ Ci.

Kết quả: Ghi ra thiết bị chuẩn (màn hình) số lượng can tối đa có thể làm rỗng.

Ví dụ:

Input:

5
4 5
2 7
5 5
0 10
7 9

Output:

3

Giải thích:

Một phương án tối ưu đưa ra với số lượng nước còn lại của các can theo thứ từ từ 1 đến 5 là: 0 0 0 10 8.

Cách làm như sau:

Đổ toàn bộ nước từ can số 1 vào can số 2.

Đổ toàn bộ nước từ can số 2 vào can số 4.

Đổ bốn lít nước từ can số 3 vào can số 4.

Đổ một lít từ can số 3 vào can số 5.

Kết quả là các can số 1, 2 và 3 hiện đã rỗng.

Ràng buộc:

• 40% số điểm thỏa mãn tất cả các can có cùng dung tích.

• 60% số điểm còn lại không có ràng buộc gì thêm.