USACO 2013 - US Open - Hạng Đồng

Trong nỗ lực thách thức quan niệm rập khuôn rằng bò là những sinh vật vụng về, Bessie, cô bò quý của Farmer John, đã đăng ký một lớp ba lê nhập môn. Buổi biểu diễn cuối khóa của cô diễn ra vào tuần tới, và FJ muốn giúp cô bằng cách dựng một sân khấu hình chữ nhật đủ lớn để cô có thể thực hiện toàn bộ bài múa mà không bị ngã khỏi mép sân khấu.

Bài múa của Bessie sẽ diễn ra trên một sân khấu hình chữ nhật gồm một lưới các ô vuông \(1 \times 1\). Bốn chân của Bessie được ký hiệu ngắn gọn như sau:

FR: Chân trước bên phải
FL: Chân trước bên trái
RR: Chân sau bên phải
RL: Chân sau bên trái

Ban đầu, bốn chân của cô nằm trong 4 ô kề nhau tạo thành một hình vuông như sau, với Bessie quay mặt về hướng bắc:

FL FR
RL RR

Bài múa của Bessie tuân theo một chuỗi gồm \(N\) chỉ dẫn (\(1 \le N \le 1000\)), mỗi chỉ dẫn yêu cầu cô di chuyển một chân sang một ô hoặc xoay 90 độ theo chiều kim đồng hồ.

Chỉ dẫn di chuyển một chân gồm 3 ký tự: hai ký tự đầu xác định chân cần di chuyển, còn ký tự cuối xác định hướng di chuyển (F = tiến, B = lùi, R = sang phải, L = sang trái). Ví dụ, FRF nghĩa là Bessie phải di chuyển chân trước bên phải về phía trước một ô, còn RLR nghĩa là cô phải di chuyển chân sau bên trái sang phải một ô. Tất nhiên, hướng di chuyển được tính tương đối theo hướng mà Bessie đang quay mặt.

Chỉ dẫn xoay cũng gồm 3 ký tự: hai ký tự đầu xác định chân duy nhất mà Bessie giữ cố định và xoay 90 độ theo chiều kim đồng hồ quanh chân đó. Ký tự cuối là P (viết tắt của pivot, tức là xoay). Ví dụ, chỉ dẫn FRP nghĩa là Bessie phải xoay 90 độ theo chiều kim đồng hồ quanh chân trước bên phải đang giữ cố định. Điều này có nghĩa là nếu các chân của cô hiện nằm như sau (với Bessie quay mặt về hướng bắc):

.. .. .. 
.. .. FR 
.. FL .. 
.. RL RR 

thì sau chỉ dẫn FRP, các chân của cô sẽ nằm như sau, với Bessie lúc này quay mặt về hướng đông:

RL FL .. 
RR .. FR 
.. .. ..  
.. .. .. 

Cho \(N\) chỉ dẫn trong bài múa của Bessie, hãy tính diện tích nhỏ nhất của một sân khấu hình chữ nhật cần thiết để chứa các chân của cô trong suốt toàn bộ bài múa.

Nếu Bessie vụng về di chuyển một chân vào cùng ô với một chân khác ở bất kỳ thời điểm nào, cô sẽ vấp ngã và không thể hoàn thành bài múa; trong trường hợp này, hãy in ra -1. Lưu ý rằng đây là trường hợp duy nhất khiến Bessie vấp ngã; sau tất cả quá trình luyện tập, cô đã trở nên khá dẻo dai và có thể dễ dàng đưa chân vào những tư thế khá kỳ lạ (ví dụ, hai chân sau nằm xa về phía trước hơn hai chân trước).

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, từ dòng 2 đến dòng \(1+N\), mỗi dòng chứa một chỉ dẫn gồm 3 ký tự trong bài múa của Bessie.

Dữ liệu ra

• Dòng 1 chứa diện tích nhỏ nhất của một sân khấu hình chữ nhật cần thiết để chứa các chân của Bessie trong suốt toàn bộ bài múa, hoặc -1 nếu Bessie vấp ngã.

Ví dụ

3
FRF
FRP
RLB

16

.. .. .. .. 
.. .. .. .. (quay mặt về hướng bắc)
.. .. FL FR 
.. .. RL RR 

.. .. .. .. 
.. .. .. FR (quay mặt về hướng bắc)
.. .. FL .. 
.. .. RL RR 

.. RL FL .. 
.. RR .. FR (quay mặt về hướng đông)
.. .. .. .. 
.. .. .. .. 

RL .. FL ..
.. RR .. FR (quay mặt về hướng đông)
.. .. .. ..
.. .. .. ..

Nguồn

USACO 2013 US Open, Bronze — Problem 1: Bovine Ballet

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

Không hài lòng với ánh sáng lờ mờ trong chuồng, Farmer John vừa lắp một chiếc đèn chùm mới lộng lẫy gồm \(N\) bóng đèn (\(3 \le N \le 16\)) xếp thành một vòng tròn.

Những cô bò rất thích thú với bộ đèn mới này và vui vẻ chơi trò chơi sau: tại thời điểm \(T\), chúng đảo trạng thái của mỗi bóng đèn nếu bóng đèn bên trái nó đang bật tại thời điểm \(T-1\). Chúng tiếp tục trò chơi trong \(B\) đơn vị thời gian (\(1 \le B \le 10^{15}\)). Lưu ý rằng \(B\) có thể quá lớn để lưu trong một số nguyên 32 bit tiêu chuẩn.

Cho trạng thái ban đầu của các bóng đèn, hãy xác định trạng thái cuối cùng của chúng sau khi \(B\) đơn vị thời gian trôi qua.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(B\), cách nhau bởi một dấu cách.
• Các dòng từ 2 đến \(1+N\): dòng \(i+1\) chứa trạng thái ban đầu của bóng đèn \(i\), là 0 (tắt) hoặc 1 (bật).

Dữ liệu ra

• Các dòng từ 1 đến \(N\): dòng \(i\) chứa trạng thái cuối cùng của bóng đèn \(i\), là 0 (tắt) hoặc 1 (bật).

Ví dụ

5 6
1
0
0
0
0

1
1
1
0
1

Thời điểm T=0: 1 0 0 0 0
Thời điểm T=1: 1 1 0 0 0
Thời điểm T=2: 1 0 1 0 0
Thời điểm T=3: 1 1 1 1 0
Thời điểm T=4: 1 0 0 0 1
Thời điểm T=5: 0 1 0 0 1
Thời điểm T=6: 1 1 1 0 1

Nguồn

USACO 2013 US Open, Bronze — Problem 2: Blink

Tác giả đề: Videh Seksaria và Brian Dean, 2013.

Buổi liên khối chuyên Tin của trường Nguyễn Bỉnh Khiêm diễn ra với sự tham gia của \(N\) học sinh. Cuối giờ, Oanh Trúc Béo ra hiệu cho các học sinh này xếp thành một hàng và đánh số họ từ \(1\) đến \(N\) tương ứng với vị trí đứng của họ trong hàng. Oanh Trúc muốn chụp một số tấm ảnh kỷ niệm cho buổi liên khối, mỗi tấm sẽ chụp lại một đoạn liên tiếp các bạn trong hàng. Vì là một sự kiện trong đại nên Trúc muốn mỗi bạn học sinh tham dự đều có mặt trong ít nhất một tấm ảnh.

Tuy nhiên, trong \(N\) học sinh này có tồn tại \(K\) đôi bạn xung khắc nhau (đã từng là bạn thân nhưng hiện tại tình nghĩa đã vô cùng rạn nứt vì crush chung một em gái nào đó), các đôi bạn xung khắc này đều không muốn đứng chung với nhau trong một tấm ảnh. Bộ nhớ của điện thoại Oanh Trúc không còn nhiều nên cô ấy đã nhờ bạn lập trình tính toán số tấm ảnh ít nhất cần chụp để thỏa mãn tất cả các ràng buộc trên.

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(K\) (\(2\leq N\leq 10^9\), \(2\leq K\leq 1000\)).

• Dòng thứ \(i\) trong \(K\) dòng tiếp theo chứa hai số nguyên dương phân biệt \(A_i\) và \(B_i\) thể hiện một đôi bạn xung khắc \(\left(A_i, B_i\right)\) - họ không thể cùng đứng chung trong một tấm ảnh.

Output

• Một số nguyên duy nhất là số tấm ảnh ít nhất mà Oanh Trúc Béo cần chụp.

Example

7 3
1 3
2 4
5 6

3

\(N\) cô bò của Farmer John (\(4 \le N \le 12\), \(N\) chẵn) đã xây dựng một hệ thống thô sơ để các cặp bò thân thiết liên lạc với nhau bằng những sợi dây được bảo vệ bởi lớp bọc làm từ cỏ khô.

Mỗi cô bò có đúng 3 người bạn khác trong chuồng, và các cô bò phải tự sắp xếp để đứng trong \(N\) ô chuồng thẳng hàng. Một sợi dây có độ dài \(L\) cần đúng \(L\) đơn vị cỏ khô để làm, vì vậy, chẳng hạn nếu hai cô bò trong ô chuồng 4 và 7 là bạn thì cần 3 đơn vị cỏ khô để làm một sợi dây nối chúng.

Giả sử mỗi cặp bò thân thiết phải được nối bằng một sợi dây riêng, hãy xác định lượng cỏ khô ít nhất có thể cần để làm các sợi dây nếu các cô bò tự sắp xếp theo thứ tự tối ưu.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\). Các cô bò của FJ được đánh số thuận tiện từ 1 đến \(N\).
• Các dòng từ 2 đến \(1+N\): mỗi dòng chứa ba số nguyên cách nhau bởi dấu cách và nằm trong khoảng từ 1 đến \(N\). Dòng \(i+1\) chứa số hiệu của ba người bạn của cô bò \(i\). Nếu cô bò \(i\) là bạn của cô bò \(j\), thì cô bò \(j\) cũng là bạn của cô bò \(i\).

Dữ liệu ra

• Dòng 1 chứa tổng lượng cỏ khô ít nhất cần để nối tất cả các cặp bò thân thiết.

Ví dụ

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

17

Nguồn

USACO 2013 US Open, Bronze — Problem 4: Haywire

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