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 | 
 

 Vài bài làm chơi

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
[LTV]
Gà mờ


Tổng số bài gửi : 1
Join date : 04/06/2010

Bài gửiTiêu đề: Vài bài làm chơi   Fri 04 Jun 2010, 20:27

Asen và Boyan cùng chơi trò chơi với các đồng xu sau. Chúng chọn 2 số nguyên dương K và L khác nhau và chơi trò chơi với 1 tháp gồm N xu. Asen luôn chơi trước, tiếp theo là Boyan, sau đó lại là Asen ...

Mỗi lần chơi, chúng có thể lấy đi 1, K hoặc L đồng xu. Người thực hiện lượt đi cuối cùng là người chiến thắng. Asen nhận thấy có những trường hợp nó luôn có thể thắng, và các trường hợp mà Boyan có thể thắng bất kể nó chơi
như nào. Do đó, trước khi bắt đầu chơi, Asen muốn biết kết quả có thể của lần chơi. Hãy viết 1 chương trình dự đoán kết quả với K, L và N cho trước.
INPUT

Dữ liệu vào mô tả m lần chơi. Dòng đầu tiên gồm các số K, L và m, 1 < K < L < 10, 3 < m < 50. Dòng thứ hai gồm m số nguyên N1, N2, …, Nm, 1 ≤ Ni ≤ 1000 000, i = 1, 2, …., m, là số đồng xu trong từng lần chơi.

SAMPLE INPUT
2 3 5
3 12 113 25714 88888

OUTPUT

Hiển thị một xâu m kí tự 'A' và 'B', 'A' nếu Asen thắng và 'B' nếu ngược lại trong lần chơi thứ i.


SAMPLE OUTPUT
ABAAB

Xét hai số n chữ số A và B không có số 0 ở đầu. Cần tìm hai số có n
chữ số gần A nhất, một số >= A và một số < A mà gồm mọi chữ số của B
theo một thứ tự nào đó. Ví dụ, nếu A=3022 và B=1232, các số thu được
từ B là: 1223, 1232, 1322, 2123, 2132, 2213, 2231, 2312, 2321,
3122, 3212 và 3221. Số nhỏ nhất >= A là 3122, và số lớn nhất < A là 2321.
Nếu A=1232 và B=3022, các số thu được từ B là 2023, 2032, 2203, 2230, 2302,
2320, 3022, 3202 và 3220. Số nhỏ nhất >=A là 2023, và không có số nào < A.
Cho A, B, tìm 2 số gần nhất A như trên.

INPUT

Gồm hai dòng là hai số n chữ số A, B tương ứng (1≤n ≤ 60).

SAMPLE INPUT
Ví dụ 1 Ví dụ 2
3075 3000203
6604 4562454

OUTPUT

- Dòng 1: Số nhỏ nhất >=A theo định nghĩa trên, không có số 0 ở đầu.
Nếu không tồn tại, in ra 0.
- Dòng 2: số lớn nhất < A theo định nghĩa trên, không có số 0 ở đầu.
Nếu không tồn tại, in ra 0.
SAMPLE OUTPUT
Ví dụ 1 Ví dụ 2
4066 4244556
0 2655444

2 Problem này của Balkan dành cho cấp II thi đấy. Các bạn làm thử. Cũng chẳng khó đâu. Động não tí là ra.
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: Vài bài làm chơi   Sat 05 Jun 2010, 12:35

Thay mặt các bạn lớp 9 ở đây, mình xin nhận giải các bài tập này (có thể coi là nhận lời thách đấu)
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: Vài bài làm chơi   Sat 05 Jun 2010, 12:44

Mấy bài này đúng là khó. Tuy đang ôn thi chuyển cấp nhưng sẽ cố giải mấy bài này
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: Vài bài làm chơi   Sat 05 Jun 2010, 12:50

Bài 2 vì hai số A và B cùng có n chữ số, cộng với n<=60 nên có thể giải bằng cách tách B ra n chữ số riêng biệt, xếp lại, rồi cứ thử đặt từng kí số vào, kết hợp với cận để cho ra kết quả. Bài này nếu làm với đệ quy thì với test cự đại n=60 chắc tràn stack. Có thể dùng một vòng lặp duyệt hết các kí số và đặt vào làm cấu hình tạm. Sau đó nếu cấu hình tạm mà đảm bảo yêu cầu thì chọn luôn, nếu không thì áp dụng thuật toán sinh để đổi cho đến khi đạt được yêu cầu. Độ phức tạp sẽ là O(n^2).
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: Vài bài làm chơi   Sat 05 Jun 2010, 12:53

Bài 1 mình có thắc mắc. Chắc chắn là kết quả cuộc chơi chỉ có thể là A thắng hoặc B thắng, nhưng nếu dự đoán trước trận đấu với K,L và N thì kết quả chưa chắc là A luôn thắng hoặc B luôn thắng. Liệu điều đó có đảm bảo.
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: Vài bài làm chơi   Sat 05 Jun 2010, 12:56

Sở dĩ mình nghĩ như trên vì mình nghĩ cách giải theo kiểu phân tích. Phân tích N ra thành tổng của các số 1 và K và L bằng mọi cách. Nếu trong tất cả các cách đều có số hạng tử là lẻ thì A luôn thắng, nếu tất cả đều chẵn thì B luôn thắng. Nhưng nếu trong số đó có cả chẵn lẫn lẻ thì điều đó không khẳng định được, còn phụ thuộc quá trình chơi
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Vài bài làm chơi   Thu 10 Jun 2010, 20:37

Cái ông [LVT] này thách đấu 2 bài rùi lặn đâu lun rùi. Lên bàn lựng cho sôi nổi chứ:D
Về Đầu Trang Go down
LTVer
Gà mờ


Tổng số bài gửi : 1
Join date : 16/07/2010

Bài gửiTiêu đề: Re: Vài bài làm chơi   Fri 16 Jul 2010, 09:49

Không fải thách đấu đâu ! Lâu quá mình quên béng mất pass. big grin thấy các bạn thảo luận sôi nổi nên mình ném vài bài cho vui thôi. Mình pít 4rum này nhờ cái chữ ký của ai đó bên VNOI. Bài này cũng của VOJ. Nói chung không khó. Cần có căn bản về QHĐ + Duyệt đặt cận (mấy cái này bạn nào vào 10 chuyên sẽ học)
Bài 1 : Bạn ở vị trí thắng nếu có 1 cách đi từ vị trí này đến vị trí thua.
QHĐ : F[0] sẽ là vị trí thua. Từ đó suy ra F[i] = F[j-1] and F[i-k] and F[i-L] (sử dụng toán tử and trong boolean).
O(N)
Bài 2 : Tham lam :
Chọn các phần tử giống số đã cho nhất. Nếu có 1 số lớn hơn chỉ việc sort phần còn lại. smile O(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: Vài bài làm chơi   Fri 16 Jul 2010, 12:52

LTVer đã viết:
Không fải thách đấu đâu ! Lâu quá mình quên béng mất pass. big grin thấy các bạn thảo luận sôi nổi nên mình ném vài bài cho vui thôi. Mình pít 4rum này nhờ cái chữ ký của ai đó bên VNOI. Bài này cũng của VOJ. Nói chung không khó. Cần có căn bản về QHĐ + Duyệt đặt cận (mấy cái này bạn nào vào 10 chuyên sẽ học)
Bài 1 : Bạn ở vị trí thắng nếu có 1 cách đi từ vị trí này đến vị trí thua.
QHĐ : F[0] sẽ là vị trí thua. Từ đó suy ra F[i] = F[j-1] and F[i-k] and F[i-L] (sử dụng toán tử and trong boolean).
O(N)
Bài 2 : Tham lam :
Chọn các phần tử giống số đã cho nhất. Nếu có 1 số lớn hơn chỉ việc sort phần còn lại. smile O(bựa)

^^ Bài 1 ni theo ý của bạn giống 1 trò chơi mình đã từng học. Cái ni mà ai hok bit trò đó chắc khó mà hỉu được.
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Vài bài làm chơi   Today at 18:50

Về Đầu Trang Go down
 
Vài bài làm chơi
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