Фалшиви монети

Задача:

Владетелят на едно далечно царство заповядал да бъдат изсечени известно количество златни монети с тегла 1,2,...,n грама. Монетите били изсечени и част от тях незабавно влезли в обръщение. Няколко дни по-късно постъпили първите оплаквания за фалшиви монети от търговците, снабдяващи двореца. Първият министър извършил незабавно разследване, което установило наличие на нестандартни монети от един-единствен тип, тежащи с един грам по-малко от предвиденото, което вeднага било съобщено на царя. Главният златар обаче категорично отхвърлял обвиненията и твърдял, че търговците и министрите се опитват да го злепоставят съвършено неоснователно. Царят, който по принцип нямал особено доверие на никого, решил да се заеме лично със случая. В двореца незабавно били доставени по една торба монети от всеки тип, както и специален кантар, побиращ едновременно произволен брой монети от произволен тип (типове).

Напишете програма, която да помогне на царя да провери дали има злоупотреба, а в случай че има ѕ и да установи кой тип монети са нестандартни (има неповече от един нестандартен тип), за да могат веднага да бъдат извадени от употреба. Имайте предвид, че за всяко претегляне Националният институт по мерки и теглилки получавал една и съща предварително фиксирана сума, независеща от броя, типа(типовете) и теглата на монетите, което налага минимизиране на броя на извършваните претегляния.

Решение:

Задачата ще решим с единствено претегляне за произволно n. (Предполагаме, че във всеки чувал има поне n монети).

PROGRAM Falshivi_Moneti;

BEGIN

WriteLn('Вземете една монета от първия вид,');

WriteLn('две - от втория, ');

WriteLn('три - от третия, ');

WriteLn('.................');

WriteLn('n - от n-тия');

WriteLn('и ги претеглете.');

WriteLn('Разликата в грамове (ако има разлика) между очакваното и полученото');

WriteLn('общо тегло еднозначно определя номера на торбата с фалшиви монети.');

END.

Преслав Наков

студент - СУ