結果

問題 No.428 小数から逃げる夢
ユーザー 37zigen37zigen
提出日時 2017-09-05 05:26:34
言語 Java
(openjdk 23)
結果
AC  
実行時間 683 ms / 1,000 ms
コード長 9,464 bytes
コンパイル時間 2,969 ms
コンパイル使用メモリ 86,420 KB
実行使用メモリ 61,428 KB
最終ジャッジ日時 2024-11-06 21:32:59
合計ジャッジ時間 65,113 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
class Int {
long[] mag;
int sig = 0;
long long_mask = -1L;
long int_mask = long_mask >>> 32;
long radix = int_mask + 1;
int intLen = 0;
public Int(int v) {
intLen = v == 0 ? 0 : 1;
mag = new long[] { (long) Math.abs(v) };
sig = (int) Math.signum(v);
}
public Int(long v) {
if (v == 0) {
intLen = 0;
sig = 0;
mag = new long[] { 0 };
return;
}
sig = (int) Math.signum(v);
v = (long) (Math.abs(v));
intLen = (v >= (1L << 32)) ? 2 : 1;
mag = new long[] { int_mask & v, v >>> 32, };
}
// public Int(String str) {
// if (str.equals("0")) {
// mag = new long[] { 0 };
// return;
// }
// if (str.charAt(str.length() - 1) == '-') {
// sig = -1;
// }
// 1~9992^10> 10
// 100010
// 201310
// 2^10>10^3
// 2^(10/3)>10
// 1 2^(10/3)
// 2 2^(10/3)*2
// long numBits = (str.length() * 10 + 2) / 3;
// mag = new long[(int) numBits];
// for (int i = 0; i < str.length(); ++i) {
//
// add(new Int(str.charAt(i) - '0'));
// }
// }
void add(Int a) {
if (a.sig == 0) {
return;
}
if (sig * a.sig >= 0) {
unsignedAdd(a);
if (sig == 0) {
sig = a.sig;
}
} else {
Int u = a.copy();
u.sig *= -1;
sub(u);
}
}
void sub(Int a) {
if (a.sig == 0)
return;
if (sig != a.sig) {
unsignedAdd(a);
if (sig == 0) {
sig = (-1) * a.sig;
}
} else {
if (sig * compare(a) > 0) {
unsignedSub(a);
} else {
Int t = a.copy();
t.unsignedSub(this);
sig *= -t.sig;
mag = t.mag;
intLen = t.intLen;
}
}
}
void unsignedAdd(Int a) {
long res = 0;
if (mag.length < a.mag.length) {
mag = Arrays.copyOf(mag, a.mag.length);
}
intLen = Math.max(intLen, a.intLen);
for (int i = 0; i < a.intLen; ++i) {
long v = mag[i] + a.mag[i] + res;
mag[i] = int_mask & v;
res = v >>> 32;
}
for (int i = a.intLen; res != 0; ++i) {
if (i >= mag.length) {
mag = Arrays.copyOf(mag, 1 + mag.length);
}
long v = mag[i] + res;
mag[i] = int_mask & v;
res = v >>> 32;
intLen = Math.max(intLen, i + 1);
}
}
void unsignedSub(Int a) {
if (sig == 0) {
mag = Arrays.copyOf(a.mag, a.mag.length);
sig = -1 * a.sig;
}
long res = 0;
for (int i = 0; i < a.intLen; ++i) {
long t = mag[i] - a.mag[i] - res;
if (t < 0) {
res = 1;
t += radix;
} else {
res = 0;
}
mag[i] = t;
}
for (int i = a.intLen; res != 0; ++i) {
long t = mag[i] - res;
if (t < 0) {
res = 1;
t += radix;
} else {
res = 0;
}
mag[i] = t;
}
boolean f = false;
for (int i = intLen - 1; i >= 0; --i) {
if (mag[i] != 0) {
intLen = i + 1;
f = true;
break;
}
}
if (!f) {
sig = 0;
intLen = 0;
}
}
int compare(Int a) {
if (sig != a.sig) {
return Integer.compare(sig, a.sig);
}
if (intLen != a.intLen) {
return sig * Integer.compare(intLen, a.intLen);
}
for (int i = intLen - 1; i >= 0; --i) {
if (mag[i] == a.mag[i])
continue;
return sig * Long.compare(mag[i], a.mag[i]);
}
return 0;
}
void singleMul(Int a) {
if (intLen > 1 || a.intLen > 1) {
throw new AssertionError();
}
if (a.sig == 0) {
intLen = 0;
sig = 0;
mag = new long[] { 0 };
return;
}
long prd = mag[0] * a.mag[0];
mag[0] = int_mask & prd;
long res = prd >>> 32;
if (res > 0) {
++intLen;
mag = Arrays.copyOf(mag, 2);
mag[1] = res;
}
sig *= a.sig;
}
// n^1.58
void karatsuba(Int o) {
int len_ = Math.max(intLen, o.intLen);
if (len_ <= 1) {
singleMul(o);
return;
}
int Len = 1;
while (Len < len_) {
Len *= 2;
}
Int ret = new Int(0);
Int a = copy(Len / 2, Len);
Int b = copy(0, Len / 2);
Int c = o.copy(Len / 2, Len);
Int d = o.copy(0, Len / 2);
Int X = a.copy();
X.add(b);
Int Y = c.copy();
Y.add(d);
X.karatsuba(Y);
// (a*r+b)(c*r+d)
// (a+b)(c+d)r-(ac+bd)r+acr^2+db
// XYr -(Z+W)r+Zr^2+W;
// a=0b=1
X.shift(Len / 2);
ret.add(X);
Int Z = a.copy();
Z.karatsuba(c);
Int W = b.copy();
W.karatsuba(d);
ret.add(W);
Int tmp = Z.copy();
tmp.shift(Len);
ret.add(tmp);
Z.add(W);
Z.shift(Len / 2);
ret.sub(Z);
this.sig = ret.sig;
this.mag = Arrays.copyOf(ret.mag, ret.mag.length);
this.intLen = ret.intLen;
}
void div(Int b) {
if (b.sig == 0)
throw new ArithmeticException();
int nextsig = sig * b.sig;
sig = (int) (Math.abs(sig));
b.sig = (int) (Math.abs(b.sig));
if (compare(b) < 0) {
sig = 0;
mag = new long[] { 0 };
intLen = 0;
return;
}
Int M = new Int(1);
Int X = new Int(1);
M.shift(intLen + 3);
Int pre = X.copy();
while (true) {
Int tmp = X.copy();
tmp.karatsuba(tmp);
tmp.karatsuba(b);
tmp.shift(-M.intLen);
X.add(X);
X.sub(tmp);
if (X.compare(pre) == 0) {
break;
}
pre = X.copy();
}
X.karatsuba(this);
X.shift(-M.intLen);
mag = X.mag;
sig = nextsig;
intLen = X.intLen;
}
// num<<k;
void shift(int k) {
if (sig == 0)
return;
if (intLen + k <= 0) {
mag = new long[] { 0 };
sig = 0;
intLen = 0;
return;
}
Int u = copy();
mag = new long[intLen + k];
if (k >= 0)
System.arraycopy(u.mag, 0, mag, k, intLen);
else
System.arraycopy(u.mag, -k, mag, 0, intLen + k);
intLen += k;
// tr("shift", mag, intLen);
}
Int copy(int l, int r) {
Int a = copy();
a.mag = new long[r - l];
r = Math.min(r, a.intLen);
if (l >= r) {
return new Int(0);
}
System.arraycopy(mag, l, a.mag, 0, r - l);
a.intLen = r - l;
return a;
}
Int copy() {
Int ret = new Int(0);
ret.sig = sig;
ret.mag = Arrays.copyOf(mag, mag.length);
ret.intLen = intLen;
return ret;
}
void check() {
// v=0->sig==0
boolean f = true;
for (int i = 0; i < mag.length; ++i) {
f &= mag[i] == 0;
}
if (f && sig != 0) {
throw new AssertionError();
}
if (sig == 0)
return;
// intLen
f = mag[intLen - 1] > 0;
for (int i = mag.length - 1; i > intLen - 1; --i) {
f &= mag[i] == 0;
}
if (!f) {
throw new AssertionError();
}
}
void mod(Int mod) {
Int tmp = copy();
tmp.div(mod);
tmp.karatsuba(mod);
sub(mod);
}
ArrayList<Int> rs = new ArrayList<>();
// rs
String toString(int radix) {
if (sig == 0)
return "0";
rs.clear();
Int r = new Int(radix);
Int b = r.copy();
int cnt = 0;
rs.add(b.copy());
// rs.get(i) = b^{2^i}
// rs.back=b^{2^cnt} s.t b^{2^(cnt+1)}>=this
while (true) {
++cnt;
b.karatsuba(b);
rs.add(b.copy());
Int tmp = b.copy();
tmp.karatsuba(b);
if (tmp.compare(this) >= 0) {
break;
}
}
String str = toString(radix, cnt);
while (str.charAt(0) == '0') {
str = str.substring(1, str.length());
}
if (sig == -1)
str = "-" + str;
return str;
}
String toString(int radix, int cnt) {
if (intLen <= 1) {
if (radix == 10) {
return String.valueOf(mag[0]);
} else if (radix == 2) {
return Long.toBinaryString(mag[0]);
} else {
throw new AssertionError();
}
}
// radix==10
Int b = rs.get(cnt);
Int u = copy();
u.div(b);
Int l = copy();
u.rs = rs;
String us = u.toString(radix, cnt - 1);
while (us.length() < 1 << cnt) {
us = "0" + us;
}
u.karatsuba(b);
l.sub(u);
l.rs = rs;
String ls = l.toString(radix, cnt - 1);
while (ls.length() < 1 << cnt) {
ls = "0" + ls;
}
return us + ls;
}
long toLong() {
if (sig == 0) {
return 0;
}
if (intLen == 1) {
return sig * mag[0];
}
if (intLen == 2) {
return sig * (mag[0] + (mag[1] << 32));
}
throw new AssertionError();
}
String toStringRadix2() {
String ret = "";
if (sig == 0)
return "0";
if (mag[intLen - 1] == 0)
throw new AssertionError();
for (int i = 0; i < intLen; ++i) {
String s = Long.toBinaryString(mag[i]);
while (s.length() < 32) {
s = "0" + s;
}
ret = s + ret;
}
return ret;
}
}
public void run() {
Scanner sc = new Scanner(System.in);
String str = "0.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
            68697071727374757677787980818283848586878889909192939495969798991";
// 1e190
Int a = new Int(0);
for (int i = 2; i < str.length(); ++i) {
a.karatsuba(new Int(10));
a.add(new Int(str.charAt(i) - '0'));
}
Int n = new Int(sc.nextInt());
a.karatsuba(n);
String ans = a.toString(10);
if (ans.length() > 190) {
System.out.println(
ans.substring(0, ans.length() - 190) + "." + ans.substring(+ans.length() - 190, ans.length()));
} else {
System.out.println(
0 + "." + ans.substring(+ans.length() - 190, ans.length()));
}
}
public static void main(String[] args) throws FileNotFoundException {
new Main().run();
}
static void tr(Object... objects) {
System.out.println(Arrays.deepToString(objects));
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0