Truy tìm tiền giả!

[513minh891]

Lâu rồi mình không post bài nào, hôm nào post 1 bài cho các bạn thảo luận cho vui ^^:
Có 12 đồng tiền, trong đó có 1 đồng là giả. Các đồng tiền thật có trọng lượng như nhau, đồng tiền giả có thể nặng hoặc nhẹ hơn tiền thật. Chúng ta có 1 cái cân mỗi lần cân 8 đồng tiền, mỗi bên cân 4 đồng. Cho kết quả 3 lần cân, tìm ra đồng tiền giả.
COINS.INP
3 dòng là kết quả của 3 lần cân theo dạng: A B C D r E F G H
Trong đó a,b,c,d,e,f,g,h là số hiệu đồng tiền. r là phép so sánh ">" hoặc "<".
COINS.OUT
Đưa ra số hiệu của đồng tiền giả và dấu "+" hoặc "-" với ý nghĩa + là tiền giả nặng hơn, ngược lại là "-". Nếu không thể xác định do thiếu dữ kiện thì in Indifinite, nếu dữ kiện mâu thuẫn in Impossible
VD:
INP
1 4 6 10 < 5 8 7 12
2 9 11 7 > 6 3 4 10
12 9 6 5 < 1 4 10 3
OUT
6-

[Boom]

Giờ mới đọc bài này, nghĩ bừa 1 thuật toán thế này, binhnguyen xem đúng chưa
_ 2 tập hợp với ý nghĩa 1 tập hợp chứa các quả cân bên vế nhỏ hơn và 1 tập hợp - vế lớn hơn. Lúc đầu 2 tập hợp này chứa tất cả các quả cân
_ Mỗi 1 dòng dữ liệu vào sẽ tạo 1 tập hợp con mới của mỗi vế, ta lấy giao với tập hợp ban đầu mỗi vế => thay đổi 2 tập hợp ban đầu
_ Sau khi mọi dòng đã đọc, tập hợp nào chỉ còn 1 phần tử (và tập hợp kia rỗng) thì xác định được, không thì thiếu dữ kiện - không xác định được.
Vì thuật toán nghĩ ra ngay sau khi đọc đề và không suy nghĩ, không kiểm tra lại nên có thể còn sai xót, mình chỉ post lên mọi người tham khảo tìm chỗ sai, chứ thực tế mình cũng chưa chứng minh được nó đúng. Nhưng nghe cũng hợp lí đó chứ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[duhocbluesea]

Bác nói rở hôn xíu nữa y em chưa hiểu lắm ...

[quangcao3a]

:| Mình nói rõ hết mức rồi, thử lấy giấy ra làm theo thuật toán thì tự nhiên sẽ hiểu.

[hathuan]

mình hỏi: các số hiệu này đc đánh số ngẫu nhiên (cũng có thể dùng kí tự..v..) hay chỉ đánh số từ 1 tới 12 thôi.

[canhothegoldview]

Ngẫu nhiên hay theo thứ tự đều có thể quy về 1 dạng chung được mà em, ví dụ em quy định A là 1, B là 2 thì với kí tự ngẫu nhiên, em có thể quy về 12 số 1->12 để thực hiện các bước sau dễ dàng hơn.

[thethitotiu]

Tạo 2 mảng: 1 mảng chứa các đồng tiền nằm bên vế lớn, 1 mảng chứa các đồng tiền nằm bên vế nhỏ.
Kết thúc, nếu tìm được 1 đồng tiền chỉ xuất hiện ở 1 mảng thì đó là đồng tiền giả, nằm ở mảng lớn là đồng tiền lớn hơn, ngược lại là nhỏ hơn. Nếu ko tìm được đồng tiền nào chỉ nằm ở 1 mảng hoặc có nhiều hơn 1 đồng tiền chỉ nằm ở 1 mảng thì ko xác định được.
p/s: e ko hiểu thuật toán của a Ginta lắm!

[huyettulam]

Tạo 2 mảng: 1 mảng chứa các đồng tiền nằm bên vế lớn, 1 mảng chứa các đồng tiền nằm bên vế nhỏ.
Kết thúc, nếu tìm được 1 đồng tiền chỉ xuất hiện ở 1 mảng thì đó là đồng tiền giả, nằm ở mảng lớn là đồng tiền lớn hơn, ngược lại là nhỏ hơn. Nếu ko tìm được đồng tiền nào chỉ nằm ở 1 mảng hoặc có nhiều hơn 1 đồng tiền chỉ nằm ở 1 mảng thì ko xác định được.
p/s: e ko hiểu thuật toán của a Ginta lắm!

[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) Đây là cách của anh nhưng dùng mảng để giải quyết mà em, sao em bảo không hiểu cách anh [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])
Chỉ khác là anh đưa ra cách dùng tập hợp để giải quyết vì như thế việc em kiểm tra phần tử chỉ xuất hiện trong 1 mảng sẽ dễ dàng hơn nhiều (do tập hợp có phép lấy giao khá gọn là dùng '-').

[nhimbien12]

E vừa mới lấy giấy ra làm thử theo thuật toán của a, hiểu rồi ạ. Thật ra cũng có giống thuật toán của e đâu (của em tương tự nhưng khác chút). Mà ko biết e có code đc ko nữa, e chưa làm kiểu tập hợp bao h.

[greenhome]

Bảo Bình nói đúng rồi đó! [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
Giao cả 3 trường hợp lại, ta được 1 tập hợp, tiền giả chỉ nằm trong đó.
Ai code thử tớ xem nào ^^