Simulation Problems - Забони барномасозии C++ барои барномасозии рақобатӣ

Week 10Stacks, Queues, Deques and Simulation Problems

Simulation Problems

Doing exactly what the statement says: choosing the container from the story, a card game with two queues, a railway siding that is a stack, clocks that jump, and a checklist for long simulations.

Назария
Дарси 5 аз 7
Хониш: 21 дақиқа
Саволҳо: 5

Some problems hide no clever idea at all. The statement describes a process — a card game, a printer, a railway yard — and asks what happens in the end. To solve one, make the program do exactly what the statement says, step by step, in the same order. That is a simulation.

The thinking goes into two questions: how to keep the state of the process, and how not to get a single detail wrong. Stacks, queues and deques answer the first question surprisingly often.

Choose the container from the story

The wording of a statement usually names the container for you:

The statement says…	Keep it in
"in the order they arrived", "a line", "takes turns", "goes to the back"	`queue`
"on top", "the most recent", "the last one placed", "undo"	`stack`
"at either end", "the leftmost or the rightmost"	`deque`
"the k-th one", "any position"	`vector`

A card game: two decks, two queues

Two players each hold a deck; all the cards are different. In every fight both turn over their top card; the higher card wins, and its owner puts first the beaten card, then their own at the bottom of their deck. Whoever runs out of cards loses. Print the number of fights and the winner, 1 or 2 — or -1 if the game never ends.

Input

Output

Top cards come from the front, won cards go to the back: each deck is a queue.

навбатӣ

Practice: Simulation Problems

Four simulations, from one gate to a whole spaceport.

Дарси навбатӣ

Дарси пешина Ба харитаи курс

3 6 1 4
2 2 5

-1

5
2 4 1 3 5

NO

6 7 13 22

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    queue<int> a, b;                          // each deck: the top card is the front
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        a.push(x);
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        b.push(x);
    }
    int fights = 0;
    while (!a.empty() && !b.empty() && fights < 1000000) {
        int x = a.front(), y = b.front();
        a.pop();
        b.pop();
        if (x > y) {
            a.push(y);                        // the beaten card first...
            a.push(x);                        // ...then the winner's own
        } else {
            b.push(x);
            b.push(y);
        }
        fights++;
    }
    if (b.empty()) {
        cout << fights << " 1\n";
    } else if (a.empty()) {
        cout << fights << " 2\n";
    } else {
        cout << "-1\n";                       // still going: the game loops forever
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> want(n);
    for (int i = 0; i < n; i++) {
        cin >> want[i];
    }
    stack<int> siding;
    int arriving = 1;                         // the next car still to arrive
    bool ok = true;
    for (int i = 0; i < n; i++) {
        while (arriving <= want[i]) {
            siding.push(arriving);            // drive cars in until want[i] is there
            arriving++;
        }
        if (siding.top() == want[i]) {
            siding.pop();                     // it is on top: it can leave
        } else {
            ok = false;                       // it is buried under another car
            break;
        }
    }
    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<pair<int, int>> jobs(n);           // (arrival minute, pages), as they were given
    for (int i = 0; i < n; i++) {
        cin >> jobs[i].first >> jobs[i].second;
    }
    sort(jobs.begin(), jobs.end());           // in order of arrival
    queue<pair<int, int>> line;               // the jobs waiting for the printer
    for (int i = 0; i < n; i++) {
        line.push(jobs[i]);
    }
    long long t = 0;                          // when the printer is free again
    while (!line.empty()) {
        pair<int, int> job = line.front();    // the printer takes the front job
        line.pop();
        t = max(t, (long long)job.first);     // an idle printer waits for the job
        t += job.second;                      // one page a minute
        cout << t << " ";
    }
    cout << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long c, T;
    cin >> n >> c >> T;
    vector<long long> d(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i] >> b[i];                  // on day d[i], b[i] buckets of rain
    }
    long long water = 0, pumped = 0;
    for (int i = 0; i < n; i++) {
        water += b[i];
        long long until = (i + 1 < n) ? d[i + 1] : T + 1;   // the next event
        long long out = min(water, (until - d[i]) * c);     // all the quiet days at once
        pumped += out;
        water -= out;
    }
    cout << pumped << "\n";
    return 0;
}