結果
問題 | No.509 塗りつぶしツール |
ユーザー |
![]() |
提出日時 | 2017-04-28 23:04:30 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 125 ms / 2,000 ms |
コード長 | 14,460 bytes |
コンパイル時間 | 2,769 ms |
コンパイル使用メモリ | 92,360 KB |
実行使用メモリ | 41,672 KB |
最終ジャッジ日時 | 2024-09-13 18:30:17 |
合計ジャッジ時間 | 7,351 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import java.awt.geom.Point2D;import java.io.IOException;import java.io.InputStream;import java.util.*;import java.util.function.BiFunction;import java.util.function.Function;import java.util.function.Supplier;public class Main {final static int INF = 1 << 28;final static long MOD = 1_000_000_007;final static double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;Scanner sc = new Scanner(System.in);public static void main(String[] args) {new Main().run();}void run() {int[] kaisu = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};String str = sc.next();long min = INF;long cnt = ((((long) str.length()) * 2) + 1);for (int i = 0; i < str.length(); ++i) {int v = str.charAt(i) - '0';cnt += kaisu[v];}min = Math.min(min, cnt);long dnt = 2 + (long) str.length();for (int i = 0; i < str.length(); ++i) {int v = str.charAt(i) - '0';dnt += kaisu[v] * 2;}min = Math.min(min, dnt);System.out.println(min);}int ni() {return Integer.parseInt(sc.next());}void debug(Object... os) {System.err.println(Arrays.deepToString(os));}/*** ユークリッドの互除法** @return a と b の最大公約数*/long gcd(long a, long b) {if (b == 0) {return a;}return gcd(b, a % b);}/*** 拡張ユークリッドの互除法** @return mx + ny = gcd(m, n)となるような(x, y)を返す*/Pair<Long, Long> gcd_ex(long m, long n) {long[][] mat = _gcd_ex(m, n);return new Pair<>(mat[0][0], mat[0][1]);}long[][] _gcd_ex(long m, long n) {if (n == 0) {return new long[][]{{1, 0}, {0, 1}};}long k = m / n;long[][] K = new long[][]{{0, 1}, {1, -k}};long[][] r = _gcd_ex(n, m % n);long[][] dst = new long[2][2];for (int y = 0; y < 2; ++y)for (int x = 0; x < 2; ++x)for (int i = 0; i < 2; ++i)dst[y][x] += r[y][i] * K[i][x];return dst;}/*** 繰り返し2乗法を用いたべき乗の実装** @return a^r (mod 1,000,000,007)*/long pow(long a, long r) {long sum = 1;while (r > 0) {if ((r & 1) == 1) {sum *= a;sum %= MOD;}a *= a;a %= MOD;r >>= 1;}return sum;}/*** 組み合わせ* O(n)** @return {}_nC_r*/long C(int n, int r) {long sum = 1;for (int i = n; 0 < i; --i) {sum *= i;sum %= MOD;}long s = 1;for (int i = r; 0 < i; --i) {s *= i;s %= MOD;}sum *= pow(s, MOD - 2);sum %= MOD;long t = 1;for (int i = n - r; 0 < i; --i) {t *= i;t %= MOD;}sum *= pow(t, MOD - 2);sum %= MOD;return sum;}/*** 黄金分割探索** @param left 下限* @param right 上限* @param f 探索する関数* @param comp 上に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue)* 下に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue).reversed()* @return 極値の座標x*/double goldenSectionSearch(double left, double right, Function<Double, Double> f, Comparator<Double> comp) {double c1 = divideInternally(left, right, 1, GOLDEN_RATIO);double c2 = divideInternally(left, right, GOLDEN_RATIO, 1);double d1 = f.apply(c1);double d2 = f.apply(c2);while (right - left > 1e-9) {if (comp.compare(d1, d2) > 0) {right = c2;c2 = c1;d2 = d1;c1 = divideInternally(left, right, 1, GOLDEN_RATIO);d1 = f.apply(c1);} else {left = c1;c1 = c2;d1 = d2;c2 = divideInternally(left, right, GOLDEN_RATIO, 1);d2 = f.apply(c2);}}return right;}/*** [a,b]をm:nに内分する点を返す*/double divideInternally(double a, double b, double m, double n) {return (n * a + m * b) / (m + n);}/*** http://alexbowe.com/popcount-permutations/* bitの立っている数が小さい順にループしたいときに使う。* ex)* <pre>* for (int i = 0; i < 25; ++i) {* int bits = (1 << i) - 1;* long m = C(25, num);* for (j = 0; j < m; ++j) {* ...(25個の中からi個bitが立っている)* if (bits != 0)* bits = next_perm(bits);* }* }* </pre>** @param v 現在のbit列* @return 次のbit列*/int next_perm(int v) {int t = (v | (v - 1)) + 1;return t | ((((t & -t) / (v & -v)) >> 1) - 1);}/*** from http://gihyo.jp/dev/serial/01/geometry part 6*/static class Line {double a;double b;double c;/*** 一般形のパラメータから直線を作成する** @param a xの係数* @param b yの係数* @param c 定数項*/Line(double a, double b, double c) {this.a = a;this.b = b;this.c = c;}/*** 2点(x1, y1), (x2, y2)を通る直線を作成する** @param x1 1点目のx座標* @param y1 1点目のy座標* @param x2 2点目のx座標* @param y2 2点目のy座標* @return 直線*/static Line fromPoints(double x1, double y1, double x2, double y2) {double dx = x2 - x1;double dy = y2 - y1;return new Line(dy, -dx, dx * y1 - dy * x1);}/*** 与えられた直線との交点を返す** @param l 直線* @return 交点。2直線が平行の場合はnull*/Point2D getIntersectionPoint(Line l) {double d = a * l.b - l.a * b;if (d == 0.0) {return null;}double x = (b * l.c - l.b * c) / d;double y = (l.a * c - a * l.c) / d;return new Point2D.Double(x, y);}@Overridepublic String toString() {return "a = " + a + ", b = " + b + ", c = " + c;}}/*** from http://gihyo.jp/dev/serial/01/geometry part 6*/static public class LineSegment {double x1;double y1;double x2;double y2;LineSegment(double x1, double y1, double x2, double y2) {this.x1 = x1;this.y1 = y1;this.x2 = x2;this.y2 = y2;}Line toLine() {return Line.fromPoints(x1, y1, x2, y2);}boolean intersects(Line l) {double t1 = l.a * x1 + l.b * y1 + l.c;double t2 = l.a * x2 + l.b * y2 + l.c;return t1 * t2 <= 0;}boolean intersects(LineSegment s) {return bothSides(s) && s.bothSides(this);}// sが自線分の「両側」にあるかどうかを調べるprivate boolean bothSides(LineSegment s) {double ccw1 = GeomUtils.ccw(x1, y1, s.x1, s.y1, x2, y2);double ccw2 = GeomUtils.ccw(x1, y1, s.x2, s.y2, x2, y2);if (ccw1 == 0 && ccw2 == 0) { // sと自線分が一直線上にある場合// sのいずれか1つの端点が自線分を内分していれば、sは自線分と共有部分を持つので// trueを返すreturn internal(s.x1, s.y1) || internal(s.x2, s.y2);} else { // それ以外の場合// CCW値の符号が異なる場合にtrueを返すreturn ccw1 * ccw2 <= 0;}}// (x, y)が自線分を内分しているかどうかを調べるprivate boolean internal(double x, double y) {// (x, y)から端点に向かうベクトルの内積がゼロ以下であれば内分と見なすreturn GeomUtils.dot(x1 - x, y1 - y, x2 - x, y2 - y) <= 0;}public Point2D getIntersectionPoint(Line l) {if (!intersects(l)) {return null; // 交差しない場合はnullを返す}return l.getIntersectionPoint(toLine());}public Point2D getIntersectionPoint(LineSegment s) {if (!intersects(s)) {return null; // 交差しない場合はnullを返す}return s.toLine().getIntersectionPoint(toLine());}@Overridepublic String toString() {return "(" + x1 + ", " + y1 + ") - (" + x2 + ", " + y2 + ")";}}/*** from http://gihyo.jp/dev/serial/01/geometry part 6*/static class GeomUtils {static double cross(double x1, double y1, double x2, double y2) {return x1 * y2 - x2 * y1;}static double dot(double x1, double y1, double x2, double y2) {return x1 * x2 + y1 * y2;}// (x1, y1) -> (x2, y2) -> (x3, y3) と進む道のりが半時計回りの場合は正の値、// 時計回りの場合は負の値、一直線上の場合はゼロを返すstatic double ccw(double x1, double y1, double x2, double y2,double x3, double y3) {return cross(x2 - x1, y2 - y1, x3 - x2, y3 - y2);}static double ccw(Point2D p1, Point2D p2, Point2D p3) {return ccw(p1.getX(), p1.getY(), p2.getX(), p2.getY(), p3.getX(), p3.getY());}}/*** http://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b*/static class FastScanner {private final InputStream in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;public FastScanner(InputStream in) {this.in = in;}private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}private boolean hasNextByte() {if (ptr < buflen) {return true;} else {ptr = 0;try {buflen = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (buflen <= 0) {return false;}}return true;}private int readByte() {if (hasNextByte()) return buffer[ptr++];else return -1;}private void skipUnprintable() {while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}public boolean hasNext() {skipUnprintable();return hasNextByte();}public String next() {if (!hasNext()) throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public long nextLong() {if (!hasNext()) throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while (true) {if ('0' <= b && b <= '9') {n *= 10;n += b - '0';} else if (b == -1 || !isPrintableChar(b)) {return minus ? -n : n;} else {throw new NumberFormatException();}b = readByte();}}}static class Pair<F extends Comparable<F>, S extends Comparable<S>> implements Comparable<Pair<F, S>> {F f;S s;Pair() {}Pair(F f, S s) {this.f = f;this.s = s;}Pair(Pair<F, S> p) {f = p.f;s = p.s;}@Overridepublic int compareTo(Pair<F, S> p) {if (f.compareTo(p.f) != 0) {return f.compareTo(p.f);}return s.compareTo(p.s);}@Overridepublic int hashCode() {return f.hashCode() ^ s.hashCode();}@Overridepublic boolean equals(Object o) {if (this == o) {return true;}if (o == null || this.f == null || this.s == null) {return false;}if (this.getClass() != o.getClass()) {return false;}Pair p = (Pair) o;return this.f.equals(p.f) && this.s.equals(p.s);}@Overridepublic String toString() {return "{" + f.toString() + ", " + s.toString() + "}";}}class BIT<T> {int n;ArrayList<T> bit;BiFunction<T, T, T> bif;/*** 1-indexed なBinary Indexed Treeを構築する** @param n 容量* @param bif 適用させる関数* @param sup 初期値*/BIT(int n, BiFunction<T, T, T> bif, Supplier<T> sup) {this.n = n;bit = new ArrayList<>(n + 1);for (int i = 0; i < n + 1; ++i) {bit.add(sup.get());}this.bif = bif;}/*** iの位置の値をvで更新する** @param i index* @param v 新しい値*/void set(int i, T v) {for (int x = i; x <= n; x += x & -x) {bit.set(x, bif.apply(bit.get(x), v));}}/*** クエリー** @param defaultValue 初期値* @param i index* @return [1, i]までfを適用した結果*/T reduce(T defaultValue, int i) {T ret = defaultValue;for (int x = i; x > 0; x -= x & -x) {ret = bif.apply(ret, bit.get(x));}return ret;}}class SegmentTree<T> {int n;ArrayList<T> dat;BiFunction<T, T, T> bif;Supplier<T> sup;/*** 0-indexed なSegment Treeを構築する** @param n_ 要求容量* @param bif 適用させる関数* @param sup 初期値*/SegmentTree(int n_, BiFunction<T, T, T> bif, Supplier<T> sup) {n = 1;while (n < n_) n *= 2;dat = new ArrayList<>(2 * n - 1);for (int i = 0; i < 2 * n - 1; ++i) {dat.add(sup.get());}this.bif = bif;this.sup = sup;}/*** kの位置の値をvで更新する** @param k index* @param v 新しい値*/void set(int k, T v) {k += n - 1;dat.set(k, v);while (k > 0) {k = (k - 1) / 2;dat.set(k, bif.apply(dat.get(k * 2 + 1), dat.get(k * 2 + 2)));}}/*** クエリー** @param l はじめ* @param r おわり* @return [l, r)での演算bifを適用した結果を返す*/T reduce(int l, int r) {return _reduce(l, r, 0, 0, n);}T _reduce(int a, int b, int k, int l, int r) {if (r <= a || b <= l) return sup.get();if (a <= l && r <= b) return dat.get(k);T vl = _reduce(a, b, k * 2 + 1, l, (l + r) / 2);T vr = _reduce(a, b, k * 2 + 2, (l + r) / 2, r);return bif.apply(vl, vr);}}}