USACO 2017 - Tháng 12 - Hạng Đồng

Trong những buổi vắt sữa kéo dài, cô bò Bessie thích nhìn qua cửa sổ chuồng bò về phía hai tấm biển quảng cáo hình chữ nhật khổng lồ bên kia đường, quảng cáo cho “Cỏ linh lăng ngon tuyệt của bác nông dân Alex” và “Ngũ cốc tuyệt hảo của bác nông dân Greg”. Hình ảnh hai loại thức ăn cho bò trên các tấm biển trông hấp dẫn với Bessie hơn nhiều so với cỏ ở trang trại của cô.

Một ngày nọ, khi Bessie đang nhìn ra cửa sổ, cô hoảng hốt thấy một chiếc xe tải hình chữ nhật khổng lồ đỗ bên kia đường. Thành xe có quảng cáo “Bít tết hảo hạng của bác nông dân Smith”; Bessie không hiểu lắm về quảng cáo này, nhưng điều cô lo nhất là chiếc xe tải có thể che khuất hai tấm biển yêu thích của mình.

Cho vị trí của hai tấm biển quảng cáo và vị trí của chiếc xe tải, hãy tính tổng diện tích của cả hai tấm biển vẫn còn nhìn thấy được. Chiếc xe tải có thể không che tấm biển nào, che cả hai, hoặc chỉ che một tấm biển.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên cách nhau bởi dấu cách: \(x_1\) \(y_1\) \(x_2\) \(y_2\), trong đó \((x_1, y_1)\) và \((x_2, y_2)\) lần lượt là tọa độ góc dưới bên trái và góc trên bên phải của tấm biển thứ nhất trong trường nhìn hai chiều của Bessie. Dòng tiếp theo chứa thêm bốn số nguyên, tương tự mô tả góc dưới bên trái và góc trên bên phải của tấm biển thứ hai. Dòng thứ ba, cũng là dòng cuối cùng, chứa bốn số nguyên mô tả góc dưới bên trái và góc trên bên phải của chiếc xe tải. Mọi tọa độ đều nằm trong khoảng từ \(-1000\) đến \(+1000\). Hai tấm biển được đảm bảo không có phần giao nhau với diện tích dương.

Dữ liệu ra

In ra tổng diện tích của cả hai tấm biển vẫn còn nhìn thấy được.

Ví dụ

1 2 3 5
6 0 10 4
2 1 8 3

17

Nguồn

USACO 2017 December Contest, Bronze — Blocked Billboard

Tác giả bài toán: Brian Dean.

Tin rằng những cô bò vui vẻ sẽ cho nhiều sữa hơn, bác nông dân John đã lắp một quả cầu disco khổng lồ trong chuồng và dự định dạy đàn bò của mình khiêu vũ!

Sau khi tìm hiểu các điệu nhảy phổ biến của loài bò, bác nông dân John quyết định dạy đàn bò điệu “Bovine Shuffle”. Điệu Bovine Shuffle bắt đầu với \(N\) cô bò (\(1 \leq N \leq 100\)) xếp thành một hàng theo một thứ tự nào đó, rồi thực hiện liên tiếp ba lần “xáo trộn”; sau đó, chúng có thể xếp theo một thứ tự khác. Để đàn bò dễ xác định vị trí của mình hơn, bác nông dân John đánh dấu các vị trí trong hàng từ \(1 \ldots N\): cô bò đầu hàng đứng ở vị trí \(1\), cô tiếp theo ở vị trí \(2\), và cứ thế cho đến vị trí \(N\).

Một lần xáo trộn được mô tả bởi \(N\) số \(a_1 \ldots a_N\), trong đó cô bò ở vị trí \(i\) sẽ di chuyển đến vị trí \(a_i\) trong lần xáo trộn đó (vì vậy mỗi \(a_i\) nằm trong khoảng \(1 \ldots N\)). Mọi cô bò đều di chuyển đến vị trí mới trong lần xáo trộn. May mắn thay, tất cả các giá trị \(a_i\) đều khác nhau, nên không có hai cô bò nào cố di chuyển đến cùng một vị trí.

Mỗi cô bò của bác nông dân John được gán một mã ID nguyên gồm \(7\) chữ số, và các mã ID đôi một khác nhau. Biết thứ tự của đàn bò sau ba lần xáo trộn, hãy xác định thứ tự ban đầu của chúng.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), số lượng bò. Dòng tiếp theo chứa \(N\) số nguyên \(a_1 \ldots a_N\). Dòng cuối cùng chứa thứ tự của \(N\) cô bò sau ba lần xáo trộn, trong đó mỗi cô bò được biểu diễn bằng mã ID của mình.

Dữ liệu ra

In ra \(N\) dòng, mỗi dòng chứa mã ID của một cô bò, mô tả thứ tự của đàn bò trước ba lần xáo trộn.

Ví dụ

5
1 3 4 5 2
1234567 2222222 3333333 4444444 5555555

1234567
5555555
2222222
3333333
4444444

Nguồn

USACO 2017 December Contest, Bronze — The Bovine Shuffle

Tác giả bài toán: Brian Dean.

Bác nông dân John mua ba cô bò: Bessie, Elsie và Mildred; ban đầu mỗi cô cho \(7\) gallon sữa mỗi ngày. Vì sản lượng sữa của một cô bò có thể thay đổi theo thời gian, bác nông dân John định kỳ đo sản lượng trong \(100\) ngày tiếp theo và ghi vội kết quả vào sổ nhật ký. Các mục trong sổ có dạng như sau:

35 Bessie -2
14 Mildred +3

Mục đầu tiên cho biết vào ngày \(35\), sản lượng sữa của Bessie thấp hơn \(2\) gallon so với lần đo gần nhất. Mục tiếp theo cho biết vào ngày \(14\), sản lượng sữa của Mildred tăng \(3\) gallon so với lần đo gần nhất. Bác nông dân John chỉ có đủ thời gian để thực hiện nhiều nhất một phép đo trong mỗi ngày. Không may là bác khá thiếu ngăn nắp và không nhất thiết ghi các phép đo theo thứ tự thời gian.

Để khích lệ đàn bò, bác nông dân John tự hào trưng trên tường chuồng ảnh của cô bò đang có sản lượng sữa cao nhất (nếu nhiều cô bò cùng đạt sản lượng cao nhất, bác trưng ảnh của tất cả các cô đó). Hãy xác định số ngày mà bác nông dân John cần thay đổi bảng ảnh này.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), số phép đo bác nông dân John thực hiện. Mỗi dòng trong \(N\) dòng tiếp theo chứa một phép đo theo định dạng trên, gồm một ngày (một số nguyên trong khoảng \(1 \ldots 100\)), tên của một cô bò và mức thay đổi sản lượng sữa của cô ấy kể từ lần đo gần nhất (một số nguyên khác \(0\)). Sản lượng sữa của mỗi cô bò luôn nằm trong khoảng \(0 \ldots 1000\).

Dữ liệu ra

In ra số ngày (một số nguyên trong khoảng \(0 \ldots 100\)) mà bác nông dân John cần điều chỉnh bảng ảnh khích lệ của mình.

Ví dụ

4
7 Mildred +3
4 Elsie -1
9 Mildred -1
1 Bessie +2

3

Nguồn

USACO 2017 December Contest, Bronze — Milk Measurement

Tác giả bài toán: Brian Dean.