USACO 2013 - Tháng 1 - Hạng Đồng

Những con bò của Farmer John đã gây quá nhiều rắc rối quanh trang trại, vì vậy FJ muốn giám sát chúng kỹ hơn. Bằng cách lắp đặt \(N\) hàng rào phản chiếu (\(1 \le N \le 200\)) tại nhiều vị trí trong trang trại, ông hy vọng có thể nhìn từ ngôi nhà ở vị trí \((0,0)\) đến chuồng ở vị trí \((a,b)\).

Trên bản đồ hai chiều của trang trại FJ, hàng rào \(i\) là một đoạn thẳng ngắn có tâm tại vị trí nguyên \((x_i, y_i)\) và nghiêng \(45\) độ (theo hình dạng / hoặc \). Chẳng hạn, một hàng rào có hướng / tại vị trí \((3,5)\) có thể được mô tả là đoạn thẳng từ \((2.9,4.9)\) đến \((3.1,5.1)\). Mỗi hàng rào (và cả vị trí của chuồng) nằm ở một vị trí riêng biệt có tọa độ nguyên trong khoảng từ \(-1\,000\,000\) đến \(1\,000\,000\). Không có hàng rào nào nằm tại \((0,0)\) hoặc \((a,b)\).

FJ dự định ngồi tại nhà ở vị trí \((0,0)\) và nhìn thẳng sang phải (theo hướng \(+x\)). Với ánh nhìn phản xạ qua một số hàng rào phản chiếu trong trang trại, ông hy vọng có thể nhìn thấy điểm \((a,b)\). Không may, FJ cho rằng ông đã đặt sai hướng của một hàng rào (chẳng hạn, \ thay vì /). Hãy in chỉ số của hàng rào đầu tiên trong danh sách của FJ sao cho khi đảo hướng của nó (giữa / và \), FJ có thể nhìn thấy điểm \((a,b)\).

Nếu FJ đã có thể nhìn thấy điểm \((a,b)\) mà không cần đảo hướng hàng rào nào, hãy in \(0\). Nếu ông vẫn không thể nhìn thấy \((a,b)\) ngay cả sau khi đảo hướng nhiều nhất một hàng rào, hãy in \(-1\).

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(N\), \(a\) và \(b\), cách nhau bởi dấu cách.
• \(N\) dòng tiếp theo: dòng thứ \(i+1\) mô tả hàng rào \(i\) và có dạng x_i y_i / hoặc x_i y_i \, trong đó \((x_i, y_i)\) là vị trí tâm của hàng rào, còn \ hoặc / cho biết hướng của nó.

Dữ liệu ra

In ra chỉ số của hàng rào đầu tiên mà việc đảo hướng hàng rào đó cho phép FJ nhìn thấy điểm \((a,b)\). Nếu FJ đã có thể nhìn thấy điểm \((a,b)\), hãy in \(0\); nếu không có cách nào để ông nhìn thấy \((a,b)\) ngay cả sau khi đảo hướng nhiều nhất một hàng rào, hãy in \(-1\).

Ví dụ

5 6 2
3 0 /
0 2 /
1 2 /
3 2 \
1 3 \

4

3 .\.....
2 //.\..B
1 .......
0 H../...
  0123456

3 .\.....
2 //./--B
1 ...|...
0 H--/...
  0123456

Nguồn

USACO 2013 January Contest, Bronze — Problem 1: Mirrors

Tác giả đề: Brian Dean và Travis Hance, 2013.

Farmer John đã nghĩ ra một phương pháp tuyệt vời để sơn hàng rào dài cạnh chuồng của mình (hãy xem hàng rào như một trục số một chiều). Ông chỉ việc gắn một chiếc chổi sơn vào Bessie, con bò yêu thích của mình, rồi thong thả đi uống một ly nước lạnh trong khi Bessie đi tới đi lui dọc hàng rào và quét sơn lên mọi đoạn hàng rào mà cô đi qua.

Bessie bắt đầu tại vị trí \(0\) trên hàng rào và thực hiện một chuỗi \(N\) bước di chuyển (\(1 \le N \le 100\,000\)). Chẳng hạn, bước 10 L nghĩa là Bessie di chuyển \(10\) đơn vị sang trái, còn 15 R nghĩa là Bessie di chuyển \(15\) đơn vị sang phải. Với danh sách tất cả các bước di chuyển của Bessie, FJ muốn biết phần nào của hàng rào được phủ ít nhất \(K\) lớp sơn. Trong suốt hành trình, Bessie sẽ cách gốc tọa độ không quá \(1\,000\,000\,000\) đơn vị.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách.
• \(N\) dòng tiếp theo, mỗi dòng mô tả một bước di chuyển của Bessie (chẳng hạn 15 L).

Dữ liệu ra

In ra tổng độ dài được phủ ít nhất \(K\) lớp sơn.

Ví dụ

6 2
2 R
6 L
1 R
8 L
1 R
2 R

6

Nguồn

USACO 2013 January Contest, Silver — Problem 1: Painting the Fence

Tác giả đề: Brian Dean, 2012.

Sau khi ở bên những con bò quá lâu, Farmer John đã bắt đầu hiểu ngôn ngữ của chúng. Hơn nữa, ông nhận thấy trong số \(N\) con bò (\(2 \le N \le 1000\)), một số luôn nói thật, còn những con khác luôn nói dối.

FJ cẩn thận lắng nghe \(M\) phát biểu (\(1 \le M \le 10\,000\)) từ những con bò, mỗi phát biểu có dạng x y T, nghĩa là "bò \(x\) khẳng định bò \(y\) luôn nói thật", hoặc x y L, nghĩa là "bò \(x\) khẳng định bò \(y\) luôn nói dối". Mỗi phát biểu liên quan đến một cặp bò khác nhau, và cùng một cặp bò có thể xuất hiện trong nhiều phát biểu.

Không may, FJ cho rằng mình có thể đã ghi sai một số mục trong danh sách, nên có thể không tồn tại cách hợp lệ để xác định mỗi con bò là bò nói thật hay bò nói dối mà nhất quán với cả \(M\) phát biểu trong danh sách của FJ. Để giúp FJ tận dụng được nhiều nhất có thể từ danh sách, hãy tính giá trị \(A\) lớn nhất sao cho tồn tại một cách hợp lệ để xác định mỗi con bò là bò nói thật hoặc bò nói dối, đồng thời nhất quán với \(A\) mục đầu tiên trong danh sách của FJ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.
• \(M\) dòng tiếp theo, mỗi dòng có dạng x y L hoặc x y T, mô tả một phát biểu của bò \(x\) về bò \(y\).

Dữ liệu ra

In ra giá trị \(A\) lớn nhất sao cho \(A\) mục đầu tiên trong danh sách của FJ có thể nhất quán với một cách gán trạng thái "nói thật" hoặc "nói dối" nào đó cho \(N\) con bò.

Ví dụ

4 3
1 4 L
2 3 T
4 1 T

2

Nguồn

USACO 2013 January Contest, Bronze — Problem 3: Liars and Truth Tellers

Tác giả đề: Brian Dean, 2013.