HDU 2149 Public Sale

3387 ワード

http://acm.hdu.edu.cn/showproblem.php?pid=2149
Problem Description
いやだが、現実は結局現実で、Leleは奨学金をもらっていないので退学の運命を逃れなかった.今彼を待っているのは、FarmJohnのような農地生活だ.
畑を作るには田が必要だ.Leleは街で別のオークションが行われていると聞いた.オークションの品物はちょうど20ムーの畑だ.そこで、Leleは彼の貯金を全部持って、オークションに向かった.
その後、オークション全体がLeleと彼の死の向こうYueyueだけであることが分かった.
聞いてみると、Leleはこのオークションのルールがこうであることを知っています.最初は最低価格が0で、二人で交代で値上げを始めましたが、値上げの幅は1~Nの間で、価格が畑のコスト価格M以上になると、主催者はこの畑を今回の値上げ者に売っています.
LeleとYueyueは試験はだめだが、オークションには精通しており、二人ともこの畑を手に入れたいと思っている.だから彼らは毎回自分にとって最も有利な方法を選んで値上げします.
Lele辞書の順序はYueyueより前なので、毎回Leleが先に値上げを始めます.すみません、初めて値上げしたとき、Leleはどのくらい出して自分でこの土地を買うことができますか?
Input
この問題には複数のテストが含まれています.ファイルの終了(EOF)まで処理してください.各グループのテストは1行を占めます.各グループのテストは2つの整数MとNを含む(意味は問題の説明を参照して、0Output
各グループのデータについて、Leleが初めて加算できる価格を1行ごとに増加順に出力します.2つのデータの間はスペースで区切られています.Leleが初めていくら値切ってもこの土地が買えないなら、「none」を輸出します.
Sample Input
4 2 3 2 3 5
Sample Output 1 none 3 4 5
簡単なバッシュゲームの問題
まずバッシュ・ゲームについてお話しします.n個の品物しかありません.二人は交代でこの品物から物を取り、毎回少なくとも1個、最大m個を取ることを規定しています.最後に光を取った者が勝つ.
明らかに、n=m+1であれば、一度に最大m個しか取れないので、先取者が何個持って行っても、後取者は一度に残りのものを持っていくことができ、後者が勝つ.そこで,n=(m+1)r+s,(rは任意の自然数,s≦m)であれば,先取者はs個の物品を持ち去り,後取者がk(≦m)個を持ち去ると,先取者はm+1−k個を持ち去り,結果として(m+1)(r−1)個を残して後保持すると,先取者は必ず勝つという法則を見出した.要するに,相手に(m+1)の倍数で、最後に勝つことができます.このゲームには、2人が交代で数え、毎回少なくとも1つ、最大10つ、誰が100人に勝つことができますか.
上の説明を読めば問題がわかる
#include<iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.txt", "r", stdin);
#endif
    int n, m;
    while(~scanf("%d%d", &m, &n))
    {
        if (n >= m)
        {
            for (int i = m; i < n; i++)
            {
                cout << i << " ";
            }
            cout << n << endl;
            continue;
        }
        if (m %(n+1) == 0)
        {
            cout << "none" << endl;
            continue;
        }
        else
        {
            cout << m%(n+1) << endl;
        }
    }

    return 0;
}