Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Фальшивая монета как ее написать
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию Фальшивая монета как ее написать - 01.02.2006, 20:53

В продолжение темы сравнения ЯП приведу интересную задачу с 1998-99 ACM Northeastern European Regional Programming Contest (всё-таки по-сложнее чем школьные олимпиады). Перевод с английского мой. Очень интересно в частности посмотреть её решение на Питоне. У меня есть два решения на Паскале: одно своё - старое, неоптимальное, хотя и удовлетворяющее условию, второе написал Roman Elizarov - очень элегантное, потом выложу его сюда.

Условие
Банк "Gold Bar" получил информацию из достоверных источников, что в последней партии из N монет содержится одна фальшивая, которая отличается по весу от остальных монет (другие монеты одного веса). После экономического кризиса банку доступны только простые весы, используя которые можно определить, что вес объектов в левом лотке меньше, равен или больше чем вес объектов в правом лотке. Для того чтобы определить фальшивую монету, работники банка перенумеровали все монеты целыми числами от 1 до N, поставив таким образом в соответствие каждой монете уникальный целый идентификатор. После этого они начали взвешивать различные группы монет, помещая одинаковое количество монет в левом и правом лотках. Идентификаторы монет и результаты взвешиваний были тщательно записаны. Вы должны написать программу, которая поможет работникам банка определить идентификатор фальшивой монеты, используя результаты этих взвешиваний.

Входной файл: COIN.IN
В первой строке содержатся два числа N (2 <= N <= 100) и K (1 <= K <= 100), разделённые пробелами, где N - количество монет, а K - количество сделанных взвешиваний. Следующие 2*K строк описывают результаты всех взвешиваний. Каждое взвешивание представляется двумя идущими друг за другом строками. В первой из них содержится число монет Pi, размещённых в каждом лотке, после которого идут идентификаторы монет, сначала Pi идентификаторов монет в левом лотке, потом Pi идентификаторов монет в правом лотке. Все числа разделяются пробелами. Вторая строка содержит один из следующих символов: '<', '>' или '='. Они обозначают результат взвешивания:
'<' означает, что вес монет в левом лотке меньше веса монет в правом;
'>' означает, что вес монет в левом лотке больше веса монет в правом;
'=' означает, что вес монет в левом лотке равен весу монет в правом.

Выходной файл: COIN.OUT
Запишите в выходной файл идентификатор фальшивой монеты или 0, если невозможно её определить по результатам представленных взвешиваний.

Ограничение времени: 10 секунд на тест (тогда тестовыми машинами были 486, Pentium, а иногда и 386, так что ограничение на современных машинах вполне можно сделать 1 секунду на тест).

Примеры
Пример входного файла #1
5 3
2 1 2 3 4
<
1 1 4
=
1 2 5
=
Выходной файл для примера #1
3

Пример входного файла #2
6 4
3 1 2 3 4 5 6
<
1 1 2
=
2 1 3 4 5
<
2 4 5 2 6
>
Выходной файл для примера #2
0
Ответить с цитированием
  (#2 (permalink)) Старый
Mr. Пронька Mr. Пронька вне форума
Member
 
Сообщений: 168
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.06.2005
По умолчанию 01.02.2006, 21:51

Отличная задача! Меня мама в детстве ею мучила.
Ответить с цитированием
  (#3 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 02.02.2006, 10:49

Прочитал. Решение придумал. Жуткий цейтнот на работе (нужно решить задачку на порядок сложней этой, причем, до сегоднешнего вечера) .Постараюсь успеть все. michael, если можно, не публикуйте пока свое решение.
Ответить с цитированием
  (#4 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 02.02.2006, 15:56

Вот, набросал какое-то решение (максимально тупое и прямолинейное).


Код:
from string import *
import sys

def tmp(l,r,op): #вспомогательная функция
    if (l and op=='<') or (r and op=='>'): return 1
    if (r and op=='<') or (l and op=='>'): return 2
    return 0

def change_state(state,l,r,op): #идиотская функция для перехода между состояниями
    if op=='=' and (l or r): return -1
    if op!='=' and not(l or r): return -1
    if state==0: return tmp(l,r,op)
    if state==3-tmp(l,r,op): return -1
    return state        

flag=False
f1=open('coin.in','r')
sys.stdout=open('coin.out', 'w')
[coins,checks]=rsplit(f1.readline()) #читаем первую строчку, получаем кол-во монет и взвешиваний
coins_list=[(n+1,0) for n in xrange(int(coins))] #инициализируем список пар (монета,состояние)
for i in xrange(int(checks)): #для каждого взвешивания
    tmp_lst=map(int,rsplit(f1.readline())) #читаем строку, преобразуем в список целых чисел
    left=tmp_lst[1:tmp_lst[0]+1] #делим его на два списка, для левой чаши
    right=tmp_lst[tmp_lst[0]+1:] #и для правой
    op=strip(f1.readline()) #читаем следующую строку, получаем оператор сравнения
    for j in xrange(len(coins_list)): #пробегаем по списку подозрительных монет
        (ID,state)=coins_list[j] #берем очередную монету
        l=(ID in left);r=(ID in right) #помечаем чашу в которой она находится значением true 
        new_state=change_state(state,l,r,op) #переводим монету в новое состояние 
        coins_list[j]=(ID,new_state) #записываем новое состояние монеты                     
    coins_list=[(x,y) for (x,y) in coins_list if y!=-1] #вычеркиваем подлинные монеты
    #print coins_list
    if len(coins_list)==1: # если осталась одна монета
        print coins_list[0][0];flag=True;break #печатаем ее индекс и выходим из цикла
if not(flag):print 0 #если после всех взвешиваний на подозрении больше одной монеты, печатаем 0
f1.close()
sys.stdout.close()
Если раскоментировать эту строчку:
Код:
#print coins_list
можно увидеть весь ход рассуждений.
"1" рядом с индексом монеты означает, что программа подозревает монету в том, что она легче остальных.
"2" соответственно - тяжелее.
"0" монета пока вне подозрений.

Потом, если будет время, попробую оптимизировать и подсократить.

michael, у Вас есть тестовые файлы с большим колличеством взвешиваний? Интересно было бы погонять.

Прологовское решение этой задачки должно быть очень коротким.
Ответить с цитированием
  (#5 (permalink)) Старый
Mr. Пронька Mr. Пронька вне форума
Member
 
Сообщений: 168
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.06.2005
По умолчанию 02.02.2006, 16:25

Опять влезу, ничё? Только мне эта задача представала, как из 10 монет за 3 (или 4) шага вычленить фальшивую. Вот это была головоломка!
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 02.02.2006, 21:21

Цитата:
Originally posted by Mr. Пронька
[b]Опять влезу, ничё? Только мне эта задача представала, как из 10 монет за 3 (или 4) шага вычленить фальшивую. Вот это была головоломка!
Может это и злостный оффтоп, но...

Как-то нам учитель пристал, мол, в течении дня решить. [именно это]. Так вот я единственный кто решил. Помню те славные времена)))


А вот насчет задачи данной хочу сказать, что задача действительно мощная. Поискал в нете и [как ни странно] нашел. Там еще дохрена таких жирных задач. Спасибо.
Ответить с цитированием
  (#7 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 02.02.2006, 23:19

Странно...
На работе набрал, все выглядело нормально, дома открыл, весь код разлезается... На всякий случай код без комментариев:
Код:
from string import *
import sys

def tmp(l,r,op): 
    if (l and op=='<') or (r and op=='>'): return 1
    if (r and op=='<') or (l and op=='>'): return 2
    return 0

def change_state(state,l,r,op): 
    if op=='=' and (l or r): return -1
    if op!='=' and not(l or r): return -1
    if state==0: return tmp(l,r,op)
    if state==3-tmp(l,r,op): return -1
    return state        

flag=False
f1=open('coin.in','r')
sys.stdout=open('coin.out', 'w')
[coins,checks]=rsplit(f1.readline()) 
coins_list=[(n+1,0) for n in xrange(int(coins))] 
for i in xrange(int(checks)): 
    tmp_lst=map(int,rsplit(f1.readline())) 
    left=tmp_lst[1:tmp_lst[0]+1] 
    right=tmp_lst[tmp_lst[0]+1:] 
    op=strip(f1.readline()) 
    for j in xrange(len(coins_list)): 
        (ID,state)=coins_list[j] 
        l=(ID in left);r=(ID in right)  
        new_state=change_state(state,l,r,op)  
        coins_list[j]=(ID,new_state)                      
    coins_list=[(x,y) for (x,y) in coins_list if y!=-1] 
    #print coins_list
    if len(coins_list)==1: 
        print coins_list[0][0];flag=True;break 
if not(flag):print 0 
f1.close()
sys.stdout.close()
Ответить с цитированием
  (#8 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 02.02.2006, 23:48

Цитата:
Originally posted by Mr. Пронька
[b]Опять влезу, ничё? Только мне эта задача представала, как из 10 монет за 3 (или 4) шага вычленить фальшивую. Вот это была головоломка!
Это совсем другая задача (там вроде известно, что ф.м. весит меньше, нужно определить её за 3 шага [причём в удачном случае это будут 2 шага]), она не сложная, если немного подумать. А вот в той, о которой разговор, красивое решение не каждый найдёт. Но оно есть. В довольно многословном Паскале оно заняло 44 строки (со всеми program'ами, begin'ами и end'ами), причём хорошо читаемо и кажется очевидным. Кстати, в C (без ++) оно так просто не реализуемо.

Цитата:
Originally posted by gromozeka
[b]michael, у Вас есть тестовые файлы с большим колличеством взвешиваний? Интересно было бы погонять.
Есть. Могу отправить на мыло.
Ответить с цитированием
  (#9 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 02.02.2006, 23:58

Цитата:
Originally posted by michael+-->
Цитата:
<!--QuoteBegin-Mr. Пронька
Цитата:
[b]Опять влезу, ничё? Только мне эта задача представала, как из 10 монет за 3 (или 4) шага вычленить фальшивую. Вот это была головоломка!
Это совсем другая задача (там вроде известно, что ф.м. весит меньше, нужно определить её за 3 шага [причём в удачном случае это будут 2 шага]), она не сложная, если немного подумать. А вот в той, о которой разговор, красивое решение не каждый найдёт. Но оно есть. В довольно многословном Паскале оно заняло 44 строки (со всеми program'ами, begin'ами и end'ами), причём хорошо читаемо и кажется очевидным. Кстати, в C (без ++) оно так просто не реализуемо.

Цитата:
Originally posted by gromozeka
[b]michael, у Вас есть тестовые файлы с большим колличеством взвешиваний? Интересно было бы погонять.
Есть. Могу отправить на мыло.
Самая сложная задача из этой серии:
13 монет, три взвешивания, весы чашечные, без гирь.
одна монета фальшивая, тяжелее или легче - неизвестно.
это возможно.

можно тесты на fuks.michael@gmail.com?
Как Вам лобовое решение на Питоне?
Ответить с цитированием
  (#10 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 03.02.2006, 00:10

Цитата:
Originally posted by gromozeka
[b]можно тесты на fuks.michael@gmail.com?
Как Вам лобовое решение на Питоне?
Тесты отправил.
Решение чем-то похоже на то, как её решал и я в своё время. Алгоритм, не зная Питона, честно говоря, разглядеть сложно.
Ответить с цитированием
  (#11 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 03.02.2006, 10:37

Погонял. Работает правильно. В секунду укладывается с запасом. В большинстве случаев, находит решение до того, как переберет все взвешивания.
Можно посмотреть на гениальное решение на паскале?
Я заинтригован. Подозреваю, что там подмечены какие-нибудь математические свойства всего происходящего.
Ответить с цитированием
  (#12 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 03.02.2006, 11:04

Цитата:
Originally posted by gromozeka
[b]Можно посмотреть на гениальное решение на паскале?
Я заинтригован. Подозреваю, что там подмечены какие-нибудь математические свойства всего происходящего.
Само собой подмечены.
Код:
{ NEERC'98 Problem "False coin"
  Solution by Roman Elizarov
  19.11.98
}
{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
program COIN_SOLUTION;

const
  maxn = 100;

var
  n, k, i, j, p, u, cnt, idx: integer;
  less, more, l, r, all: set of 1..maxn;
  c: char;

begin
  assign ( input, 'coin.in' ); reset ( input );
  assign ( output, 'coin.out' ); rewrite ( output );

 { Gathering information }
  read ( n, k );
  less:= [1..n]; { Possible false coins with lower weight   }
  more:= [1..n]; { Possible false coins with greater weight }
  for i:= 1 to k do begin
    read ( p );
    l:= []; { Coins in left pan  }
    r:= []; { Coins in right pan }
    for j:= 1 to p do begin
      read ( u );
      include ( l, u );
    end;
    for j:= 1 to p do begin
      read ( u );
      include ( r, u );
    end;
    readln;
    read ( c );
    case c of
      '=': begin less:= less - l - r; more:= more - l - r; end;
      '<': begin less:= less * l; more:= more * r; end;
      '>': begin less:= less * r; more:= more * l; end;
    end;
  end;

 { Analyzing information and writing answer }
  all:= less + more;
  cnt:= 0;
  for i:= 1 to n do
    if i in all then begin
      inc ( cnt );
      idx:= i;
    end;
  if cnt = 1 then
    writeln ( idx )
  else
    writeln ( 0 );
end.
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 03.02.2006, 11:37

Презумпция виновности, класс!
И вообще, обожаю sets. В си это можно сделать при помощи bitwise операций. Правда, кода выйдет чуть больше.

Зачем только пробегать по всем взвешиваниям?
В самом большом из ваших файлов (16К) реально потребовалось проверить только 4 первых взвешивания.
Ответить с цитированием
  (#14 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 03.02.2006, 11:52

Цитата:
Originally posted by gromozeka+-->
Цитата:
В си это можно сделать при помощи bitwise операций. Правда, кода выйдет чуть больше.
Ну, я же и говорил, что не так просто, всё-таки 100 бит - это будет массив, а операции пересечение и объединение - цикл (отдельная функция). Операция вычитания ещё сложней.

<!--QuoteBegin-gromozeka

[b]Зачем только пробегать по всем взвешиваниям?
В самом большом из ваших файлов (16К) реально потребовалось проверить только 4 первых взвешивания.
В Паскале, насколько я помню, нельзя проверить мощность множества (может ошибаюсь). Видимо, чтобы не усложнять программу, это же решение на время.
Ответить с цитированием
  (#15 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 03.02.2006, 12:29

Перевод на Питон:
Код:
from string import * 
import sys 
 
f1=open('coin.in','r') 
sys.stdout=open('coin.out', 'w') 
[coins,checks]=rsplit(f1.readline()) 
more=set(range(1,int(coins)+1))
less=more.copy()
for i in xrange(int(checks)): 
    tmp=map(int,rsplit(f1.readline())) 
    l=set(tmp[1:tmp[0]+1]) 
    r=set(tmp[tmp[0]+1:]) 
    op=strip(f1.readline()) 
    if op=='=':more-=l|r;less-=l|r
    elif op=='<':less&=l;more&=r
    elif op=='>':less&=r;more&=l
all=list(less|more)
if len(all)==1:print all[0]
else: print 0
f1.close() 
sys.stdout.close()
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как написать ряд 0,-2*x,4*x^2,(-2)^3*x^3,.......,(-2)^n*x^n Alenka-dev Lisp 0 05.05.2010 07:10
Веб-бот как его написать tsi Общие вопросы создания ПО 3 11.02.2010 19:15
Как написать TSR программу в С++ kosetsky Вопросы начинающих программистов 1 03.10.2009 21:25
Написать программу blackcat Задания за деньги 3 20.09.2009 12:12
Как написать формулу в VBA samo Visual Basic 2 06.08.2008 23:09
Как написать? Angel07 Prolog 0 10.11.2007 13:39
Как это написать на VB? SOm26 Visual Basic 0 16.03.2007 04:48
Как написать DLL для 1С Root_in C++ Builder 1 22.11.2005 12:09
Как написать DLL ? HeiHeShang Prolog 7 28.09.2005 16:28
If в SQL в C++ Builder 5 как написать Fet SQL 5 15.04.2004 14:29
Как написать AVI-проигрыватель Anonymous Visual C++ 1 29.01.2004 16:11
Как написать CGI Anonymous Некоммерческие проекты 1 02.10.2002 16:15



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов