USACO 2015 - Tháng 1 - Hạng Vàng

Sau đợt tập huấn dài chuẩn bị cho kì thi VOI, Bảo Anh quyết định sẽ đi phượt để giải tỏa stress. Hôm nay, Anh sẽ đến Tam Kì để thăm người đàn anh thân thiết của mình. Vừa hay, đàn anh của Anh đang bận trồng rau làm ruộng cho vụ mùa năm nay. Vì không muốn tới chơi nhưng không được tiếp đón, Bảo Anh quyết định sẽ giúp người đàn anh hoàn thành công việc sớm.

Thửa ruộng của người đàn anh có 2 loại rau, rau ăn được và rau trồng cho vui. Người đàn anh đang muốn xây một hàng rào hình chữ nhật với các cạnh song song với các trục tọa độ, sao cho trong hình chữ nhật chỉ chứa loại rau ăn được (một bó rau được tính là bao bọc ngay cả khi nó nằm trên ranh giới hàng rào). Trong số tất cả hàng rào có thể xây được, người đàn anh muốn xây hàng rào bao được nhiều loại rau ăn được nhất. Và trong số các hàng rào này, người đàn anh muốn xây hàng rào có diện tích nhỏ nhất có thể. Hàng rào với chiều dài hoặc chiều rộng bằng 0 vẫn được phép.

Bảo Anh muốn giúp người đàn anh hoàn thành công việc, nhưng cậu cũng không muốn làm việc khi đang đi phượt. Vì vậy, bạn hãy giúp Bảo Anh giải bài toán này nhé.

INPUT

• Dòng đầu tiên gồm số nguyên dương \(N\) (\(1 \leq N \leq 500\))
• \(N\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên \(x, y\) (\(0 \leq x, y \leq 1000\)) và 1 kí tự, mô tả tọa độ và loại của rau \(i\). Kí tự H mô tả rau ăn được và G là rau trồng cho vui. Không có 2 bó rau nào ở cùng 1 tọa độ, và có ít nhất 1 bó rau là rau ăn được

OUTPUT

Gồm 2 dòng. Dòng 1 chứa số lượng rau ăn được lớn nhất trong hàng rào mà không có bó rau trồng cho vui nào. Dòng 2 chứa số nguyên là diện tích nhỏ nhất có thể của hàng rào đó.

VÍ DỤ:

INPUT:

5
1 1 H
4 4 H
6 6 H
3 3 G
2 2 H

OUTPUT:

2
1

Hôm nay là ngày nghỉ, Hân muốn xem vài bộ phim anime để giải trí sau một tuần học căng thẳng. Hân rất thích xem anime, do đó cậu ấy muốn xem phim liên tục trong \(L\) phút. Hân có \(N\) bộ phim muốn xem, mỗi bộ có một thời lượng nhất định và có các buổi chiếu trong ngày. Hân có thể vào xem và thoát ra một bộ phim bất cứ lúc nào trong suốt quá trình một buổi chiếu của bộ phim. Tuy nhiên, Hân không muốn vào xem cùng một bộ phim 2 lần, và Hân không thể chuyển sang một buổi chiếu khác của cùng một phim mà bị chồng lên buổi chiếu hiện tại của phim đó.

Hân muốn biết rằng liệu cậu ấy có thể xem phim liên tục từ thời điểm \(0\) xuyên suốt đến thời điểm \(L\) hay không. Nếu được, Hân muốn biết số lượng phim ít nhất mà cậu ấy cần xem để đạt được mục tiêu (vì cậu ấy không thích xem phim bị ngắt quãng). Vì đang chìm đắm trong thế giới anime, Hân không thể tự tính toán được. Bạn hãy giúp Hân giải quyết bài toán này nhé.

INPUT

• Dòng đầu tiên gồm 2 số nguyên dương \(N, L\) (\(1 \leq N \leq 20\), \(1 \leq L \leq 10^8\))
• \(N\) dòng tiếp theo, mỗi dòng mô tả bộ phim thứ \(i\). Mỗi dòng bắt đầu bởi số nguyên \(D\) là thời lượng của bộ phim (\(1 \leq D \leq L\)), và số nguyên \(C\) là số lượng buổi chiếu của phim (\(1 \leq C \leq 1000\)). \(C\) số tiếp theo mô tả thời điểm bắt đầu của mỗi buổi chiếu (\(0 \leq C \leq L\)). Các thời điểm của mỗi buổi chiếu là phân biệt, và theo thứ tự tăng dần.

OUTPUT

Gồm 1 số nguyên là số lượng bộ phim ngắn nhất mà Hân cần coi để đạt được mục tiêu. Nếu không thể xem liên tục \(L\) phút, in ra \(-1\).

VÍ DỤ:

INPUT:

4 100
20 1 0
30 2 20 90
40 2 0 65
50 3 15 30 55

OUTPUT:

3

Đại King là một phi công trẻ tài năng, sở thích của cậu là lái máy bay du lịch khắp nơi. Hôm nay, Đại King quyết định làm 1 chuyến bay thăm quan các thành phố trên thế giới. Tuy nhiên, vì dịch bệnh nên lộ trình của King chỉ có \(N\) thành phố, và mỗi lộ trình chỉ cho phép đường bay một chiều.

Như thường lệ, King muốn thăm quan nhiều thành phố nhất có thể. Vào đầu ngày, cậu ấy luôn xuất phát từ thành phố \(1\) (nơi cậu đang ở), thăm quan một dãy các thành phố, cuối cùng quay trở về thành phố \(1\) vào cuối ngày. King muốn check-in ở số thành phố phân biệt theo lộ trình là lớn nhất có thể (nếu King tới một thành phố nhiều lần thì vẫn chỉ tính là check-in một lần ở đây).

King rất không vui vì sự hạn chế đường đi một chiều của các nước, vì điều này làm giảm số thành phố mà cậu có thể thăm quan. King thắc mắc rằng nếu cậu lách luật và đi ngược chiều tối đa 1 đường bay thì cậu có thể thăm quan được nhiều nhất bao nhiêu thành phố. King đang háo hức vì được lái máy bay nên không tiện tính toán được, bạn hãy giúp cậu ấy nhé.

Hãy tính số thành phố có thể thăm quan lớn nhất, nếu King xuất phát và kết thúc cùng tại thành phố \(1\), đồng thời King cũng có thể đi ngược chiều tối đa 1 đường bay trong lộ trình của anh ấy. Đặc biệt, King không thể đi ngược chiều cùng 1 đường bay 2 lần.

INPUT

• Dòng đầu tiên gồm 2 số nguyên dương \(N, M\) là số thành phố và số đường bay được bay (\(1 \leq N, M \leq 10^5\))
• \(M\) dòng tiếp theo, mỗi dòng mô tả đường đi 1 chiều thứ \(i\). Mỗi dòng gồm 2 số nguyên dương \(u, v\) (\(1 \leq u, v \leq N\)) thể hiện đường bay 1 chiều từ \(u\) đến \(v\). Không có đường bay nào xuất hiện quá 1 lần.

OUTPUT

Gồm 1 số nguyên là số lượng thành phố phân biệt mà King có thể thăm quan

VÍ DỤ:

INPUT:

7 10
1 2
3 5
2 4
4 7
3 1
2 5  
3 7
3 6
6 5
7 2

OUTPUT:

6

Giải thích: King có thể thăm quan thành phố \(1, 2, 4, 7, 2, 5, 3, 1\) bằng cách đi ngược chiều đường bay từ 5 đến 3.