•

Check out our Community Blogs

Register and join over 40,000 other developers!

### Recent Blog Entries

• phi

I love this community !

• JackJames

hi i am jack i am seo expert jack james would love you to read new post

# coins

pascal

This topic has been archived. This means that you cannot reply to this topic.
14 replies to this topic

### #1 phananhtuan

phananhtuan

CC Newcomer

• Member
• 21 posts

Posted 07 August 2014 - 06:25 AM

3rd JUNIOR BALKAN OLYMPIAD IN INFORMATICS
(JBOI 2009)
November 27 – 29, 2009
Shumen, Bulgaria
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”.

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

### #2 Sundance

Sundance

CC Devotee

• Validating
• 572 posts

Posted 07 August 2014 - 07:55 AM

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

### #3 phananhtuan

phananhtuan

CC Newcomer

• Member
• 21 posts

Posted 07 August 2014 - 08:00 AM

i want to know optimal algorithm

### #4 Sundance

Sundance

CC Devotee

• Validating
• 572 posts

Posted 07 August 2014 - 08:17 AM

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

### #5 phananhtuan

phananhtuan

CC Newcomer

• Member
• 21 posts

Posted 07 August 2014 - 08:41 AM

I have no idea

### #6 WingedPanther73

WingedPanther73

A spammer's worst nightmare

• Moderator
• 17757 posts

Posted 07 August 2014 - 08:49 AM

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

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/

### #7 phananhtuan

phananhtuan

CC Newcomer

• Member
• 21 posts

Posted 07 August 2014 - 03:11 PM

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

### #8 Sundance

Sundance

CC Devotee

• Validating
• 572 posts

Posted 07 August 2014 - 03:36 PM

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.

### #9 phananhtuan

phananhtuan

CC Newcomer

• Member
• 21 posts

Posted 07 August 2014 - 07:56 PM

Ok

### #10 phananhtuan

phananhtuan

CC Newcomer

• Member
• 21 posts

Posted 08 August 2014 - 07:52 AM

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

### #11 WingedPanther73

WingedPanther73

A spammer's worst nightmare

• Moderator
• 17757 posts

Posted 08 August 2014 - 08:29 AM

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.

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/

### #12 Sundance

Sundance

CC Devotee

• Validating
• 572 posts

Posted 08 August 2014 - 08:35 AM

^ 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.