結果

問題 No.2 素因数ゲーム
コンテスト
ユーザー バカらっく
提出日時 2017-06-25 14:27:15
言語 C#(csc)
(csc 3.9.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,877 bytes
コンパイル時間 3,736 ms
コンパイル使用メモリ 110,208 KB
実行使用メモリ 185,804 KB
最終ジャッジ日時 2024-12-26 13:13:34
合計ジャッジ時間 56,869 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30 WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        int num = int.Parse(Reader.ReadLine());
        CreatePrimeList(num);
        string ans = "Bob";
        if(IsWin(PrimeDevide(num).Select(a=>a.Value).OrderBy(a=>a).ToList())) {
            ans = "Alice";
        }
        Console.WriteLine(ans);
    }

    private Dictionary<int, int> PrimeDevide(int num) {
        int tmp = num;
        Dictionary<int, int> ret = new Dictionary<int, int>();
        int idx = 0;
        while(tmp>1) {
            if(tmp%PrimeList[idx]==0) {
                if(!ret.ContainsKey(PrimeList[idx])) {
                    ret.Add(PrimeList[idx], 1);
                } else {
                    ret[PrimeList[idx]]++;
                }
                tmp = tmp / PrimeList[idx];
            } else {
                idx++;
            }
        }
        return ret;
    }
    private void CreatePrimeList(int num) {
        bool[] flags = new bool[num + 1];
        List<int> list = new List<int>();
        for (int i = 2; i < flags.Length; i++) {
            if (flags[i]) {
                continue;
            }
            list.Add(i);
            int max = num / i;
            for (int j = 1; j <= max; j++) {
                flags[i * j] = true;
            }
        }
        this.PrimeList = list.ToArray();
    }

    private Dictionary<string, bool> dic = new Dictionary<string, bool>();
    private bool IsWin(List<int> list) {
        string key = string.Join("#", list);
        if(dic.ContainsKey(key)) {
            return dic[key];
        }
        if(list.Count == 0) {
            dic[key] = false;
            return false;
        }
        if(list.Count == 1) {
            dic[key] = true;
            return true;
        }
        bool canWin = false;
        int idx = -1;
        if (list.Any(a => a > 2))
        {
            idx = list.FindIndex(a => a > 2);
            List<int> subList = new List<int>(list);
            subList[idx] = 2;
            bool ret = IsWin(subList.OrderBy(a => a).ToList());
            if(!ret) {
                canWin = true;
            }
            if (!canWin) {
                subList = new List<int>(list);
                subList[idx] = 1;
                ret = IsWin(subList.OrderBy(a => a).ToList());
				if (!ret)
				{
					canWin = true;
				}
			}
            if(!canWin) {
				subList = new List<int>(list);
                subList.RemoveAt(idx);
				ret = IsWin(subList);
				if (!ret)
				{
					canWin = true;
				}

			}
        }
        if((!canWin) && list.Any(a=>a==2)) {
			idx = list.FindIndex(a => a == 2);
			List<int> subList = new List<int>(list);
			subList[idx] = 1;
			bool ret = IsWin(subList.OrderBy(a => a).ToList());
			if (!ret)
			{
				canWin = true;
			}
			if (!canWin)
			{
				subList = new List<int>(list);
				subList.RemoveAt(idx);
				ret = IsWin(subList);
				if (!ret)
				{
					canWin = true;
				}

			}

		}
		if ((!canWin) && list.Any(a => a == 1))
		{
			idx = list.FindIndex(a => a == 1);
			List<int> subList = new List<int>(list);
            subList.RemoveAt(idx);
			bool ret = IsWin(subList);
			if (!ret)
			{
				canWin = true;
			}
		}
        dic[key] = canWin;
        return canWin;
    }



    private int[] PrimeList;

    public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"





100000000




";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}
0