Cách giải chắc chắn đúng với bài 2 khi money >= 3(n+1)
Ta chỉ cần 3$ để xác định A có màu gì, thật vậy,
Giả sử trạng thái s1 có s1 = R, compare (s1) = c1.
Cho s2 := s1; s2 = G, compare (s2) = c2.
- TH1 : c2 > c1, có nghĩa là sự thay đổi ở s2 có hiệu quả, khi đó, A chắc chắn bằng G.
- TH2 : c2 < c1, khi đó, A chắc chắn bằng R
- TH3 : c2 = c1, khi đó, A chắc chắn bằng Y
Áp dụng với bài toán RGYRYYRGG:
s0 = RRRRRRRRR -> compare(s0) = 3
{thực ra ta cũng chẳng cần compare cái này cho mất nhiều tiền, tính count (R) = 3 là đủ }
s1 = RRRRRRRRG -> compare(s1) = 4 -> A[9] = G;
s2 = RRRRRRRGR -> compare(s2) = 4 -> A[8] = G;
s3 = RRRRRRGRR -> compare(s3) = 2 -> A[7] = R;
s4 = RRRRRGRRR -> compare(s4) = 3 -> A[6] = Y;
....
s9 = GRRRRRRRR -> compare(s9) = 2 -> A[1] = R;
Từ đó xác định được cả dãy màu, với chi phí để compare từ s0 đến s9 là 30$ !
______________________________________________________________
Bài 1 nếu viết nhanh, chính xác thì duyệt trâu cũng ăn được 9 tét đầu, khỏi xoắn. Hôm nào rảnh mình code lại, h chuẩn bị học môn khác.
ps: Gặp thiên nữ, tưởng là nickname hóa ra tên là Thiên Nữ thật =)). Mình đứng ngay sau bạn lúc điểm danh đó =)).
Gặp mà tự nhiên cái họng ko phát ra âm thanh đc, mặc dù gặp ko ít :-S
