結果

問題 No.620 ぐるぐるぐるりん
ユーザー 👑 hos.lyrichos.lyric
提出日時 2019-06-15 11:42:14
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 17 ms / 1,000 ms
コード長 4,084 bytes
コンパイル時間 2,674 ms
コンパイル使用メモリ 163,524 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-22 01:45:37
合計ジャッジ時間 4,251 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,948 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 1 ms
6,944 KB
testcase_13 AC 1 ms
6,944 KB
testcase_14 AC 1 ms
6,944 KB
testcase_15 AC 1 ms
6,944 KB
testcase_16 AC 1 ms
6,944 KB
testcase_17 AC 1 ms
6,944 KB
testcase_18 AC 1 ms
6,940 KB
testcase_19 AC 1 ms
6,940 KB
testcase_20 AC 1 ms
6,944 KB
testcase_21 AC 1 ms
6,940 KB
testcase_22 AC 1 ms
6,944 KB
testcase_23 AC 1 ms
6,944 KB
testcase_24 AC 1 ms
6,940 KB
testcase_25 AC 1 ms
6,944 KB
testcase_26 AC 17 ms
6,940 KB
testcase_27 AC 1 ms
6,940 KB
testcase_28 AC 17 ms
6,940 KB
testcase_29 AC 17 ms
6,940 KB
testcase_30 AC 17 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
  z[0] = (1, 0)
  z[i + 1] = [[1 + v, -w], [w, 1 + v]] z[i] + u[i]
  
  z[1] = r z[0] + u[0]
  z[2] = r^2 z[0] + r u[0] + u[1]
  ...
  
  minimize sum_i (x[i]^2 + y[i]^2) subject to
    sum_i (a[i] x[i] + b[i] y[i]) = e
    sum_i (c[i] x[i] + d[i] y[i]) = f
  
  h = sum_i (x[i]^2 + y[i]^2) - p (sum_i (a[i] x[i] + b[i] y[i]) - e) - q (sum_i (c[i] x[i] + d[i] y[i]) - f)
  0 = dh/dx[i] = 2 x[i] - a[i] p - c[i] q
  0 = dh/dy[i] = 2 y[i] - b[i] p - d[i] q
*/

import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.complex, std.container, std.math, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


int T;
real P, W, V, GX, GY;

void main() {
  try {
    for (; ; ) {
      const numCases = readInt();
      foreach (caseId; 0 .. numCases) {
        T = readInt();
        P = readReal();
        W = readReal();
        V = readReal();
        GX = readReal();
        GY = readReal();
        
        const real[][] r = [[1.0 + V, -W], [W, 1.0 + V]];
        auto rr = new real[][][](T + 1, 2, 2);
        rr[0] = [[1.0, 0.0], [0.0, 1.0]];
        foreach (i; 0 .. T) {
          foreach (j; 0 .. 2) foreach (k; 0 .. 2) {
            rr[i + 1][j][k] = 0.0;
          }
          foreach (j; 0 .. 2) foreach (l; 0 .. 2) foreach (k; 0 .. 2) {
            rr[i + 1][j][k] += rr[i][j][l] * r[l][k];
          }
        }
        
        /*
          x[i] = (1/2) (rr[T - 1 - i][0][0] p + rr[T - 1 - i][1][0] q)
          y[i] = (1/2) (rr[T - 1 - i][0][1] p + rr[T - 1 - i][1][1] q)
        */
        real[][] a = [[0.0, 0.0], [0.0, 0.0]];
        foreach (i; 0 .. T) {
          foreach (j; 0 .. 2) foreach (k; 0 .. 2) foreach (l; 0 .. 2) {
            a[j][k] += (rr[T - 1 - i][j][l] * rr[T - 1 - i][k][l]) / 2.0;
          }
        }
        real[] b = [GX, GY];
        foreach (j; 0 .. 2) {
          b[j] -= (rr[T][j][0] * 1.0 + rr[T][j][1] * 0.0);
        }
        
        const det = a[0][0] * a[1][1] - a[0][1] * a[1][0];
        const p = (b[0] * a[1][1] - a[0][1] * b[1]) / det;
        const q = (a[0][0] * b[1] - b[0] * a[1][0]) / det;
        debug {
          writeln(a, " ", [p, q], " ", b, "; ", a[0][0] * p + a[0][1] * q, " ", a[1][0] * p + a[1][1] * q);
        }
        auto ansX = new real[T];
        auto ansY = new real[T];
        foreach (i; 0 .. T) {
          ansX[i] = (rr[T - 1 - i][0][0] * p + rr[T - 1 - i][1][0] * q) / 2.0;
          ansY[i] = (rr[T - 1 - i][0][1] * p + rr[T - 1 - i][1][1] * q) / 2.0;
        }
        
        debug {
          real sum = 0.0;
          foreach (i; 0 .. T) {
            sum += ansX[i]^^2 + ansY[i]^^2;
          }
          writefln("P = %s; %s", P, sum);
          real x = 1.0, y = 0.0;
          foreach (i; 0 .. T) {
            const xx = x - y * W + x * V + ansX[i];
            const yy = y + x * W + y * V + ansY[i];
            x = xx;
            y = yy;
          }
          writefln("(GX, GY) = (%s, %s); (%s, %s)", GX, GY, x, y);
        }
        
        foreach (i; 0 .. T) {
          writefln("%.20f %.20f", ansX[i], ansY[i]);
        }
      }
    }
  } catch (EOFException e) {
  }
}
0