APIO2008.pdf

"APIO2008.pdf" 本文档是亚洲信息学奥林匹克竞赛（APIO）2008年的竞赛题目，包含三个问题，分别是珠链交换器、换器交和DNA。本文档详细介绍了每个问题的描述、输入格式、输出格式、时间限制和空间限制等信息。 珠链交换器 珠链交换器（UBS）是一个工具，可以通过交换一些珠子使珠链更有趣。它有N条平行于南北方向的传送带，每条传送带的速度相同，且都是由北向南传送。有M个交换器，每个交换器都安放在某两个相邻的传送带上，任意两个交换器与传送带最北端的距离都是不同的。 任务是编写一个程序，对于给定的传送带条数N，交换器个数M，以及每个交换器的位置，回答以下形式的问题：给出K（传送带的编号）和J（交换器的编号），当所有的珠子都刚好完全经过交换器J（又称J号交换器）时，最开始时放在第K条传送带（又称K号传送带）最北端的珠子现在位于哪一条传送带上。 输入格式 从标准输入读入数据。第一行包含传送带的条数N()和交换器的个数M()。接下来的M行，按照从北向南的顺序描述所有的交换器，每行包含一个整数P（1≤P≤M-1），表示在传送带P和P+1之间有一个交换器。 交互方法 在读入上述数据之后，你的程序需要和表格1中所描述的库进行交互。库中的函数必须按下面的顺序调用： 1. 调用getNumQuestions以获取Q()，表示有多少个问题。 2. 以后Q次，每次（a）调用函数getQuestion来获取一个问题。（b）调用函数answer回答对应的问题。 特别注意，getNumQuestions必须首先调用，且只能调用1次。getQuestion和answer必须交替调用：当调用完getQuestion之后，你的程序不能马上再次调用getQuestion，而必须先调用answer，反之亦然。如果你的程序在某个测试点违反了这一约定，则该测试点你的得分为0。 函数原型 Pascal function getNumQuestions(): integer C 和C++ int getNumQuestions() 返回你的程序应该回答的问题个数 Pascal procedure getQuestion(var K: integer, var J: integer) C void getQuestion(int *K, int *J) C++ void getQuestion(int &K, int &J) K为珠子在最北端时的传送带编号，J为交换器的编号 Pascal procedure answer(x:integer) C 和C++ void answer(int x) x给出上一个getQuestion对应的答案