結果

問題 No.2 素因数ゲーム
ユーザー バカらっくバカらっく
提出日時 2017-06-25 14:27:15
言語 C#(csc)
(csc 3.9.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,877 bytes
コンパイル時間 3,759 ms
コンパイル使用メモリ 108,544 KB
実行使用メモリ 190,216 KB
最終ジャッジ日時 2023-08-27 04:47:07
合計ジャッジ時間 46,656 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
21,856 KB
testcase_01 AC 70 ms
19,888 KB
testcase_02 AC 74 ms
21,976 KB
testcase_03 AC 75 ms
21,888 KB
testcase_04 AC 74 ms
19,912 KB
testcase_05 AC 75 ms
21,992 KB
testcase_06 AC 272 ms
46,276 KB
testcase_07 AC 334 ms
47,664 KB
testcase_08 AC 289 ms
47,912 KB
testcase_09 AC 3,087 ms
190,216 KB
testcase_10 AC 2,590 ms
167,856 KB
testcase_11 AC 1,189 ms
96,796 KB
testcase_12 AC 1,175 ms
100,844 KB
testcase_13 WA -
testcase_14 AC 168 ms
36,504 KB
testcase_15 AC 573 ms
68,580 KB
testcase_16 AC 1,717 ms
125,920 KB
testcase_17 AC 2,603 ms
173,396 KB
testcase_18 AC 2,827 ms
184,016 KB
testcase_19 AC 1,598 ms
118,336 KB
testcase_20 AC 2,171 ms
151,204 KB
testcase_21 AC 2,935 ms
184,804 KB
testcase_22 AC 2,703 ms
177,304 KB
testcase_23 AC 1,227 ms
102,744 KB
testcase_24 AC 2,821 ms
182,896 KB
testcase_25 AC 2,102 ms
141,932 KB
testcase_26 AC 1,423 ms
109,936 KB
testcase_27 AC 739 ms
69,452 KB
testcase_28 AC 1,642 ms
120,836 KB
testcase_29 AC 1,324 ms
106,416 KB
testcase_30 AC 1,239 ms
103,660 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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