LINUX.ORG.RU
ФорумTalks

Задачка.


0

0

Приветcтвую благородное собрание.

Кто хочет задачку порешать? :-)

-= disclaimer =-

Понятно, что ответ можно легко нагуглить - но не советую лишать себя удовольствия поразмять мозги. Поверьте, задачка того стоит.

-= условие =-

Есть 12 монеток, одна из которых фальшивая. Она отличается от настоящих по весу (неизвестно, легче или тяжелее). Есть аптечные весы - ну, которые умеют показывать "больше/меньше/равно".
Нужно за три взвешивания сделать следующее: во-первых найти фальшивую монету, а во-вторых определить, легче она или тяжелее.
Всё.


p.s. Кто знает ответ - не подсказывайте pls ;-)

Ответ на: комментарий от anonymous

> 12 - это для конспирации?

Это другой вопрос и другая задачка.

Ты решай и ответ пиши ;) Если хочешь конечно.

Dimentiy ★★
() автор топика

Тю, фигня! А вот решите то же самое для 13 монет, а?

Shaman007 ★★★★★
()
Ответ на: комментарий от Selecter

Неподходит ибо как и в первой 6 так и вторая может быть фальшивая так и во 2

если бы точно знали бы что монетка тяжедей или наоботорот--легче то тогда способ подошёл бы

Borys ★★
()
Ответ на: комментарий от Selecter

2 Selecter:

Решение неправильное.
Неизвестно, легче монета или тяжелее.

--------

p.s. Это только кажется, что задачка тривиальна ;)

Dimentiy ★★
() автор топика
Ответ на: комментарий от Dimentiy

вот нагуглил :)

...
второе взвешивание:
берем вторые, третьи и четвертые весы (а где бл@ в условиях задачи сказано что весы должны быть одни) ...

Также написано, что за 3 взыешивания найти такую монету нельзя нельзя (если не знаем легче/тяжелее)

Krasu
()
Ответ на: комментарий от Krasu

третье взвешивание: с 70% вероятностью не состоится является повторением второго взвешивания
Да и лабуда с палкой нужна для того чтобы не придрались типа весов несколько, соответственно и взвешваний тоже несколько, х@й все монеты упали на весы одновременно, значит и взвешивание получилось одно

:))))

Krasu
()
Ответ на: комментарий от Krasu

> Также написано, что за 3 взыешивания найти такую монету нельзя
> нельзя (если не знаем легче/тяжелее)

Решение ЕСТЬ.
Нормальное решение, логическое, без подъёбок.
Очень красивое кстати решение.

> вот нагуглил :)

Krasu, не надо гуглить. И яндексить тоже. Не обламывай людям задачку, пожалуйста.

Dimentiy ★★
() автор топика

В первый раз явно надо по 4 взвешивать. Если равно, то всё гладко. Если больше/меньше, надо думать. :)

mikhail
()
Ответ на: комментарий от sakura-obscura

В первый раз нельзя по три взвешивать, т. к. если 123=456, то нам только известно, что фальшивая среди 7-12. Таких вариантов 6*2=12. А из последующих двух взвешиваний мы сможем различить не более 3^2=9 вариантов.

mikhail
()
Ответ на: комментарий от sakura-obscura

Максимальное значение которое мы можем отбросить это взвешивая 4:4 в данном случае есть два исхода если висы показывают равно то все 8 монет идут н****.

Ну а в другом варианте только 4 :(.

Так как я вынужден признать свою глупость то жду от автора ответа, хотя ещё не здюсь окончательно.

Borys ★★
()

Первый!:]

Возможно решения не рационально, зато правильно.
Кстати почему ispell не нашёл исправления к слову бИгимот.

Возьмём вместо монеток пингвинов (я так решал на пингвинах).

Среди них затесался бегимот (либо маленький либо большой).

Пингвины одинаковы по весу.
Бегимот либо больше, либо меньше.

Разделяем на три кучи по 4 пингвина.

Сверяем первые две кучи:
Если они равны то следующий блок:
--------------------
Берём оставшуюся кучку
Разделяем её на 3: по к1 = 1, к2 = 1 и к3 = 2 пингвина.
добавляем в к2 одного пингвина из уже проверенных(т.е. точно настоящих пингвинов, которых у нас
 в данном случае целых 8, далее "эталонный")
Если к2 и к3 равны то:
   -------------------
   сравниваем к1 с эталонным пингвином
   если к1 больше значит к1 - большой бегимот, иначе к1 маленький бегемот [ОТВЕТ 1]
   --------------------
Если к2 < к3:(значит либо в к3 большой бегимот, либо первый пингвин к2 - маленький, т.к. второй - эталонный) 
   -----------
   сравниваем первого пингвина из к3 со вторым из к3:
   если они равны, то первый пингвин из к2 - маленький бегимот[ОТВЕТ 2]
   иначе больший из к3 - большой бегимот [ОТВЕТ 3, 4]
   ------------
Если к2 > к3:
   делаем тоже что и в предыдущем пункте только наоборот (> => <, большой => маленький)

--------------------
Если самые первые две кучки по 4 пингвина не равны:
рассмотрим вариант, если первая больше второй (если наоборот делаем тоже самое но меняем местами больше на меньше)
Итак первые 4 пингвина (куча1) > вторых 4 четырёх (куча2).
------------------------
Убираем из кучи1 двух пингвинов в кучу3,
 а из кучи2 одного пингвина убираем в кучу4
И САМОЕ ГЛАВНОЕ НАД ЧЕМ Я БОЛЬШЕ ВСЕГО Е***СЯ  меняем одного пингвина из кучи 1 на пингвина из кучи 2.  
добавляем в кучу1ы одни одного эталонного пингвина.
получается так.
в куче1:
 два пингвина неизвестных и один эталонный
в куче2:
 три пингвина неизвестных.
в куче3:
 два пингвина из кучи 1
в куче4:
 один пингвин из кучи 2
СРАВНИВАЕМ кучу 1 и кучу 2:
Если они равны то значит либо в кучи3 большой бегимот, либо в куче4 маленький бегимот.
-------------
сравниваем пингвинов из кучи3:
если они равны, то пингвин из кучи4 - маленький бегимот.[ОТВЕТ 5]
иначе больший пингвин из кучи3 - большой бегимот.[ОТВЕТ 6,7]
--------------
Итак если куча 1 осталась больше кучи 2 после перемещения и добавления:
	значит большой бегимот - это первый пингвин из кучи 1,
	либо один из двух первых пингвинов из 
	кучи2 - это маленький бегимот (третьего исключаем из кучи2, 
	и второго из первой исключаем,
        т.к. мы их меняли и они не повлияли на вес,
	и третьего из первой тоже, т.к. он эталонный)
	-------
        	теперь сравниваем двух первых пингвинов из кучи2, если они равны
	    	значит первый из кучи1 - большой бегимот[ОТВЕТ 8]
		либо наименьший из первых двух во второй куче - маленький бегимот.[ОТВЕТ 9,10]
	-------
Ну а если куча1 стала меньше кучи 2, значит 
либо пингвин 2 из кучи1 (которого мы перенесли из кучи2) маленький бегимот,
либо пингвин 3 из кучи2 (которого мы перенесли из кучи1) большой бегимот.
Сравниваем пингвина 2 из кучи1 с эталоном.
если он меньше, то он маленький бегимот[ОТВЕТ 11]
если они равны, то пингвин 3 из кучи2 - большой бегимот.[ОТВЕТ 12]

Ух всё, всё вроде. 

CrazyPit ★★★
()

> -= условие =-

> Есть 12 монеток, одна из которых фальшивая. Она отличается от
> настоящих по весу (неизвестно, легче или тяжелее). Есть аптечные
> весы - ну, которые умеют показывать "больше/меньше/равно". Нужно за
> три взвешивания сделать следующее: во-первых найти фальшивую монету,

> а во-вторых определить, легче она или тяжелее.

это лишнее imo, так как самая трюкастая часть решения как раз тогда
когда первое взвешивание не дает баланса .. а раз ты определил
фальшивку то если она хоть раз учавствовала в дисбалансном взвешивании
то ты имеешь инфо о ее легкости/тежелости (ЛТ) ..

бообще основные такие посылы для решения задачи типа:

* Последнее взвешивание это выбор либо между 3 монетами зная ЛТ.  Либо
  выбор между 2 монетами не зная ЛТ.  Потому что за одно взвешивание
  не реально выбрать между 4-мя   (1)

* Первое взвешивание это взвешивание 4-4, т/к   (2)

  - Взвешивать имеет смысл только равное кол-во монет

  - Из шести монет невозможно выявить фальшивку за 2 взвешивания, т/к
    вторым взвешиванием неизбежно будешь выбирать между >=4 монетами

Итого тут решение, три кучки по четыре (o, * и x):

рассмотрю только интересные моменты, полного решения не будет

первое взвешивание (2):

  1234
  oooo
                1234
                xxxx

  1234
  ****

дисбаланс o и *, второе взвешивание

  1231
  ooo*
                234  4
                ***  x

  4123
  oxxx

после этого второго взвешивания мы пришли к нашему посылу (1), то есть:

  - либо ктото из o(123) и мы знаем ЛТ (в случае такого же дисбаланса
    как и в 1м взвешивании)

  - либо ктото из *(234) и мы знаем ЛТ (в случае баланса во 2м
    взвешивании)

  - либо o4 или *1 и мы не знаем ЛТ (в случае различных дисбалансов
    1-го и 2-го взвешивания)

в случае баланса первого взвешивания, это выбор из x(1234) не зная ЛТ,
то же сводится к (1) за одно взвешивание

lg ★★
()
Ответ на: комментарий от lg

CrazyPit, lg: вроде правильно. Самое сложное - что с чем сравнить, если после первого взвешивания первая куча не равна второй.

>Понятно, что ответ можно легко нагуглить - но не советую лишать себя удовольствия поразмять мозги.

Как и у многих присутствующих, со времён школы стопка дипломов со всевозможных олимпиад валяется, а "удовольствия" ни разу не получил, только ~150$ с них со всех в сумме получил от школы, и то давно и не совсем по делу прое*л. :) Хотя вот не решаю ничего этого, и уже мозги потихоньку отключаются. :)

mikhail
()
Ответ на: Первый!:] от CrazyPit

CrazyPit, я всё твоё решение пока не читал до единой буквы (стараюсь на работе на форумах много не сидеть) - но вроде верно.

P.s. Вопрос в другом - если ты её уже решал, нафига ответ написал? ;) Ну да ладно ;))

Dimentiy ★★
() автор топика
Ответ на: комментарий от Dimentiy

>CrazyPit, я всё твоё решение пока не читал до единой буквы (стараюсь на работе на форумах много не сидеть) - но вроде верно. >P.s. Вопрос в другом - если ты её уже решал, нафига ответ написал? ;) Ну да ладно ;))

Мне тоже кажется, что я её решал... Или не её... Но там точно были фальшивые монеты и такие же весы...

mikhail
()

задача элементарная :)

P.S. не взлетит, конечно!

anonymous
()
Ответ на: комментарий от mikhail

> CrazyPit, lg: вроде правильно. Самое сложное - что с чем сравнить,
> если после первого взвешивания первая куча не равна второй.

у тебя же есть знания без каких либо взвешиваний (посылы (1) и (2)).
Поэтому задача на самом деле это скомпоновать второе взвешивание, но
ты уже знаешь что тебе надо неизбежно прийти к посылу (1) после
второго взвешивания, используя это знание скомпоновать второе
взвешивание не так сложно

lg ★★
()
Ответ на: комментарий от mikhail

Не знаю мне нравился факт открытия правильного решения. Также кайфово было чувство приближающегося решения (когда правильно решаешь=).

linux_newbe
()
Ответ на: Первый!:] от CrazyPit

БЕГЕМОТ, бля!

anonymous
()

задачка на ТРОИЧНОЕ представление чисел :) берем 27 (не 12) монеток. (18 = 3^3) -1. взвешиваем 2 набора по 9 монеток - получаем набор в котором 1 монета легкая -2. взвешиваем 2 наборчика по 3 монетки из этого набора. получаем наборчик с легкой монеткой. -3. взвешиваем 2 монетки из этого наборчика. Всё :)

а если брать все-таки 12 - то: -1 взвешиваем 2 набора по 4 монетки - получаем набор в котором 1 монета легкая -2. взвешиваем 2 наборчика по 2 монетки из этого набора... -3. взвешиваем 2 оставшиеся монетки. :)

anonymous
()
Ответ на: комментарий от anonymous

> задачка на ТРОИЧНОЕ представление чисел :) берем 27 (не 12)
> монеток.

Условие прочитай ДО КОНЦА, потом пиши.

Nothing personal :)

Dimentiy ★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.