問題1: カーペットの重なり

会場の矩形エリア（平面直交座標系の第一象限と見なされます）にいくつかの矩形カーペットを敷きます。合計n枚のカーペットがあり、1からnまで番号が付けられています。これらのカーペットは、番号の小さい順に座標軸に平行に順次敷かれ、後から敷かれたカーペットが前に敷かれたカーペットの上に重なります。カーペットの敷き詰めが完了した後、組織者は地面の特定の点を最も上から覆っているカーペットの番号を知りたいと考えています。注意：矩形カーペットの境界と4つの頂点にある点もカーペットに覆われていると見なされます。

入力形式

入力はn+2行からなります。

第一行：整数n(0 ≤ n ≤ 10,000) - カーペットの総数

次のn行：i+1行目は番号iのカーペットの情報を表し、4つの正整数a, b, g, k(0 ≤ a, b, g, k ≤ 100,000)がスペースで区切られて含まれます。これらはそれぞれカーペットの左下の座標(a, b)およびx軸とy軸方向の長さを表します。

第n+2行：2つの正整数xとy - 調べたい地面の点の座標

出力形式

1行の出力：求めるカーペットの番号を表す整数。該当する点がカーペットで覆われていない場合は-1を出力します。

サンプル入力1

3
1 0 2 3
0 2 3 3
2 1 3 3
2 2

サンプル出力1

3

サンプル入力2

3
1 0 2 3
0 2 3 3
2 1 3 3
4 5

サンプル出力2

-1

制約

実行時間制限：1秒

解説

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector carpets(n, vector<int>(4));
    for(int i = 0; i < n; i++) {
        cin >> carpets[i][0] >> carpets[i][1] >> carpets[i][2] >> carpets[i][3];
    }
    
    int x, y;
    cin >> x >> y;
    
    int result = -1;
    for(int i = n-1; i >= 0; i--) {
        int left = carpets[i][0];
        int bottom = carpets[i][1];
        int right = left + carpets[i][2];
        int top = bottom + carpets[i][3];
        
        if(x >= left && x <= right && y >= bottom && y <= top) {
            result = i + 1;
            break;
        }
    }
    
    cout << result << endl;
    return 0;
}

問題2: ホテルの選択

麗江河畔にはn軒の特色あるホテルがあり、ホテルは位置の順序に従って1からnまで番号が付けられています。各ホテルは特定の色調で装飾されており（合計k種類、整数0~k-1で表されます）、各ホテルにはコーヒーショップが設置されています。各コーヒーショップにはそれぞれ最低消費額があります。

2人の観光客が麗江を旅行に行き、彼らは同じ色調が好きで、2つの異なるホテルに宿泊したいと決めました。夜、彼らはコーヒーショップでコーヒーを飲みたいと考えています。条件は、コーヒーショップが2人が宿泊するホテルの間（含む）にあり、かつコーヒーショップの最低消費額がp以下であることです。

彼らは、夜に最低消費額がp元以下のコーヒーショップで集まることを保証できる宿泊方案の総数を知りたいです。

入力形式

第一行：3つの整数n, k, p - ホテルの数、色調の数、許容できる最低消費額の最大値

次のn行：i+1行目は2つの整数がスペースで区切られて含まれ、それぞれi番目のホテルの装飾色調とコーヒーショップの最低消費額を表します。

出力形式

1行の出力：選択可能な宿泊方案の総数を表す整数。

サンプル入力1

5 2 3
0 5
1 3
0 2
1 4
1 5

サンプル出力1

3

制約

実行時間制限：1秒

ヒント

30%のデータに対して、n≤100

50%のデータに対して、n≤1,000

100%のデータに対して、2≤n≤200,000、0

解説

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k, p;
    cin >> n >> k >> p;
    
    vector> hotels(n);
    for(int i = 0; i < n; i++) {
        cin >> hotels[i].first >> hotels[i].second;
    }
    
    vector<int> count(k, 0);
    vector<int> prefix(k, 0);
    long long result = 0;
    
    for(int i = 0; i < n; i++) {
        int color = hotels[i].first;
        int cost = hotels[i].second;
        
        if(cost > p) {
            count[color]++;
        } else {
            for(int j = 0; j < k; j++) {
                prefix[j] += count[j];
                count[j] = 0;
            }
            prefix[color]++;
            result += prefix[color] - 1;
        }
    }
    
    cout << result << endl;
    return 0;
}

問題3: マヤ拼図ゲーム

Mayan puzzleは最近流行しているゲームです。ゲームのインターフェースは7行5列のボードで、いくつかのブロックが積み上げられています。ブロックは浮かせて置くことができず、最下段または他のブロックの上に置かれている必要があります。ゲームをクリアするとは、指定された手数内ですべてのブロックを消去することを指します。ブロックを消去するルールは以下の通りです：

1. 各手で、あるブロックを横方向（左または右）に1マスだけドラッグできます：ブロックをドラッグすると、ドラッグ後の位置（以下、目標位置と呼びます）にもブロックがある場合、2つのブロックは位置を交換します（図6から図7を参照）；目標位置にブロックがない場合、ドラッグされたブロックは元の縦列から抜き取られ、目標位置から落下します（図1と図2を参照）；
2. 任意の時点で、横行または縦列に同じ色のブロックが3つ以上連続している場合、それらは直ちに消去されます（図1から図3を参照）。

注意：

a) 同時に複数のブロックグループが消去条件を満たしている場合、複数のグループが同時に消去されます（例えば、以下の図4では、色1のブロック3つと色2のブロック3つが同時に消去され、最後に色2のブロック1つが残ります）。

b) 行と列の両方が消去条件を満たし、かつ行と列が同じブロックを共有している場合、行と列で消去条件を満たすすべてのブロックが同時に消去されます（以下の図5のような状況）。

3、ブロックが消去された後、消去された位置の上にあるブロックは落下します。落下後、新しいブロックの消去が発生する可能性があります。注意：落下の過程ではブロックの消去は発生しません。

図1から図3は、ボード上でブロックを移動した後のボードの変化を示しています。ボードの左下のブロックの座標は(0, 0)です。座標(3, 3)にあるブロックを左に移動した後、ゲームのインターフェースは図1から図2に示される状態に変わり、この時、縦列に色4のブロックが3つ連続しており、消去条件を満たしているため、色4のブロック3つを消去した後、上の色3のブロックが落下し、図3に示される状態が形成されます。

入力形式

第一行：正整数n - ゲームをクリアするために必要な手数

次の5行：7*5のゲームインターフェースを記述します。各行にはいくつかの整数がスペースで区切られて含まれ、各行は0で終わります。下から上へ各縦列のブロックの色番号を表します（色は10種類以下、1から順に番号が付けられ、同じ数字は同じ色を表します）。

入力データは、初期ボードに消去可能なブロックがないことを保証しています。

出力形式

解決方案がある場合、n行の出力を生成します。各行には3つの整数x, y, gが含まれ、スペースで区切られます。ここで(x, y)は移動するブロックの座標を表し、gは移動方向を表します。1は右への移動、-1は左への移動を表します。**複数の解がある場合、xを第一キー、yを第二キー、1を-1より優先し、辞書式順序最小の解を出力してください。** ゲームインターフェースの左下の座標は(0, 0)です。

解決方案がない場合、1行の出力を生成し、整数-1を含みます。

サンプル入力1

3
1 0
2 1 0
2 3 4 0
3 1 0
2 4 3 4 0

サンプル出力1

2 1 1
3 1 1
3 0 1

制約

実行時間制限：3秒

ヒント

サンプル入力のゲーム局面は図6から図11に示されています。順次移動する3手は：(2, 1)にあるセルを右に移動、(3, 1)にあるセルを右に移動、(3, 0)にあるセルを右に移動であり、最終的にボード上のすべてのブロックを消去できます。

データ規模：

30%のデータに対して、初期ボードのブロックはすべてボードの最下段にあります；

100%のデータに対して、0 < n ≤ 5。

解説

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int ROWS = 7;
const int COLS = 5;
const int MAX_COLORS = 10;

vector board(ROWS, vector<int>(COLS));

bool checkBoard() {
    vector<int> colorCount(MAX_COLORS, 0);
    for(int i = 0; i < ROWS; i++) {
        for(int j = 0; j < COLS; j++) {
            if(board[i][j] > 0) {
                colorCount[board[i][j]]++;
            }
        }
    }
    
    for(int color = 1; color < MAX_COLORS; color++) {
        if(colorCount[color] > 0 && colorCount[color] < 3) {
            return false;
        }
    }
    
    for(int i = 0; i < ROWS; i++) {
        for(int j = 0; j < COLS; j++) {
            if(board[i][j] != 0) {
                return false;
            }
        }
    }
    return true;
}

void dropColumn(int col) {
    int emptyRow = 0;
    while(emptyRow < ROWS && board[emptyRow][col] != 0) {
        emptyRow++;
    }
    
    for(int row = emptyRow + 1; row < ROWS; row++) {
        if(board[row][col] != 0) {
            board[emptyRow][col] = board[row][col];
            board[row][col] = 0;
            emptyRow++;
        }
    }
}

bool eliminateBlocks() {
    vector toEliminate(ROWS, vector<bool>(COLS, false));
    
    // Check horizontal matches
    for(int i = 0; i < ROWS; i++) {
        for(int j = 0; j <= COLS - 3; j++) {
            if(board[i][j] != 0 && 
               board[i][j] == board[i][j+1] && 
               board[i][j] == board[i][j+2]) {
                toEliminate[i][j] = toEliminate[i][j+1] = toEliminate[i][j+2] = true;
            }
        }
    }
    
    // Check vertical matches
    for(int j = 0; j < COLS; j++) {
        for(int i = 0; i <= ROWS - 3; i++) {
            if(board[i][j] != 0 && 
               board[i][j] == board[i+1][j] && 
               board[i][j] == board[i+2][j]) {
                toEliminate[i][j] = toEliminate[i+1][j] = toEliminate[i+2][j] = true;
            }
        }
    }
    
    bool eliminated = false;
    for(int j = 0; j < COLS; j++) {
        bool columnEliminated = false;
        for(int i = 0; i < ROWS; i++) {
            if(toEliminate[i][j]) {
                board[i][j] = 0;
                columnEliminated = eliminated = true;
            }
        }
        if(columnEliminated) {
            dropColumn(j);
        }
    }
    
    return eliminated;
}

void makeMove(int x, int y, int direction, int depth, vector& moves) {
    moves[depth][0] = x;
    moves[depth][1] = y;
    moves[depth][2] = direction;
    
    int newX = x;
    int newY = y + direction;
    
    swap(board[x][y], board[newX][newY]);
    
    for(int col = 0; col < COLS; col++) {
        dropColumn(col);
    }
    
    while(eliminateBlocks()) {
        for(int col = 0; col < COLS; col++) {
            dropColumn(col);
        }
    }
}

void dfs(int depth, int maxDepth, vector& moves) {
    if(checkBoard()) {
        for(int i = 0; i < depth; i++) {
            cout << moves[i][0] << " " << moves[i][1] << " " << moves[i][2] << endl;
        }
        exit(0);
    }
    
    if(depth >= maxDepth) {
        return;
    }
    
    vector boardCopy = board;
    
    for(int j = 0; j < COLS; j++) {
        for(int i = 0; i < ROWS; i++) {
            if(board[i][j] != 0 && j < COLS - 1 && board[i][j] != board[i][j+1]) {
                makeMove(i, j, 1, depth, moves);
                dfs(depth + 1, maxDepth, moves);
                board = boardCopy;
            }
            
            if(board[i][j] == 0 && j < COLS - 1 && board[i][j+1] != 0) {
                makeMove(i, j+1, -1, depth, moves);
                dfs(depth + 1, maxDepth, moves);
                board = boardCopy;
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    
    for(int j = 0; j < COLS; j++) {
        for(int i = 0; ; i++) {
            cin >> board[i][j];
            if(board[i][j] == 0) {
                break;
            }
        }
    }
    
    vector moves(n, vector<int>(3));
    dfs(0, n, moves);
    
    cout << "-1" << endl;
    return 0;
}