UVA-512 Spreadsheet Tracking 解題紀錄

🔗 UVA-512 Spreadsheet Tracking

tags: 模擬(Simulation) 排序(Sorting)

範例程式碼已於 UVA、瘋狂程設(CPE) 上皆測試通過。

題意

試算表由多個 *儲存格(cells)*組成，這些儲存格按照 橫列(rows) 和 直行(columns) 排列。對於試算表可以進行以下操作：

• 插入橫列操作： $\text{IR} \enspace A \enspace x_1, x_2, \ldots ,x_A$
• 插入直行操作： $\text{IC} \enspace A \enspace x_1, x_2, \ldots ,x_A$
• 刪除橫列操作： $\text{DR} \enspace A \enspace x_1, x_2, \ldots ,x_A$
• 刪除直行操作： $\text{DC} \enspace A \enspace x_1, x_2, \ldots ,x_A$
• 交換操作： $\text{EX} \enspace r_1 \enspace c_1 \enspace r_2 \enspace c_2$

設計一個追蹤程式，用於確定在多次行和列的插入、刪除以及交換操作後，特定儲存格中數據的位置

思路：模擬(Simulation) + 排序(Sorting)

使用一個二維陣列來模擬試算表，由於要追蹤每個儲存格的位置，因此將每個元素的值初始化為起始的位置。接著根據操作來更新陣列，最後查詢特定儲存格的位置。

• 進行插入操作時，將新增的位置初始化為 $(0, 0)$ ，代表這個儲存格原本不存在，並更新 $r$ 或 $c$ 的值。
• 進行刪除操作時，將刪除的位置從陣列中移除，並更新 $r$ 或 $c$ 的值。
• 進行交換操作時，將位置 $(r_1, c_1)$ 和 $(r_2, c_2)$ 的元素值互換。

但需要注意，由於插入或刪除時可能包含多個位置，若先對前面的位置進行操作，後面的位置可能會因為前面的操作而改變，因此需要先對位置 由大到小排序 ，再進行操作。

查詢 $(x, y)$ 的位置時，只需要遍歷整個陣列，檢查是否有元素的值等於 $(x, y)$，若有則輸出其位置 $(i, j)$，否則輸出 GONE。

複雜度分析

• 時間複雜度：$\mathcal{O}((n + m) \cdot R \cdot C)$ ，其中 $n$ 為操作數，$m$ 為查詢數，$R$ 為在操作過程中最大的橫列數，$C$ 為在操作過程中最大的直行數。
• 空間複雜度：$\mathcal{O}(R \cdot C)$

PythonC++

import sys
def input(): return sys.stdin.readline().strip()
def print(val=""): sys.stdout.write(str(val) + '\n')

class Sheet():
    def __init__(self, r, c) -> None:
        self.r = r
        self.c = c
        self.tbl = [[(i+1, j+1) for j in range(c) ] for i in range(r)] # 1-based, original position
    def DR(self, target):
        for i in target:
            self.tbl.pop(i)
        self.r -= len(target)
    def DC(self, target):
        for row in self.tbl:
            for j in target:
                row.pop(j)
        self.c -= len(target)
    def IR(self, target):
        for i in target:
            self.tbl.insert(i, [(0, 0) for _ in range(self.c)])
        self.r += len(target)
    def IC(self, target):
        for row in self.tbl:
            for j in target:
                row.insert(j, (0, 0))
        self.c += len(target)
    def EX(self, pos):
        r1, c1, r2, c2 = pos
        self.tbl[r1][c1], self.tbl[r2][c2] = self.tbl[r2][c2], self.tbl[r1][c1]
    def query(self, x, y):
        for i in range(self.r):
            for j in range(self.c):
                if self.tbl[i][j] == (x, y):
                    return (i+1, j+1)
        return (0, 0)

kase = 1
while True:
    r, c = map(int, input().split())
    if r == 0 and c == 0:
        break
    sheet = Sheet(r, c)
    n = int(input()) # number of operations
    for _ in range(n):
        cmd, *args = input().split()
        args = list(map(lambda x: int(x)-1, args))
        if cmd != "EX": # sort in descending order
            args = sorted(args[1:], reverse=True) 

        if cmd == "DR":
            sheet.DR(args)
        elif cmd == "DC":
            sheet.DC(args)
        elif cmd == "IR":
            sheet.IR(args)
        elif cmd == "IC":
            sheet.IC(args)
        elif cmd == "EX":
            sheet.EX(args)
    
    if kase > 1: print()
    print(f"Spreadsheet #{kase}")
    kase += 1
    m = int(input()) # number of queries
    for _ in range(m):
        x, y = map(int, input().split())
        i, j = sheet.query(x, y)
        if i and j:
            print(f"Cell data in ({x},{y}) moved to ({i},{j})")
        else:
            print(f"Cell data in ({x},{y}) GONE")

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';

class Sheet {
    int r, c;
    vector<vector<pair<int, int>>> tbl;
public:
    Sheet(int r, int c) : r(r), c(c) {
        tbl = vector<vector<pair<int, int>>>(r, vector<pair<int, int>>(c));
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                tbl[i][j] = {i+1, j+1};
            }
        }
    }
    void DR(vector<int> target) {
        for (int i: target) {
            tbl.erase(tbl.begin()+i);
        }
        r -= target.size();
    }
    void DC(vector<int> target) {
        for (int i = 0; i < r; i++) {
            for (int j: target) {
                tbl[i].erase(tbl[i].begin()+j);
            }
        }
        c -= target.size();
    }
    void IR(vector<int> target) {
        for (int i: target) {
            tbl.insert(tbl.begin()+i, vector<pair<int, int>>(c, {0, 0}));
        }
        r += target.size();
    }
    void IC(vector<int> target) {
        for (int i = 0; i < r; i++) {
            for (int j: target) {
                tbl[i].insert(tbl[i].begin()+j, {0, 0});
            }
        }
        c += target.size();
    }
    void EX(vector<int> pos) {
        int r1 = pos[0], c1 = pos[1], r2 = pos[2], c2 = pos[3];
        swap(tbl[r1][c1], tbl[r2][c2]);
    }
    void query(int x, int y) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (tbl[i][j] == make_pair(x, y)) {
                    cout << "Cell data in (" << x << "," << y << ") moved to (" << i+1 << "," << j+1 << ")" << endl;
                    return;
                }
            }
        }
        cout << "Cell data in (" << x << "," << y << ") GONE" << endl;
        return;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int kase = 1, r, c, m, n, x, y, argc;
    while (cin >> r >> c && (r || c)){
        Sheet sheet(r, c);
        cin >> n;
        while (n--){
            // Read command
            string cmd;
            cin >> cmd;
            vector<int> args;
            if (cmd == "EX"){
                for (int i = 0; i < 4; i++){
                    cin >> x;
                    args.push_back(x-1);
                }
            } else {
                cin >> argc;
                for (int i = 0; i < argc; i++){
                    cin >> x;
                    args.push_back(x-1);
                }
            }
            // sort in descending order
            if (cmd != "EX"){
                sort(args.begin(), args.end(), greater<int>());
            }
            // Process command
            if (cmd == "DR") sheet.DR(args);
            else if (cmd == "DC") sheet.DC(args);
            else if (cmd == "IR") sheet.IR(args);
            else if (cmd == "IC") sheet.IC(args);
            else if (cmd == "EX") sheet.EX(args);
        }
        // Output & Query
        if (kase > 1) cout << endl;
        cout << "Spreadsheet #" << kase++ << endl;
        cin >> m;
        while (m--){
            cin >> x >> y;
            sheet.query(x, y);
        }
    }
    return 0;
}

---

寫在最後

Cover photo is remixed from @Ice maker, thanks for their work!