USACO training 密码锁
环形距离求解:
两个数之间的距离有两种可能
1. 直线距离(如30和20之间距离为10),取两个数差的绝对值
2. 圆盘上的环形距离(如49与1的距离为2而不是48)
取两个数的最大值,用n减去,最后再加上两个数的最小值。(如1,49,就是50-49+1=2)
使用两种方法之间取距离最小值
int both( ) {
int res = 1;
for ( int i = 0; i < 3; i++ ) {
int x = a[i], y = b[i];
// 求环形距离
int d = min( abs(x-y) , n - abs(x - y) );
res *= min( n, max(0, 5 - d));
}
return res;
}
int single() {
int res = 1;
for ( int i = 0; i < 3; i++ ) res *= min(n, 5); // 环形距离使用
return res;
}
int main( ) {
scanf("%d", &n);
for( int i = 0; i < 3; i++ ) cin >> a[i];
for ( int i = 0; i < 3; i++ ) cin >> b[i];
cout << single() + single() - both() << endl; // 容斥原理
return 0;
}