結果

問題 No.376 立方体のN等分 (2)
ユーザー EmKjpEmKjp
提出日時 2016-06-05 00:20:26
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 324 ms / 5,000 ms
コード長 5,470 bytes
コンパイル時間 2,091 ms
コンパイル使用メモリ 109,696 KB
実行使用メモリ 35,584 KB
最終ジャッジ日時 2024-11-06 21:52:57
合計ジャッジ時間 9,152 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 116 ms
35,328 KB
testcase_01 AC 118 ms
35,200 KB
testcase_02 AC 117 ms
35,328 KB
testcase_03 AC 118 ms
35,200 KB
testcase_04 AC 119 ms
35,072 KB
testcase_05 AC 119 ms
35,072 KB
testcase_06 AC 118 ms
35,328 KB
testcase_07 AC 118 ms
35,328 KB
testcase_08 AC 118 ms
35,456 KB
testcase_09 AC 118 ms
35,328 KB
testcase_10 AC 133 ms
35,200 KB
testcase_11 AC 118 ms
35,328 KB
testcase_12 AC 118 ms
35,072 KB
testcase_13 AC 118 ms
35,200 KB
testcase_14 AC 117 ms
35,200 KB
testcase_15 AC 119 ms
35,456 KB
testcase_16 AC 304 ms
35,328 KB
testcase_17 AC 120 ms
35,072 KB
testcase_18 AC 117 ms
35,456 KB
testcase_19 AC 120 ms
35,200 KB
testcase_20 AC 119 ms
35,328 KB
testcase_21 AC 317 ms
35,328 KB
testcase_22 AC 118 ms
35,328 KB
testcase_23 AC 317 ms
35,328 KB
testcase_24 AC 281 ms
35,456 KB
testcase_25 AC 117 ms
35,200 KB
testcase_26 AC 324 ms
35,328 KB
testcase_27 AC 119 ms
35,200 KB
testcase_28 AC 118 ms
35,200 KB
testcase_29 AC 116 ms
35,072 KB
testcase_30 AC 118 ms
35,328 KB
testcase_31 AC 117 ms
35,200 KB
testcase_32 AC 119 ms
35,200 KB
testcase_33 AC 119 ms
35,328 KB
testcase_34 AC 117 ms
35,200 KB
testcase_35 AC 118 ms
35,328 KB
testcase_36 AC 118 ms
35,328 KB
testcase_37 AC 118 ms
35,456 KB
testcase_38 AC 119 ms
35,584 KB
testcase_39 AC 117 ms
35,328 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.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;
partial class Solver {
public class Factor {
public long Prime;
public long Count;
public List<long> Pows = new List<long>();
}
public class PrimeSet : List<int> {
private bool[] isPrime;
public PrimeSet(int size)
: base() {
isPrime = Enumerable.Repeat(true, size).ToArray();
Add(2);
for (int i = 3; i <= size; i += 2) {
if (!isPrime[i >> 1]) continue;
Add(i);
for (long j = (long)i * i; j <= size; j += i + i)
isPrime[j >> 1] = false;
}
}
public bool IsPrime(long x) {
if (x == 2) return true;
if (x <= 1 || x % 2 == 0) return false;
return isPrime[x >> 1];
}
}
static public List<Factor> Factorization(PrimeSet primes, long x) {
var ret = new List<Factor>();
foreach (var p in primes) {
if (x % p == 0) {
int count = 0;
var factor = new Factor();
long pow = 1;
factor.Pows.Add(pow);
while (x % p == 0) {
count++;
x /= p;
pow *= p;
factor.Pows.Add(pow);
}
factor.Pows.Add(pow * p);
factor.Prime = p;
factor.Count = count;
ret.Add(factor);
}
}
if (x > 1) ret.Add(new Factor { Prime = x, Count = 1, Pows = new List<long> { 1, x } });
return ret;
}
//
long Solve(List<Factor> factors, int pos = 0, long a = 1, long b = 1, long c = 1) {
if (pos == factors.Count) {
return a + b + c - 3;
} else {
var prime = factors[pos].Prime;
var count = factors[pos].Count;
var pows = factors[pos].Pows;
long result = long.MaxValue;
for (int x = 0; x <= count; x++) {
for (int y = 0; x + y <= count; y++) {
int z = (int)(count - x - y);
var sa = x == 0 ? 1 : pows[x];
var sb = y == 0 ? 1 : pows[y];
var sc = z == 0 ? 1 : pows[z];
var sub = Solve(factors, pos + 1, a * sa, b * sb, c * sc);
result = Math.Min(sub, result);
}
}
return result;
}
}
public void Run() {
var N = nl();
long tmin = long.MaxValue, tmax = 0;
var primeSet = new PrimeSet(10000010);
var factors = Factorization(primeSet, N);
tmin = Solve(factors);
tmax = N - 1;
cout.WriteLine(string.Format("{0} {1}", tmin, tmax));
}
}
// PREWRITEN CODE BEGINS FROM HERE
partial class Solver : Scanner {
public static void Main(string[] args) {
new Solver(Console.In, Console.Out).Run();
}
TextReader cin;
TextWriter cout;
public Solver(TextReader reader, TextWriter writer)
: base(reader) {
this.cin = reader;
this.cout = writer;
}
public Solver(string input, TextWriter writer)
: this(new StringReader(input), writer) {
}
public int ni() { return NextInt(); }
public int[] ni(int n) { return NextIntArray(n); }
public long nl() { return NextLong(); }
public long[] nl(int n) { return NextLongArray(n); }
public double nd() { return NextDouble(); }
public string ns() { return Next(); }
public string[] ns(int n) { return NextArray(n); }
}
public class Scanner {
private TextReader Reader;
private Queue<String> TokenQueue = new Queue<string>();
private CultureInfo ci = CultureInfo.InvariantCulture;
public Scanner()
: this(Console.In) {
}
public Scanner(TextReader reader) {
this.Reader = reader;
}
public int NextInt() { return Int32.Parse(Next(), ci); }
public long NextLong() { return Int64.Parse(Next(), ci); }
public double NextDouble() { return double.Parse(Next(), ci); }
public string[] NextArray(int size) {
var array = new string[size];
for (int i = 0; i < size; i++) array[i] = Next();
return array;
}
public int[] NextIntArray(int size) {
var array = new int[size];
for (int i = 0; i < size; i++) array[i] = NextInt();
return array;
}
public long[] NextLongArray(int size) {
var array = new long[size];
for (int i = 0; i < size; i++) array[i] = NextLong();
return array;
}
public String Next() {
if (TokenQueue.Count == 0) {
if (!StockTokens()) throw new InvalidOperationException();
}
return TokenQueue.Dequeue();
}
public bool HasNext() {
if (TokenQueue.Count > 0)
return true;
return StockTokens();
}
private bool StockTokens() {
while (true) {
var line = Reader.ReadLine();
if (line == null) return false;
var tokens = line.Trim().Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
if (tokens.Length == 0) continue;
foreach (var token in tokens)
TokenQueue.Enqueue(token);
return true;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0