Блог пользователя SummerSky

Автор SummerSky, 7 лет назад, По-английски

A. A Student's Dream

We use Gn and Bn to denote the number of fingers of hands, which the girl and boy hold, respectively. According to the problem, Bn>=Gn-1 should hold, since otherwise at least two fingers of the girl will touch. Moreover, Bn<=2*(Gn+1) should hold as well, since otherwise at least three fingers of the boy will touch.

B. Tyndex.Brome

We first deal with the address entered by the user. As only lowercase letters are involved, we can adopt 26 arrays and use each of them to store all the positions at which the corresponding letter has appeared in the entered address, and sort the positions in an increasing order. Then, we calculate the value of the error function for each potential address. As the problem requires, for each letter at position j in some potential address, we try to find the closest position at which the same letter appears in the entered address. To find this, we can implement index-based binary search on the previously stored array H[n], and find the position i such that H[i]=<j<H[i+1]. Thus, min(j-H[i],H[i+1]-j) is just the value of error function for the current letter.

In fact, I find it more difficult than I thought to write a correct index-based binary search... Therefore, I give some of the details that I think are quite important.

Suppose that a[0],a[1],...,a[n-1] have been sorted in an increasing order, and T is the "target". The following index-based binary search will find the largest a[num_L] such that a[num_L]<=T<a[num_L+1] (assuming that num_L+1 is reasonable, i.e., num_L+1<=n-1). The comments have been added in the corresponding places.

int num_L=0;  // num_L denotes the left border, and one should guarantee that a[0]<=T, which can be tested in advance;  if a[0]>T, it is even not necessary to implement such a binary search;
int num_R=n-1; // num_R denotes the right border, and one should guarantee that it is initialized so that the whole range can be covered
while (num_L<num_R)  // note that the termination condition is num_L<num_R but not num_L<=num_R, while the latter one might lead to an infinite loop
{
	int num_M=(num_L+num_R+1)/2;  // num_M denotes the middle point which we are going to check, and note that using (num_L+num_R)/2 might lead to an infinite loop as well
	if (a[num_M]>T)  // this is not a[num_M]>=T, since we are to find a[num_L]<=T rather than a[num_L]<T
	{
		num_R=num_M-1;  // update the right border as num_M-1 for the next loop; note that here is not num_R=num_M, since num_M has been checked and it can definitely not satisfy a[num_M]<=T in the current loop
	}
	else
	{
		num_L=num_M;  //update the left border as num_M for the next loop; note that this is not num_M+1, since we can only guarantee that num_M is safe for the next loop as a[num_M]<=T holds in the current loop
	}
}

One can check that, when the loop terminates, num_L will always satisfy that a[num_L]<=T<a[num_L+1].

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится