URAL 1180. Stone Game (博弈 + 规律)[通俗易懂]

URAL 1180. Stone Game (博弈 + 规律)

大家好,又见面了,我是全栈君。

1180. Stone Game

Time limit: 1.0 second

Memory limit: 64 MB

Two Nikifors play a funny game. There is a heap of
N stones in front of them. Both Nikifors in turns take some stones from the heap. One may take any number of stones with the only condition that this number is a nonnegative integer power of 2 (e.g. 1, 2, 4, 8 etc.). Nikifor who takes the last stone wins.You are to write a program that determines winner assuming each Nikifor does its best.

Input

An input contains the only positive integer number
N (condition
N ≤ 10
250 holds).

Output

The first line should contain 1 in the case the first Nikifor wins and 2 in case the second one does. If the first Nikifor wins the second line should contain the minimal number of stones he should take at the first move in order to guarantee his victory.

Sample

input output
8
1
2

Problem Author: Dmitry Filimonenkov


Problem Source: Third USU personal programming contest, Ekaterinburg, Russia, February 16, 2002

解析:找规律。

考虑例如以下样例:
剩余石子的数量    first Nikifor
1                              win
2                              win
—- 依次选择1,2. 而且1 和 2是能够选择的。

3                              lose
—- 由于你选1或2的时候,另外一个人总能一次把剩下的取完。

4, 5                          win

—- 依次选择1,2,可以获胜。

6                              lose

7, 8                          win

…. 从上面的规律我们能够看出当 N mod 3 == 0 我们能确认first Nikifor一定能失败;否则的话。我们能选择的最小石子的数量 = N mod 3,此时first Nikifor获胜。

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int ans = 0;
    char c;
    while(scanf("%c", &c) && c != '\n') ans += c - '0';     //求个位数字之和以推断数字能否被3整除,数太大。直接存不下!

if(ans % 3 == 0) puts("2"); else printf("%d\n%d", 1, ans % 3); return 0;}

.

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116181.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • python截图识别文字_Python文字截图识别OCR工具实例解析

    python截图识别文字_Python文字截图识别OCR工具实例解析#!/usr/bin/envpython3#-*-coding:utf-8-*-Author:MaYiDate:2020-03-02Name:test_ocrSoftware:PyCharmNote:用Python开发截图识别OCR小工具importkeyboard#用于监控键盘按下,触发事件(pipinstallkeyboard)importtim…

  • mac 安装pymssql

    mac 安装pymssql我们在mac环境下想连接mssqlserver数据库,首先要考虑的就是使用pymssql库,而pymssql是在freedts的基础上研发的,所以要先安装freedts,但是安装这个库之前还需有有一系列的支撑库brewinstallunixodbcpipinstallCythonpipinstallsetuptools_git我们正常直接使用pipinstallpymssql时会报下面的错误Jason-MacBook-Pro:~wangying$pipinstal..

  • crm使用FetchXml聚合查询

    crm使用FetchXml聚合查询

  • L3-001 凑零钱(回溯和0-1背包)[通俗易懂]

    L3-001 凑零钱(回溯和0-1背包)[通俗易懂]韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有 10​4​​ 枚来自各个星球的硬币,需要请你帮她盘算一下,是否可能精确凑出要付的款额。输入格式:输入第一行给出两个正整数:N(≤10​4​​ )是硬币的总个数,M(≤10​2​​ )是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。输出格式:在一行中输出硬币的面值 V​1​​ ≤V​2​​ ≤⋯≤V​k

  • navicate 15 激活码 在线[在线序列号]「建议收藏」

    navicate 15 激活码 在线[在线序列号],https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • docker下载安装教程_安卓安装docker

    docker下载安装教程_安卓安装docker前言Docker提供轻量的虚拟化,你能够从Docker获得一个额外抽象层,你能够在单台机器上运行多个Docker微容器,而每个微容器里都有一个微服务或独立应用,例如你可以将Tomcat运行在一个D

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号