[USAO training题]Combination Lock

2024-02-17 04:30
文章标签 lock training combination usao

本文主要是介绍[USAO training题]Combination Lock,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Combination Lockicon-default.png?t=M4ADhttps://train.usaco.org/usacoprob2?a=bWHoWMsO5Pi&S=combo

农夫约翰的奶牛不停地从他的农场中逃出来,导致了很多损害。为了防止它们再逃出来,他买了一只很大的号码锁以防止奶牛们打开牧场的门。

    农夫约翰知道他的奶牛很聪明,所以他希望确保它们不会在简单地试了很多不同的号码组合之后就能轻易开锁。锁上有三个转盘,每个上面有数字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)不同。

INPUT FORMAT

第一行:整数N。

第二行:三个以空格分隔的整数,为农夫约翰的号码组合。

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

SAMPLE INPUT (file comb.in)
50

1 2 3

4 5 6

OUTPUT FORMAT

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

SAMPLE OUTPUT (file comb.out)

249

(翻译转载自https://blog.csdn.net/finded/article/details/39999241)

这道题思路其实非常简单:

先找出两个密码各个位数上的有效数字:在1——n中找到可以和当前数字有效匹配的5个数字(n-2,n-1,n,n+1,n+2)要注意,如果数字是n,n-1,或者1,2的情况要另外判断。

#include<bits/stdc++.h>
using namespace std;
int n;
int a1,a2,a3,b1,b2,b3;
int a11[5],a22[5],a33[5],b11[5],b22[5],b33[5];//每一位数字都给一个相应的数组范围存储有效数字
void range(int q[5],int num)
{if(num==1)//如果数字为1{q[0]=n-1;q[1]=n;q[2]=2;q[3]=3;q[4]=num;}else if(num==2)//如果数字为2{q[0]=n;q[1]=1;q[2]=3;q[3]=4;q[4]=num;}else if(num==n)//如果数字为n{q[0]=n-1;q[1]=n-2;q[2]=1;q[3]=2;q[4]=num;}else if(num==n-1)//如果数字为n-1{q[0]=n-2;q[1]=n-3;q[2]=n;q[3]=1;q[4]=num;}else//正常计算{q[0]=num-2;q[1]=num-1;q[2]=num+1;q[3]=num+2;q[4]=num;}
}

在每一个数字的有效数字都确定好之后,先遍历在1——n数字的所有可能。

int main()
{freopen("combo.in","r",stdin);freopen("combo.out","w",stdout);cin>>n>>a1>>a2>>a3>>b1>>b2>>b3;range(a11,a1);range(a22,a2);range(a33,a3);range(b11,b1);range(b22,b2);range(b33,b3);int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){if(check1(i,j,k)||check2(i,j,k)){ans++;}}}}cout<<ans<<endl;return 0;
}

分别判断和两个密码的匹配情况。只要有一种匹配上了,那这个密码就是一个有效密码,ans+1.

两个判断代码十分简单,如下:

int check1(int i,int j,int k)
{for(int z=0;z<5;z++){if(i==a11[z]){break;}if(z==4){return 0;}}for(int z=0;z<5;z++){if(j==a22[z]){break;}if(z==4){return 0;}}for(int z=0;z<5;z++){if(k==a33[z]){break;}if(z==4){return 0;}}return 1;
}
int check2(int i,int j,int k)
{for(int z=0;z<5;z++){if(i==b11[z]){break;}if(z==4){return 0;}}for(int z=0;z<5;z++){if(j==b22[z]){break;}if(z==4){return 0;}}for(int z=0;z<5;z++){if(k==b33[z]){break;}if(z==4){return 0;}}return 1;
}

最后放上全代码,记得点个赞捏╮( ̄▽ ̄)╭

(文件名为combo,记得看题目描述)

/*
ID:s.randy1
PROG:combo
LANG:C++
*/
#include<bits/stdc++.h>
using namespace std;
int n;
int a1,a2,a3,b1,b2,b3;
int a11[5],a22[5],a33[5],b11[5],b22[5],b33[5];//每一位数字都给一个相应的数组范围存储有效数字
void range(int q[5],int num)
{if(num==1)//如果数字为1{q[0]=n-1;q[1]=n;q[2]=2;q[3]=3;q[4]=num;}else if(num==2)//如果数字为2{q[0]=n;q[1]=1;q[2]=3;q[3]=4;q[4]=num;}else if(num==n)//如果数字为n{q[0]=n-1;q[1]=n-2;q[2]=1;q[3]=2;q[4]=num;}else if(num==n-1)//如果数字为n-1{q[0]=n-2;q[1]=n-3;q[2]=n;q[3]=1;q[4]=num;}else//正常计算{q[0]=num-2;q[1]=num-1;q[2]=num+1;q[3]=num+2;q[4]=num;}
}
int check1(int i,int j,int k)
{for(int z=0;z<5;z++){if(i==a11[z]){break;}if(z==4){return 0;}}for(int z=0;z<5;z++){if(j==a22[z]){break;}if(z==4){return 0;}}for(int z=0;z<5;z++){if(k==a33[z]){break;}if(z==4){return 0;}}return 1;
}
int check2(int i,int j,int k)
{for(int z=0;z<5;z++){if(i==b11[z]){break;}if(z==4){return 0;}}for(int z=0;z<5;z++){if(j==b22[z]){break;}if(z==4){return 0;}}for(int z=0;z<5;z++){if(k==b33[z]){break;}if(z==4){return 0;}}return 1;
}
int main()
{freopen("combo.in","r",stdin);freopen("combo.out","w",stdout);cin>>n>>a1>>a2>>a3>>b1>>b2>>b3;range(a11,a1);range(a22,a2);range(a33,a3);range(b11,b1);range(b22,b2);range(b33,b3);int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){if(check1(i,j,k)||check2(i,j,k)){ans++;}}}}cout<<ans<<endl;return 0;
}

这篇关于[USAO training题]Combination Lock的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/716672

相关文章

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

Post-Training有多重要?一文带你了解全部细节

1. 简介 随着LLM学界和工业界日新月异的发展,不仅预训练所用的算力和数据正在疯狂内卷,后训练(post-training)的对齐和微调方法也在不断更新。InstructGPT、WebGPT等较早发布的模型使用标准RLHF方法,其中的数据管理风格和规模似乎已经过时。近来,Meta、谷歌和英伟达等AI巨头纷纷发布开源模型,附带发布详尽的论文或报告,包括Llama 3.1、Nemotron 340

【硬刚Java并发】JUC基础(六):Lock 同步锁

本文是对《【硬刚大数据之学习路线篇】从零到大数据专家的学习指南(全面升级版)》的Java并发部分补充。 显示锁 Lock 在 Java 5.0 之前,协调共享对象的访问时可以使用的机制只有 synchronized 和 volatile 。Java 5.0 后增加了一些新的机制,但并不是一种替代内置锁的方法,而是当内置锁不适用时,作为一种可选择的高级功能。 ReentrantLock 实

解决 The sandbox is not sync with the Podfile.lock问题

问题描述: github / sourcetree下载的Demo,很多时候使用到CocoaPods,有的时候因为依赖关系或者版本问题不能编译运行。出现例如The sandbox is not sync with the Podfile.lock问题时候,如下所示 diff: /../Podfile.lock: No such file or directory diff: Manifest.l

【PostgreSQL教程】PostgreSQL 高级篇之 LOCK(锁)

博主介绍:✌全网粉丝20W+,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物联网、机器学习等设计与开发。 感兴趣的可以先关注收藏起来,在工作中、生活上等遇到相关问题都可以给我

在 python3 中使用 multiprocessing,加上锁,却发现锁没用,怎么办?Lock 多进程 多线程 锁 LOCK lock

multiprocessing 是多进程库,而不同进程之间的全局变量是不共享的,所以,这也是为什么当你对 python3 全局变量加上锁的时候会失效。 正确处理方式如下: 使用 multiprocessing.Value 和 multiprocessing.Array 来共享数据,可以使进程池中的所有进程能够正确访问和修改共享数据。 代码如下 import multiprocessing#

java线程 yield,sleep,join,synchronized wait notify notifyAll,ReentrantLock lock condition, 生产者消费者

yield,sleep,join yield,join,sleep,join是Thread中的方法,不需要 在synchronized 代码块中调用,和synchronized 没关系,也不会释放锁。 Thread.sleep(100);Thread.yield();Thread t;t.join(); (1)yield()不一定保证让出cpu yield()只是使当前线程重新回

mysql Deadlock found when trying to get lock; try restarting transaction

一、现场情况 sql:insert into a ...... 数据库隔离级别:read-committed 表a有唯一索引 二、死锁发生的4个必要条件 1、互斥条件(Mutual Exclusion):资源独享 2、占有并等待条件(Hold and Wait):占有资源并等待其他资源 3、非抢占条件(No Preemption):占有的资源不可以被剥夺,只能主动释放 4、循环等待