KDP/Regioni

Izvor: SI Wiki
Pređi na navigaciju Pređi na pretragu

Regioni su oblast konkurentnog programiranja iz drugog bloka nastave i dolaze na drugom kolokvijumu za SI i kolokvijumu za RTI.




Jun 2020, 4. zadatak

Debug: KDP/Jun 2020 4. zadatak
Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

U nekom obdaništu postoji pravilo koje kaže da se na svaka tri deteta mora naći barem jedna vaspitačica (The Child Care Problem). Roditelj dovodi jedno ili više dece u obdanište i čeka sve dok se ne pojavi mesto, kako bi ostavio svu decu odjednom i otišao. Roditelj takođe može da odvede jedno ili više dece, takođe odjednom. Vaspitačica dolazi na posao i sme da napusti obdanište samo ukoliko to ne narušava pravilo. Mora se poštovati redosled dolaska roditelja koji ostavljaju decu i vaspitačica koje odlaze sa posla. Koristeći uslovne kritične regione, napisati procedure za roditelje koji dovode decu, roditelje koji odvode decu, vaspitačice koje dolaze na posao i vaspitačice koje odlaze sa posla. Inicijalizovati početne uslove.

Rešenje

Jun 2021, 2. zadatak

Debug: KDP/Jun 2021 2. zadatak

Postavka

Posmatra se agencija za iznajmljivanje automobila. U voznom parku postoje 20 standardnih vozila i 10 luks vozila. Prilikom dolaska klijenta da iznajmi auto, on se izjašnjava da li želi da iznajmi standardno ili luks vozilo ili mu je sve jedno. Nakon toga on čeka u redu sve dok mu se vozilo ne dodeli na korišćenje. Po završetku korišćenja, korisnik dolazi još jednom u agenciju i vraća auto. U agenciji postoji jedan zaposleni koji vodi evidenciju o tome koji auto je trenutno na korišćenju kod kog korisnika. Klijentima nije dozvoljeno napuštanje agencije sve dok zaposleni ne obradi njihov zahtev za preuzimanje ili vraćanje vozila. Koristeći regione napisati metodu koje se poziva prilikom dolaska klijenta da iznajmi auto, metodu koje se poziva prilikom dolaska klijenta da vrati auto i metodu koja simulira rad zaposlenog, kao i kod za inicijalizaciju. Potrebno je obezbediti da vozila ne stoje na parkingu agencije, ukoliko postoji bilo koji klijent koji želi da iznajmi taj tip vozila.

Rešenje

#include <map>
#include <queue>

using namespace std;

// Структуре за упућивање захтева запосленом
struct Request {
    int customerId;
    unsigned place;
};
enum RequestType {
    STANDARD_VEHICLE,
    LUXURY_VEHICLE,
    ANY_VEHICLE,
    RETURN_VEHICLE
};

// Монитор
struct CarDealership {
    queue<Request> standardRequests;
    queue<Request> luxuryRequests;
    queue<Request> anyRequests;
    queue<Request> returnRequests;
    map<int, int> rentedCars;
    int place = 1;
};
CarDealership dealership;

// Ова два реда се мењају само из запосленог, тако да не морају да буду у региону.
queue<int> standardCars;
queue<int> luxuryCars;

int rentCar(int customerId, int which) {
    region (dealership) {
        unsigned myPlace = dealership.place++;
        switch (which) {
            case STANDARD_VEHICLE:
                dealership.standardRequests.push({customerId, myPlace});
                break;
            case LUXURY_VEHICLE:
                dealership.luxuryRequests.push({customerId, myPlace});
                break;
            case ANY_VEHICLE:
                dealership.anyRequests.push({customerId, myPlace});
                break;
        }
        await (dealership.rentedCars[customerId]);
    }
}

void returnCar(int customerId) {
    region (dealership) {
        unsigned myPlace = dealership.place++;
        dealership.returnRequests.push({customerId, myPlace});
        await (!dealership.rentedCars[customerId]);
    }
}

void employee() {
    while (true) {
        Request req;
        int request = 0;
        region (dealership) {
            await (
                dealership.standardRequests.size() +
                dealership.luxuryRequests.size() +
                dealership.anyRequests.size() +
                dealership.returnRequests.size() > 0
            );
            unsigned minPlace = -1;
            if (
                !dealership.standardRequests.empty() &&
                !standardCars.empty() &&
                dealership.standardRequests.front().place < minPlace
            ) {
                minPlace = dealership.standardRequests.front().place;
                request = STANDARD_VEHICLE;
            }
            if (
                !dealership.luxuryRequests.empty() &&
                !luxuryCars.empty() &&
                dealership.luxuryRequests.front().place < minPlace
            ) {
                minPlace = dealership.luxuryRequests.front().place;
                request = LUXURY_VEHICLE;
            }
            if (
                !dealership.anyRequests.empty() &&
                (!standardCars.empty() || !luxuryCars.empty()) &&
                dealership.anyRequests.front().place < minPlace
            ) {
                minPlace = dealership.anyRequests.front().place;
                request = ANY_VEHICLE;
            }
            if (!dealership.returnRequests.empty() && dealership.returnRequests.front().place < minPlace) {
                minPlace = dealership.returnRequests.front().place;
                request = RETURN_VEHICLE;
            }
            switch (request) {
                case STANDARD_VEHICLE:
                    req = dealership.standardRequests.front();
                    dealership.standardRequests.pop();
                    break;
                case LUXURY_VEHICLE:
                    req = dealership.luxuryRequests.front();
                    dealership.luxuryRequests.pop();
                    break;
                case ANY_VEHICLE:
                    req = dealership.anyRequests.front();
                    dealership.anyRequests.pop();
                    break;
                case RETURN_VEHICLE:
                    req = dealership.returnRequests.front();
                    dealership.returnRequests.pop();
                    break;
            }
        }
        // Овде запослени ради неки свој посао бележења
        region (dealership) {
            switch (request) {
                case STANDARD_VEHICLE:
                    dealership.rentedCars[req.customerId] = standardCars.front();
                    standardCars.pop();
                    break;
                case LUXURY_VEHICLE:
                    dealership.rentedCars[req.customerId] = luxuryCars.front();
                    luxuryCars.pop();
                    break;
                case ANY_VEHICLE:
                    if (standardCars.empty()) {
                        dealership.rentedCars[req.customerId] = luxuryCars.front();
                        luxuryCars.pop();
                    } else {
                        dealership.rentedCars[req.customerId] = standardCars.front();
                        standardCars.pop();
                    }
                    break;
                case RETURN_VEHICLE:
                    int carId = dealership.rentedCars[req.customerId];
                    dealership.rentedCars[req.customerId] = 0;
                    if (carId > 20) {
                        luxuryCars.push(carId);
                    } else {
                        standardCars.push(carId);
                    }
                    break;
            }
        }
    }
}

int main() {
    for (int i = 0; i < 20; ++i) {
        standardCars.push(i + 1);
    }
    for (int i = 0; i < 10; ++i) {
        luxuryCars.push(i + 21);
    }
    return 0;
}

Jun 2022, 4. zadatak

Debug: KDP/Jun 2022 4. zadatak

Postavka

Trajekt za prevoz automobila, kamiona i autobusa prevozi vozila sa obale na obalu. Trajekt poseduje N pozicija koje su linearno postavljene jedna iza druge. Kamion zauzima tri, autobus dve, a automobil jednu poziciju. Vozila čekaju na trajekt u redu i na njega ulaze jedno po jedno po redosledu u kojem čekaju u redu, dok na trajektu ima mesta. Kada naredno vozilo u redu za trajekt nema mesta da se ukrca ili kada je trajekt pun, trajekt započinje prevoz vozila na drugu obalu. Na drugoj obali vozila se iskrcavaju u redosledu suprotnom od redosleda u kojem su se ukrcala. Kada se sva vozila iskrcaju, prazan trajekt se vraća na početnu obalu. Koristeći regione napisati program koji rešava ovaj problem.

Rešenje

struct Trajekt {
    int cap = N;
    int curr = 0, next = 0, ticketIn = 0, ticketOut = 0;
    bool ukrcavanje = false, iskrcavanje = false
}

Trajekt t;

void vozilo(int space) {
    int myTicketIn, myTicketOut;
    region(t) {
        myTicketIn = t.ticketIn++;
        await (t.ukrcavanje && t.ticketIn == myTicketIn);
        if (t.cap - t.curr < space) {
            // ukoliko nema mesta za mene, posalji trajekt pa sacekaj da se vrati
            t.ukrcavanje = false;
            await (t.ukrcavanje);
        }
        t.curr += space;
        myTicketOut = ++t.ticketOut;
        t.next++;
        if (t.curr == t.cap)
            t.ukrcavanje = false;
    }
    // prevozimo se
    region(t) {
        await (t.iskrcavanje && myTicketOut == t.ticketOut);
        if (--t.ticketOut == 0)
            // ukoliko sam poslednji, posalji trajekt nazad
            t.iskrcavanje = false
    }     
}

void trajekt() {
    while (1) {
        region(t) {
            t.ukrcavanje = true
            await (!t.ukrcavanje);
        }
        preveziVozila();
        region(t) {
            t.iskrcavanje = true;
            await (!t.iskrcavanje);
        }
        vratiSeNazad();
    }
}


K 2021, 2. zadatak

Debug: KDP/K 2021 2. zadatak

Postavka

Problem vožnje autobusom (The bus problem). Putnici dolaze na autobusku stanicu i čekaju prvi autobus koji naiđe. Autobus kreće sa stanice kada svi putnici koji su bili na stanici u trenutku dolaska autobusa provere da li mogu da uđu i uđu ukoliko ima mesta. Putnici se izjašnjavaju na kojoj stanici će izaći iz autobusa. Kapacitet autobusa je K mesta. Putnici koji su došli dok je autobus bio na stanici čekaju na sledeći autobus. Postoje M autobusa koji saobraćaju između N stanica. Koristeći uslovne kritične regione napisati program za putnike i autobuse.

Rešenje

const int N = 100;
const int M = 100;
const int K = 50;

// Одређују са које станице на коју станицу иду путници
// Претпоставља се да један путник неће ићи са једне на ту исту станицу
int getStationIdFrom();
int getStationIdTo();

struct Station {
    // Број путника који чекају на станици
    int numPassengers = 0;
    // Број путника који треба да провере свој статус
    // пре него што аутобус настава
    int passengersChecking = 0;
    // Овим бројем ће бити ажуриран број путника у аутобусу
    // након што сви путници провере свој статус
    int busPassengers = 0;
    // Редослед доласка аутобуса на станицу
    int currTicket = 0;
    int nextTicket = 0;
    // Аутобус који је тренутно на станици
    int busId = -1;
    // Број путника који треба да изађу на станици
    // из одређеног аутобуса
    int passengersExiting[M] = {0};
};
Station stations[N];

void bus(int busId) {
    int stationId = 0;
    int numPassengers = 0;
    while (true) {
        Station& station = stations[stationId];
        region (station) {
            int myTicket = station.nextTicket++;
            // Чекамо ред на станици
            await (station.currTicket == myTicket);
            station.busId = busId;
            station.passengersChecking = station.numPassengers + station.passengersExiting[busId];
            station.busPassengers = numPassengers;
            // Чекамо да сви путници који улазе или излазе провере свој статус
            await (station.passengersChecking == 0);
            station.busId = -1;
            numPassengers = station.busPassengers;
            // Пуштамо следећи аутобус
            ++station.currTicket;
        }
        // Путујемо
        // Бирамо следећу станицу по кружном принципу
        stationId = (stationId + 1) % N;
    }
}

void passenger() {
    while (true) {
        Station& stationFrom = stations[getStationIdFrom()];
        Station& stationTo = stations[getStationIdTo()];
        bool entranceSuccessful = false;
        int currentBusId;
        while (!entranceSuccessful) {
            region (stationFrom) {
                // Дошли смо на станицу
                ++stationFrom.numPassengers;
                if (stationFrom.busId == -1) {
                    // Чекамо аутобус
                    await (stationFrom.busId != -1);
                } else {
                    // Аутобус је већ био ту, проверавамо статус
                    ++stationFrom.passengersChecking;
                }
                currentBusId = stationFrom.busId;
                if (stationFrom.busPassengers < K) {
                    // Успели смо да уђемо у аутобус
                    ++stationFrom.busPassengers;
                    --stationFrom.numPassengers;
                    entranceSuccessful = true;
                }
            }
            region (stationTo) {
                if (entranceSuccessful) {
                    ++stationTo.passengersExiting[currentBusId];
                }
            }
            region (stationFrom) {
                // Проверили смо свој статус и ажурирали бројеве
                --stationFrom.passengersChecking;
            }
        }
        // Путујемо
        region (stationTo) {
            // Чекамо док аутобус не дође на станицу
            await (stationTo.busId == currentBusId);
            --stationTo.passengersExiting[currentBusId];
            --stationTo.busPassengers;
            --stationTo.passengersChecking;
        }
    }
}

K 2022, 2. zadatak

Debug: KDP/K 2022 2. zadatak

Postavka

Posmatra se jedan uzak i relativno kratak put kroz kanjon, kojim prolaze kauboji i Indijanci. Ako njime prolaze samo kauboji ili samo Indijanci, oni će biti fini i proći će jedni pored drugih. Ako kroz klisuru žele da prođu i kauboji i Indijanci, primenjuje se "zakon jačeg", tj. onih kojih ima više imaju prvenstvo prolaza kroz kanjon. Treba obezbediti da jednom dobijeno prvenstvo ne važi zauvek - kada se odnos snaga promeni, treba zabraniti dolazak novih osoba koje su do tada bile brojnije, kako bi oni drugi (sada brojniji[1]) mogli da dobiju prvenstvo prolaska kroz kanjon. Koriteći uslovne kritične regione napisati program koji rešava ovaj problem. [2]

Rešenje


K2 2019, 2. zadatak

Debug: KDP/K2 2019 2. zadatak

Postavka

U berbernici rade dva berberina, Aca i Braca, postoji 10 stolica za čekanje i još petoro mušterija može da stoji i čeka. Mušterije koje dolaze se izjašnjavaju da li čekaju kod Ace ili Brace ili im je svejedno ko će da ih usluži. Ako mušterija vidi da nema mesta u berbernici i ne može biti uslužena, odlazi. Kada je berberin slobodan, mušterija koja je najduže čekala će prva biti uslužena (osim ako čeka na drugog berberina i tada tražimo sledeću mušteriju u nizu). Kada se oslobodi stolica za čekanje, mušterija koja je najduže stajala treba da sedne. Ukoliko je neki od berberina besposlen, on spava, i prva mušterija koja kod njega dođe na red treba da ga probudi i bude uslužena. Koristeći uslovne kritične regione rešiti ovaj problem.

Rešenje

#include "common.h"
#include <map>
#include <queue>

using namespace std;

struct BarberShop {
    // Додељивање идентификатора муштеријама по реду доласка
    int ticket = 1;
    // Идентификатор особе која седи у седишту, или 0 уколико нико не седи
    int seat[2] = {0};
    // Да ли је берберин завршио са шишањем и чека особу да плати
    bool finished[2] = {false};
    // std::map је подразумевано сортиран
    map<int, int> waitingQueue;
    // Редови чекања за муштерије код Аце, Браце и оне којима је свеједно
    queue<int> barberQueue[3];
};
BarberShop shop;

const int ACA_ID = 0;
const int BRACA_ID = 1;
const int ANY_ID = 2;

void barber(int id) {
    while (true) {
        region (shop) {
            // Спавамо док чекамо да прва особа која дође седне на столицу
            await (shop.seat[id] != 0);
        }
        // Шишање
        region (shop) {
            // Завршено шишање, чекамо на плаћање
            shop.finished[id] = true;
            await (!shop.finished[id]);
            // Узимамо следећу муштерију
            if (!shop.barberQueue[id].empty()) {
                shop.seat[id] = shop.barberQueue[id].front();
                shop.barberQueue[id].pop();
            } else if (!shop.barberQueue[ANY_ID].empty()) {
                shop.seat[id] = shop.barberQueue[ANY_ID].front();
                shop.barberQueue[ANY_ID].pop();
            } else {
                shop.seat[id] = 0;
            }
        }
    }
}

// Да ли је седиште за шишање код одређеног берберина тренутно резервисано за неку особу
int barberEquals(int barberId, int value) {
    if (barberId == ACA_ID && shop.seat[ACA_ID] == value) {
        return ACA_ID;
    }
    if (barberId == BRACA_ID && shop.seat[BRACA_ID] == value) {
        return BRACA_ID;
    }
    if (barberId == ANY_ID) {
        if (shop.seat[ACA_ID] == value) {
            return ACA_ID;
        }
        if (shop.seat[BRACA_ID] == value) {
            return BRACA_ID;
        }
    }
    return -1;
}

int barberFree(int barberId) {
    return barberEquals(barberId, 0);
}

void client(int barberId) {
    region (shop) {
        if (shop.waitingQueue.size() == 15 && barberFree(barberId) == -1) {
            // Особа не може бити услужена
            return;
        }
        int myTicket = shop.ticket++;
        if (barberFree(barberId) != 1) {
            // Без чекања седамо на столицу за шишање
            shop.seat[barberFree(barberId)] = myTicket;
        } else {
            shop.barberQueue[barberId].push(myTicket);
            // Овиме повећавамо shop.waitingQueue.size()
            shop.waitingQueue[myTicket] = shop.waitingQueue.size();
            // Чекамо на столицу за чекање или шишање
            await (shop.waitingQueue[myTicket] < 10 || barberEquals(barberId, myTicket) != -1);
            if (barberEquals(barberId, myTicket) == -1) {
                // Седамо на столицу за чекање
                await (barberEquals(barberId, myTicket) != -1);
            }
            // Устали смо са столице и смањујемо shop.waitingQueue.size
            shop.waitingQueue.erase(myTicket);
            int i = 0;
            for (auto& it : shop.waitingQueue) {
                shop.waitingQueue[it.first] = i++;
            }
        }
        int barber = barberEquals(barberId, myTicket);
        // Чекање током шишања
        await (shop.finished[barber]);
        // Плаћање
        shop.finished[barber] = false;
    }
}

K2 2022, 2. zadatak

Debug: KDP/K2 2022 2. zadatak

Postavka

Na obali reke se nalazi čamac koji može da primi tačno deset putnika. Čamac mogu da koriste muškarci, žene i deca. Čamac može da isplovi samo ako se u njemu nalazi tačno onoliko putnika koliki mu je kapacitet, ali samo pod uslovom da se u čamcu nalaze bar dva muškarca. Deca ne smeju ući u čamac ukoliko se u njemu ne nalaze bar jedna odrasla osoba i po završetku vožnje u čamcu ne smeju da ostanu samo deca. Smatrati da će se[sic] čamac nakon iskrcavanja svih putnika odmah biti spreman da primi narednu grupu putnika. Koristeći regione napisati program koji rešava ovaj problem.

Rešenje

struct Boat {
    // Број мушкараца, жена и деце
    int men = 0;
    int women = 0;
    int children = 0;
    // Да ли је вожња готова (да ли је у току искрцавање)
    bool done;
    // Помоћне методе
    int total() {
        return men + women + children;
    }
    int adults() {
        return men + women;
    }
};
Boat boat;

void boatP() {
    while (true) {
        region (boat) {
            boat.done = false;
            await (boat.total() == 10 && boat.men >= 2);
        }
        // Вожња
        region (boat) {
            boat.done = true;
            await (boat.total() == 0);
        }
    }
}

void man() {
    while (true) {
        region (boat) {
            await (!boat.done);
            if (boat.total() < 10) {
                ++boat.men;
                break;
            } else {
                // Нисмо се укрцали, чекамо да се заврши вожња па поново
                await (boat.done);
            }
        }
    }
    // Укрцани смо
    region (boat) {
        await (boat.done);
        // Ако смо последњи одрасли, чекамо да сва деца изађу
        if (boat.adults() == 1 && boat.children > 0) {
            await (boat.children == 0);
        }
        --boat.men;
    }
}

void woman() {
    while (true) {
        region (boat) {
            await (!boat.done);
            if (boat.total() < 10 && boat.total() - boat.men <= 7) {
                ++boat.women;
                break;
            } else {
                // Нисмо се укрцали, чекамо да се заврши вожња па поново
                await (boat.done);
            }
        }
    }
    // Укрцани смо
    region (boat) {
        await (boat.done);
        // Ако смо последњи одрасли, чекамо да сва деца изађу
        if (boat.adults() == 1 && boat.children > 0) {
            await (boat.children == 0);
        }
        --boat.women;
    }
}

void child() {
    while (true) {
        region (boat) {
            await (!boat.done);
            if (boat.total() < 10 && boat.total() - boat.men <= 7 && boat.adults() > 0) {
                ++boat.children;
                break;
            } else {
                // Нисмо се укрцали, чекамо да се заврши вожња па поново
                await (boat.done);
            }
        }
    }
    // Укрцани смо
    region (boat) {
        await (boat.done);
        --boat.children;
    }
}

Februar 2020, 2. zadatak

Debug: KDP/Februar 2020 2. zadatak

Postavka

Postoji grupa od N filozofa koji provodi svoj život tako što naizmenično filozofiraju, čekaju na piće, i piju (The Drinking Philosophers Problem). Filozofi su tako raspoređeni da je po jedna flaša sa pićem postavljena između susednih filozofa. U nekom trenutku filozof može da postane žedan. Žednom filozofu je potrebno nekoliko susednih flaša da bi napravio koktel i počeo da ga pije. Izbor pića zavisi od trenutnog raspoloženja i može se razlikovati od prilike do prilike. Kada prikupi sva potrebna pića filozof započinje sa njihovim ispijanjem koje traje izvesno vreme. Kada se napije, filozof vraća flaše da i drugi uživaju, a on prelazi na filozofiranje. Napisati program koji simulira ponašanje filozofa koristeći uslovne kritične regione.

Rešenje

#include <queue>
#include <vector>

using namespace std;

const int N = 100;

struct Table {
    int drinks[N] = {-1};
    queue<int> drinkQueues[N];
};
Table table;

void philosophizing();
void drinking();
vector<int> getDrinkRound();

void philosopher(int id) {
    while (true) {
        vector<int> drinks = getDrinkRound();
        region (table) {
            for (int drink : drinks) {
                if (table.drinks[drink] == -1) {
                    table.drinks[drink] = id;
                } else {
                    table.drinkQueues[drink].push(id);
                    await (table.drinks[drink] == id);
                }
            }
        }
        drinking();
        region (table) {
            for (int drink : drinks) {
                if (table.drinkQueues[drink].empty()) {
                    table.drinks[drink] = -1;
                } else {
                    table.drinks[drink] = table.drinkQueues[drink].front();
                    table.drinkQueues[drink].pop();
                }
            }
        }
        philosophizing();
    }
}


Februar 2024, 2. zadatak

Debug: KDP/Februar 2024 2. zadatak

Postavka

Koristeći uslovne kritične regione napisati program koji rešava problem putovanja liftom. Putnik poziva lift sa proizvoljnog sprata. Kada lift stigne na neki sprat svi putnici koji su izrazili želju da siđu na tom spratu obavezno izađu. Nakon izlaska putnika svi putnici koji su čekali na ulazak uđu u lift i kažu na koji sprat žele da pređu. Tek kada se svi izjasne lift prelazi dalje. Nije potrebno optimizovati put lifta i putnika.

Rešenje

  1. ↑ Gleda se zbira broja koji čeka i onih koji su u kanjonu
  2. ↑ Na uvidu je asistentkinja objasnila da je bilo zamišljeno (mada se i sama složila ne nužno napisano) da ukoliko je došlo do promene prvenstva, svi koji su do tada čekali treba da prođu pre obrtanja prava prvenstva, bez obzira na brojno stanje.
Preuzeto iz „https://siwiki.rs/w/index.php?title=КДП/Региони&oldid=5661”