Текущ брой на Списание ИнфоМан
 


USACO квалификационен кръг - октомври, SILVER Division, Задача allow

Уловието на задачата може да прочетете тук.

Решение

Номиналите на монетите са числа, кратни едно на друго. Затова всеки достатъчно голям брой монети с даден номинал, може да се замени с монета с по-голям номинал. Още повече – FJ печели ако направи такава зямяна, защото за него е полезно да може да използва повече монети с по-малък номинал. Затова, за да събере сумата C, FJ ще действа по следния начин:

Първо взема максимален брой монети с възможно най-голям номинал, чиято сума не надвишава C. Остатъка до C започва да събира по същият начин – с монети с максимален номинал, които не надвишават разликата. Това продължава докато не получи желаната сума или докато не използва и монетите с най-малкия номинал. Ако е събрал сумата, вече може да мисли за следващата седмица, ако не – трябва да вземе още монети. Оказва се, че му е достатъчно да вземе най-евтината монета от оставащите му и сумата ще е събрана. Тази процедура той повтаря всяка седмица, докато сумата от всичките му монети не стане по-малка от C.

По този начин FJ претърпява най-малка загуба на пари. Ако събере точната сума, загуба няма. Ако пък след обхождането на монетите не я е събрал, добавянето на най-евтината монета от останалите му носи най-малка загуба. Сигурно е, че всякак една монета от останалите ще е достатъчна за попълването на сумата, понеже ако не е достатъчна, FJ щеше да я сложи преди това. Понеже всяка ще свърши работа, най-подходяща е най-евтината, защото така FJ дава най-малко пари.

Ако в дадена седмица FJ използва съответно по a1, a2, ..., anмонети от всеки вид, и има достатъчно монети да вземе няколко пъти по ai(за i от 1 до n), тогава през следващите седмици конфигурацията ще е същата и няма нужда да я намира отново.

Решението на задачата следва оптималния алгоритъм на FJ. Следователно намирането на подходяща конфигурация става със сложност O(n). Тъй като всяка конфигурация се търси само по един път, сложността на цеият алгоритъм е O(m*n), където m е броят на различните конфигурации. При намирането на всяка нова конфигурация и прилагането и максимален брой пъти, броят на поне един вид монети ще се намали поне на половина (ако това не е изпълнено, означава че конфигурацията може да се използва още поне един път). Тогава, за да се изчерпи количеството монети от даден вид, те трябва да участват в най-много log21000000 ≈ 20 конфигурации. А за да се изчерпят всички монети – най-много n пъти по толкова. Следователно m<20*n и сложността на алгоритъма е О(n2)

Примерна реализация


#include <stdio.h>
#define MAX_N 20

void sort();

struct coin
{
	int br;
	int pr;
} coins[MAX_N];

int n,c;			
int rest = 0;     //The amount of coins FJ has not used
int result = 0;	  //The number of weeks
int weeks[MAX_N]; //The number of weeks each coin can be 
				  //used in the current configuration
int rems[MAX_N];  //The count of coins of a particular 
				  //type for the current configuration

int main()
{	
	int i;
	int sum;      //The current sum for the current configuration
	int min;      //The minimal number among weeks[i], giving the 
                  //number of weeks for a configuration

	freopen("allow.in","r",stdin);
	freopen("allow.out","w",stdout);

	scanf("%d%d",&n,&c);
	
	for(i=0;i<n;i++)
	{
		scanf("%d%d",&coins[i].pr,&coins[i].br);
		rest += coins[i].br;
	}
	sort();
	
	//While there are still some coins, configurations are searched
	while(rest>0)
	{
		sum = 0;
		min = 2000000000;
		for(i=0; i<n; i++) weeks[i]=0;

		//Each coin is added the maximal 
		//number of times, so that the sum 
		//doesn't exceed c
		for(i=0;i<n;i++)
			if(coins[i].br!=0 && coins[i].pr<=c-sum)
				{
					if((c-sum)/coins[i].pr
					<=coins[i].br)
					{
						rems[i]=
						(c-sum)/coins[i].pr;
						weeks[i]=
						coins[i].br/rems[i];
						sum+=rems[i]*coins[i].pr;
					}else
					{
						weeks[i]=1;
						rems[i]=coins[i].br;
						sum+=rems[i]*coins[i].pr;
					}
					if(min>weeks[i]) 
						min = weeks[i];


					if(sum>=c) break;
					
				}
		
		//If the sum is smaller than c, 
		//another coin is added to the 
		//configuration so that sum>=c
		if(sum<c)
		{	
			
			for(i=n-1; i>=0; i--)
			{
				if(coins[i].br>=rems[i]+1) break;
			}
			
			if(i<0) break;
			rems[i]++;
			weeks[i]=coins[i].br/rems[i];
			if(min>weeks[i]) min = weeks[i];
		}
		
		//The configuration found 
		//is taken out the largest 
		//possible number of times
		for(i=0; i<n; i++)
			{
				if(weeks[i]>0) 
				{
					coins[i].br-=min*rems[i];
					rest -= min*rems[i];
					weeks[i]=rems[i]=0;
				}
			}
			
		result+=min;
		
				
	}
	printf("%d\n",result);
	return 0;
}

void sort()
{
	int i,j;
	struct coin temp;

	for(i=0; i<n; i++)
		for(j=i+1; j<n; j++)
			if(coins[i].pr<coins[j].pr)
			{
				temp = coins[i];
				coins[i] = coins[j];
				coins[j] = temp;
			}
}

Автор: Орлин Тенчев


обратно към текущ брой