Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Đàn cừu hỗn loạn

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Đàn cừu hỗn loạn   Tue 27 Jul 2010, 13:48

Ngày đẹp trời nọ, đàn cừu trắng rủ nhau đi chơi. Chúng đi đến một chiếc cầu thì gặp một đàn cừu đen cũng đang dẫn nhau đi chơi. :D.

Chiếc cầu có độ dài 2*N+1. Mỗi đàn cừu đều có N con, mỗi con chiếm hết một đơn vị độ dài trên cầu. Hai đàn cừu đứng ở 2 đầu cầu, vì thế chỉ trống 1 ô duy nhất ở giữa cầu. Các con cừu đều hiếu chiến, không chịu lùi và chỉ muốn tiến. Vì thế muốn đi lên phía trước chỉ có thể đi vào ô trống, hoặc nhảy qua các con cừu khác để đến ô trống. Tuy vậy sức các con cừu có hạn, chỉ nhảy qua được tối đa 1 con cừu khác mà thôi.

Các con cừu không thông minh cho lắm nên không tìm được cách đi qua cầu. May mắn thay, đúng lúc đó LC đi thuyền ngang qua, các con cừu vội hỏi LC. Nhưng LC cũng bí, do không đem theo laptop theo :D. Hãy giúp LC chỉ cho các con cừu 1 cách đi tối ưu nhất.

Ví dụ: Với n=1, B mô tả đàn cừu đen, W mô tả đàn cừu trắng. Một trong các cách di chuyển tối ưu là:

W B
WB
BW
B W

Input

* Gồm một số nguyên N duy nhất (1≤N≤12)

Output

* Gồm 1 dòng duy nhất ghi dãy số a với ý nghĩa tại bước thứ i thì con cừu đứng ở vị trí a[i] trên cầu cần di chuyển. Nếu có nhiều đáp án, in ra đáp án với thứ tự từ điển nhỏ nhất.

Example

Input:
1

Output:
1 3 2
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Thu 29 Jul 2010, 18:52

Có 12 thôi à. Sao dễ thế. Hồi trước em làm với 151. Lúc đầu thấy ma ơi là ma. Sau tìm được quy luật thì dễ ơi là dễ laughing . Có công thức rồi, n=1000 cũng chạy loáng cái là ra.

Bài này hay, nên để mấy bạn khác suy nghĩ. Với lại bài ni mà nói quy luật ra thì chả còn gì cả. ^^

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Thu 29 Jul 2010, 22:50

MÌnh cũng chưa nghĩ ra.quy luật là gì vậy bạn?
Mình write mù mịt.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Fri 30 Jul 2010, 12:01

Bài ni nếu anh lấy y nguyên trên spoj về thì công nhận đề dễ. Nếu thế anh cứ đệ quy là ra thôi, có 12 mà ^^.

Anh viết đáp án của n=3 và n=4 ra giấy là thấy ngay. Em hồi đó cũng làm thế.

Đề này là đề tin học trẻ toàn quốc bảng B lần thứ 14 - bài 2

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Fri 30 Jul 2010, 15:21

Cho mình output n=3,4 được không?

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Fri 30 Jul 2010, 17:35

Bài này hồi đó em làm là ko phải in ra đen trắng mà in ra số thứ tự các con đàng hoàng, bên âm, bên dương.

Mà sao lạ thế, bên đó hok cho out put mẫu à. Mà giờ nghĩ lại em thấy nghi nghi cái vụ "tối ưu" ghê. Nói chung giờ làm kiểu em là ra chắc đáp số. Tuy nhiên em chưa bao giờ tìm được ra với một n mà ra hơn 1 cách đi cả (ko kể hoán vị 2 bên cho nhau). Chính vì thế mà em thấy chỉ có thể là được hay ko được thôi.

Để rãnh em suy nghĩ lại đã. Còn về đáp án thì [You must be registered and logged in to see this link.]

Anh vô đó chơi sẽ rõ.

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Fri 30 Jul 2010, 17:38

Khi anh đã chơi xong cái đó là anh sẽ hiểu đề nói gì. Và cũng khi đó anh đánh số thứ tự ra hoặc viết trắng đen càng dễ phát hiện sẽ thấy quy luật ngay.

Em nói về cách của em. Em ko làm như đề, em chỉ ghi lần lượt các chữ W hoặc B để chỉ con đen hay trắng di chuyển, con nào thì tự hiểu.

BWWBBBWWWBBBWWB

Nhìn vô đó chắc anh cũng thấy có chi lạ rồi. ^^

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Today at 21:32

Về Đầu Trang Go down
 
Đàn cừu hỗn loạn
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến