18 Wheeler Caravans (aka Semigroups)

A binary operation on a set S is a function that assigns to each ordered pair of elements of S a unique element of S. We often use some special symbol (such as * or +) to represent a binary operation. For example, if we use the symbol '#' to represent some arbitrary binary operation on the set S = {a, b, c}, then a#b equals some element of S (as does b#a, a#a, a#c, and every other possible permutation).
From the above definition, it would follow that the normal definitions for addition, subtraction, and multiplication are all binary operations when defined on the set of all integers. However, division (the mathematical kind - not "integer division") is not a binary operation for the set of integers, since 1=2 = 0.5 which is not an integer.

The use of the word "ordered" in the definition for binary operations is important, for it allows the possibility that the element assigned to a#b may be different from the one assigned to b#a. In the case of integers, this is evident with the binary operation we know as subtraction, since 5 - 3 is not equal to 3 - 5. If in a particular case, x # y = y # x for all elements x and y in the set, we say that the binary operation is commutative. The standard addition operation on the set of integers is commutative.

For the remainder of this problem we will only concern ourselves with small sets (1 to 26 elements). For small sets such as these, the unique assignments that define an operation can be expressed by simply writing down all possible assignments in a "multiplication" table. For instance, the binary operation '#' on the set S = {a, b, c} might be defined by:

| a b c


a | b c b
b | a c b
c | c b a

The left column of the table represents the first number in an ordered pair, and the top row represents the second. Thus, in this example, a # b = c, b # a = a, and c # c = a. Notice that the body of the table consists solely of elements from the set S, which must be true for any binary operation. Also notice that this operation is not commutative, since b # a is not equal to a # b.

A binary operation, #, on a set S is associative if (x#y)#z = x#(y#z) for all elements x, y, and z in the set X. In the example with the table above, the operation is not associative, since (a#b)#c is not equal to a#(b#c). If a binary operation, #, on a set is associative, then we say that the pair forms a semigroup. If the binary operation is commutative as well as associative, then we say that the semigroup is commutative.

Input

Write a program that will read the elements of sets together with corresponding "multiplication" tables which denote possible binary operations. Your program should then determine if the set S with the defined operation constitutes a semigroup. If the set and corresponding table do not form a semigroup, your program should report that the pair do not form a semigroup and state why. If the set and operation pair do form a semigroup, your program should check to see if the semigroup is also a commutative semigroup.

Thus, for each set and corresponding table one of the following four results is possible:

NOT A SEMIGROUP: x#y = z WHICH IS NOT AN ELEMENT OF THE SET
NOT A SEMIGROUP: (x#y)#z IS NOT EQUAL TO x#(y#z)
SEMIGROUP BUT NOT COMMUTATIVE (x#y IS NOT EQUAL TO y#x)
COMMUTATIVE SEMIGROUP

In the first three results you should substitute actual elements of the set that yield a counter-example to the definitions for a semigroup and a commutative operation. If more than one counter-example exist, choose the lexicographically first one.

The first line of the input file contains a single integer, n where (1 <= n <= 26).

The next line of the input file will contain n unique, lower case letters of the alphabet. These letters represent the elements of the set. Although each letter is unique (no duplicates), they are not necessarily arranged in alphabetical order.

The next n lines contain the body of the "multiplication" table that corresponds to the elements in the previous line. Each of these lines will contain n lower case letters. For example, the first such line corresponds to the first row of the body of the table. We will assume that the ordering of the rows and columns of the table coincide with the ordering in the line that defines the elements of the set.

After the table, the input file will contain a line with a single integer, n where (0 <= n <= 26). If n > 0 then there is another set and corresponding table contained in the next n + 1 lines that should be reported. If n = 0 then you have reached the end of the input file.

Output

The output file should contain the following for each set and table found in the input file:

  1. List of the elements of S in same order as found in the input file using the following format: S = {a,b,c,d}

  2. A line that starts with a space followed by the characters '#|' followed by the n elements of the set (no spaces or commas). For example: #|abcd

  3. A line that begins with a space followed by the characters '-+' followed by n more dashes '-'. For example: -+----

  4. List of the n rows and columns of the "multiplication" table in the same order as found in the input file. The ith line of the table should begin with a space followed by the ith element of the set followed by the '|' character followed by the n characters in the ith row of the body of the table (no spaces). For example: a|abcd

  5. One blank line.

  6. One line that reports what your program found to be true. This must be one of the four possible results listed above.

  7. A line of 30 dashes.

  8. One blank line to separate this report from subsequent reports.

Sample Input

3
abc
abc
bca
cab
3
abc
abc
bca
cad
4
acdb
aaaa
aaca
aada
aaab
5
abcde
aaaaa
bbabb
cccbc
ddddd
eeeee
0

Sample Output

S = {a,b,c}
#|abc
-+---
a|abc
b|bca
c|cab

COMMUTATIVE SEMIGROUP

S = {a,b,c}
#|abc
-+---
a|abc
b|bca
c|cad

NOT A SEMIGROUP: c#c = d WHICH IS NOT AN ELEMENT OF THE SET

S = {a,c,d,b}
#|acdb
-+----
a|aaaa
c|aaca
d|aada
b|aaab

SEMIGROUP BUT NOT COMMUTATIVE (c#d IS NOT EQUAL TO d#c)

S = {a,b,c,d,e}
#|abcde
-+-----
a|aaaaa
b|bbabb
c|cccbc
d|ddddd
e|eeeee

NOT A SEMIGROUP: (b#a)#c IS NOT EQUAL TO b#(a#c)

0

查看全部1条回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
18 Wheeler Caravans (aka Semigroups)
A binary operation on a set S is a function that assigns to each ordered pair of elements of S a unique element of S. We often use some special symbol (such as * or +) to represent a binary operation. For example, if we use the symbol '#' to represent some arbitrary binary operation on the set S = a, b, c, then a#b equals some element of S (as does b#a, a#a, a#c, and every other possible permutation).nFrom the above definition, it would follow that the normal definitions for addition, subtraction, and multiplication are all binary operations when defined on the set of all integers. However, division (the mathematical kind - not "integer division") is not a binary operation for the set of integers, since 1=2 = 0.5 which is not an integer.nnThe use of the word "ordered" in the definition for binary operations is important, for it allows the possibility that the element assigned to a#b may be different from the one assigned to b#a. In the case of integers, this is evident with the binary operation we know as subtraction, since 5 - 3 is not equal to 3 - 5. If in a particular case, x # y = y # x for all elements x and y in the set, we say that the binary operation is commutative. The standard addition operation on the set of integers is commutative.nnFor the remainder of this problem we will only concern ourselves with small sets (1 to 26 elements). For small sets such as these, the unique assignments that define an operation can be expressed by simply writing down all possible assignments in a "multiplication" table. For instance, the binary operation '#' on the set S = a, b, c might be defined by:nn# | a b cn---------na | b c bnb | a c bnc | c b annThe left column of the table represents the first number in an ordered pair, and the top row represents the second. Thus, in this example, a # b = c, b # a = a, and c # c = a. Notice that the body of the table consists solely of elements from the set S, which must be true for any binary operation. Also notice that this operation is not commutative, since b # a is not equal to a # b.nnA binary operation, #, on a set S is associative if (x#y)#z = x#(y#z) for all elements x, y, and z in the set X. In the example with the table above, the operation is not associative, since (a#b)#c is not equal to a#(b#c). If a binary operation, #, on a set is associative, then we say that the pair forms a semigroup. If the binary operation is commutative as well as associative, then we say that the semigroup is commutative.nnnInputnnWrite a program that will read the elements of sets together with corresponding "multiplication" tables which denote possible binary operations. Your program should then determine if the set S with the defined operation constitutes a semigroup. If the set and corresponding table do not form a semigroup, your program should report that the pair do not form a semigroup and state why. If the set and operation pair do form a semigroup, your program should check to see if the semigroup is also a commutative semigroup.nnThus, for each set and corresponding table one of the following four results is possible:nnNOT A SEMIGROUP: x#y = z WHICH IS NOT AN ELEMENT OF THE SETnNOT A SEMIGROUP: (x#y)#z IS NOT EQUAL TO x#(y#z)nSEMIGROUP BUT NOT COMMUTATIVE (x#y IS NOT EQUAL TO y#x)nCOMMUTATIVE SEMIGROUPnnIn the first three results you should substitute actual elements of the set that yield a counter-example to the definitions for a semigroup and a commutative operation. If more than one counter-example exist, choose the lexicographically first one.nnThe first line of the input file contains a single integer, n where (1 <= n <= 26).nnThe next line of the input file will contain n unique, lower case letters of the alphabet. These letters represent the elements of the set. Although each letter is unique (no duplicates), they are not necessarily arranged in alphabetical order.nnThe next n lines contain the body of the "multiplication" table that corresponds to the elements in the previous line. Each of these lines will contain n lower case letters. For example, the first such line corresponds to the first row of the body of the table. We will assume that the ordering of the rows and columns of the table coincide with the ordering in the line that defines the elements of the set.nnAfter the table, the input file will contain a line with a single integer, n where (0 <= n <= 26). If n > 0 then there is another set and corresponding table contained in the next n + 1 lines that should be reported. If n = 0 then you have reached the end of the input file.nnnOutputnnThe output file should contain the following for each set and table found in the input file:nn1. List of the elements of S in same order as found in the input file using the following format: S = a,b,c,dnn2. A line that starts with a space followed by the characters '#|' followed by the n elements of the set (no spaces or commas). For example: #|abcdnn3. A line that begins with a space followed by the characters '-+' followed by n more dashes '-'. For example: -+----nn4. List of the n rows and columns of the "multiplication" table in the same order as found in the input file. The ith line of the table should begin with a space followed by the ith element of the set followed by the '|' character followed by the n characters in the ith row of the body of the table (no spaces). For example: a|abcdnn5. One blank line.nn6. One line that reports what your program found to be true. This must be one of the four possible results listed above.nn7. A line of 30 dashes.nn8. One blank line to separate this report from subsequent reports.nnnSample Inputnn3nabcnabcnbcancabn3nabcnabcnbcancadn4nacdbnaaaanaacanaadanaaabn5nabcdenaaaaanbbabbncccbcndddddneeeeen0nnnSample OutputnnS = a,b,cn #|abc n -+---n a|abcn b|bcan c|cabnnCOMMUTATIVE SEMIGROUPn------------------------------nnS = a,b,cn #|abcn -+---n a|abcn b|bcan c|cadnnNOT A SEMIGROUP: c#c = d WHICH IS NOT AN ELEMENT OF THE SETn------------------------------nnS = a,c,d,bn #|acdbn -+----n a|aaaan c|aacan d|aadan b|aaabnnSEMIGROUP BUT NOT COMMUTATIVE (c#d IS NOT EQUAL TO d#c)n------------------------------nnS = a,b,c,d,en #|abcde n -+-----n a|aaaaa n b|bbabb n c|cccbc n d|ddddd n e|eeeee nnNOT A SEMIGROUP: (b#a)#c IS NOT EQUAL TO b#(a#c)n------------------------------
Gravitation-Misner Thorne Wheeler
Gravitation-Misner Thorne Wheeler Gravitation-Misner Thorne Wheeler Gravitation-Misner Thorne Wheeler
A sequence of Problems on semigroups
A sequence of Problems on semigroups
替换OpenSSL Engine加密之替换EVP_CIPHER结构
http://www.cnblogs.com/crunchyou/archive/2013/01/19/2867735.html
AKA鉴权
 AKA鉴权 目前IMS的鉴权的机制有“Sip Digest”、“AKA”、“CAVE-based AKA”三种。   在《中国电信IMS网络SIP协议总体技术要求》里对这三种方式的适用范围描述如下: SIP Digest 鉴权适用于无 ISIM 卡的移动和固定终端 AKA 鉴权适用于具有 ISIM 卡的移动和固定终端
AKA认证初探
       近期工作中遇到了有关SIP AKA认证的相应协议规范,目前在IMS中已得到应用支持,本文主要是希望探索一下AKA认证的具体机制,以及相应算法。为简便起见,暂时先抛开IMS内部架构,从参数着手分析AKA认证。        AKA认证主要还是基于DIGEST认证方式,在此基础上加入了对称加密机制。先简单看一下AKA的流程图与信令:     如图所示,AKA认证流程与DIGEST...
基于AKA的IMS接入认证机制
基于AKA的IMS接入认证机制IP多媒体子系统(IMS)作为3G网络的核心控制平台,其安全问题正面临着严峻的挑战。IMS的接入认证机制的实现作为整个IMS安全方案实施的第一步,是保证IMS系统安全的关键。基于认证和密钥协商(AKA)的IMS接入认证机制是由因特网工程任务组(IETF)制定,并被3GPP采用,广泛应用于3G无线网络的鉴权机制。此机制基于“提问/回答”模式实现对用户的认证和会话密钥
For AKA Security Salon
For AKA Security SalonFor AKA Security Salon
EAP-SIM/AKA学习资料(包括EAP-SIM白皮书,EAP-SIM测试手册等)
这是一份很好的EAP-SIM学习资料,里面包括了EAP-SIM/AKA白皮书和两份EAP-SIM/AKA测试手册。希望对大家初学EAP-SIM能够起到帮助作用!
Xcode警告、错误解决方法总结
从sdk3.2.5升级到sdk 7.1中间废弃了很多的方法,还有一些逻辑关系更加严谨了。 1,警告:“xoxoxoxo”  is deprecated 解决办法:查看xoxoxoxo的这个方法的文档,替换掉这个方法即可。 2,警告:Declaration of "struct sockaddr" will not be visible outside of this functi
IMS AKA鉴权及应用流程详解
IMS AKA鉴权及应用流程详解@auth doubleRabbit @date 2017-03-14目的 了解鉴权及通信类业务相关鉴权算法的概念原理 了解IMS注册流程 了解IMS鉴权流程应用 鉴权含义鉴权是指用户访问系统的权利,是提升系统安全性的一种方式,传统鉴权方法就是用户名与密码。 鉴权与授权的区别联系。逻辑上授权过程发生在鉴权之后,而实际中有时鉴权与授权对于用户来说体现为同一过程。例如
C与C++混编所遇到的问题
今天团队成员做了一个PID算法
5G系统——5G鉴权(5G AKA)
缩略语 5GC    5G Core Network 5G-AN    5G Access Network 5G-RAN    5G Radio Access Network  5G AV    5G Authentication Vector 5G HE AV    5G Home Environment Authentication Vector AES    Advanced Encryp...
burrow wheeler transformation
burrow wheeler transformation, algorithm in sequence matching
CGFloat和float的区别及案例分析
CGFloat和float的区别及案例分析 在32位下,CGFloat定义为float; 在64位下,CGFloat定义为double typedef float CGFloat;// 32-bit   typedef double CGFloat;// 64-bit   编程策略: 对于需要兼容64位机器的程序而言,所有使用float的地方都改为用CGFloat。 长远角度考
【通用引导架构】基于GBA的AKA认证机制
基于GBA(Generic Bootstrapping Architecture)的AKA认证机制 本课题提出的物联网安全框架中,众多的业务采用的是集中认证的方式。所以需要采用相同的鉴权机制。同一种机制也可以解决不同机制造成的兼容问题。所以定义了通用认证架构(GAA)。GAA分为基于共享密钥的GBA和基于公钥证书的SSC。而SSC基于非对称加密,需要更多的计算量处理PKI的公钥私钥问题,当物联网...
AndroidStudio之NDK常见编译错误
1、执行ndk-build 提示error: request for member 'FindClass' in something not a structure or union /Users/lvxiangan/Workspace/Android_Studio/NDK/app/src/main/jni/test.c:33:30: error: member reference base ty...
使用@mipmap/ic_launcher编译报错解决方案
原文链接:http://www.apkfuns.com/error16-9-attribute-applicationicon-valuemipmapic_launcher-from-androidmanifest-xml169.html Error:(16, 9) Attribute application@icon value=(@mipmap/ic_launcher) from And
IOS开发各种疑难 二
1、 Implicit conversion of 'BOOL' (aka 'signed char') to 'id' is disallowed with ARC 解决: [NSNumber numberWithBool:value]
Gcc编译出错处理--openssl 依赖问题
出错信息:error: dereferencing pointer to incomplete type 'RSA {aka struct rsa_st}' 原因:由于默认使用了openssl 1.1.x 版本,导致的API不一致引起 解决: 1,直接安装openssl1.0版本,Debian 系:apt-get install libssl1.0-dev 2,编译openssl 1.0
EAP-AKA认证算法源程序(基于SHA-1)
基于SHA-1的AKA算法实现:源程序代码(ANSI-C编写) 本算法详细描述参见:3GPP2: S.S0055-A_v2.0_050120.pdf UNIX/Linux下gcc编译通过
常遇见的警告、错误以及相关解决方法
从sdk3.2.5升级到sdk 7.1中间废弃了很多的方法,还有一些逻辑关系更加严谨了。 1,警告:“xoxoxoxo”  is deprecated 解决办法:查看xoxoxoxo的这个方法的文档,替换掉这个方法即可。 2,警告:Declaration of "struct sockaddr" will not be visible outside of this function
合并代码 & AGPBI报错
合并代码之后,项目无法运行,报错如下: AGPBI: {&quot;kind&quot;:&quot;error&quot;,&quot;text&quot;:&quot;error: resource drawable/nim_list_item_selector (aka com.rise.planner:drawable/nim_list_item_selector) not found.&quot;,&quot;sources&quot;:[{&quot;.
QMUI Android框架升级到1.1.6后,编译报not found的错误,原来是要加入appcompat兼容包。
一段时间没关注,QMUI Android框架从1.1.3升级到了1.1.6,欣喜的在gradle中将版本号升级到1.1.6,然后点击同步。 结果报错了! 这是最不愿意看到的情况,而且还是错误一大堆。都是not found的错误。 error: style attribute 'attr/colorPrimaryDark (aka net.dalu2048.wechatgenius:...
bleed aka doann ajjdna
bleed aka doann ajjdna
又见AKA
        北京的这个夏天真的很凉快,7月份下了28天雨,好多天的最高气温只有22度,以至于来自武汉的老乡Ark体会到这种凉爽,竟然忿忿不平地说:"北京的夏天太假了。" 每到这个时候,我就可以摆一摆老资格,语重心长地说,北京的夏天不都这么假,也有桑那天,也有酷热难耐的时候。比如1999年40度的夏天... 一提起那个夏天,我的思想就会开小差,想起很多事情。五道口附近那个热烘烘的小旅馆,清华新大
Normal (aka Gaussian) distribution 正态分布 高斯分布算法 C#
Normal (aka Gaussian) distribution
NAS信令学习笔记 ——AKA过程
AKA过程:Authentication and Key agreement (AKA)过程,鉴权和秘钥协商过程。 eKSI:Key Set Identifier in E-UTRAN,E-UTRAN的密码组标识。 1. 鉴权四向量 KASME:UE(USIM)和网络侧(AuC)根据CK、IK以及serving network identity (SN id)生成的中间秘钥,是EPS加...
iOS 工程的警告修复
原文地址:http://www.cocoachina.com/ios/20170601/19396.html 在项目中碰到300+的警告,强迫症只能修复了 1:#warning这个后面添加中文的话,在xcode的左边警告列表页会显示不全,所以推荐使用英文注释 2:(Method possibly missing a [super awakeFromNib] c
Android 引用第三方库报错(floatingactionbutton)
报错: Android resource linking failed C:\Users\zoukaicai\Desktop\testFBA\app\src\main\res\layout\activity_main.xml:10: error: attribute fab_orientation (aka com.ruijie.testfba:fab_orientation) not foun...
编译pano13的一些注意事项
作者:朱金灿来源:http://blog.csdn.net/clever101        pano是一个开源图像拼接库,pano13就是它的1.3版本。今天编译这个库,发现需要注意一个地方。pano是依赖于png库的。我设置依赖的png库的版本是1.5.12。在编译pano13出现下面错误: 错误285error C2037: “jmpbuf”的左侧部分指定未定义的结构/联合“png_stru
Aka 应用讲座 JSP
Aka 应用讲座 JSP
【二分答案&&最短路】URAL - 2034 Caravans
Problem Description 给你n个点,m条边。接下来m行每行u, v代表u 可以到达v,边权为1。最后一行输入s,f,r。代表s到f的所有最短路中。让你求r到这些最短路中最小值的最大值。(r到这些最短路的距离是最小值。但是因为有很多条最短路,所以找出到这些条最短路的最大值) 思路: 先求出s-f的最短路的值res。在求出r到各个点的最短路。这时候二分答案。从1-n查找答案。假设
Spring in Practice, 2013
完整版的 Spring in Practice by Willie Wheeler and Joshua White, 2013 Amazon上的五星图书
安卓中找不到Theme.AppCompat.Light的解决方法
将 <style name="AppBaseTheme" parent="Theme.AppCompat.Light"> 改为 <style name="AppBaseTheme" parent="android:Theme.Light"> 同理,将 <style name="AppBaseTheme" parent="Theme.AppCompat.Light.DarkActionBa
linux 编译C++错误整理
1、undefined reference to `__gxx_personality_v0' 需要-l libstdc++
Ervius_Visual_Kitchen Last Version: 1.8.1 aka 10.8.1 (1.8.1)
Ervius_Visual_Kitchen Last Version: 1.8.1 aka 10.8.1 (1.8.1)
AKAEmbedded00.pdf
AKA 嵌入式开发兴趣小组杂志第0期
【网络安全】EAP协议
EAP(Extensible Authentication Protocol),可扩展认证协议,是一种普遍使用的支持多种认证 方法的认证框架协议,主要用于网络接入认证。 该协议一般运行在数据链路层上,即可以直接运行于PPP或者IEEE 802之上,不必依赖于IP。EAP 可应用于无线、有线网络中。 EAP的架构非常灵活,在Authenticator(认证方)和Supplicant(客户端)
3gpp-aka-milenage
3gpp-aka-milenage全部投文件和c文件的完整实现,具体参考
文章热词 设计制作学习 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 大数据18掌门视频 长江师范学院大数据