Diễn đàn tin học Nguyễn Văn Linh
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

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

The second house for every one
 
Trang ChínhLatest imagesTìm kiếmĐăng kýĐăng Nhập

 

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

Go down 
2 posters
Tác giảThông điệp
Hovanthong
Admin
Admin
Hovanthong


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

Đàn cừu hỗn loạn Empty
Bài gửiTiêu đề: Đàn cừu hỗn loạn   Đàn cừu hỗn loạn I_icon_minitimeTue 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
littlelee


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

Đàn cừu hỗn loạn Empty
Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Đàn cừu hỗn loạn I_icon_minitimeThu 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ả. ^^
Về Đầu Trang Go down
Hovanthong
Admin
Admin
Hovanthong


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

Đàn cừu hỗn loạn Empty
Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Đàn cừu hỗn loạn I_icon_minitimeThu 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.
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin
littlelee


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

Đàn cừu hỗn loạn Empty
Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Đàn cừu hỗn loạn I_icon_minitimeFri 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
Về Đầu Trang Go down
Hovanthong
Admin
Admin
Hovanthong


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

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

Cho mình output n=3,4 được không?
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin
littlelee


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

Đàn cừu hỗn loạn Empty
Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Đàn cừu hỗn loạn I_icon_minitimeFri 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õ.
Về Đầu Trang Go down
littlelee
Admin
Admin
littlelee


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

Đàn cừu hỗn loạn Empty
Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Đàn cừu hỗn loạn I_icon_minitimeFri 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. ^^
Về Đầu Trang Go down
Sponsored content





Đàn cừu hỗn loạn Empty
Bài gửiTiêu đề: Re: Đàn cừu hỗn loạn   Đàn cừu hỗn loạn I_icon_minitime

Về Đầu Trang Go down
 
Đàn cừu hỗn loạ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