Hotline : +84 0988.131.808       endefr
  1. Anh Đông
  2. Thảo luận Internet CNTT
  3. Thứ năm, Tháng 3 16 2017, 02:36 PM
  4.  Đăng ký qua email

Nông dân John và đàn bò ngốc nghếch của ông ta đang tập luyện cho vở nhạc kịch mới, "The Street Cow Named Desire". Tại một thời điểm trong lúc diễn tập, đàn bò của John chồng lên nhau thành N (1 <= N <= 1,000) cột, mỗi cột có 30 con, con nọ đứng lên lưng con kia (mấy con bò này thật thú vị). Vì thế mà trên đồng cỏ các cột bò này coi như là các ô nhỏ và bên cạnh đó còn có M ô (1 <= M <= 1,000) là các đống cỏ khô.

Dưới đây là ví dụ về một đồng cỏ :

                8 .........
                7 ....CH.H.         C = cột 30 con bò
                6 .........
                5 .........         H = đống cỏ khô
                4 ..C.HH...
                3 .........
                2 .....C.HH
                1 .........
                  123456789

Là người chỉ đạo buổi nhạc kịch, John có 4 cái còi với 4 âm thanh khác nhau. Một cái còi sẽ ra lệnh cho tất cả các con bò ở dưới cùng của mỗi cột bò di chuyển ( tất cả các con bò ở cột đó tất nhiên cũng bị di chuyển theo )về phía bắc 1 đơn vị, cái khác lại ra lệnh cho di chuyển về phía nam, 1 cái về phía đông và cái còn lại về hướng tây.

Mỗi lần các cột bò đi vào một ô mà có cỏ khô, con bò trên cùng của cột bò ( kể cả nếu cột bò chỉ còn mỗi một con ) sẽ nhảy vào đống cỏ khô trong khi số còn lại sẽ tiếp tục di chuyển vào ô có đống cỏ đó. Vì vậy, nếu con bò ở dưới cùng mà đi qua 30 đống cỏ khô ( các đống cỏ có thể khác nhau hoặc không khác nhau ) thì cột bò sẽ hết sạch bò. Giả sử rằng các đống cỏ khô có sức chịu đựng là không giới hạn, bao nhiêu bò ở trên cũng được.

Nông dân John liếc qua đồng cỏ của mình nhìn về phía khu vắt sữa bò của nông dân Don và kinh hoàng khi thấy một thùng chứa sữa khổng lồ bị nổ tung, sữa đổ tràn ra ngoài thành một cơn lũ sữa và nó đang tràn về phía các con bò của John. Các con bò ở trên các đống cỏ khô thì sẽ an toàn, John cần phải làm tất cả để cứu được nhiều con bò nhất có thể bằng cách sử dụng các cái còi để ra lệnh cho đàn bò.

Cho số nguyên K ( 1 <= K <= 30 ) là số giây John có thể thổi còi cho đến khi lũ sữa ập tới và các tọa độ X_i, Y_i (1 <= X_i <= 1,000; 1 <= Y_i <= 1,000) của N cột bò và M đống cỏ khô ( trên các đống cỏ khô hiện thời chưa có con bò nào ), hãy cho biết số lượng lớn nhất bò có thể cứu được và trình tự thổi còi ra sao. Trình tự thổi còi sẽ là một xâu ký tự bao gồm 4 loại ký tự tương ứng với 4 hướng, ‘E’ là hướng Đông, ‘N’ là hướng Bắc, ‘W’ là hướng Tây, ‘S’ là phía Nam. Trong tất cả các trình tự thoả mãn thì ghi ra trình tự có thứ tự từ điển nhỏ nhất.

Vị trí lúc đầu của các con bò và các đống cỏ là khác nhau.

Các con bò có thể di chuyển tới bất kỳ vị trí nào, kể cả ra ngoài cánh đồng.

Dữ liệu

  • Dòng 1: 3 số nguyên cách nhau bởi dấu cách: N, M, và K
  • Dòng 2..N+1: Dòng i+1 mô tả tọa độ X,Y của 1 cột bò bằng 2 số nguyên cách nhau bởi dấu cách: X_i và Y_i
  • Dòng N+2..N+M+1: Dòng i+N+1 mô tả tọa độ X,Y của một đống cỏ khô bằng 2 số nguyên cách nhau bởi dấu cách: X_i and Y_i
Bình luận
Không có ý kiến đóng góp nào.
Thêm bình luận
Thu Viên Chấp nhận Trả lời
0
Bầu chọn

Kết quả

  • Dòng 1: Một số nguyên cho biết số lượng nhiều nhất bò có thể cứu được.
  • Dòng 2: K ký tự, trình tự ra lệnh có thứ tự từ điển nhỏ nhất mà John có thể thực hiện nhằm cứu được nhiều con bò nhất.

Ví dụ

Dữ liệu
3 6 3
3 4
6 2
5 7
8 2
9 2
6 4
5 4
6 7
8 7

Kết quả
6
EEE

Giải thích

Sử dụng còi ‘Đông’ 3 lần, lúc mà cơn lũ sữa tràn đến thì ở mỗi đống cỏ cứu được 1 con bò.

Bình luận
Không có ý kiến đóng góp nào.
Thêm bình luận
  1. hơn một tháng trước đây
  2. Thảo luận Internet CNTT
  3. Trả lời này
  • Trang :
  • 1


Không có trả lời ở đây.
khách
Gửi phản hồi của bạn
Tải lên tập tin hoặc hình ảnh cho cuộc thảo luận này bằng cách nhấp vào nút tải ở dưới. hỗ trợ gif,jpg,png,zip,rar
• Xóa s (Maximum File Size: 2 MB)
Bạn có thể chèn các thăm dò ý kiến vào bài viết của bạn. Các cuộc thăm dò sau đó sẽ xuất hiện trong bài viết.
Tùy chọn bỏ phiếu
Chia sẻ vị trí

Chia sẻ vị trí hiện tại của bạn trong khi đăng một câu hỏi mới cho phép người xem để xác định vị trí bạn đang nằm.

Vi độ:
Kinh độ:
  • Bùi Văn Lương
    1897.00 Điểm
  • Hoàng Tiến An
    1502.00 Điểm
  • Phạm Minh Anh
    1335.00 Điểm
  • Hoàng Trung Kiên
    1197.00 Điểm
  • Nguyễn Anh Đông
    1165.00 Điểm
  • Nguyễn Văn Cường
    1042.00 Điểm
  • Hoàng Mạnh Thái
    942.00 Điểm
  • Hoàng Anh Thư
    815.00 Điểm
  • Hoàng Thế Anh
    792.00 Điểm
  • Triệu Hùng Cường
    692.00 Điểm
  • Hoàng Thị Mai
    625.00 Điểm
  • Triệu Mai Anh
    237.00 Điểm
  • Lưu Phương Dung
    162.00 Điểm
  • Phạm Thị Hồng
    142.00 Điểm
  • Hoàng Thế Quỳnh
    87.00 Điểm