2014
02-24

# Hidden Music Score

Do you like music? Let’s play a game. I wrote down some notes on a piece of staff paper, then erase every other thing and leave only the notes. Can you guess what I wrote?

Fig 1. Names of Notes

If you’re not familiar with music, take a look at the picture above. The vertical position of a note determines its name,
which is one of C, D, E, F, G, A and B, in this problem (yes, you don’t have to consider notes in other octaves).
Consecutive lines in the staff have the same vertical distances. We call it one standard distance (sd), which is always between 1.0 and 5.0. For example, C and E are 1sd apart, and D and B are 2.5sd. The horizontal order of the notes
determines how the sequence is played (or sung). The exact horizontal positions do not matter, as long as the relative order is preserved. But since I never write down ugly scores, you can safely assume that the horizontal distance of an arbitrary pair of neighboring notes is at least 1sd and at most 5sd.

(a) Everything                                         (b) The Notes                                (c) Note positions only

Fig 2. Transforming the original score into a hidden form

Figure 2(a) corresponds to the sequence EEECEG. Figure 2(b) shows the notes when other stuffs have been erased. Then, I rotate the paper and tell you the positions of the notes, shown in figure 2(c). Write a program to find my original music score, given the rotated positions of the notes. To make your life a little bit easier, I can tell you the name of the first and last note, and I promise that the answer could be uniquely determined. The rotation angle is an integer between -60 and 60 degrees (inclusive).

The input consists of several test cases. The first line of each case contains one integer n (3 ≤ n ≤ 20) and two different capital letters from ‘A’ to ‘G’. This is followed by n lines each containing two real numbers to eight decimal places, the rotated positions of each note. The notes can appear in any order. All the real numbers have absolute values not greater than 1000. The last test case is followed by a single zero, which should not be processed.

The input consists of several test cases. The first line of each case contains one integer n (3 ≤ n ≤ 20) and two different capital letters from ‘A’ to ‘G’. This is followed by n lines each containing two real numbers to eight decimal places, the rotated positions of each note. The notes can appear in any order. All the real numbers have absolute values not greater than 1000. The last test case is followed by a single zero, which should not be processed.

6 E G
0.00000000 1.00000000
1.00000000 1.00000000
2.00000000 1.00000000
4.00000000 0.00000000
5.00000000 1.00000000
8.00000000 2.00000000
4 A C
0.00000000 15.62499286
11.28111236 5.80618831
20.63744497 6.54957842
37.94846083 0.00000000
7 B F
0.00000000 0.00000000
15.14798698 18.22443643
25.04608611 30.65582149
19.58478851 24.56084570
23.09216832 27.86533768
11.29672536 9.31513384
8.65999632 3.84492903
0

Case 1: EEECEG
Case 3: BDEGGFF

#include <stdio.h>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

struct P
{
double x,y;
}c[25],d[25];
int ans[25];

bool operator<(P a,P b)
{
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}

int ctd[255];

int main()
{
int n;
int T=0;
//printf("%d ",int(-.2));
char a,b;
double pi=acos(-1.0);
double eps=1e-7;
ctd['C']=0,ctd['D']=1,ctd['E']=2;
ctd['F']=3,ctd['G']=4,ctd['A']=5;
ctd['B']=6;
char dtc[10];
dtc[0]='C',dtc[1]='D',dtc[2]='E';
dtc[3]='F',dtc[4]='G',dtc[5]='A';
dtc[6]='B';

while(scanf("%d",&n),n)
{

scanf(" %c %c",&a,&b);
int i,j;
for(i=0;i<n;i++)
scanf("%lf %lf",&c[i].x,&c[i].y);

for(double i=-60.0;i<61.0;i+=0.005)
{
double ang;
ang=i*pi/180.0;
for(j=0;j<n;j++)
{
d[j].x=c[j].x*cos(ang)+c[j].y*sin(ang);
d[j].y=-c[j].x*sin(ang)+c[j].y*cos(ang);
}
sort(d,d+n);

double sd=(d[n-1].y-d[0].y)/(ctd[b]-ctd[a]);
//	if(sd<0)sd=-sd;
double ssd=sd*2;
//	printf("%lf\n ",sd);
if(ssd+eps<1.0 || ssd>5.0+eps)
continue;
ans[0]=ctd[a];

for(j=1;j<n;j++)
{
if(d[j].x-d[j-1].x>5*ssd+eps || d[j].x-d[j-1].x+eps<ssd)
break;
if(d[j].y-d[j-1].y>(6-ans[j-1])*sd+eps)
break;
if(d[j-1].y-d[j].y>ans[j-1]*sd+eps)
break;
double dis=d[j].y-d[j-1].y;
int tmp=(int)(dis/sd);
//	if(tmp*sd<dis)
//			tmp++;
//	printf("%d ",tmp);
if(dis>=0)
{
if(tmp*sd-dis+eps<0)
tmp++;
if(tmp*sd-dis>0+eps)
break;
}
else
{
if(tmp*sd-dis>0+eps)
tmp--;
if(tmp*sd-dis+eps<0)
break;
}
ans[j]=tmp+ans[j-1];
}
//	printf("\n");
if(j==n)
{//printf(" %lf\n",sd);
break;
}
}

printf("Case %d: ",++T);
for(i=0;i<n;i++)
{
//printf("%lf %lf ",d[i].x,d[i].y);
printf("%c",dtc[ans[i]]);
}
printf("\n");
}
return 0;
}

1. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮