math, programming, and little something to laugh

TopCoder SRM 414 DIV 2

C/C++ TopCoder

Problem	Check	Points
250	○	120ぐらい
500	×	-
1000	-	-

250に大苦戦、120点なんて初めて・・・そして500もバグが取れず、結局あとで教えられて何とか解けました・・・

TopCoder Statistics: SRM 414 Problem Set & Analysis

Problem 250 RestaurantManager

問題

You are the manager in charge of service at a restaurant. Over the course of an evening, groups of customers arrive and you need to allocate tables to them. The restaurant has tables of various sizes in order to cope with different sized groups. The tables are allocated as follows:
When a group of customers arrives, it is allocated the smallest unallocated table that is at least as big as the group. Apart from their sizes, tables are otherwise the same, so if there are multiple appropriate tables, one is allocated arbitrarily. If there is no appropriate table available when the group arrives, the group is immediately turned away, and it will not return again that evening. When a group finishes eating and leaves, its table becomes available again to be allocated to a new group of customers.
You want to know how many customers will be turned away using this method of allocating tables.
The sizes of the tables in the restaurant are given in a int[] tables, in which each element gives the size of a single table. The size, arrival time and departure time of group i will be represented by groupSizes[i], arrivals[i] and departures[i], respectively. The groups will be listed in the order that they arrive at the restaurant, and no two groups will arrive at the same time. If a group arrives at exactly the same time another group departs, the table of the departing group will be available to be allocated to the arriving group (see example 0). Return the number of customers who are turned away.

My code

class RestaurantManager {
public:
  int allocateTables(vector <int> tables, vector <int> groupSizes, vector <int> arrivals, vector <int> departures) {

	  int turnaway = 0;
	  bool tableUsed[100];
	  int tableDeparture[100];

	  for(int i=0; i<tables.size() ; i++){
		  tableUsed[i] = false;
		  tableDeparture[i] = 0;
	  }

	  // i -> time
	  for(int i=0 ; i<1000 ; i++){
		  for(int j=0 ; j<tables.size() ; j++){
			  if(tableDeparture[j]==i){
				  tableDeparture[j]=0;
				  tableUsed[j] = false;
			  }
		  }

		  int arriveSize =  -1;
		  int arriveGroup = -1;

		  for(int j=0 ; j<arrivals.size() ; j++){
			  if(i==arrivals[j]){
				  arriveSize = groupSizes[j];
				  arriveGroup = j;
			  }
		  }
		  if(arriveSize==-1) continue;

		  int usageTable = -1;
		  int minTableSize = 9999;

		  for(int j=0 ; j<tables.size() ; j++){
			  if(!tableUsed[j] && tables[j]>=arriveSize && minTableSize > tables[j]){
				  minTableSize = tables[j];
				  usageTable = j;
			  }
		  }

		  if(usageTable==-1) turnaway += arriveSize;
		  else{
			  tableUsed[usageTable] = true;
			  tableDeparture[usageTable] = departures[arriveGroup];
		  }
	  }
	  return turnaway;
  }
};

Problem 500 Embassy

問題

You've just qualified for the on-site round of a major coding tournament! You now need to sort out a visa to allow you to travel to the event. You know that this is likely to be a long process, but are determined to sort it out as quickly as possible, even if it means working day and night. The process involves filling out a series of forms, which then have to be approved by the embassy. When the last form is approved your visa is granted. The approval process is very quick (instantaneous for the purpose of this problem), but there is a catch: each form has to be approved by the embassy before they will give you the next form to fill out. The embassy opens at exactly the same time each day and remains open for openTime time units. By the non-standard embassy clocks, a day is dayLength time units long, so the embassy then remains closed for dayLength - openTime time units before it opens the next day. Forms can be approved at any point in time between the time that the embassy opens and the time it closes, inclusive. However, if you finish filling in a form when the embassy is closed, you have to wait until it opens again before the form can be approved. The length of time it takes you to fill out form i is forms[i] units and the forms must be completed in the order they are given in forms. You already have the first form in your possession and can start filling it out at any time. Return the minimum length of time between starting to fill out the first form and getting your visa granted.

My code

int calcTime(vector<int> forms, int dayLength, int openTime, int now){
	int totalTime = forms[0];
	for(int i=1 ; i<forms.size() ; i++){
		totalTime += forms[i];
		now = (now+forms[i])%dayLength;

		if(now > openTime){
			totalTime += dayLength-now;
			now = 0;
		}
	}
	return totalTime;
}

class Embassy {
public:
  int visaApplication(vector <int> forms, int dayLength, int openTime) {
	  int t = 99999999;
	  for(int i=0 ; i<=openTime ; i++) t = min(t, calcTime(forms, dayLength, openTime, i));
	  return t;
  }
};

Problem 1000 Shape3D

問題

A shape in 3D Cartesian space is valid if it is made up of identical unit cubes, each cube in the shape has all its edges parallel to coordinate axes and its vertices are at non-negative integer coordinates. Two shapes are considered the same if one can be transformed into the other by some rotation and translation. You are given a description of a valid shape and should return the lexicographically smallest description of a valid shape that is the same as the one supplied.
You are given a String shape. Each element of shape describes a single unit cube from the shape and will contain three space-separated non-negative integers. The first of these gives the x-coordinate of the cube, the second gives the y-coordinate, and the third the z-coordinate. The cube is positioned such that the line segment between (x, y, z) and (x+1, y+1, z+1) is a diagonal of the cube and its edges are all parallel to the coordinate axes. Return a String containing the lexicographically smallest description of a valid shape in the same format as the input that can be transformed to the supplied shape by rotation and translation. Each element of your return must contain 3 single-space-separated non-negative integers without leading zeros and with no leading or trailing spaces. Each element of your return must describe a distinct cube from the shape.