14 replies to this topic

[phananhtuan]

3rd JUNIOR BALKAN OLYMPIAD IN INFORMATICS 

(JBOI 2009) 

November 27 – 29, 2009 

Shumen, Bulgaria 

Task 3. COINS

You have a balance scale and 12 coins (numbered 1, 2, …, 12), one of which is counterfeit. 

The counterfeit coin is either lighter or heavier than the other, “normal” coins. Three 

weighings are performed on the balance scale. Write a program coins, which attempts to 

identify the counterfeit coin and determines if it is heavier or lighter. 

Input: 

The data for each weighing is given on a line of the standard input in the form: 

A B C D x E F G H 

where A, B, C, D, E, F, G and H are the numbers of eight different coins, and x is one of the 

characters <, > or =, with the following meaning: 

x Meaning 

< The total weight of coins A, B, C and D is 

less than the total weight of coins E, F, G и H. 

> The total weight of coins A, B, C and D is 

greater than the total weight of coins E, F, G и H. 

= 

The total weight of coins A, B, C and D is 

equal to the total weight of coins E, F, G и H. 

Output: 

The program writes to the standard output the number of the counterfeit coin and the character 

‘+’, when it is heavier than the others, or the character ‘–‘, when it is lighter. 

If the data of the three weighings is contradictory the program has to output 

“impossible”. 

If the data is not contradictory but is insufficient for determining the number of the counterfeit 

coin, or if it is heavier or lighter the program has to output “indefinite”. 

http://www.cs.org.mk...tasks/coins.pdf

Edited by phananhtuan, 07 August 2014 - 06:27 AM.

[Sundance]

Awesome...so how much code have you done so far? Show us what you have & what you're stuck on?

[phananhtuan]

i want to know optimal algorithm

[Sundance]

Well show us what you think it is and if you're wrong we will help push you into the right direction.

[phananhtuan]

I have no idea

[WingedPanther73]

This is a pretty standard logic puzzle, actually. Have you googled for things like "counterfeit coin" or anything?

[phananhtuan]

Edited by Kadence, 07 August 2014 - 03:35 PM.
"I do what I want" - Maury Show

[Sundance]

Fixed your post...

 

Perhaps you should try that with your other problem too and see what you've got.

 

Perhaps you could also take a look at "towers of hanoi" for a vague idea.

[phananhtuan]

Ok

[phananhtuan]

i will do like that:

for i:=1 to 12 do

                 with a coin, i review it like as counterfeit coin

                 assuming  it hevier or  lighter, use it for input, if ok then it a coin we must find

ok??

but i dont know how to input

[WingedPanther73]

The usual strategy is something like putting four coins on each side of a scale, and comparing weights. Then swap one set of coins for a set not on the scale and compare again. That tells you 1) whether the face is heavier or lighter, and 2) which set it's in. Split the set with the fake in half, compare, split the set with the fake in half again (now 1 and 1), compare, and you found it.

[Sundance]

^ This

 

It's a division problem although I would do it in two piles of 6, then you'd have two piles of 3 and then you would have 3 coins...weigh two at one time and then you'll know which one is the fake.