math, programming, and little something to laugh

TopCoder SRM 412 DIV 2

C/C++ TopCoder

Problems	Check	Points
250	○	227.76
500	×	-
1000	-	-

500は計算し過ぎでTLEでした。計算すりゃいいってもんじゃないですね。もっと計算量を意識しないと・・・
1000とか問題みて発狂。これを時間内に解けた人が6人いるのがすごい。

TopCoder Statistics: SRM 412 Problem Set & Analysis

Problem 250 TrueSpace

問題

In some filesystems, the disk space used by a file is not always equal to the file's size. This is because the disk is divided into clusters of equal size, and each cluster can only be used by a single file. For example, if the cluster size is 512 bytes, and we have a file of size 600 bytes, it would have to be stored in two clusters. Those two clusters cannot be shared with any other files, so the file ends up using 1024 bytes of disk space.
You are given a int[] sizes, where each element is the size of a single file, and an int clusterSize, the cluster size of the filesystem. Return the total disk space used by the given files.

My code

class TrueSpace {
public:
  long long calculateSpace(vector <int> sizes, int clusterSize) {
    long long result = 0;

	for(int i=0 ; i<sizes.size() ; i++){
		if(sizes[i]==0) continue;

		double tmp = ceil((double)sizes[i]/(double)clusterSize);
		result += (ll)tmp*clusterSize;
	}
    return result;
  }
};

Problem 500 BirthdayReminders

問題

You are a geek with so many geeky friends that you sometimes forget about their birthdays. So, you've decided to write a program that will remind you about such recurring events. Since your friends are geeks, they may celebrate occasions other than their actual birthdays. For example, they might celebrate whenever their age in days becomes divisible by 1000.
You are given a String friendNames and a int birthDates. Your i-th friend is named friendNames[i] and was born on birthDates[i]. All dates in this problem are non-negative integers representing the number of days that have elapsed since day 0.
The occasions celebrated by all your friends are given in the String occasions and int days. Occasion i is named occasions[i]. Each of your friends celebrates that occasion on each date b+n*day[i], where b is that friend's birth date and n is an integer greater than or equal to 1. For example, if a friend was born on day 10, and there's an occasion that is celebrated every 4 days, that friend would celebrate it on day 14, day 18, day 22, etc.
Today's date is given as an int currentDate. Your task is to generate the next k occasions that will be celebrated by your friends (starting from today). Return these occasions in a String where each element represents a single occasion formatted as "DATE. FRIEND OCCASION (NUMBER)" (quotes for clarity). Each DATE is the date of the occasion with no extra leading zeroes, FRIEND is the name of the friend, OCCASION is the name of the occasion, and NUMBER is the number of the occasion (1 is the first time the occasion has happened since that person's birth date, 2 is the second time, etc.). The String should be sorted in chronological order from earliest to latest. If multiple occasions happen on the same day, order them by occasion (occasions that appear earlier in occasions and days should be listed earlier), breaking ties by friend (friends that appear earlier in friendNames and birthDates should be listed earlier).

My code

class BirthdayReminders {
public:
  vector <string> remind(vector <string> friendNames, vector <int> birthDates, int currentDate, vector <string> occasions, vector <int> days, int k) {
	  vector<string> result;
	  result.clear();


	  set<ll> nums;
	  for(int i=0 ; i<occasions.size() ; i++){
		  for(int j=0 ; j<friendNames.size() ; j++){
			  int cc = 0;
			  ll a = (currentDate - birthDates[j])/days[i];

			  for(int k=a ; cc<100 ; k++){
				  ll tmp = birthDates[j]+days[i]*k;
				  if(tmp >= currentDate){
					  nums.insert(tmp);
					  cc++;
				  }
			  }
		  }
	  }


	  int cnt = 0;
	  ll time;
	  set<ll>::iterator it = nums.begin();

	  while(it != nums.end() ){

		  time = *it;
		  if(time < currentDate){
			  it++;
			  continue;
		  }

		  for(int i=0 ; i<occasions.size() ; i++){
			  string occasion = occasions[i];
			  int gap = days[i];

			  for(int j=0 ; j<friendNames.size() ; j++){
				  string myFriend = friendNames[j];
				  int birth = birthDates[j];

				  int tmp = time-birth;

				  if(tmp%gap==0){
					  ostringstream os;
					  os << time << ". " << myFriend << " " << occasion << " (" << tmp/gap << ")";
					  //cout << os.str() << endl;
					  result.push_back(os.str());
					  cnt++;
					  if(cnt==k) return result;
				  }
			  }
		  }
		  it++;
	  }

	  return result;
	
  }
};

Problem 1000 StringsAndTabs

問題

Tablature is a popular way of notating songs played on fretted string instruments. Each line represents a string, and numbers written on the lines tell you which frets to press down when playing those strings. Here is an example:

-

3----------

0----

2--------

0----

-

The top line is the first string, the line below that is the second string, and so on. Tablature is read from left to right, and the i-th column represents the notes played at time i. In this example, there are no numbers in column 0, so this means that nothing is played at time 0. At time 1, a note is played by holding down the 3rd fret of the second string and plucking that string. At time 3, a note is played on the 2nd fret of the fourth string. Finally, at time 7, there are two notes played simultaneously as a chord. The number 0 means that you should pluck a string without holding down a fret. This is called an open string. In this example, you play the open third and fifth strings simultaneously.
Each open string may have a different pitch (i.e. may produce a higher or lower sound). For example, in standard guitar tuning, the pitch of the first string is 5 semitones higher than the second string. When you hold down the n-th fret (where 1 is the first fret) while playing a string, the resulting pitch is n semitones higher than that open string's pitch.
You are given a String tab containing the tablature for a song played on some instrument A (a guitar, for example). However, you want to play it on a different instrument B (maybe a mandolin, for example). You know the pitches of the open strings on each instrument, and they are given in the ints stringsA and stringsB. The i-th element of each int represents the pitch of the i-th string, and is given as the number of semitones above some base pitch 0. Both instrument A and instrument B have 35 frets. Frets numbered 10 through 35 are represented by the uppercase letters 'A' to 'Z'.
Your task is to write a program that will automatically transform the original tablature so it can be played on instrument B. Since different instruments have different ranges, you may also want to transpose the song to a different key. For this, you are given an int d, and you must increase the pitch of every note by d semitones (d can be negative, so you may end up lowering the pitches). Note that it is possible for different strings to play the same exact pitch at the same time in the original song. When that happens, the transformed tablature must also play that sound the same number of times as in the original version.
Sometimes there will be multiple ways to play a note on instrument B. In such cases, choose the string with the highest open pitch that can play that note. If there are multiple such strings, choose the bottom-most one among them (strings are listed from top to bottom). For chords, apply that same rule to each individual note in the chord. You must assign the notes in order, starting with the note that has the highest pitch, then the note with the second-highest pitch, and so on. You can only play a single note on each string, so only consider unused strings when assigning the notes of a chord. If you are unable to find a valid way to play a note or chord on instrument B using these rules, fill the entire column with lowercase 'x' characters instead. Return a String containing the transformed tablature for instrument B.