hdu Stone Game SG 함수

1320 단어 바둑 을 두다
N 개의 상자, 상자 마다 하나의 size 가 가장 많이 담 긴 돌 수 를 나타 내 고, 하나의 c 는 현재 c 개의 돌 을 담 았 음 을 나타 낸다.현재 두 사람 이 돌아 가면 서 조작 할 수 있 습 니 다. 매번 조작 할 때마다 한 상 자 를 선택 하여 1 - k 개의 돌 을 놓 을 수 있 습 니 다. 그 중에서 k 는 상자 에 현재 가지 고 있 는 돌 수의 제곱 입 니 다. 가장 먼저 조작 할 수 없 는 쪽 이 지고 먼저 승 부 를 구 할 수 있 습 니 다.언뜻 보기 에는 동태 적 인 게임 인 것 같 지만, 사실은 그렇게 복잡 하 게 생각 하지 않 았 다.
i 번 째 상자 에 Si, Ci 가 있 으 면 최대 Ti 만족 Ti * Ti + Ti 를 구 할 수 있 습 니 다.
ci > Ti, 현재 상자 의 선 수 는 필승 방안 이 있 습 니 다. sg 값 은 Si - ci 입 니 다.
Ci = = = Ti, 현재 상자 의 선 수 는 반드시 패 하 므 로 sg = 0
Ci
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
int n,m;
int sg(int s,int c)
{
    int l=sqrt(s*1.0);
    while(l*l+l>=s) l--;
    if (c>l) return s-c;
    else if (c==l) return 0;
    else
    {
        return sg(l,c);
    }
}
int main()
{
//    freopen("in.txt","r",stdin);
    int tt=0;
    while(scanf("%d",&n) && n)
    {
        int x,y;
        int ans=0;
        for (int i=1; i<=n; i++)
        {
            scanf("%d%d",&x,&y);
            ans^=sg(x,y);
        }
        printf("Case %d:
",++tt); if (!ans) puts("No"); else puts("Yes"); } return 0; }

좋은 웹페이지 즐겨찾기