2008, TCHS, Весна, Раунд 1, Зачисление студентов

(StudentEnrollment)

Массив names содержит названия предметов, которые следует сдавать абитуриентам. Массив spaces содержит количество свободных мест на данный момент для каждого предмета. То есть еще spaces[i] абитуриентов может записаться на сдачу предмета names[i]. Массив queries содержит запросы – названия предметов, на сдачу которых хотят записаться новые абитуриенты. Для каждого запроса следует или записать абитуриента на курс, или отказать, сообщив ему что либо нет свободных мест, либо нет в наличии требуемого курса. Для каждого запроса следует вернуть одну из строк:

1. Если на требуемый предмет есть свободные места, то вернуть “GOOD”;

2. Если на требуемый предмет не осталось свободных мест, то вернуть “NOT GOOD”;

3. Если требуемого предмета не существует, вернуть “DOES NOT EXIST”.

Класс: StudentEnrollment

Метод: vector<string> checkClasses(vector<string> names, vector<int> spaces, vector<string> queries)

Ограничения: каждый из массивов names и queries содержит от 0 до 50 строк, каждая из которых содержит от 1 до 50 символов ‘A’ – ‘Z’, все элементы names разные.

Вход. Массивы names, spaces и queries.

Выход. Массив строк, содержащий результаты запросов в соответствии с описанными в условии задачи правилами.

Пример входа

names	spaces	queries
{"MATH", "ENGLISH"}	{1, 2}	{"ENGLISH", "MATH", "MATH"}
{"MATH", "ENGLISH"}	{2, 0}	{"ENGLISH", "MATH", "MATH"}
{"MATH", "ENGLISH"}	{2, 0}	{"ENGLISH", "FRENCH"}

Пример выхода

{"GOOD", "GOOD", "NOT GOOD"}

{"NOT GOOD", "GOOD", "GOOD"}

{"NOT GOOD", "DOES NOT EXIST"}

РЕШЕНИЕ

структуры данных

В отображении map<string,int> m будем хранить информацию о предметах и количестве свободных для их сдачи мест. Например, если m["MATH"] = 2, то на математику может записаться еще два абитуриента. Используя массивы names и spaces, заполняем m. Для удобства дальнейшей обработки количество свободных мест для каждого предмета увеличим на 1.

Проходим по массиву queries. Если на предмет queries[i] еще можно записать абитуриента, то заносим “GOOD” в результирующий массив res, а значение m[queries[i]] уменьшаем на 1. Если на текущий момент m[queries[i]] равно 1, то свободные места закончились. Если m[queries[i]] равно 0, то предмета queries[i] не существует.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <map>

using namespace std;

map<string,int> m;

class StudentEnrollment

{

public:

vector<string> checkClasses(vector<string> names, vector<int> spaces,

vector<string> queries)

{

int i;

vector<string> res;

for(i=0;i<names.size();i++) m[names[i]] = spaces[i]+1;

for(i=0;i<queries.size();i++)

{

if (m[queries[i]] == 0) res.push_back("DOES NOT EXIST"); else

if (m[queries[i]] == 1) res.push_back("NOT GOOD"); else

{

res.push_back("GOOD");

m[queries[i]]--;

}

}

return res;

}

};