КДП/Региони
Региони су област конкурентног програмирања из другог блока наставе и долазе на другом колоквијуму за СИ и колоквијуму за РТИ.
Јун 2020, 4. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
У неком обданишту постоји правило које каже да се на свака три детета мора наћи барем једна васпитачица (The Child Care Problem). Родитељ доводи једно или више деце у обданиште и чека све док се не појави место, како би оставио сву децу одједном и отишао. Родитељ такође може да одведе једно или више деце, такође одједном. Васпитачица долази на посао и сме да напусти обданиште само уколико то не нарушава правило. Мора се поштовати редослед доласка родитеља који остављају децу и васпитачица које одлазе са посла. Користећи условне критичне регионе, написати процедуре за родитеље који доводе децу, родитеље који одводе децу, васпитачице које долазе на посао и васпитачице које одлазе са посла. Иницијализовати почетне услове.
Решење
Јун 2021, 2. задатак
Поставка
Посматра се агенција за изнајмљивање аутомобила. У возном парку постоје 20 стандардних возила и 10 лукс возила. Приликом доласка клијента да изнајми ауто, он се изјашњава да ли жели да изнајми стандардно или лукс возило или му је све једно. Након тога он чека у реду све док му се возило не додели на коришћење. По завршетку коришћења, корисник долази још једном у агенцију и враћа ауто. У агенцији постоји један запослени који води евиденцију о томе који ауто је тренутно на коришћењу код ког корисника. Клијентима није дозвољено напуштање агенције све док запослени не обради њихов захтев за преузимање или враћање возила. Користећи регионе написати методу које се позива приликом доласка клијента да изнајми ауто, методу које се позива приликом доласка клијента да врати ауто и методу која симулира рад запосленог, као и код за иницијализацију. Потребно је обезбедити да возила не стоје на паркингу агенције, уколико постоји било који клијент који жели да изнајми тај тип возила.
Решење
#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;
}
Јун 2022, 4. задатак
Поставка
Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарно постављене једна иза друге. Камион заузима три, аутобус две, а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у којем чекају у реду, док на трајекту има места. Када наредно возило у реду за трајект нема места да се укрца или када је трајект пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од редоследа у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи регионе написати програм који решава овај проблем.
Решење
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();
}
}
К 2021, 2. задатак
Поставка
Проблем вожње аутобусом (The bus problem). Путници долазе на аутобуску станицу и чекају први аутобус који наиђе. Аутобус креће са станице када сви путници који су били на станици у тренутку доласка аутобуса провере да ли могу да уђу и уђу уколико има места. Путници се изјашњавају на којој станици ће изаћи из аутобуса. Капацитет аутобуса је K места. Путници који су дошли док је аутобус био на станици чекају на следећи аутобус. Постоје M аутобуса који саобраћају између N станица. Користећи условне критичне регионе написати програм за путнике и аутобусе.
Решење
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;
}
}
}
К 2022, 2. задатак
Поставка
Посматра се један узак и релативно кратак пут кроз кањон, којим пролазе каубоји и Индијанци. Ако њиме пролазе само каубоји или само Индијанци, они ће бити фини и проћи ће једни поред других. Ако кроз клисуру желе да прођу и каубоји и Индијанци, примењује се "закон јачег", тј. оних којих има више имају првенство пролаза кроз кањон. Треба обезбедити да једном добијено првенство не важи заувек - када се однос снага промени, треба забранити долазак нових особа које су до тада биле бројније, како би они други (сада бројнији[1]) могли да добију првенство проласка кроз кањон. Коритећи условне критичне регионе написати програм који решава овај проблем. [2]
Решење
К2 2019, 2. задатак
Поставка
У берберници раде два берберина, Аца и Браца, постоји 10 столица за чекање и још петоро муштерија може да стоји и чека. Муштерије које долазе се изјашњавају да ли чекају код Аце или Браце или им је свеједно ко ће да их услужи. Ако муштерија види да нема места у берберници и не може бити услужена, одлази. Када је берберин слободан, муштерија која је најдуже чекала ће прва бити услужена (осим ако чека на другог берберина и тада тражимо следећу муштерију у низу). Када се ослободи столица за чекање, муштерија која је најдуже стајала треба да седне. Уколико је неки од берберина беспослен, он спава, и прва муштерија која код њега дође на ред треба да га пробуди и буде услужена. Користећи условне критичне регионе решити овај проблем.
Решење
#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;
}
}
К2 2022, 2. задатак
Поставка
На обали реке се налази чамац који може да прими тачно десет путника. Чамац могу да користе мушкарци, жене и деца. Чамац може да исплови само ако се у њему налази тачно онолико путника колики му је капацитет, али само под условом да се у чамцу налазе бар два мушкарца. Деца не смеју ући у чамац уколико се у њему не налазе бар једна одрасла особа и по завршетку вожње у чамцу не смеју да остану само деца. Сматрати да ће се[sic] чамац након искрцавања свих путника одмах бити спреман да прими наредну групу путника. Користећи регионе написати програм који решава овај проблем.
Решење
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;
}
}
Фебруар 2020, 2. задатак
Поставка
Постоји група од N филозофа који проводи свој живот тако што наизменично филозофирају, чекају на пиће, и пију (The Drinking Philosophers Problem). Филозофи су тако распоређени да је по једна флаша са пићем постављенa између суседних филозофа. У неком тренутку филозоф може да постане жедан. Жедном филозофу је потребно неколико суседних флаша да би направио коктел и почео да га пије. Избор пића зависи од тренутног расположења и може се разликовати од прилике до прилике. Када прикупи сва потребна пића филозоф започиње са њиховим испијањем које траје извесно време. Када се напије, филозоф враћа флаше да и други уживају, а он прелази на филозофирање. Написати програм који симулира понашање филозофа користећи условне критичне регионе.
Решење
#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();
}
}
Фебруар 2024, 2. задатак
Поставка
Користећи условне критичне регионе написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Није потребно оптимизовати пут лифта и путника.