QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 8632. 算式密码锁

Statistics

题目描述

小C给他的自行车装了一把密码锁,但他经常苦恼于忘记密码。不过小C虽然记忆力不太好,但拥有超乎常人的计算能力,于是他给自己量身打造了一把特殊的密码锁。

这把密码锁共有6位,与常规的密码锁相同,每一位是一个转盘,可以自由转动。但每个转盘上不再是0~9的数字简单排列,而是一些特定的数字或符号:

  • 第1、3、5、6个转盘上,每个位置是一个数字;
  • 第2个转盘上,每个位置是一个运算符,共有加(+)、减(-)、乘(*)、除(/)4种可能;
  • 第4个转盘上,每个位置是一个关系符,共有大于(>)、等于(=)、小于(<)3种可能。

每个转盘上的数字或字符均有 $n$ 个。这样,任意转动转盘后,从不同角度看去,这些数字和字符可以组成 $n$ 个不同的算式。对于任意转动转盘后的结果而言,这 $n$ 个算式有的正确有的错误,而经过小C的精心设计,这把密码锁刚好可以在转动到正确的算式个数最多时打开锁。

凭借小C的计算能力,可以现场推算出如何转动转盘才能使正确的算式个数尽可能多。现在你好奇地盯上了他这把密码锁,想要尝试将其打开,但你苦于计算能力不够,所以打算写个程序来帮忙。

需要注意的是,式子中有前导0也可被视为正确,如 1+1=02, 2-2=00 等;除法是数学意义上的除法而非计算机中的整数除法,如 9/4=02 这样的式子被视为错误;除以0的式子将直接被视为错误,如 1/0=00 等。

输入格式

从标准输入读入数据。

第 $1$ 行,一个正整数 $n$,表示密码锁的算式个数,同时也是一个转盘上的数字或符号个数。

接下来 $6$ 行,每行一个长度为 $n$ 的字符串 $s_i$,表示从左往右第 $i$ 个转盘上的数字或符号(从转盘的初始位置起按顺序描述)。其中:

  • $s_1,s_3,s_5,s_6$ 中的字符为数字( 0123456789 );
  • $s_2$ 中的字符为运算符( +-*/ );
  • $s_4$ 中的字符为关系符( >=< )。

输出格式

输出到标准输出。

输出一行,一个非负整数,表示任意旋转密码锁后,正确的算式数量的最大值。

样例

输入

2
23
*+
34
><
12
05

输出

2

解释

一种转动转盘使得两个算式均成立的方案为:

2+3<25
3*4>10

样例

输入

10
0123456789
+-*/+-+-*/
0123456789
=<=>=<=>=>
0123456789
0123456789

输出

5

数据范围

对于所有测试数据保证:$n \leq 10$。

测试点编号 $n \leq $ 特殊性质
$1\sim 2$ $1$ AB
$3\sim 4$ A
$5\sim 6$ B
$7\sim 9$
$10\sim 11$ $2$ AB
$12\sim 13$ $10$
$14\sim 15$ A
$16\sim 17$ B
$18\sim 20$

“特殊性质A”为:$s_2$ 中仅包含字符 +

“特殊性质B”为:$s_4$ 中仅包含字符 =