880101 - 扑克牌

有 N(3≤N≤50)张反面朝上的扑克牌排成一排,每次可以翻转任意 3 张扑克牌(正面翻转后为反面,反面翻转后为正面,且不考虑正面花色和点数),请问最少翻转几次可以将 N 张扑克牌全部翻转为正面。 例如:N=5,最少翻转 3 次可以使 5 张扑克牌全部翻转为正面朝上。 初始状态: 第 1 次:将第 1、2、3 张扑克牌进行翻转,翻转后如下图所示; 第 2 次:将第 1、2、4 张扑克牌进行翻转,翻转后如下图所示; 第 3 次:将第 1、2、5 张扑克牌进行翻转,翻转后如下图所示。

输入

输入一个正整数 N(3≤N≤50),表示扑克牌的数量

输出

输出一个整数,如果可以将 N 张反面朝上的扑克牌全部翻转为正面朝上,输出最少需要翻转的次数,否则输出-1

样例

输入

5

输出

3

提示

题目解析: 有N(3≤N≤50)张反面朝上的扑克牌。 每次翻转任意3张, 最少翻转几次可以将N张扑克牌全部翻转为正面。 如果模拟几个情况,就会发现其中规律: (以下用1表示反面,0表示正面) 当N=4时,翻4次; 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 当N=5时,翻3次; 1 1 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 0 0 0 当N=6时,翻2次; 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 当N=7时,翻3次; 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 当N=8时,翻4次; 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 当N=9时,翻3次; 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 当N=10时,翻4次; 1111111111 0001111111 0000001111 0000010011 0000000000 当N=11时,翻5次; 11111111111 00011111111 00000011111 00000000011 00000001101 00000000000 这时候会发现当这个数是3的倍数(能被3整除),倍数就是翻转的次数。//余数为0时 要注意4这个特殊的边界存在,其余的数都符合以下规则: 当这个数除3余1或余2时,请注意看样例,是不是最后的步骤都一样, 最后步骤的执行次数,恰好是除3的余数。 而相同步骤之前翻转的次数,恰好是除3的商。 再仔细看看发现翻转次数正好是除3的余数与商之和。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题