VIJOS-P1141

题目描述

输入一个自然数n(n< 1e1000)，表示1到n共n个自然数排成一列，你要在每一个数前添上+或-,要使得添加符号后这个代数式的值最小且非负.

输入

一个数，n.

输出

一个数，即最小非负值。

样例输入

5

样例输出

1

题目分析：
输入数N用到高精度，固要用字符串或字符数组型
题目中用到的知识：
　　

我们知道，连续的四个整数可以让其和为0。-n+(n+1)+(n+2)-(n+3)=0。所以我们把1到n个数从后往前分成n div 4份。若n为5则1(-2+3+4-5)＝1

N=10则-1+2(-3+4+5-6)(-7+8+9-10)＝1

当然n mod 4=0时和就为0。于是我们要计算出n mod 4的值，只要计算1..n mod 4的最小非负值（n mod 4+1…n这些数的和为0，不用管它们）。那么需要高精度除法吗？不！若n>=100，我们设n=100a+b|b<100，前面的100a mod 4必=0，不用考虑，于是要计算n mod 4，只要计算n的最后两位(就是b)mod 4就行了！最后在根据mod出来的余数进行特判：

N mod 4=0:ans=0

N mod 4=1:ans=1

N mod 4=2:ans=-1+2=1

N mod 4=3:ans=-1-2+3=0

在算法中，若输入N是一位数，则将字符串的最后一位进行强制类型转换；若字符串长度大于1，则将倒数第二位也进行强制类型转换并乘10加上后一位。


代码实现：

#include<iostream>
#include<cstring>  

using namespace std;
int a,longth;
string n;
int main()
{
    getline (cin,n);
    longth=n.length();
    a=(int(n[longth-1])-int('0'));
    if (longth>1) {a=a+( int(n[longth-2])-int('0') )*10 ;}
    if  ( ((a%4)==1)||((a%4)==2) ) cout<<'1'<<endl; else cout<<'0'<<endl;
    return 0;
}