Submission #994871


Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.IO;
//using System.Diagnostics;

using Binary = System.Func<System.Linq.Expressions.ParameterExpression, System.Linq.Expressions.ParameterExpression, System.Linq.Expressions.BinaryExpression>;
using Unary = System.Func<System.Linq.Expressions.ParameterExpression, System.Linq.Expressions.UnaryExpression>;

class Program
{
    static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    static Scan sc = new Scan();
    const int M = 1000000007;
    const double eps = 1e-9;
    static readonly int[] dd = { 0, 1, 0, -1, 0 };
    static void Main()
    {
        // T = (N / p) + q(A + p ^ (1 / q))

        long n, a;
        sc.Multi(out n, out a);
        long l = 1, r = n / 2 + 1;
        long best = n;
        int c = 0;
        while (l < r - 2 && ++c < 50)
        {
            long lp = (l * 2 + r) / 3, rp = (l + r * 2) / 3;

            long lq = 1, rq = a == 0 ? n : n / a + 1;
            int cnt = 0;
            while (lq < rq - 2 && ++cnt < 50)
            {
                long mlq = (lq * 2 + rq) / 3, mrq = (lq + rq * 2) / 3;
                long llt = (n - 1) / lp + 1 + mlq * (a + (long)(Math.Pow(lp, 1 / (double)mlq) + 1 - eps));
                long rrt = (n - 1) / lp + 1 + mrq * (a + (long)(Math.Pow(lp, 1 / (double)mrq) + 1 - eps));
                if (llt < rrt)
                    rq = mrq;
                else if (llt > rrt)
                    lq = mlq;
            }
            long lt = long.MaxValue / 10;
            for (long i = lq; i <= rq; i++)
            {
                lt = Math.Min(lt, (n - 1) / lp + 1 + i * (a + (long)(Math.Pow(lp, 1 / (double)i) + 1 - eps)));
            }

            lq = 1; rq = a == 0 ? n : n / a + 1;
            cnt = 0;
            while (lq < rq - 2 && ++cnt < 50)
            {
                long mlq = (lq * 2 + rq) / 3, mrq = (lq + rq * 2) / 3;
                long llt = (n - 1) / rp + 1 + mlq * (a + (long)(Math.Pow(rp, 1 / (double)mlq) + 1 - eps));
                long rrt = (n - 1) / rp + 1 + mrq * (a + (long)(Math.Pow(rp, 1 / (double)mrq) + 1 - eps));
                if (llt < rrt)
                    rq = mrq;
                else if (llt > rrt)
                    lq = mlq;
            }
            long rt = long.MaxValue / 10;
            for (long i = lq; i <= rq; i++)
            {
                rt = Math.Min(rt, (n - 1) / rp + 1 + i * (a + (long)(Math.Pow(rp, 1 / (double)i) + 1 - eps)));
                if (rt < lt) break;
            }
            if (lt < rt)
                r = rp;
            else if (lt > rt)
                l = lp;


            best = Min(best, lt, rt);
        }
        for (long p = l; p <= r; p++)
        {

            long lq = 1, rq = a == 0 ? n : n / a + 1;
            int cnt = 0;
            while (lq < rq - 2 && ++cnt < 50)
            {
                long mlq = (lq * 2 + rq) / 3, mrq = (lq + rq * 2) / 3;
                long llt = (n - 1) / p + 1 + mlq * (a + (long)(Math.Pow(p, 1 / (double)mlq) + 1 - eps));
                long rrt = (n - 1) / p + 1 + mrq * (a + (long)(Math.Pow(p, 1 / (double)mrq) + 1 - eps));
                if (llt < rrt)
                    rq = mrq;
                else if (llt > rrt)
                    lq = mlq;
            }

            long lt = long.MaxValue / 10;
            for (long i = lq; i <= rq; i++)
            {
                lt = Math.Min(lt, (n - 1) / p + 1 + i * (a + (long)(Math.Pow(p, 1 / (double)i) + 1 - eps)));
            }

            best = Min(best, lt);
        }
        Prt(best);
        sw.Flush();
    }

    static void swap<T>(ref T a, ref T b) { var t = a; a = b; b = t; }
    static T Max<T>(params T[] a) => a.Max();
    static T Min<T>(params T[] a) => a.Min();
    static void DBG<T>(params T[] a) => Console.WriteLine(string.Join(" ", a));
    static void DBG(params object[] a) => Console.WriteLine(string.Join(" ", a));
    static void Prt<T>(params T[] a) => sw.WriteLine(string.Join(" ", a));
    static void Prt(params object[] a) => sw.WriteLine(string.Join(" ", a));
}
static class ex
{
    public static void swap<T>(this IList<T> a, int i, int j) { var t = a[i]; a[i] = a[j]; a[j] = t; }
    public static T[] copy<T>(this IList<T> a)
    {
        var ret = new T[a.Count];
        for (int i = 0; i < a.Count; i++) ret[i] = a[i];
        return ret;
    }
}
static class Operator<T>
{
    static readonly ParameterExpression x = Expression.Parameter(typeof(T), "x");
    static readonly ParameterExpression y = Expression.Parameter(typeof(T), "y");
    public static readonly Func<T, T, T> Add = Lambda(Expression.Add);
    public static readonly Func<T, T, T> Subtract = Lambda(Expression.Subtract);
    public static readonly Func<T, T, T> Multiply = Lambda(Expression.Multiply);
    public static readonly Func<T, T, T> Divide = Lambda(Expression.Divide);
    public static readonly Func<T, T> Plus = Lambda(Expression.UnaryPlus);
    public static readonly Func<T, T> Negate = Lambda(Expression.Negate);
    public static Func<T, T, T> Lambda(Binary op) => Expression.Lambda<Func<T, T, T>>(op(x, y), x, y).Compile();
    public static Func<T, T> Lambda(Unary op) => Expression.Lambda<Func<T, T>>(op(x), x).Compile();
}

class ScanCHK : Scan
{
    public new string Str { get { var s = Console.ReadLine(); if (s != s.Trim()) throw new Exception(); return s; } }
}
class Scan
{
    public int Int => int.Parse(Str);
    public long Long => long.Parse(Str);
    public double Double => double.Parse(Str);
    public string Str => Console.ReadLine().Trim();
    public int[] IntArr => StrArr.Select(int.Parse).ToArray();
    public long[] LongArr => StrArr.Select(long.Parse).ToArray();
    public double[] DoubleArr => StrArr.Select(double.Parse).ToArray();
    public string[] StrArr => Str.Split();
    bool eq<T, U>() => typeof(T).Equals(typeof(U));
    T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
    T cv<T>(string s) => eq<T, int>() ? ct<T, int>(int.Parse(s))
                       : eq<T, long>() ? ct<T, long>(long.Parse(s))
                       : eq<T, double>() ? ct<T, double>(double.Parse(s))
                       : eq<T, char>() ? ct<T, char>(s[0]) : ct<T, string>(s);
    public void Multi<T>(out T a) => a = cv<T>(Str);
    public void Multi<T, U>(out T a, out U b)
    { var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); }
    public void Multi<T, U, V>(out T a, out U b, out V c)
    { var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); }
    public void Multi<T, U, V, W>(out T a, out U b, out V c, out W d)
    { var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); }
    public void Multi<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e)
    { var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); e = cv<X>(ar[4]); }
}
class mymath
{
    public static long Mod = 1000000007;
    public static bool isprime(long a)
    {
        if (a < 2) return false;
        for (long i = 2; i * i <= a; i++) if (a % i == 0) return false;
        return true;
    }
    public static bool[] sieve(int n)
    {
        var p = new bool[n + 1];
        for (int i = 2; i <= n; i++) p[i] = true;
        for (int i = 2; i * i <= n; i++) if (p[i]) for (int j = i * i; j <= n; j += i) p[j] = false;
        return p;
    }
    public static List<int> getprimes(int n)
    {
        var prs = new List<int>();
        var p = sieve(n);
        for (int i = 2; i <= n; i++) if (p[i]) prs.Add(i);
        return prs;
    }
    public static long[][] E(int n)
    {
        var ret = new long[n][];
        for (int i = 0; i < n; i++) { ret[i] = new long[n]; ret[i][i] = 1; }
        return ret;
    }
    public static long[][] pow(long[][] A, long n)
    {
        if (n == 0) return E(A.Length);
        var t = pow(A, n / 2);
        if ((n & 1) == 0) return mul(t, t);
        return mul(mul(t, t), A);
    }
    public static long dot(long[] x, long[] y)
    {
        int n = x.Length;
        long ret = 0;
        for (int i = 0; i < n; i++) ret = (ret + x[i] * y[i]) % Mod;
        return ret;
    }
    public static long[][] trans(long[][] A)
    {
        int n = A[0].Length, m = A.Length;
        var ret = new long[n][];
        for (int i = 0; i < n; i++) { ret[i] = new long[m]; for (int j = 0; j < m; j++) ret[i][j] = A[j][i]; }
        return ret;
    }
    public static long[] mul(long[][] A, long[] x)
    {
        int n = A.Length;
        var ret = new long[n];
        for (int i = 0; i < n; i++) ret[i] = dot(x, A[i]);
        return ret;
    }
    public static long[][] mul(long[][] A, long[][] B)
    {
        int n = A.Length;
        var Bt = trans(B);
        var ret = new long[n][];
        for (int i = 0; i < n; i++) ret[i] = mul(Bt, A[i]);
        return ret;
    }
    public static long[] add(long[] x, long[] y)
    {
        int n = x.Length;
        var ret = new long[n];
        for (int i = 0; i < n; i++) ret[i] = (x[i] + y[i]) % Mod;
        return ret;
    }
    public static long[][] add(long[][] A, long[][] B)
    {
        int n = A.Length;
        var ret = new long[n][];
        for (int i = 0; i < n; i++) ret[i] = add(A[i], B[i]);
        return ret;
    }
    public static long pow(long a, long b)
    {
        if (a >= Mod) return pow(a % Mod, b);
        if (a == 0) return 0;
        if (b == 0) return 1;
        var t = pow(a, b / 2);
        if ((b & 1) == 0) return t * t % Mod;
        return t * t % Mod * a % Mod;
    }
    public static long inv(long a) => pow(a, Mod - 2);
    public static long gcd(long a, long b)
    {
        while (b > 0) { var t = a % b; a = b; b = t; }
        return a;
    }
    // a x + b y = gcd(a, b)
    public static long extgcd(long a, long b, out long x, out long y)
    {
        long g = a; x = 1; y = 0;
        if (b > 0) { g = extgcd(b, a % b, out y, out x); y -= a / b * x; }
        return g;
    }
    public static long lcm(long a, long b) => a * (b / gcd(a, b));
    public static long comb(int n, int r)
    {
        if (n < 0 || r < 0 || r > n) return 0;
        if (n - r < r) r = n - r;
        if (r == 0) return 1;
        if (r == 1) return n;
        int[] numer = new int[r], denom = new int[r];
        for (int k = 0; k < r; k++) { numer[k] = n - r + k + 1; denom[k] = k + 1; }
        for (int p = 2; p <= r; p++)
        {
            int piv = denom[p - 1];
            if (piv > 1)
            {
                int ofst = (n - r) % p;
                for (int k = p - 1; k < r; k += p) { numer[k - ofst] /= piv; denom[k] /= piv; }
            }
        }
        long ret = 1;
        for (int k = 0; k < r; k++) if (numer[k] > 1) ret = ret * numer[k] % Mod;
        return ret;
    }
}

Submission Info

Submission Time
Task E - Cookies
User riantkb
Language C# (Mono 4.6.2.0)
Score 0
Code Size 11120 Byte
Status WA
Exec Time 2103 ms
Memory 7128 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 0 / 500 0 / 500
Status
AC × 3
AC × 20
WA × 3
TLE × 4
AC × 25
WA × 3
TLE × 41
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
dataset1 sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt
dataset2 sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt, 02-25.txt, 02-26.txt, 02-27.txt, 02-28.txt, 02-29.txt, 02-30.txt, 02-31.txt, 02-32.txt, 02-33.txt, 02-34.txt, 02-35.txt, 02-36.txt, 02-37.txt, 02-38.txt, 02-39.txt, 02-40.txt
Case Name Status Exec Time Memory
01-01.txt TLE 2103 ms 7128 KB
01-02.txt TLE 2103 ms 7128 KB
01-03.txt WA 457 ms 7128 KB
01-04.txt TLE 2103 ms 7128 KB
01-05.txt AC 361 ms 6488 KB
01-06.txt TLE 2103 ms 7128 KB
01-07.txt AC 896 ms 7128 KB
01-08.txt WA 273 ms 6488 KB
01-09.txt AC 366 ms 7128 KB
01-10.txt AC 157 ms 5336 KB
01-11.txt WA 158 ms 5336 KB
01-12.txt AC 26 ms 3160 KB
01-13.txt AC 27 ms 3160 KB
01-14.txt AC 265 ms 5336 KB
01-15.txt AC 644 ms 7128 KB
01-16.txt AC 1177 ms 7128 KB
01-17.txt AC 193 ms 5336 KB
01-18.txt AC 26 ms 3032 KB
01-19.txt AC 26 ms 3032 KB
01-20.txt AC 26 ms 3032 KB
01-21.txt AC 26 ms 3032 KB
01-22.txt AC 26 ms 3032 KB
01-23.txt AC 26 ms 3032 KB
01-24.txt AC 26 ms 3032 KB
01-25.txt AC 26 ms 3032 KB
01-26.txt AC 26 ms 3160 KB
02-01.txt AC 26 ms 3032 KB
02-02.txt TLE 2103 ms 2528 KB
02-03.txt TLE 2103 ms 3296 KB
02-04.txt TLE 2103 ms 3936 KB
02-05.txt TLE 2103 ms 4576 KB
02-06.txt TLE 2103 ms 5088 KB
02-07.txt TLE 2103 ms 5600 KB
02-08.txt TLE 2103 ms 6112 KB
02-09.txt TLE 2103 ms 6624 KB
02-10.txt TLE 2103 ms 7128 KB
02-11.txt TLE 2103 ms 7128 KB
02-12.txt TLE 2103 ms 7128 KB
02-13.txt TLE 2103 ms 7128 KB
02-14.txt TLE 2103 ms 7128 KB
02-15.txt TLE 2103 ms 7128 KB
02-16.txt TLE 2103 ms 7128 KB
02-17.txt TLE 2103 ms 7128 KB
02-18.txt TLE 2103 ms 7128 KB
02-19.txt TLE 2103 ms 7128 KB
02-20.txt TLE 2103 ms 7128 KB
02-21.txt TLE 2103 ms 7128 KB
02-22.txt TLE 2103 ms 7128 KB
02-23.txt AC 27 ms 3288 KB
02-24.txt AC 27 ms 3288 KB
02-25.txt TLE 2103 ms 7128 KB
02-26.txt TLE 2103 ms 2528 KB
02-27.txt TLE 2103 ms 7128 KB
02-28.txt TLE 2103 ms 7128 KB
02-29.txt TLE 2103 ms 2528 KB
02-30.txt TLE 2103 ms 4320 KB
02-31.txt TLE 2103 ms 4704 KB
02-32.txt TLE 2103 ms 7128 KB
02-33.txt TLE 2103 ms 5216 KB
02-34.txt TLE 2103 ms 7128 KB
02-35.txt TLE 2103 ms 7128 KB
02-36.txt TLE 2103 ms 7128 KB
02-37.txt TLE 2103 ms 7128 KB
02-38.txt TLE 2103 ms 7128 KB
02-39.txt TLE 2103 ms 7128 KB
02-40.txt TLE 2103 ms 7128 KB
sample-01.txt AC 26 ms 3032 KB
sample-02.txt AC 27 ms 3288 KB
sample-03.txt AC 459 ms 7128 KB