UVa 377 Cowculations

题目描述

一种原始的奶牛文化被著名人类学家Dr. Bo Vine \texttt{Dr. Bo Vine}Dr. Bo Vine发现。在达拉斯附近的某片牧场上出土了数百块计算石板。Dr. Vine \texttt{Dr. Vine}Dr. Vine在意识到它们代表数学计算后，成功破译了这些石板的秘密。他说：“我一直怀疑奶牛比它们让我们认为的更聪明，这就是证据。重大突破是认识到它们不能用牛蹄数数，但能用蹄子思考。但现在我有数百块石板，需要帮助验证我的假设。”

编写程序帮助Dr. Vine \texttt{Dr. Vine}Dr. Vine验证他的假设。

石板格式

每块石板包含6 66行：

• 第1 11行：第一个奶牛数字（5 55个符号）
• 第2 22行：第二个奶牛数字（5 55个符号）
• 第3 33、4 44、5 55行：三个操作（每个操作一个符号）
• 第6 66行：结果数字（8 88个符号）

符号系统

奶牛数字使用四种符号：V、U、C、D，表示数字0 00、1 11、2 22、3 33。每个数字实际上是四进制表示，但符号顺序是从左到右（最高位在左）。

例如：

• VVVVV=0 00
• VVVVU=1 11
• VVVUV=4 44（因为U在倒数第二位）

操作

• A（加法）：N u m 2 = N u m 1 + N u m 2 Num_2 = Num_1 + Num_2Num2​=Num1​+Num2​（使用给定的加法表，考虑进位）
• R（右移）：N u m 2 Num_2Num2​右移一位，最右边符号丢失，最左边补V（0 00）
• L（左移）：N u m 2 Num_2Num2​左移一位，最左边符号保留，最右边补V（0 00）
• N（空操作）：N u m 2 Num_2Num2​不变

加法表

加法表定义了两位符号相加的结果和进位。例如：

• U A V=U（结果），进位为U（1 11）
• C A C=V（0 00），进位为U（1 11）

验证过程

初始时N u m 1 Num_1Num1​= 第1 11行数字，N u m 2 Num_2Num2​= 第2 22行数字。依次应用三个操作。最终N u m 2 Num_2Num2​应与第6 66行数字匹配（第6 66行数字总是8 88位，如位数不足则在左边补V）。

题目分析

问题的本质

这是一个四进制计算器模拟问题。需要：

1. 将奶牛数字（V、U、C、D）转换为整数
2. 模拟加法（使用给定的加法表）和移位操作
3. 将最终结果与预期结果比较

四进制转换

V=0 00，U=1 11，C=2 22，D=3 33。字符串从左到右是高位到低位。

转换公式：

value = value * 4 + digit

加法实现

加法表可以编码为两个4 × 4 4 \times 44×4的矩阵：

• 结果矩阵：result[dig1][dig2]
• 进位矩阵：carry[dig1][dig2]

intaddResult[4][4]={{0,1,2,3},// V+V=V, V+U=U, V+C=C, V+D=D{1,2,3,0},// U+V=U, U+U=C, U+C=D, U+D=V{2,3,0,1},// C+V=C, C+U=D, C+C=V, C+D=U{3,0,1,2}// D+V=D, D+U=V, D+C=U, D+D=C};intaddCarry[4][4]={{0,0,0,0},// V...{0,0,0,1},// U+D 产生进位{0,0,1,1},// C+C 和 C+D 产生进位{0,1,1,1}// D+U、D+C、D+D 产生进位};

移位实现

• 右移：number2 / 4（因为四进制，右移一位相当于除以4 44）
• 左移：number2 * 4（左移一位相当于乘以4 44）

结果比较

最终N u m 2 Num_2Num2​需要与第6 66行数字比较。第6 66行总是8 88位，但N u m 2 Num_2Num2​可能不足8 88位，需要在左边补V（0 00）后比较。

实际上，由于N u m 2 Num_2Num2​是整数，将其转换为四进制字符串，左边补零（V）到8 88位，然后与输入字符串比较。

参考代码

// Cowculations// UVa ID: 377// Verdict: Accepted// Submission Date: 2016-06-30// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;map<char,int>digits;// 将奶牛数字字符串转换为整数intgetNumber(string&text){intvalue=0;for(autoc:text)value=value*4+digits[c];returnvalue;}// 模拟操作intcowculation(intnumber1,intnumber2,string&op){if(op=="A")returnnumber1+number2;if(op=="R")returnnumber2/4;if(op=="L")returnnumber2*4;returnnumber2;// 'N'}// 将整数转换为 8 位奶牛数字字符串stringtoString(intvalue){stringresult(8,'V');// 初始全为 V（0）intidx=7;while(value>0){switch(value%4){case0:result[idx]='V';break;case1:result[idx]='U';break;case2:result[idx]='C';break;case3:result[idx]='D';break;}value/=4;idx--;}returnresult;}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intn;string line;getline(cin,line);n=stoi(line);// 建立符号到数字的映射digits['V']=0,digits['U']=1,digits['C']=2,digits['D']=3;cout<<"COWCULATIONS OUTPUT"<<endl;string text1,text2,text3,op1,op2,op3;for(inti=1;i<=n;i++){getline(cin,text1);getline(cin,text2);getline(cin,op1);getline(cin,op2);getline(cin,op3);getline(cin,text3);intnumber1=getNumber(text1);intnumber2=getNumber(text2);intnumber3=getNumber(text3);// 依次应用三个操作number2=cowculation(number1,number2,op1);number2=cowculation(number1,number2,op2);number2=cowculation(number1,number2,op3);// 比较结果if(toString(number2)==text3)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}cout<<"END OF OUTPUT"<<endl;return0;}