BlurredDartboard.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <climits>
#include <cstring>
using namespace std;

typedef long long  int64;
typedef vector<int> vi;
typedef string ST;
typedef stringstream SS;
typedef vector< vector <int> > vvi;
typedef pair<int,int> ii;
typedef vector <string> vs;

#define Pf	printf
#define	Sf	scanf

#define	ep	1e-9
#define PI M_PI
#define E M_E

#define	CL(a, b)	memset(a, b, sizeof(a))
#define	mp	make_pair

#define	pb	push_back

#define	all(c)	(c).begin(), (c).end()
#define	tr(i, c)	for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

#define	present(x, c)	((c).find(x) != (c).end())		//map & set//
#define	cpresent(x, c)	(find(all(c),x) != (c).end())	//vector & list//

#define forn(i, n)	for(int i = 0, loop_ends_here = (int)n; i < loop_ends_here; i++)
#define forab(i, a, b)	for(int i = a, loop_ends_here = (int) b; i <= loop_ends_here; i++)
#define rep(i, a, b)	for(int i = a, loop_ends_here = (int)b; i>=loop_ends_here; i--)

#define read(n)		scanf("%d", &n)
#define write(n)	printf("%d ", n)
#define writeln(n)	printf("%d\n", n)

class BlurredDartboard
{
public:
	int minThrows(vector <int> points, int P);
};

vector <int64> pts;
int64 P;

int BlurredDartboard::minThrows (vector <int> points, int _P) 
{
	P = _P;
	pts.clear();
	int64 mx = 0, sum = 0, cnt = 0;

	cout << "#1\n";
	forn(i, points.size()) {
		pts.pb(points[i]);	
		mx = max(mx, (int64)points[i]);
		Pf();
		cout << "#1a\n";

		if(points[i] == 0)
			cnt++;
		cout << "#1b\n";

		if(cpresent(i+1, points) == false)
			sum+= i+1;
		cout << "#1c\n";
	}

	Pf("mx = %lld, sum0 = %lld, cnt0 = %lld, ", mx, sum, cnt);

	int64 step1 = 1e15;
	int64 tmpStep = 1e15;

	if(sum) {
		step1 = P/sum*cnt;
		tmpStep = 0;
		int64 rem = P % sum;

		int64 tmpSum = 0;

		forab(i, 1, pts.size())	if(!cpresent(i, pts)) {
			if (tmpSum >= rem)
				break;
			tmpStep++;
			tmpSum += i;	
		}

		step1 += min(tmpStep, rem/mx + (rem%mx? 1 : 0));
	}

	Pf("step1 = %lld ", step1);

	cout << endl;

	return (int)min(step1, P/mx + (P%mx ? 1 : 0));
}

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <int> p0, int p1, bool hasAnswer, int p2) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p0[i];
	}
	cout << "}" << "," << p1;
	cout << "]" << endl;
	BlurredDartboard *obj;
	int answer;
	obj = new BlurredDartboard();
	clock_t startTime = clock();
	answer = obj->minThrows(p0, p1);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p2 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p2;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	vector <int> p0;
	int p1;
	int p2;
	
	{
	// ----- test 0 -----
	int t0[] = {0,3,4,0,0};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 8;
	p2 = 2;
	all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	int t0[] = {0,0,0,0,0};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 15;
	p2 = 5;
	all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	int t0[] = {4,7,8,1,3,2,6,5};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 2012;
	p2 = 252;
	all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	int t0[] = {0,0,5,0,0,0,1,3,0,0};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 2012;
	p2 = 307;
	all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	int t0[] = {0,2,0,0,0,0,0,0,0,9,0,0,6,0,0,0,4,0,0,0};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 1000000000;
	p2 = 84656087;
	all_right = KawigiEdit_RunTest(4, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// This problem statement contains superscripts and/or subscripts. It may not display properly outside the applet.
// 
// 
// Wojtek and Tomek are playing darts. Unfortunately the dartboard is blurred and Wojtek can't read some of the numbers written on it. On the other hand, Tomek remembers the numbers written on the dartboard.
// 
// 
// The dartboard is divided into N parts. Wojtek knows that for each integer x between 1 and N, inclusive, there is exactly one part that is worth x points. You are given a vector <int> points containing N integers. If points[i] is positive, the i-th part is worth points[i] points. If points[i] is zero, he can't read the number that indicates the point value of the i-th part.
// 
// 
// Wojtek and Tomek will play the following game. First, Wojtek throws K darts. Wojtek is perfectly skilled at darts, so he will certainly hit the parts he wants to hit. He is allowed to hit the same part with multiple darts. After Wojtek throws all the darts, Tomek calculates Wojtek's total score. The total score is simply the sum of the points hit by each of the darts. (Note that each part of the dartboard may be counted multiple times if Wojtek hits it with multiple darts.) If the total score is at least P points, Wojtek wins. Otherwise, Tomek wins.
// 
// 
// You are given the vector <int> points and the int P. Return the smallest K such that Wojtek is guaranteed to win the game if he follows the optimal strategy when throwing the darts.
// 
// DEFINITION
// Class:BlurredDartboard
// Method:minThrows
// Parameters:vector <int>, int
// Returns:int
// Method signature:int minThrows(vector <int> points, int P)
// 
// 
// CONSTRAINTS
// -points will contain between 1 and 50 elements, inclusive.
// -Each element of points will be between 0 and N, inclusive, where N is the number of elements in points.
// -Each of the integers from 1 to N, inclusive, will appear at most once in points.
// -P will be between 1 and 1,000,000,000 (109), inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// {0, 3, 4, 0, 0}
// 8
// 
// Returns: 2
// 
// Wojtek should hit part 2 twice. He will get 8 points.
// 
// 1)
// {0, 0, 0, 0, 0}
// 15
// 
// Returns: 5
// 
// Wojtek should hit each part exactly once. He doesn't know the point values, but the total score will be always 15.
// 
// 2)
// {4, 7, 8, 1, 3, 2, 6, 5}
// 2012
// 
// Returns: 252
// 
// 
// 
// 3)
// {0, 0, 5, 0, 0, 0, 1, 3, 0, 0}
// 2012
// 
// Returns: 307
// 
// 
// 
// 4)
// {0, 2, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 6, 0, 0, 0, 4, 0, 0, 0}
// 1000000000
// 
// Returns: 84656087
// 
// 
// 
// END KAWIGIEDIT TESTING


//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!