AOJ 1625: Origami, or the art of folding paper

競技プログラミング ICPC シミュレーション AOJ

問題

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1625&lang=jp

問題概要

幅 n, 高さ m の長方形の紙が与えられる. (n, m は32以下の正整数)

紙を t回折る操作をした後 p 回穴を開ける. (t, p は20 以下の正整数)

t 組の d_i, c_i が与えられ, 以下のように紙を折る. (d_i は 1 または 2, c_i は正整数)

  • d_i == 1 のとき

    • 左端から c_i だけ右側に紙を折る

  • d_i == 2 のとき

    • 下端から c_i だけ上側に紙を折る.

原点 (0, 0) は，紙の最終的な形での左下の点とする.

穴を開ける座標を表す p組の (x_i, y_i) が与えられる. x_i, y_i はともに非負整数であり, それぞれ, 最終的な形の幅と高さより小さい. その座標における紙の厚さを出力せよ.

解答例

指針

  • 実装を頑張る

解説

ICPC2018国内予選のB問題.

制約も小さくただシミュレーションをするだけのいわゆるやるだけの問題だが実装が結構きつい.

折り紙のデータを２次元配列で保持し, 状態をシミュレートする.

実装例

#include <iostream>

using namespace std;

const int max_v = 100;

int origami[max_v][max_v];
int tmp[max_v][max_v];

void copy() {
    for (int i = 0; i < max_v; i++) {
        for (int j = 0; j < max_v; j++) { tmp[i][j] = origami[i][j]; }
    }
}

// デバッグ用の関数
void show() {
    for (int i = 0; i < max_v; i++) {
        for (int j = 0; j < max_v; j++) {
            cout << origami[i][j] << " ";
        } 
        cout << endl;
    }
    cout << "-------------------" << endl;
}

// 右に折る
void fold_a(int c) {
    int t = c;
    for (int i = 0; i < c; i++) {
        for (int j = 0; j < max_v; j++) {
            origami[j][t+i] += origami[j][t-i-1];
            origami[j][t-i-1] = 0;
        }
    }

    copy();

    // 左につめる
    for (int i = 0; i < max_v; i++) {
        for (int j = 0; j < max_v; j++) {
            if (j-c < 0 || max_v-1 < j-c) { continue; }
            origami[i][j-c] = tmp[i][j];
        }
    }
}

// 上に折る
void fold_b(int c) {
    int t = max_v-c-1;
    for (int i = 0; i < max_v; i++) {
        for (int j = 0; j < c; j++) {
            origami[t-j][i] += origami[t+j+1][i];
            origami[t+j+1][i] = 0;
        }
    }

    copy();
    // 下につめる
    for (int i = 0; i < max_v; i++) {
        for (int j = 0; j < max_v; j++) {
            if (i+c < 0 || max_v-1 < i+c) { continue; }
            origami[i+c][j] = tmp[i][j];
        }
    }
}

int main() {
    int n, m, t, p;
    int d, c, x, y;

    while (cin >> n >> m >> t >> p) {
        if (!n && !m && !t && !p) { break; }

        for (int i = 0; i < max_v; i++) {
            for (int j = 0; j < max_v; j++) {
                origami[i][j] = 0;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                origami[max_v-j-1][i] = 1;
            }
        }

        for (int i = 0; i < t; i++) {
            cin >> d >> c;
            if (d == 1) { fold_a(c); }
            if (d == 2) { fold_b(c); }
        }
 
        for (int i = 0; i < p; i++) {
            cin >> x >> y;
            cout << origami[max_v-y-1][x] << endl;
        }
    }
    return 0;
}
  • Python3
#!/usr/bin/python3
# coding: utf-8

MAX_V = 100

# デバッグ用の関数
def show(origami):
    for i in range(MAX_V):
        for j in range(MAX_V):
            print(origami[i][j], end = " ")
        print()
    print("--------------------------------------")

# 右に c だけ折り返す処理
def fold_a(origami, c):
    t = c
    for i in range(c):
        for j in range(MAX_V):
            origami[j][t+i] += origami[j][t-i-1]
            origami[j][t-i-1] = 0

    copy = [x[:] for x in origami]

    for i in range(MAX_V):
        for j in range(MAX_V):
            if j-c < 0 or MAX_V-1 < j-c:
                continue
            origami[i][j-c] = copy[i][j]


# 上に c だけ折り返す処理
def fold_b(origami, c):
    t = MAX_V - c - 1
    for i in range(MAX_V):
        for j in range(c):
            origami[t-j][i] += origami[t+j+1][i]
            origami[t+j+1][i] = 0

    copy = [x[:] for x in origami]

    for i in range(MAX_V):
        for j in range(MAX_V):
            if i+c < 0 or MAX_V-1 < i+c:
                continue
            origami[i+c][j] = copy[i][j]


def main():
    while True:
        n, m, t, p = map(int, input().split())

        origami = [[0 for i in range(MAX_V)] for _ in range(MAX_V)]

        for i in range(n):
            for j in range(m):
                origami[-1-j][i] = 1

        if n == 0 and m == 0 and t == 0 and p == 0:
            break

        for _ in range(t):
            d, c = map(int, input().split())

            if d == 1:
                fold_a(origami, c)
            if d == 2:
                fold_b(origami, c)

        for _ in range(p):
            x, y = map(int, input().split())
            print(origami[MAX_V-y-1][x])

    return 0

main()

参考文献