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

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.

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)

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

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).

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.

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

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

Không fải thách đấu đâu ! Lâu quá mình quên béng mất pass. 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. O(bựa)

LTVer đã viết:

Không fải thách đấu đâu ! Lâu quá mình quên béng mất pass. 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. 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.