Di chúc của Analu

Hoàng Lê Vĩnh Hưng
(hungmk)

Thành viên danh dự
Di chúc của Analu(Analu nó thách thức mọi người kìa)

Analu có một khám phá trong đời của nó. Nó có giải được bài toán mà nó trăn trở từ kiếp trước (khi nó còn là Hưng Khỉ mới vào cấp hai). Ngày nay khi nó chết nó không muốn bài này thất truyền nên có để lại cho đời lời giả bài này, và người đang có trong tay bí mật này là tôi, Hoàng lê Vĩnh Hưng.
Nay xin công bố đề bài để mọi người cùng thưởng thức(lời giải xin miễn công bố)
Nếu ai TỰ giải bài này trong vòng một tuần thì Analu sẽ chết hẳn. Nếu hơn 1 tuần chưa có ai giải được thì hồn Analu có thể đôi khi quay lại trêu ngươi HAO. Nếu trong 1 tháng không ai giải được thì Analu sẽ quay trở lại. Vì các bác đã truyền thêm sự sống cho nó(đó là sự ngông nghênh, khinh đời).
Đề bài đây này:
Không sử dụng biện pháp trâu bò húc(duyệt tất cả các khả năng) hãy lập thuật toán cho trò chơi sau:
Cho 4 hàng sỏi hàng 1 có 1 viên hàng 2 có 3 viên, hàng 3 có 5 viên hàng 4 có 7 viên.
Minh họa:
*
***
*****
*******
Cách chơi: mỗi lần lấy 1 lượng sỏi lớn hơn hoặc bằng 1 viên và chỉ được lấy các viên sỏi trên cùng 1 hàng. Ai là người còn sót lại viên sỏi cuối cùng là người đó thua cuộc.

Lập thuật toán cho người chơi thứ hai(người bắt đầu sau) luôn thắng. Lập thuật toán cho người thứ nhất(người lấy sỏi đầu tiên) có thể thắng nếu người chơi thứ hai không biết qui luật.

VD của 1 cuộc chơi:
*
***
*****
*******
số 1 lấy 1 viên ở hàng 1:

***
*****
*******
Số hai lấy 3 viên hàng 4:

***
*****
***
Số 1 lấy 3 viên hàng 2:

*****
***
Số 2 lấy hết hàng 4(3 viên):


*****

Số 1 lấy 4 viên hàng 3:


*

Chỉ còn lại 1 viên duy nhất- số 2 thua cuộc

Đây là công sức của Analu đã suy nghĩ 1 tuần đầu trong kì hè 2002 tại quê nhà Việt Nam. Chính vì thế mà các cao thủ HAO phải cố gắng giải nhanh hơn nó mới được - không nó mà trở lại thì HAO lại loạn lên mất.
 
Chỉnh sửa lần cuối:
Ngày thứ nhất đã trôi qua mà không thấy một cao thủ HAO nào động đậy tới bài của nó-Analu đã nhúc nhích được ngón chân cái rồi. Thêm một chi tiết hấp dẫn: hình như bài này cả lớp Tin khóa 98-01 tài năng với cả giải quốc tế cũng không có chú nào dám giải thì phải.
 
Ba ngày trôi qua mà không ai dám động tới bài này à, thế thì có lẽ Analu sống lại thật. Hạn là 1 tháng trời. Mọi người cố gắng lên
 
Chỉ còn hai ngày nữa là hồn của Analu có thể bay về HAO chơi rồi. Các cao thủ tin học, toán học đâu rồi, trường Ams cũng không hiếm giải quốc tế mà không ai chịu động vào bài này à?
 
Hì, nói thuật toàn thì nghe cao siêu quá, chẳng biết lập, chứ còn chơi thì chị nhớ hồi xưa chơi trò này suốt, toàn thắng :razz:
 
Choáng- chị Giao biết bài này à? bài này độc lắm cơ mà, em tưởng cả VN chỉ có mỗi em biết- nhưng ý tưởng của bài này hay vậy vã. Chú nào cang cao siêu càng nghĩ to tát thì toàn gặp thất bại thôi, chú nao mà cứ chơi null thì đi teo ngay từ đầu. bài này mà phát triển lên với n hàng thì là cả một vấn đề vô cùng khó khăn. Chị Giao thử nói cách chơi của chị đi. Hay là em với chị chơi thử 1 ván. Để em chịu phần thiệt đi trước vậy.
Lấy 1 ở hàng đầu tiên:

***
*****
*******
Chú ý không dùng thuật toán duyệt.
 
chưa có ai vào đây hạ thổ analu à. Đang bận project quá, nên chưa cầu siêu cho analu đuợc.

Nghĩ nhanh một cách là lập ra một bộ các set gồm 4 số từ 0-7, sao cho giao của any 2 set < 3, bắt đầu từ {0,0,0,1} (nói cách khác la 2 set bất kỳ khác nhau ít nhất là 2 số).

Còn có cách nào khác thì đợi xong prọect đã. :).

PS. anh lấy tiếp 1 ở hàng số 3 ;)
 
hơ hơ gặp cướp rồi- em thử xem có phải anh Điềm lấy rùa không: lấy 1 ở hàng 4:thành 2-4-6.

**
****
******
còn 1 ngày nữa là tới 1 tuần rồi đấy- kết liễu Analu nhanh lên
 
Chỉnh sửa lần cuối:
Hoàng Lê Vĩnh Hưng đã viết:
hơ hơ gặp cướp rồi- em thử xem có phải anh Điềm lấy rùa không: lấy 1 ở hàng 4:thành 2-4-6.

**
****
******
còn 1 ngày nữa là tới 1 tuần rồi đấy- kết liễu Analu nhanh lên

Bậy nào, thế thành 3 4 6 chứ.

Để yên cho anh học ;)
 
he he đang học mà anh Điềm cũng tinh ra phết ;)
thì thử 3-4-6 đi. He he không xong rồi.
 
học mãi, buồn ngủ rồi. 3-4-6 thi anh lay thanh 2-4-6. Cám ơn chú gợi ý trước.
Ê làm ván cờ không
 
Thôi đi rồi - cái ván đó coi như đi tong, anh Điềm trình bày cặn kẽ cách chơi trò đấy cho cả nhà hiểu rõ đi. Cách của anh đúng rồi nhưng set có vấn đề thì phải-cho số không vào set làm gì. Anh có làm tổng quát cho dãy n hàng không?
Đánh cờ với anh cũng được thôi, anh thích chơi trên PM không? Trường em nó cấm chơi game trên mạng nên không đánh bằng yahoo hay www.freechess.org được. Nếu anh thích đánh thì vào www.freechess.org chơi, đấu thử với HLV của em cũng được nick: spiffo. 1st board của đội tuyển em: doommachine, 2nd board:shogunII 3rd:schmmic, 4th:Nsorhog em đứng ở vị trí thứ 5(1 năm về trước): aloser

Huấn luyện viên spiffo (Robert Millete) của em cũng là dân Tin elo: 197x
trong lich sử em hòa được 2 ván và thắng một ván do được chấp thế.

1st board Adams Nelson elo:1630. Tỉ lệ chiến thắng của em với nó: 5%

2nd- Sean W. hình như thằng này phát triển tốc độ cao giờ này có lẽ elo của nó lên 1800 mất rồi. Tỉ lệ chiến thắng:0%

3r Michael Smith- thằng này chắc elo cũng lên 1500 rồi đánh với thằng này em có cơ hội thắng 30%. Thằng này có IQ cao nhất đội thuộc vào dạng thần đồng ở Mĩ. Nó chính là người hay đánh với em nhất nên hai đứa hay bắt vở nhau.

4th Sheth Nilay(thằng Ấn Độ)-1426 thằng này đánh rất củ chuối tuy điểm số không cao nhưng em chưa bao giờ đánh thắng được nó(toàn thua hay hòa)

Và người yếu kém nhất đội tuyển đứng thứ 5 chính là em. Nhưng được cái thông minh - biết lượng sức nên xuống đánh ở division 2 nên mới vô địch WI(div.2).
Đội tuyển của em mà có được cả năm đứa cùng 1 lúc đi giao đấu cùng 1 lúc thì sức mạnh cực lớn- cũng có thể coi là 1 trong 100 đội mạnh nhất nước Mĩ lứa tuổi U20 được.
À quên mất còn thằng anh trai của chú Sean W. nữa Chris W. -chú này kiến thức về cờ vua nhiều hơn tất cả các chú khác(chỉ kém có huấn luyện viên) nhưng thực hành thì củ chuối lắm lại rất dễ nổi cáu, nên tinh thần không ổn định
 
Chỉnh sửa lần cuối:
Ủa, thế không phải là em lấy viên đầu hàng trên cùng, đến hàng thứ 2 chị lấy hết trừ lại 1 viên -> em phải lấy viên cuối hàng 2. Rồi đến hàng 3 chị lấy hết để lại 1 viên, -> em phải lấy viên cuối hàng 3. Rồi hàng 4 chị lại lấy tiếp hết để còn 1 viên cuối -> em thua :)

Chẳng biết có đúng vậy không nữa.:)
 
nhét 0 vào cho dế biểu diễn thôi.

Intuition là mỗi lần đi thì chỉ thay đổi được một hàng, i.e 1 số trong set of 4. Nếu tất cả các set trong một class dều khác nhau (đôi một) ít nhất là 2 số, thì trong 1 nước đi em không thể chyển từ set này sang set khác. Tỉ dụ từ 0-0-2-2 không thể về 0-0-0-1 bằng 1 nước.

Dựa vào đó mà backtrack từ 0001 lên, lập thành cẩm nang rồi cứ thế mà đi. Có thể làm lên bao nhiêu cũng đuợc, với điều kiện bộ nhớ cho phép + thuật toán build up class. Ví dụ cho mấy set đầu:
0001, 0022, 0033,0044,0055,0111,0123,...

P.S chị Giao. thuật toán của chị cũng đúng, Nhưng trước khi chơi phải giao hẹn: "mày nhớ lấy viên cuối nhé, không thì chị ĐÁNH đấy" :D

PS Hưng. ờ, định chơi tí cho đỡ buồn ngủ nhưng xem ra không ổn :(. để bữa khác vậy
 
Hơ hơ tưởng gì chứ anh Điềm cũng phải dùng cách duyệt chọn
bộ 1 rồi biến ngược thành các bộ 2-2,1-1-1,1-2-3,1-5-6,...
Bài này có cách giải cực kì đặc sắc đấy, thế nên em mới phải chờ mấy năm mới nhìn ra được. Cách giải dùng máy vi tính thì không nói làm gì, kho nhớ tất cả các bộ lắm(tuy em nhớ đươc tất nhưng phải chơi nhiều mới nhớ được. Cách của em ngắn gọn, dễ nhớ, dễ trình bày. Mọi người tiếp tục cố nhé.
 
:d chị chỉ biết chơi thôi chứ nói thuật toán thì loằng ngoằng quá sức với cái đầu bã đâu của chị rồi. :mrgreen:
 
Hơ hơ... nếu mà chú này là dân tin Ams khóa 98-01 thì phải học cùng lớp với thằng Hoài chứ nhể... chẳng lẽ cái bài này mà thằng Hoài ko làm được à (anh nhớ anh dạy nó bài tổng quát hơn thế rồi cơ mà!!!).
Nghe chú em kể chuyện đánh cờ thì choáng thật còn quay sang bàn về mấy bài tin thì đúng là chả biết gì... bọn đội tuyển nó không gà như thế đâu chú ạ.... bài của chú ở VN người ta đưa vào SGK cho dân tin từ lâu rồi.....
-----
Oái xin lỗi đồng chí Hoàng Trần, tớ dùng nhầm nick của đồng chí ! Càng hay .... tớ cóc có nick trong này!
 
Chỉnh sửa lần cuối:
Hơ hơ bài này thằng Hoài cóc làm được, mà làm với thuật toán duyệt thì cũng cóc nói làm gì. Cao thủ dấu mặt(sư phụ thằng Hoài) có muốn thể hiện trình độ thì cứ việc giải, bài này phải có một cách suy nghĩ độc đáo thì mới giải bằng cách khác cách duyệt được.Cách đó khá đơn giản và dễ nhớ, có thể dùng mà không cần phải nhớ các bộ cơ bản.
Nói luôn cho mọi người biết: từ lớp 12 em đã bỏ tin từ lâu,kiến thức không còn nhiều, nói năng cũng có thể có lỗi.
 
Sao chú cứ 1,2 chê duyệt thế nhỉ? Duyệt hay thế còn gì, vừa đơn giản(trong suy nghĩ + thực hiện), chỉ phải tội máy tính chạy hơi lâu tí thôi ... nhưng mà chả sao ...Thà bắt cái máy nó nghĩ hộ còn hơn là mình phải ngồi cày chú ạ. Ay dà ....
Còn nếu chú vẫn muốn kiểu chương trình hay, thuật toán đẹp thì anh khuyên chú nên tìm thông tin về trò chơi Nim (tên bài toán của chú đấy!) thường thì nó có cách giải đi kèm .... ờ nhưng mà biết đâu nhỉ, cách giải bài đấy có khi lại phức tạp hơn của chú ấy chứ. Nếu thế thật thì chú post lên cho anh xem với nhé. Lâu rồi ko chơi mấy cái này cũng buồn tay.
PS : Chú bảo gì thế? Anh có phải SP thằng Hoài đâu.... bé bé mồm chứ ... nó thịt anh chít giừ!!!! :mad:
 
Chỉnh sửa lần cuối:
He he thuật duyệt là phải dùng máy tính, còn làm đơn giản tới mức để lúc nào cũng có trong đầu để ứng dụng mới gọi là đỉnh cao(chẳng nhẽ lúc nào chơi trò này cũng dùng máy tính ra chơi à?).
Chính vì thế Tin và Toán nó mới hơi khác nhau. Thằng Tin học ứng dụng mà thiếu cái máy tính thì chết cứng- thằng là toán học thì nó cười tỉnh bơ.
Em chê duyệt vì hồi trước không giải được cách nào khác hay hơn cách duyệt, 1 năm về trước tìm được cách hay thì mới đem khoe. Nhưng hạn 1 tháng còn chưa tới đưa ra kết quả sớm làm gì.
Ứng dụng của trò Nim không dùng vào bài này tốt lắm(nên nhớ còn 1 viên thì người đấy thắng chứ không phải là người nào lấy tất thắng-điều kiện bài Nim). Bài Nim mà gặp tổng quát của bài này(n-hàng) thì nó mất điện.
He he thế thì có phải anh phụ đạo thằng Hoài hồi đầu lớp 11 không? Không biết tình hình chú Hoài ở SG bây giờ thế nào. Hi hi chắc giờ nó phải lên tới đỉnh cao lắm rồi, thằng bé này hình như thông minh hơn mình nhiều, có tương lai sáng lạn lắm.
 
Back
Bên trên