Bài làm chơi

[ngtrhieu0011]

Đồng Xu Giả
Bạn Tùng có 12 đồng xu bạc. Tuy nhiên chỉ có 11 đồng là thật, đồng còn lại là giả. Không thể phân biệt đồng xu thật và giả qua màu sắc và kích thước của chúng. Đồng xu giả thì có trọng lượng khác so với đồng thật, bạn Tùng vẫn chưa biết là nó nặng hơn hay nhẹ hơn so với đồng thật.May mắn thay, Tùng được Vân cho mượn một cái cân thăng bằng. Vân chỉ cho Tùng cân 3 lần để tìm đồng giả. Bằng một cách nào đó, Tùng luôn tìm ra được đồng xu giả với đúng 3 lần cân.
Yêu cầu: Bạn hãy xác định đồng xu giả, dựa vào kết quả cân của Tùng.
Dữ liệu: vào từ file văn bản DONGXU.INP:
Dòng đầu tiên là số nguyên n (n>0) cho biết số lượng test. Mỗi test gồm 3 dòng, mỗi dòng thể hiện thông tin của một lần cân. Các đồng xu được xác định bằng các kí tự, từ A đến L. Thông tin của một lần cân bao gồm hai chuỗi kí tự và một trong các từ “len”, “xuong”, “bang”. Chuỗi đầu tiên thể hiện các đồng xu bên dĩa cân trái, chuỗi thứ hai cho các đồng xu ở dĩa cân phải (Tùng luôn đặt số lượng đồng xu ở hai dĩa cân bằng nhau). Từ “len”, “xuong”, “bang” cho biết dĩa cân phải nhẹ hơn, nặng hơn hay bằng dĩa cân trái.
Kết quả: Ghi ra file DONGXU.OUT
Với mỗi test, hãy xuất ra kí tự của đồng xu giả và cho biết nó nặng hơn hay nhẹ hơn so với đồng thật.
Ví dụ:
DONGXU.INP
1
ABCD EFGH bang
ABCI EFJK len
ABIJ EFGH bang

DONGXU.OUT
K la dong xu gia va no nhe hon.

(bài này rất đơn giản, chủ yếu là xảo thuật lập trình chứ không phải giải thuật. Bạn nào post code lên thử nào)

[bld]

xảo thuật là gì vậy anh +_+ ?
e ko hiểu , đơn giản gì , giải thuật e còn chưa nghĩ ra huống chi cái (?) xảo thuật (?) nữa
---hay là vét cạn nhể , chỉ có 12 đồng thôi mà --- nhưng mà chắc làm vậy thì dở quá

[quangtq]

Cái này đơn giản. Áp dụng toán vào là có ngay giải thuật chuẩn.

[bld]

thanks , áp dụng giùm mình đi , +_+ mình dở toán quá

[quangtq]

Với 3 lần cân, ta chia 12 đồng ra thành 3 nhóm, mỗi nhóm 4 đồng.
Cân 2 nhóm đầu, nếu 2 nhóm = nhau thì nó nằm ở nhóm thứ 3.
Nếu 2 nhóm ko bằng nhau thì nhóm nhẹ hơn chính là nhóm chứa đồng giả nhẹ hơn.
Tiếp tục lấy nhóm chưa đồng nhẹ, chia ra thành 2-2.
Như trên, xác định được 1 trong 2 nhóm.
Cuối cùng chia 2 đồng ra thành 1-1.
Xác định được đồng giả với 3 lần cân.
Quá dễ. Bài này học từ hồi lớp 5.

[bld]

AHAHA , vậy thì mình học từ lớp 4 kia ! nhưng mà , đọc lại đề đi quang

[=========> Bổ sung bài viết <=========]

mà đồng giả có xác định là nhẹ hơn hay nặng hơn đâu!

[=========> Bổ sung bài viết <=========]

và, các bước làm dc cho trong input chứ có phải mình muốn làm gì là làm đâu !, và mỗi lần , chưa chắc input nó cho mỗi dĩa 4 đồng , cho 5 ,6 đồng thì sao hay 2 3 viên thì sao ?
xuống lên bằng cũng dc cho trc luôn

[quangtq]

Đọc lại cái, cân những cái gì đã có trong test mà.
Cái nào bằng thì loại luôn 8 đồng đấy.
Xét xem.
Như ví dụ trên thì ta loại ra được A B C D E F G H I J.
Dựa vào lần cân 2 thì EFJK nặng hơn ABCI mà ABCI và EFJ đã loại ra
=> K là đồng giả nặng hơn.

[bld]

đúng rồi, mình cũng nghĩ vậy, nhưng các input là thiên biến vạn hóa nhỡ gì ko có cái nào bằng thì sao, hay nó cho 2 dĩa cân là 3 hay ...
phải tìm ra cách giải tổng quát

[=========> Bổ sung bài viết <=========]

ko thể tùy cơ ứng biến như bạn dc ,
...nếu tùy cơ ứng biến thì trông giống AI nhỉ , uhm ...

[quangtq]

Vì chỉ có 1 đồng giả nên ta xét xem trong những lần cân không bằng, phần tử nào chung (tính cả 2 bên) thì chính nó là cái giả.
Mình nghĩ thế.

[bld]

thế bạn thử inp này
ABC DEF bang
A B bang
GAI JKL xuong

và test này
ABCD EFGH bang
ABCI EFJK len
ABIJ EFGH bang
hãy nói 1 thuật toán duy nhất áp dụng cho cả 2 inp trên