答案提交

非传统题型练习：三道答案提交类题目

/ 4 条评论

    不少人可能为找不到非传统题型的练习题而头疼。这几天我专门发出一些用于省选集训的题目供大家参考。

Problem 1: cell 手机
题目来源：USACO Contest FEB06 Gold (Translated by Matrix67)

问题描述
    奶牛们已经开始使用手机交流了，但它们发现手机的按键设计不适合它们的蹄子。它们想设计一个新的手机，让它的按键更少，但是更大。
    它们喜欢普通手机的一个功能：词语联想。每个按键都有一些字母和它对应，打出一个单词只需要按对应的按键。因为一个按键可能对应多个字母，因此某些单词可能会发生“歧意”。不过，大多数时候这种歧意可以通过用字典判断的方法来消除。
    考虑到奶牛们在自定义一款新的手机，它们还需要用奶牛字母表替换英文字母表。神奇的是，奶牛字母表中的字母恰好是英语字母表中的前L个字母，即使顺序也一样。它们想知道如何把这些字母分配给B个按键(1<=B<=L)使得在字典中不会产生歧意的单词最多。就像普通的手机一样，他们希望每个按钮上的字母都是字母表中一段连续的字母。

    这是一个答案提交类的题目。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件cell.3.in相对应的输出文件应该为cell.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入数据
    第一行：一个整数N，表示这是第N个输入文件。
    第二行：两个用空格隔开的整数：B和L
    第三行：D，字典中的单词数(1<=D<=1000)
    第四行到第D+3行：每一行包含一个字典中的单词，用1到10个大写字母表示。这些单词按照字典序给出，并且保证没有重复。

输出数据
    第一行：字典中具有唯一的按钮序列的单词数。
    第二行到第B+1行：其中的第n行包含有第n个按钮上的字母，用大写的字母按照字典的顺序表示。所有行必须按照字典序排列，每个字母出现恰好一次。如果有多个最优解，选用第一个按键上字母最多的解。如果最优解仍然不唯一，考虑第二个按键上字母最多，依此类推。

样例输入(cell.1.in)
1
3 13
11
ALL
BALL
BELL
CALK
CALL
CELL
DILL
FILL
FILM
ILL
MILK

样例输出(cell.1.out)
7
AB
CDEFGHIJK
LM

样例说明
    第一个按键上只有AB两个字母，第二个按键上含有C到K，第三个按键上为LM。单词CELL、DILL、FILL和FILM的输入都是2233，其它7个单词的输入都是唯一的。

题解(Ctrl+A)：
    这道题目……搜索，乱搞。

Problem 2: selfstr 自描述序列
题目来源：Matrix67根据经典问题改编

问题描述
    “这句话里有1个数字零，2个数字一，1个数字二，0个数字三”。

    在N(N>=2)进制中只允许0到N-1这N个数字出现。一个N位的N进制数（允许有前导0）可以由另一个同样多位的数来描述。我们定义一个N位N进制数的描述序列为：左起第i个数字为原数中数字i-1出现的次数。
    例如，在4进制中，0023的描述序列为2011，因为0023中有2个0，0个1，1个2和1个3。
    我们惊奇地发现，4进制数1210的描述序列是它本身！我们称这样的数叫做“自描述序列”。

    你需要编写程序计算出在某个进制下的自描述序列。一个进制下的自描述序列可能有很多个，你只需要给出其中一个即可。
    这是一个答案提交类的问题。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件selfstr.3.in相对应的输出文件应该为selfstr.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入格式
    输入数据只有一个正整数N

输出格式
    输出N个字符，它表示N进制下的自描述序列。在高于10的进位制下，大于9的数字请用大写字母表示。
    如果有多种可能的解，你只需要输出其中一个。
    如果该进制下无解，请输出“NONE”。

样例输入(selfstr.1.in)
4

样例输出(selfstr.1.out)
1210

题解：
    这道题太有意思了！首先，你需要先算几个小数据。你会发现，算到N>=6后，渐渐有规律了：


   N   N进制下的自描述序列
   4    1210 or 2020
   5    21200
   6    NONE
   7    3211000
   8    42101000
   9    521001000

    事实上，这道题目就是考你当搜索到一些解后能不能找到规律得到所有解。这里我们发现，对所有N>6，至少存在一个解为R21(0…0)1000，其中R=N-4，中间0的个数为N-7。结论显然正确。
    有可能除了这个之外存在其它的解，因此我们仍然需要写一个check来核对答案。

Problem 3: relation 大小关系
题目来源：Matrix67根据经典问题改编

问题描述
    用关系“ < ”和“ = ”将3个数a、b、c依次序排列时，有13种不同的序列关系：
      a=b=c, a=b<c, a<b=c, a<b<c, a<c<b
      a=c<b, b<a=c, b<a<c, b<c<a, b=c<a
      c<a=b, c<a<b, c<b<a

    用这两种关系连接N个数有多少种不同的方案？

    这是一个答案提交类的问题。所有选手将得到10个输入数据，你只需要在你自己的计算机上计算出你的答案，然后把你的答案提交上来。与输入文件relation.x.in相对应的输出文件应该为relation.x.out，这里x表示一个1到10之间的数。

输入格式
    输入一个整数，表示N。

输出格式
    输出用小于和等于符号将N个数进行有序排列的方案数。

样例输入(relation.1.in)
3

样例输出(relation.1.out)
13

题解：
    组合数学+高精度。由于数据规模很小，我就直接搞成了答案提交类的题目。
    下面给出两种递推方法：
    Solution 1: N个数中必然存在一个最大的“等价类”，如果这个等价类里有k个数，那么剩下的数就有F(N-k)种排列方案。别忘了我们需要枚举这k个数是哪k个数。于是，F(N)
=C(N,1)F(N-1)+C(N,2)F(N-2)+C(N,3)F(N-3)+ … +C(N,N)F(0)
    Solution 2: 用F[ i, j]表示 i个数中有j 个等价类的排列方案（就是说有j-1个小于符号）。第 i个数有可能并入了F[i-1, j]中的 j个等价类中的一个，也有可能不与任何一个已有的数相等，独自成为一个等价类插入F[i-1, j-1]里产生的 j个空位中。于是，F[ i,j ]=F[i-1, j]*j + F[i-1,j-1]*j。

其它问题：
    如何用Cena评测答案提交类问题？
        见http://www.matrix67.com/blog/article.asp?id=176
    这些题的数据哪里有？
        第一题：http://ace.delos.com/FEB06，GOLD DIVISION里面的第三个
        第二题：自己写check，不需要数据
        第三题：http://www.research.att.com/~njas/sequences/b000670.txt，吓死你

Matrix67原创
转贴请注明出处

用Cena评测答案提交类题目的另类方法

/ 3 条评论

    这几天组织了几次省选模拟赛，遇到了答案提交类的题目和交互式的题目。我一直使用Cena进行评测，现在希望把这两种类型的题目方便地加入Cena的评测结果中。交互式的题目使用Cena评测非常简单，只需要在库函数运行时输出一个以得分情况为内容的文件作为选手输出即可（http://www.matrix67.com/blog/article.asp?id=179）。但答案提交类的题目却遇到了麻烦，因为Cena肯定不允许程序访问外部文件（因此不能另写程序读入提交的答案并作为选手输出文件输出），而每个选手提交的答案文件所在位置又不确定（不知道文件夹名），不能把这些文件加入Cena的评测中。后来，我想到了这样一个解决方案。我可以用程序生成一个程序来生成选手输出文件（真他妈的绕口）。

    假设测试点共10个，所有的输入文件名为name.?.in，输出文件名为name.?.out，其中?取1到10中的数。那么下列程序可以生成一个printer.pas作为选手程序。以下程序将选手提交的答案写入pas源代码“printer.pas”中，它可以根据输入文件恰当地进行输出操作。“printer”将被设置为该题的源程序文件名。
    评测时所用的输入文件只有一个整数，标识这是第几个测试点。程序的输出（即选手提交的答案）可以和标准输出比较或另写Checker评分。

program print;
const
   fname='name';
var
   i:integer;
   st:string;

procedure init;
begin
   writeln('program printer;');
   writeln('var n:integer;');
   writeln;
   writeln('begin');
   writeln('   assign(input,'+#39+fname+'.in'+#39+');');
   writeln('   reset(input);');
   writeln('   readln(n);');
   writeln('   close(input);');
   writeln('   assign(output,'+#39+fname+'.out'+#39+');');
   writeln('   rewrite(output);');
   writeln;
end;

begin
   assign(output,'printer.pas');
   rewrite(output);
   init;
   for i:=1 to 10 do
   begin
      str(i,st);
      {$i-}
      assign(input,'name.'+st+'.out');
      reset(input);
      {$i+}
      if ioresult<>0 then continue;
      writeln('   if n=',i,' then begin');
      repeat
         readln(st);
         writeln('      writeln(',#39,st,#39,');');
      until eof;
      writeln('   end;');
      writeln;
   end;
   writeln('   close(output);');
   writeln('end.');
   close(output);
end.

    采取一些工具软件可以在不同的选手文件夹下批处理运行该程序。

    过几天我可能又要思考如何评测循环赛类型的题目了。

做人要厚道
转贴请注明出处