OJ Board

Code: Select all

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <functional>
#include <string>
#include <istream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <iterator>
#include <ios>
#include <iosfwd>
#include <ios>

using namespace std;

//#define ONLINE_JUDGE

#ifdef ONLINE_JUDGE
 #define Fin stdin
 #define Fout stdout
#else
 #define Fin f1
 #define Fout f2
#endif

FILE* f1;
FILE* f2;



struct dataset
{
	int id;
	long double price;
	vector<int> amounts;
	dataset()
	{
		amounts.push_back(0);
		amounts.push_back(0);
		amounts.push_back(0);
		amounts.push_back(0);
	}
};


struct request
{
	vector<int> amounts;
	request()
	{
		amounts.push_back(0);
		amounts.push_back(0);
		amounts.push_back(0);
		amounts.push_back(0);
	}
};

vector<dataset> Datasets;
vector<request> Requests;



vector<int> filledAmounts; //a vector of 4 for the amounts
long double curPrice;		//curPrice paid
long double minPrice;

struct res
{
	int amount;
	int package;
};


vector<res> amountOfPackages; //amounts taken from each package!
vector<res> minAmountOfPackages; //amounts taken from each package!


void doSolve(unsigned int datasetToStart,int curRequest)
{
	//if finished solving, output it
	char Done=1;
	int j;
	for(j=0;j<4;j++)
		if(filledAmounts[j]<Requests[curRequest].amounts[j])
			Done=0;

	if(Done||datasetToStart==Datasets.size())
	{
		if(!Done)return;
		if(minPrice<0)
		{
			minPrice=curPrice;
			minAmountOfPackages=amountOfPackages;
		}
		else if(curPrice<minPrice)
		{
			minPrice=curPrice;
			minAmountOfPackages=amountOfPackages;

		}
		return;
	}
	if(minPrice>0&&curPrice>minPrice)
		return;




	int num=0; //amount to take from package "packageToStart"
	while(1)
	{
		//take num out of package "packageToStart"
		vector<int> oldFill=filledAmounts;
		vector<res> oldAmounts=amountOfPackages;
		long double oldCurPrice=curPrice;

		amountOfPackages[datasetToStart].amount=num;
		amountOfPackages[datasetToStart].package=datasetToStart;
		int i;
		for(i=0;i<4;i++)
			filledAmounts[i]+=Datasets[datasetToStart].amounts[i]*num;
		curPrice+=Datasets[datasetToStart].price*num;

		doSolve(datasetToStart+1,curRequest);

		int done=1;
		int j;
		for( j=0;j<4;j++)
			if(filledAmounts[j]<Requests[curRequest].amounts[j]&&Datasets[datasetToStart].amounts[j]>0)
				done=0;

		filledAmounts=oldFill;
		amountOfPackages=oldAmounts;
		curPrice=oldCurPrice;

		if(done)
			break;
		num++;
	}

}


struct IDSort:public binary_function<res,res,bool>
{
	bool operator()(res x,res y)
	{
		if(Datasets[x.package].id<Datasets[y.package].id)
			return 1;
		return 0;
	}
};

void solve(void)
{
	while(1)
	{
		Datasets.clear();
		Requests.clear();
		int numDataSets,numRequests;
		if(fscanf(Fin,"%d\n",&numDataSets)!=1)
			break;
		int i;
		for(i=0;i<numDataSets;i++)
		{
			char line[5000];
			fgets(line,4000,Fin);
			istringstream inpS(line);
			dataset temp;
			//sscanf(line,"%d %Lf",&temp.id,&temp.price);
			inpS>>temp.id>>temp.price;
			while(inpS)
			{
				char c;int t;
				inpS>>skipws>>c>>t;
				if(inpS)
					temp.amounts[c-'a']=t;
			}
			Datasets.push_back(temp);
		}
		fscanf(Fin,"%d\n",&numRequests);
		for(i=0;i<numRequests;i++)
		{
			char line[5000];
			fgets(line,4000,Fin);
			istringstream inpS(line);
			request temp;
			//sscanf(line,"%d %Lf",&temp.id,&temp.price);
			while(inpS)
			{
				char c;int t;
				inpS>>skipws>>c>>t;
				if(inpS)
					temp.amounts[c-'a']+=t;
			}
			Requests.push_back(temp);
		}


		//start solving!
		for(i=0;i<numRequests;i++)
		{
			curPrice=0;
			minPrice=-100;
			filledAmounts.clear();
			filledAmounts.push_back(0);
			filledAmounts.push_back(0);
			filledAmounts.push_back(0);
			filledAmounts.push_back(0);
			amountOfPackages.clear();
			res vv;
			vv.amount=0;
			vv.package=0;

			int j;
			for(j=0;j<numDataSets;j++)
				amountOfPackages.push_back(vv);

			doSolve(0,i);
			fprintf(Fout,"%d: %7.2Lf",i+1,minPrice);


			sort(minAmountOfPackages.begin(),minAmountOfPackages.end(),IDSort());
			unsigned int k;
			for(k=0;k<minAmountOfPackages.size();k++)
			{
				if(/*k!=minAmountOfPackages.size()-1&&*/minAmountOfPackages[k].amount>0)
					fprintf(Fout," ");
				if(minAmountOfPackages[k].amount==1)
					fprintf(Fout,"%d",Datasets[minAmountOfPackages[k].package].id);
				else if(minAmountOfPackages[k].amount>1)
					fprintf(Fout,"%d(%d)",Datasets[minAmountOfPackages[k].package].id,minAmountOfPackages[k].amount);
			}
			fprintf(Fout,"\n");
		}
		fprintf(Fout,"\n");
	}
}



int main(void)
{
#ifndef ONLINE_JUDGE
  f1=fopen("cur.in","r");
  f2=fopen("cur.out","w");
#endif

  solve();

#ifndef ONLINE_JUDGE
 fclose(Fin);
 fclose(Fout);
#endif
  return 0;
}

Code: Select all

// #include <istream>
// #include <ios>
// #include <ios>

Code: Select all

            // inpS>>skipws>>c>>t;
            inpS.setf(ios::skipws); inpS>>c; inpS.unsetf(ios::skipws); inpS>>t;