USACO Combination Lock

lzusa 发布于 2019-04-09 2 次阅读


题目描述

农夫约翰的奶牛不停地从他的农场中逃出来,导致了很多损害。为了防止它们再逃出来,他买了一只很大的号码锁以防止奶牛们打开牧场的门。
农夫约翰知道他的奶牛很聪明,所以他希望确保它们不会在简单地试了很多不同的号码组合之后就能轻易开锁。锁上有三个转盘,每个上面有数字1..N (1 <= N <= 100),因为转盘是圆的,所以1和N是相邻的。有两种能开锁的号码组合,一种是农夫约翰设定的,还有一种“预设”号码组合是锁匠设定的。但是,锁有一定的容错性,所以,在每个转盘上的数字都与一个合法的号码组合中相应的数字相距两个位置以内时,锁也会打开。
比如说,如果农夫约翰的号码组合是(1,2,3),预设号码组合是(4,5,6),在转盘被设定为(1,N,5)(因为这和农夫约翰的号码组合足够接近)或(2,4,8)(因为这和预设号码组合足够接近)。注意,(1,5,6)并不会打开锁,因为它与任一号码组合都不够接近。
给出农夫约翰的号码组合和预设号码组合,请计算能够开锁的不同的号码组合的数目。号码是有序的,所以(1,2,3)与(3,2,1)不同。

输入

第一行:整数N。
第二行:三个以空格分隔的整数,为农夫约翰的号码组合。
第三行:三个以空格分隔的整数,为预设号码组合(可能与农夫约翰的号码组合相同)。

输出

第一行:所有不同的能够开锁的号码组合的总数。

思路

用一个三维数组来记录当前数有没有被找过然后暴力枚举每一个数判断就可以了

/*
 ID: a1192631
 PROG: combo
 LANG: C++
*/
#include 
#include 
//using namespace std;
int c[101][101][101];
int a[4][3];
int n,m,ans,x,y;
int find(int x,int y)
{
    if (abs(y-x)<=2) return 1;
    if (abs(y-x)>=n-2) return 1;
    return 0;
}
int main()
{
    freopen("combo.in","r",stdin);
    freopen("combo.out","w",stdout);
    scanf("%d",&n);
    scanf("%d%d%d%d%d%d",&a[1][1],&a[2][1],&a[3][1],&a[1][2],&a[2][2],&a[3][2]);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            for (int k=1;k<=n;k++)
            {
                if ((c[i][j][k]==0&&find(i,a[1][1])==1&&find(j,a[2][1])==1&&find(k,a[3][1])==1)||(c[i][j][k]==0&&find(i,a[1][2])==1&&find(j,a[2][2])==1&&find(k,a[3][2])==1))
                    ans++;
            }
    printf("%d\n",ans);
    return 0;
}


]]>