結果

問題 No.101 ぐるぐる!あみだくじ!
ユーザー TatamoTatamo
提出日時 2016-12-13 18:11:38
言語 JavaScript
(node v21.7.1)
結果
AC  
実行時間 73 ms / 5,000 ms
コード長 2,140 bytes
コンパイル時間 38 ms
コンパイル使用メモリ 5,120 KB
実行使用メモリ 43,264 KB
最終ジャッジ日時 2024-10-13 00:04:58
合計ジャッジ時間 4,059 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 63 ms
39,168 KB
testcase_01 AC 69 ms
39,424 KB
testcase_02 AC 70 ms
39,424 KB
testcase_03 AC 67 ms
42,752 KB
testcase_04 AC 62 ms
42,752 KB
testcase_05 AC 65 ms
42,880 KB
testcase_06 AC 64 ms
42,880 KB
testcase_07 AC 63 ms
43,136 KB
testcase_08 AC 64 ms
42,752 KB
testcase_09 AC 70 ms
42,752 KB
testcase_10 AC 65 ms
42,880 KB
testcase_11 AC 70 ms
42,752 KB
testcase_12 AC 73 ms
42,880 KB
testcase_13 AC 71 ms
43,136 KB
testcase_14 AC 69 ms
42,880 KB
testcase_15 AC 70 ms
43,008 KB
testcase_16 AC 70 ms
43,136 KB
testcase_17 AC 67 ms
43,008 KB
testcase_18 AC 68 ms
42,752 KB
testcase_19 AC 66 ms
43,136 KB
testcase_20 AC 64 ms
42,880 KB
testcase_21 AC 65 ms
42,880 KB
testcase_22 AC 66 ms
42,752 KB
testcase_23 AC 69 ms
43,008 KB
testcase_24 AC 68 ms
42,880 KB
testcase_25 AC 69 ms
42,880 KB
testcase_26 AC 68 ms
43,008 KB
testcase_27 AC 69 ms
42,880 KB
testcase_28 AC 66 ms
42,880 KB
testcase_29 AC 69 ms
43,008 KB
testcase_30 AC 68 ms
43,264 KB
testcase_31 AC 66 ms
43,008 KB
testcase_32 AC 65 ms
42,880 KB
testcase_33 AC 70 ms
42,880 KB
testcase_34 AC 62 ms
39,296 KB
testcase_35 AC 62 ms
39,296 KB
testcase_36 AC 61 ms
39,296 KB
testcase_37 AC 65 ms
42,752 KB
testcase_38 AC 67 ms
42,752 KB
testcase_39 AC 65 ms
42,624 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

/// <reference path="./typings/index.d.ts" />
var Solver = (function () {
    function Solver(n, k, t) {
        this.n = n;
        this.k = k;
        this.t = t;
        this.edge = new Array(n);
    }
    Solver.prototype.gcd = function (x, y, z) {
        if (typeof z !== "undefined") {
            return this.gcd(this.gcd(x, y), z);
        }
        var result = x;
        var k = -1;
        var n = y;
        while (k != 0) {
            k = result % n;
            result = n;
            n = k;
        }
        return result;
    };
    Solver.prototype.lcm = function (x, y, z) {
        if (typeof z !== "undefined") {
            return this.lcm(this.lcm(x, y), z);
        }
        return x * y / this.gcd(x, y);
    };
    Solver.prototype.constructGraph = function () {
        var _loop_1 = function (i_1) {
            var to = i_1;
            this_1.t.forEach(function (v) {
                var l = v[0] - 1;
                var r = v[1] - 1;
                if (to == l) {
                    to = r;
                }
                else if (to == r) {
                    to = l;
                }
            });
            this_1.edge[i_1] = to;
        };
        var this_1 = this;
        for (var i_1 = 0; i_1 < this.n; i_1++) {
            _loop_1(i_1);
        }
    };
    Solver.prototype.solve = function () {
        var _this = this;
        this.constructGraph();
        var cycle = new Array(n);
        for (var i_2 = 0; i_2 < this.n; i_2++) {
            var c = 1;
            var now = this.edge[i_2];
            while (now != i_2) {
                now = this.edge[now];
                c++;
            }
            cycle[i_2] = c;
        }
        var result = cycle.reduce(function (l, r) {
            return _this.lcm(l, r);
        });
        console.log(result);
    };
    return Solver;
}());
var input = require("fs").readFileSync("/dev/stdin", "utf8");
input = input.split("\n");
var n, k;
n = +input.shift();
k = +input.shift();
var t = [];
for (var i = 0; i < k; i++) {
    t.push(input[i].split(" ").map(function (v) { return +v; }));
}
(new Solver(n, k, t)).solve();
0