| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2012 - Times 17 | 100 (p) | 4.0s | 512M |
| 2 | USACO 2012 - Connect the Cows | 100 (p) | 4.0s | 512M |
| 3 | USACO 2012 - Wrong Directions | 100 (p) | 4.0s | 512M |
Sau khi nhận ra rằng phát triển phần mềm có thể đem lại rất nhiều tiền, Farmer John đã mở một nghề tay trái nhỏ, viết các chương trình ngắn cho khách hàng trong ngành nông nghiệp địa phương.
Nhiệm vụ lập trình đầu tiên của Farmer John có vẻ khá đơn giản đối với ông, gần như quá đơn giản: khách hàng muốn ông viết một chương trình nhận một số \(N\) làm đầu vào và in ra \(17\) lần \(N\). Farmer John vừa viết xong chương trình đơn giản này thì khách hàng hoảng hốt gọi điện, báo rằng cả đầu vào lẫn đầu ra đều phải được biểu diễn dưới dạng số nhị phân và các số này có thể rất lớn.
Hãy giúp Farmer John hoàn thành nhiệm vụ lập trình. Cho số \(N\) ở dạng nhị phân với không quá 1000 chữ số, hãy viết ra biểu diễn nhị phân của \(17\) lần \(N\).
Dòng đầu tiên chứa biểu diễn nhị phân của \(N\) (không quá 1000 chữ số).
In ra biểu diễn nhị phân của \(N\) nhân với \(17\).
Ví dụ 1
10110111110000100111Số nhị phân \(10110111\) bằng \(183\) trong hệ thập phân. Ta có \(183 \times 17 = 3111\), và \(3111\) được biểu diễn là \(110000100111\) trong hệ nhị phân.
USACO 2012 March Contest, Bronze Division — Times 17. Tác giả đề: Brian Dean (2012).
Mỗi ngày, Farmer John đi quanh trang trại để kiểm tra sức khỏe và tình trạng của \(N\) con bò (\(1 \leq N \leq 10\)).
Vị trí của mỗi con bò được mô tả bằng một điểm trên mặt phẳng hai chiều, còn Farmer John xuất phát tại gốc tọa độ \((0,0)\). Để hành trình thú vị hơn, Farmer John quyết định chỉ đi theo các hướng song song với các trục tọa độ, tức là chỉ đi về phía bắc, nam, đông hoặc tây. Hơn nữa, ông chỉ đổi hướng di chuyển khi đến vị trí của một con bò (nếu muốn, ông cũng có thể đi qua vị trí của một con bò mà không đổi hướng). Khi đổi hướng di chuyển, ông có thể rẽ \(90\) độ hoặc quay \(180\) độ. Sau khi thăm tất cả đàn bò, hành trình của FJ phải đưa ông trở về gốc tọa độ.
Hãy tính số hành trình khác nhau mà FJ có thể thực hiện để thăm \(N\) con bò nếu ông đổi hướng đúng một lần tại vị trí của mỗi con. Ông được phép đi qua vị trí của một con bò mà không đổi hướng bao nhiêu lần tùy ý. Cùng một lộ trình hình học nhưng đi theo chiều xuôi và chiều ngược được tính là hai hành trình khác nhau.
In ra số hành trình khác nhau mà FJ có thể thực hiện. Kết quả có thể bằng 0 nếu không có hành trình hợp lệ.
Ví dụ 1
4
0 1
2 1
2 0
2 -52Có 4 con bò tại các vị trí \((0,1)\), \((2,1)\), \((2,0)\) và \((2,-5)\).
Có hai hành trình khác nhau: Farmer John có thể thăm đàn bò theo thứ tự 1-2-4-3 hoặc 3-4-2-1 trước khi trở về gốc tọa độ.
USACO 2012 March Contest, Bronze Division — Connect the Cows. Tác giả đề: Brian Dean (2012).
Farmer John vừa mua một chiếc máy kéo lập trình được đời mới rất hiện đại. Để điều khiển máy kéo di chuyển, ông nhập một xâu độ dài \(N\) (\(1 \leq N \leq 100\,000\)) chỉ gồm các ký tự F, L và R. Mỗi ký tự F ra lệnh cho máy kéo tiến về phía trước một đơn vị, còn các ký tự L và R lần lượt khiến máy kéo rẽ trái và rẽ phải \(90\) độ. Ban đầu, máy kéo ở gốc tọa độ \((0,0)\) và quay mặt về phía bắc.
Sau khi lập trình máy kéo bằng cách nhập xâu lệnh dự định, FJ nhớ ra rằng mình đã gõ sai đúng một ký tự trong xâu lệnh, nhưng ông không nhớ đó là ký tự nào! Chẳng hạn, ông có thể đã gõ F hoặc L tại vị trí mà xâu dự định chứa ký tự R. Hãy tính số vị trí khác nhau trên mặt phẳng mà máy kéo có thể dừng lại do lỗi này (hướng mà máy kéo quay mặt khi ở vị trí cuối cùng không quan trọng).
Dòng đầu tiên chứa xâu lệnh mà Farmer John dự định nhập.
In ra số vị trí mà máy kéo có thể dừng lại, với điều kiện FJ gõ sai một trong các ký tự của xâu lệnh.
Ví dụ 1
FF3Farmer John muốn máy kéo tiến về phía trước hai lần và trong trường hợp lý tưởng sẽ dừng tại vị trí \((0,2)\).
Có 4 xâu lệnh bị gõ sai có thể xảy ra: FL, FR, LF và RF. Chúng lần lượt đưa máy kéo tới \((0,1)\), \((0,1)\), \((-1,0)\) và \((1,0)\), tổng cộng là 3 vị trí phân biệt.
USACO 2012 March Contest, Bronze Division — Wrong Directions. Tác giả đề: Brian Dean (2012).