結果
| 問題 |
No.538 N.G.S.
|
| コンテスト | |
| ユーザー |
 くれちー
|
| 提出日時 | 2017-08-14 23:35:29 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 35 ms / 2,000 ms |
| コード長 | 8,578 bytes |
| コンパイル時間 | 2,664 ms |
| コンパイル使用メモリ | 120,400 KB |
| 実行使用メモリ | 19,584 KB |
| 最終ジャッジ日時 | 2024-09-25 00:23:04 |
| 合計ジャッジ時間 | 5,679 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 51 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Console;
using static System.Convert;
using static System.Math;
using static Extentions;
class IO
{
int idx;
string[] input = In.ReadToEnd().Split(new[] { " ", "\n", "\r" },
StringSplitOptions.RemoveEmptyEntries);
T Get<T>(Func<string, T> parser) => parser(input[idx++]);
public string S => Get(s => s);
public char C => Get(char.Parse);
public int I => Get(int.Parse);
public long L => Get(long.Parse);
public double F => Get(double.Parse);
public decimal D => Get(decimal.Parse);
public BigInteger B => Get(BigInteger.Parse);
T[] Gets<T>(int n, Func<string, T> parser)
=> input.Skip((idx += n) - n).Take(n).Select(parser).ToArray();
public string[] Ss(int n) => Gets(n, s => s);
public char[] Cs(int n) => Gets(n, char.Parse);
public int[] Is(int n) => Gets(n, int.Parse);
public long[] Ls(int n) => Gets(n, long.Parse);
public double[] Fs(int n) => Gets(n, double.Parse);
public decimal[] Ds(int n) => Gets(n, decimal.Parse);
public BigInteger[] Bs(int n) => Gets(n, BigInteger.Parse);
public void Write<T>(params T[] xs) => WriteLine(string.Join(" ", xs));
public void Write(params object[] xs) => WriteLine(string.Join(" ", xs));
}
interface IInteger<T>
{
T MinusOne { get; }
T One { get; }
T Zero { get; }
T Add(T left, T right);
int Compare(T left, T right);
T Divide(T dividend, T divisor);
T Multiply(T left, T right);
T Negate(T value);
T Remainder(T dividend, T divisor);
T Subtract(T left, T right);
}
static class Integer<T>
{
static IInteger<int> i = new IntOperations();
static IInteger<long> l = new LongOperations();
static IInteger<BigInteger> bi = new BigIntegerOperations();
public static IInteger<T> Default
{
get
{
if (typeof(T) == typeof(int)) return (IInteger<T>)i;
else if (typeof(T) == typeof(long)) return (IInteger<T>)l;
else if (typeof(T) == typeof(BigInteger)) return (IInteger<T>)bi;
else throw new NotSupportedException();
}
}
}
class IntOperations : IInteger<int>
{
public int MinusOne => -1;
public int One => 1;
public int Zero => 0;
public int Add(int left, int right) => checked(left + right);
public int Compare(int left, int right) => left.CompareTo(right);
public int Divide(int dividend, int divisor) => dividend / divisor;
public int Multiply(int left, int right) => checked(left * right);
public int Negate(int value) => checked(-value);
public int Remainder(int dividend, int divisor) => dividend % divisor;
public int Subtract(int left, int right) => checked(left - right);
}
class LongOperations : IInteger<long>
{
public long MinusOne => -1;
public long One => 1;
public long Zero => 0;
public long Add(long left, long right) => checked(left + right);
public int Compare(long left, long right) => left.CompareTo(right);
public long Divide(long dividend, long divisor) => dividend / divisor;
public long Multiply(long left, long right) => checked(left * right);
public long Negate(long value) => checked(-value);
public long Remainder(long dividend, long divisor) => dividend % divisor;
public long Subtract(long left, long right) => checked(left - right);
}
class BigIntegerOperations : IInteger<BigInteger>
{
public BigInteger MinusOne => BigInteger.MinusOne;
public BigInteger One => BigInteger.One;
public BigInteger Zero => BigInteger.Zero;
public BigInteger Add(BigInteger left, BigInteger right)
=> BigInteger.Add(left, right);
public int Compare(BigInteger left, BigInteger right)
=> BigInteger.Compare(left, right);
public BigInteger Divide(BigInteger dividend, BigInteger divisor)
=> BigInteger.Divide(dividend, divisor);
public BigInteger Multiply(BigInteger left, BigInteger right)
=> BigInteger.Multiply(left, right);
public BigInteger Negate(BigInteger value)
=> BigInteger.Negate(value);
public BigInteger Remainder(BigInteger dividend, BigInteger divisor)
=> BigInteger.Remainder(dividend, divisor);
public BigInteger Subtract(BigInteger left, BigInteger right)
=> BigInteger.Subtract(left, right);
}
struct Rational<T> : IComparable<Rational<T>>, IEquatable<Rational<T>>
{
T numer;
T denom;
public T Numer { get { this.Reduce(); return numer; } }
public T Denom { get { this.Reduce(); return denom; } }
IInteger<T> i;
public int Sign => i.Compare(numer, i.Zero) * i.Compare(denom, i.Zero);
public Rational(T numer, T denom)
{
this.numer = numer;
this.denom = denom;
i = Integer<T>.Default;
}
void Reduce()
{
if (i.Compare(numer, i.Zero) == 0) { denom = i.One; return; }
var d = Gcd(numer, denom, i);
numer = i.Divide(numer, d);
denom = i.Divide(denom, d);
if (i.Compare(denom, i.Zero) < 0)
{
numer = i.Negate(numer);
denom = i.Negate(denom);
}
}
public Rational<T> Invert() => new Rational<T>(denom, numer);
public static Rational<T> operator -(Rational<T> r)
=> new Rational<T>(r.i.Negate(r.numer), r.denom);
public static Rational<T> operator +(Rational<T> left, Rational<T> right)
{
var i = left.i;
left.Reduce(); right.Reduce();
var d = Lcm(left.denom, right.denom, i);
var n = i.Add(i.Divide(i.Multiply(left.numer, d), left.denom),
i.Divide(i.Multiply(right.numer, d), right.denom));
return new Rational<T>(n, d);
}
public static Rational<T> operator *(Rational<T> left, Rational<T> right)
{
var i = left.i;
left.Reduce(); right.Reduce();
var n = i.Multiply(left.numer, right.numer);
var d = i.Multiply(left.denom, right.denom);
return new Rational<T>(n, d);
}
public static Rational<T> operator -(Rational<T> left, Rational<T> right)
=> left + -right;
public static Rational<T> operator /(Rational<T> left, Rational<T> right)
=> left * right.Invert();
public static bool operator ==(Rational<T> left, Rational<T> right)
=> left.Equals(right);
public static bool operator !=(Rational<T> left, Rational<T> right)
=> !left.Equals(right);
public static bool operator <(Rational<T> left, Rational<T> right)
=> left.CompareTo(right) < 0;
public static bool operator >(Rational<T> left, Rational<T> right)
=> left.CompareTo(right) > 0;
public static bool operator <=(Rational<T> left, Rational<T> right)
=> left.CompareTo(right) <= 0;
public static bool operator >=(Rational<T> left, Rational<T> right)
=> left.CompareTo(right) >= 0;
public static implicit operator Rational<T>(T x)
=> new Rational<T>(x, Integer<T>.Default.One);
public int CompareTo(Rational<T> other) => (this - other).Sign;
public bool Equals(Rational<T> other)
{
var r = this / other;
return r.i.Compare(r.numer, r.denom) == 0;
}
public override bool Equals(object obj)
{
if (!(obj is Rational<T>)) return false;
var r = (Rational<T>)obj / this;
return r.i.Compare(r.numer, r.denom) == 0;
}
public override int GetHashCode()
=> this.Numer.GetHashCode() ^ this.Denom.GetHashCode();
public override string ToString() => $"{this.Numer}/{this.Denom}";
}
static partial class Extentions
{
public static T Gcd<T>(T x, T y, IInteger<T> integer)
{
T r;
while (integer.Compare((r = integer.Remainder(x, y)), integer.Zero)
!= 0) { x = y; y = r; }
return y;
}
public static T Lcm<T>(T x, T y, IInteger<T> integer)
=> integer.Multiply(integer.Divide(x, Gcd(x, y, integer)), y);
}
static class Program
{
public static void Main()
{
var sw = new StreamWriter(OpenStandardOutput()) { NewLine = "\n" };
#if DEBUG
sw.AutoFlush = true;
#else
sw.AutoFlush = false;
#endif
SetOut(sw);
Solve(new IO());
Out.Flush();
}
static void Solve(IO io)
{
var b = io.Ls(3);
var d = new Rational<long>(b[0] * b[2] - b[1] * b[1], b[0] - b[1]);
var r = b[0] != 0 ? -(d - b[1]) / b[0] : -(d - b[2]) / b[1];
io.Write((r * b[2] + d).Numer);
}
}