2.4　相关题库

【2.4.1　Gold Coins】

国王要给他的忠诚骑士支付金币。在他服务的第一天，骑士将获得1枚金币。在后两天的每一天（服务的第二和第三天），骑士将获得2枚金币。在接下来3天中的每一天（服务的第四、第五和第六天），骑士将获得3枚金币。在接下来4天中的每一天（服务的第七、第八、第九和第十天），骑士将获得4枚金币。这种支付模式将无限期地继续下去：在连续N天的每一天获得N枚金币之后，在下一个连续的N+1天的每一天，骑士将获得N+1枚金币，其中N是任意的正整数。

请编写程序，在给定天数的情况下，求出国王要支付给骑士的金币总数（从第一天开始计算）。

输入

输入至少一行，至多21行。每行给出问题的一个测试数据，该数据是一个整数（范围为1～10 000），表示天数。最后一行给出0表示输入结束。

输出

对于输入中给出的每个测试用例，输出一行。每行先给出输入的天数，后面是一个空格，然后是在这些天数中从第一天开始计算总共要支付给骑士的金币总数。

试题来源：ACM Rocky Mountain 2004

在线测试：POJ 2000，ZOJ 2345，UVA 3045

提示

我们将n天分成p个时间段，第i个时间段为i天，每天奖励i个金币（1≤i≤p，，。设n为总天数，ans为奖励的金币总数，i记录当前天数，j记录时间段序号，即国王在该时间段内每天奖励的金币数，k为该时间段内的剩余天数。

两重循环如下：

1）外循环：枚举每个时间段j（for(int i=0，j=1；i<=n；j++)）。

2）内循环：计算时间段j内奖励的金币数（int k=j；while(k-- & & ++i<=n)ans+=j）。最后得出的ans即国王n天里奖励给骑士的金币总数。

【2.4.2　The 3n+1 problem】

计算机科学的问题通常被列为属于某一特定类的问题（如NP、不可解、递归）。这个问题是请你分析算法的一个特性：算法的分类对所有可能的输入是未知的。

考虑下述算法：

1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then n <-- 3n+1
5. else n <-- n/2
6. GOTO 2

给出输入22，打印下述数字序列：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1。

人们推想，对于任何完整的输入值，上述算法将终止（当1被打印时）。尽管这一算法很简单，但还不清楚这一猜想是否正确。然而，目前已经验证，对所有整数n（0<n<1 000 000），该命题正确。

给定一个输入n，可以确定在1被打印前被打印数字的个数。这样的个数被称为n的循环长度。在上述例子中，22的循环长度是16。

对于任意两个整数i和j，请计算在i和j之间的整数中循环长度的最大值。

输入

输入是整数i和j组成的整数对序列，每对一行，所有整数都小于10 000大于0。

输出

对输入的每对整数i和j，请输出i、j以及在i和j之间（包括i和j）的所有整数中循环长度的最大值。这三个数字在一行输出，彼此间至少用一个空格分开。在输出中i和j按输入的顺序出现，然后是最大循环长度（在同一行中）。

试题来源：Duke Internet Programming Contest 1990

在线测试：POJ 1207,UVA 100

提示

本题也是一道经典的直叙式模拟题，因为整数循环一次的计算步骤是给定的。若输入的整数对为a和b，则给定的整数区间为[min(a,b)，max(a,b)]。设置两重循环：

1）外循环：枚举区间内的每个整数n（for(n=min(a,b);n<=max(a,b);n++)）。

2）内循环：计算n的循环长度i（for(i=1,m=n;m>1;i++)if(m%2==0)m/=2;else m=3*m+1;）。

显然，在[min(a,b)，max(a,b)]内所有整数的循环长度的最大值即问题解。

【2.4.3　Pascal Library】

Pascal大学要翻新图书馆大楼，因为经历了几个世纪后，图书馆开始显示它无法承受馆藏的巨大数量的书籍的重量。

为了帮助重建，大学校友协会决定举办一系列的筹款晚宴，邀请所有的校友参加。这些事件被证明是非常成功的，在过去几年举办了几次。（成功的原因之一是上过Pascal大学的学生对他们的学生时代有着美好的回忆，并希望看到一个重修后的Pascal图书馆。）

组织者保留了电子表格，表明每一场晚宴都有哪些校友参加了。现在，他们希望你帮助他们确定是否有校友参加了所有的晚宴。

输入

输入包含若干测试用例。一个测试用例的第一行给出两个整数N和D，分别表示校友的数目和组织晚宴的场数（1≤N≤100且1≤D≤500）。校友编号从1到N。后面的D行每行表示一场晚宴的参加情况，给出N个整数Xi，如果校友i参加了晚宴，则Xi=1，否则Xi=0。用N=D=0表示输入结束。

输出

对于输入中的每个测试用例，程序产生一行输出，如果至少有一个校友参加了所有的晚宴，则输出“yes”，否则输出“no”。

试题来源：ACM South America 2005

在线测试：POJ 2864，UVA 3470

提示

设yes为有校友全出席的标志；校友的出席情况为att，其中att[j]=1表示校友j到目前为止尚未缺席过。

先输入第1个测试用例的校友数n和晚宴场数d，然后进入while(n||d)循环。循环体内的计算过程如下。

1）初始时设所有校友全出席所有晚宴，即att[0]=att[1]=…=att[n-1]=1。

2）使用双重循环枚举每场晚宴校友的出席情况：

①外循环枚举晚宴场次j（0≤j≤d-1）；

②内循环枚举校友i（0≤i≤n-1）；

③循环体内输入第i场晚宴中校友j的出席情况k，计算校友j目前为止的全出席情况att[j]=att[j] & k。

3）计算是否有校友全出席的标志。

4）若yes==true，则输出“yes”，否则输出“no”。

5）输入下一测试用例的校友数n和晚宴场数d。

【2.4.4　Calendar】

大多数人都会有一个日历，我们会在日历上记下生活中重要事件的细节，诸如去看牙医、售书、参加程序设计竞赛；还有一些固定的日期，如合作伙伴的生日、结婚周年纪念日等，我们需要记住这些日期。通常情况下，当这些重要的日期临近的时候，我们需要得到提醒；事情越重要，我们就越希望事先能记下这些事。

请你编写一个提供这种服务的程序。输入给出这一年的重要日期（年份范围为1901～1999）。要注意的是，在给出的范围内，所有被4整除的年份是闰年，因此要加入额外的一天（2月29日）。输出将给出今天的日期、即将到来的事件和这些事件的相对重要性的列表。

输入

输入的第一行给出一个表示年份的整数（范围为1901～1999）。后面几行表示周年纪念日或服务所要求的日期。

一个周年纪念日由字母A、表示这一事件的日期/月份/重要性的三个整数（D,M,P）和一个描述事件的字符串组成，这些项用一个或多个空格分开。P在1到7之间取值，表示在事件前要开始提醒服务的天数。给出的描述事件的字符串以非空字符开始。

一个日期行由一个字母D及如上所述的日期和月份组成。

所有周年纪念日在日期行之前，每行不超过255个字符。文件以仅包含一个“#”的行结束。

输出

输出由若干部分组成，输出的每一行对应输入中的一个日期行，由要求的日期和后面给出的必要的事件列表组成。

输出给出事件的日期（D和M，每项宽度为3），以及事件的相对重要性。今天发生的事件标识如样例所示，明天发生的事件有P颗星，后天发生的事件有P-1颗星，等等。如果几个事件在同一天发生，则按其重要性排列。

如果还存在冲突，则按其在输入流中出现的顺序排列。格式见样例，在块之间留一个空行。

试题来源：New Zealand Contest 1993

在线测试：UVA 158

提示

本题属于一道典型的过程模拟，模拟方法是直译试题要求。

设e为事件序列，其中事件i的日期为e[i].month月e[i].day天，重要性参数为e[i].level，输入次序为e[i].index，描述事件的字符串为e[i].a。

直接根据试题要求模拟处理输入信息：

1）输入年份year，计算year是否是闰年。

2）反复处理输入和输出信息，直至输入“#”为止。

若输入周年纪念日标志“A”，则累计周年纪念日数n，输入第n个周年纪念的日期（e[n].month，e[n].day）、重要性参数e[n].level、描述事件的字符串e[n].a、输入顺序e[n].index=n。

若输入服务标志“D”，分两种情况处理：

1）若第1次输入“D”，则按照周年纪念的日期为第1关键字、重要性参数为第2关键字、输入顺序为第3关键字的递增顺序排列事件序列e[1..n]。

2）若非第1次输入“D”，则首先读服务日期(month，day)，并将日期计数器cnt初始化为-1，然后进入循环，直至cnt到达提醒天数的上限7为止：

·若当天服务（cnt==-1），则将e序列中周年纪念日期为(month，day)的事件存储在s中，按照输入次序递增的顺序重新排列s，然后以重要性参数为*TODAY*的名义依次输出s中事件的日期和描述事件的字符串。

·若非当天服务（cnt≠-1），则依次寻找e序列中周年纪念日期为(month，day)的事件e[i]（e[i].month==month & & e[i].day==day，1≤i≤n），计算该事件剩余的提醒时间num=e[i].level-cnt。若num≤0，则说明该事件已过提醒时间；否则输出服务标识（num个“*”和8-num个空格）和描述事件的字符串e[i].a。

·累计过去的天数（cnt++）。若过了提醒期限（cnt==7），则退出循环；否则获取month月day日的下一天日期(month，day)。

【2.4.5　MANAGER】

并行处理的程序设计范型之一是生产者/消费者（producer/consumer）范型，可以用一个管理者（manager）进程和几个客户（client）进程的系统来实现。管理者记录客户进程的过程。每个进程用它的耗费来标识，耗费是一个1～10 000的正整数，相同耗费的进程数目不会超过10 000。按如下请求来管理队列：

·a x——将一个耗费为x的进程加到队列中；

·r——如果可能，按照当前管理者的策略，删除一个进程；

·pi——执行管理者的策略i，其中i是1或2，默认值为1；

·e——请求列表终止。

两个管理者的策略：

·1——删除最小耗费进程；

·2——删除最大耗费进程。

只有当被删除的进程的序号在删除列表中，管理者才打印被删除进程的耗费。

你的工作就是写一个程序来模拟管理者进程。

输入

输入为标准输入，输入的每个数据集合形式如下：

1）耗费最大的进程；

2）删除列表的长度；

3）删除列表——显示被删除进程的顺序号的列表，例如1 4表示第1个和第4个被删除的进程的耗费要被显示；

4）在一个单独的行里给出一个请求的列表。

每个测试用例以一个请求e为结束，测试用例之间用空行分开。

输出

程序标准输出，给出要删除的每个进程的耗费，在队列不为空的情况下，给出列表中删除请求的顺序数。如果队列为空，输出-1。结果输出在单独的行上，用空行分开不同测试用例的结果。

试题来源：ACM Southeastern Europe 2002

在线测试：POJ 1281，UVA 2514

提示

设进程的最小耗费为minp=1；进程的最大耗费为mapx；Print为进程删除的标志序列，Print[k]=true表示进程k被删除；plen为删除的进程数；np为当前被删除的进程数；cnt存储各耗费的进程数，其中cnt[k]为耗费k的进程数；req为请求类别（a、r、p、e）；condition为管理者的策略（1或2）。

每个测试数据组的格式为：

·进程的最大耗费值maxp。

·删除的进程数plen。

·plen个被删除的进程序号。

·请求命令序列为(ax，r，pi，e)，以e结束。

整个输入以测试数据组的首个整数为0（mapx==0）结束。显然，主程序应为while(cin>>maxp)的外循环结构。外循环体内的计算过程如下：

1）输入删除的进程数plen和plen个被删除的进程序号，将这些进程的Print标志设为true。

2）当前被删除的进程数np设为0，输入第1个请求类别，进入结构为while(req!="e")的内循环，依次处理请求命令。内循环的计算过程如下：

①若增加新进程（req为“a”），则读新增进程的花费x，cnt[x]++。

②若按照当前管理者策略删除一个进程（req为“r”），则分析管理者策略condition：

·若condition==1，为删除最小耗费的进程，让k从minp递增枚举至maxp，第1个cnt[k]≠0的进程被删除，cnt[k]--。

·若condition==2，为删除最大耗费的进程，让k从maxp递减枚举至minp，第1个cnt[k]≠0的进程被删除，cnt[k]--。

累计被删的进程数np++。若该进程在被删计划之列（print[np]=true），则输出该进程的花费k。

③若执行管理者的策略（req为“p”），则读condition（1或2）。

读下一个请求类别req。

上一章目录下一章