結果

問題 No.375 立方体のN等分 (1)
ユーザー 紙ぺーぱー
提出日時 2016-06-02 21:08:38
言語 C#
(csc 2.7.0.62620)
結果
AC  
実行時間 305 ms
コード長 5,858 Byte
コンパイル時間 788 ms
使用メモリ 8,716 KB
最終ジャッジ日時 2018-07-14 21:08:43

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 25 ms
8,684 KB
sample2.txt AC 25 ms
8,680 KB
system_test1.txt AC 31 ms
8,716 KB
t01.txt AC 25 ms
8,680 KB
t02.txt AC 25 ms
8,672 KB
t03.txt AC 25 ms
8,696 KB
t04.txt AC 25 ms
8,676 KB
t05.txt AC 27 ms
8,696 KB
t06.txt AC 44 ms
8,692 KB
t07.txt AC 27 ms
8,676 KB
t08.txt AC 28 ms
8,692 KB
t09.txt AC 28 ms
8,696 KB
t10.txt AC 28 ms
8,688 KB
t11.txt AC 28 ms
8,684 KB
t12.txt AC 80 ms
8,692 KB
t13.txt AC 30 ms
8,692 KB
t14.txt AC 29 ms
8,692 KB
t15.txt AC 174 ms
8,692 KB
t16.txt AC 79 ms
8,688 KB
t17.txt AC 30 ms
8,696 KB
t18.txt AC 30 ms
8,688 KB
t19.txt AC 30 ms
8,700 KB
t20.txt AC 305 ms
8,700 KB
t21.txt AC 31 ms
8,692 KB
t22.txt AC 31 ms
8,668 KB
t23.txt AC 34 ms
8,696 KB
t24.txt AC 30 ms
8,688 KB
t25.txt AC 31 ms
8,692 KB
t26.txt AC 31 ms
8,672 KB
t27.txt AC 30 ms
8,680 KB
t28.txt AC 31 ms
8,676 KB
t29.txt AC 31 ms
8,688 KB
t30.txt AC 31 ms
8,668 KB
t31.txt AC 31 ms
8,688 KB
テストケース一括ダウンロード
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 2.6.0.62309 (d3f6b8e7)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
using System;
using System.Linq;
using System.Linq.Expressions;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using System.Numerics;
using Point = System.Numerics.Complex;
using Number = System.Int32;
namespace Program
{
    public class Solver
    {
        public void Solve()
        {
            var n = sc.Long();
            var min = n - 1;
            var max = n - 1;
            var div = new List<long>();
            for (long i = 1; i * i <= n; i++)
            {
                if (n % i == 0)
                {
                    div.Add(i);
                    if (i != (n / i)) div.Add(n / i);
                }
            }
            div.Sort();
            var val = new long[div.Count, 3];
            for (int i = 0; i < div.Count; i++) val[i, 0] = val[i, 1] = val[i, 2] = div[i] - 1;
            for (int i = 0; i < div.Count; i++)
            {
                for (int j = i + 1; j < div.Count; j++)
                {
                    if (div[j] % div[i] != 0) continue;
                    var pos = div.BinarySearch(div[j] / div[i]);
                    if (pos == -1) Console.WriteLine(div[j] / div[i]);
                    val[j, 1] = Math.Min(val[j, 1], val[i, 0] + val[pos, 0]);
                    val[j, 2] = Math.Min(val[j, 2], val[i, 0] + val[pos, 1]);
                    val[j, 2] = Math.Min(val[j, 2], val[i, 1] + val[pos, 0]);
                }
            }

            Console.WriteLine("{0} {1}", val[div.Count - 1, 2], n - 1);
        }
        public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
        static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
        static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
    }
}
#region main
static class Ex
{
    static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); }
    static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); }
    static public void Main()
    {
        var solver = new Program.Solver();
        solver.Solve();
        Program.IO.Printer.Out.Flush();
    }
}
#endregion
#region Ex
namespace Program.IO
{
    using System.IO;
    using System.Text;
    using System.Globalization;
    public class Printer : StreamWriter
    {
        static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; }
        public static Printer Out { get; set; }
        public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
        public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
        public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { }
        public void Write<T>(string format, T[] source) { base.Write(format, source.OfType<object>().ToArray()); }
        public void WriteLine<T>(string format, T[] source) { base.WriteLine(format, source.OfType<object>().ToArray()); }
    }
    public class StreamScanner
    {
        public StreamScanner(Stream stream) { str = stream; }
        public readonly Stream str;
        private readonly byte[] buf = new byte[1024];
        private int len, ptr;
        public bool isEof = false;
        public bool IsEndOfStream { get { return isEof; } }
        private byte read()
        {
            if (isEof) return 0;
            if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } }
            return buf[ptr++];
        }
        public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; }

        public string Scan()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
                sb.Append(b);
            return sb.ToString();
        }
        public string ScanLine()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b != '\n'; b = (char)read())
                if (b == 0) break;
                else if (b != '\r') sb.Append(b);
            return sb.ToString();
        }
        public long Long()
        {
            if (isEof) return long.MinValue;
            long ret = 0; byte b = 0; var ng = false;
            do b = read();
            while (b != 0 && b != '-' && (b < '0' || '9' < b));
            if (b == 0) return long.MinValue;
            if (b == '-') { ng = true; b = read(); }
            for (; true; b = read())
            {
                if (b < '0' || '9' < b)
                    return ng ? -ret : ret;
                else ret = ret * 10 + b - '0';
            }
        }
        public int Integer() { return (isEof) ? int.MinValue : (int)Long(); }
        public double Double() { var s = Scan(); return s != "" ? double.Parse(s, CultureInfo.InvariantCulture) : double.NaN; }
        private T[] enumerate<T>(int n, Func<T> f)
        {
            var a = new T[n];
            for (int i = 0; i < n; ++i) a[i] = f();
            return a;
        }

        public char[] Char(int n) { return enumerate(n, Char); }
        public string[] Scan(int n) { return enumerate(n, Scan); }
        public double[] Double(int n) { return enumerate(n, Double); }
        public int[] Integer(int n) { return enumerate(n, Integer); }
        public long[] Long(int n) { return enumerate(n, Long); }
    }
}
#endregion
#region Edge
public struct Edge : IComparable<Edge>
{
    public int from, to;
    public int cost;
    public Edge(int f, int t, int v) : this() { from = f; to = t; cost = v; }
    public int CompareTo(Edge other)
    {
        return cost.CompareTo(other.cost);
    }
}
#endregion
0