Решение задачи Диалог компьютеров с Меньшиков

Без пояснения   Просмотров: 114


Три компьютера соединены сетью. Один из них - сервер, два других - клиенты. На сервере есть несколько файлов. Полные имена файлов, состоящие из двух частей (имя и расширение), различны. Оба клиента знают полные имена всех файлов, находящихся на сервере. Сервер выбирает один из своих файлов и посылает его имя одному из клиентов, а расширение - второму.

Затем клиенты начинают общаться друг с другом, пытаясь определить, какой файл был выбран сервером (они хотят узнать полное имя файла). Однако клиенты вынуждены общаться очень ограниченным способом. Они по очереди посылают сообщения друг другу, но могут сказать только, что не знают полного имени файла. Если клиент не знает полного имени выбранного файла, он может послать другому клиенту сообщение, говорящее: "Я не знаю полного имени файла". Клиенты чередуются, посылая только это сообщение туда и обратно. Так продолжается до тех пор, пока один из клиентов не узнает полное имя файла, или они не решат закончить диалог. Клиент, получивший первую часть полного имени файла, всегда ждёт, что второй клиент пошлёт первое сообщение.

Пусть Вы знаете все полные имена файлов, находящихся на сервере, и слушаете разговор клиентов. Основываясь на этой беседе, Вы должны определить набор файлов, которые могли быть выбраны сервером. Файлы в этом наборе называются файлами-кандидатами.

Код

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <list>
#include <map>
#include <algorithm>
 
using namespace std;
 
int n,m;
vector<string>  fullName;
vector<string>  name;
vector<string>  exp;
vector<bool>    used;
map<string,vector<int> > mName;
map<string,vector<int> > mExp;
 
void ParseFileFullName(const string &fullName, string &name, string &exp)
{
    int pos = fullName.find('.');
    if (pos == -1)
    {
        name = fullName;
        exp  = "";
    }
    else
    {
        name = fullName.substr(0,pos);
        exp  = fullName.substr(pos+1,fullName.size() - (pos+1));
    }
}
void input()
{
    cin>>n>>m;
    string sFullName, sName, sExp;
 
    fullName.resize(n);
    name.resize(n);
    exp.resize(n);
    used.resize(n);
 
    for (int i=0;i<n;i++)
    {
        cin>>sFullName;
        ParseFileFullName(sFullName, sName, sExp);
        fullName[i] = sFullName;
        name[i]     = sName;
        mName[sName].push_back(i);
        exp[i]      = sExp;
        mExp[sExp].push_back(i);       
    }
}
inline void delItem(vector<int> &mas, int value)
{
    mas.erase(
        // помещаем в конец удаляемый элемент
        remove(mas.begin(), mas.end(), value), 
        mas.end()); // удаляем хвост
}
void check(map<string,vector<int> > &mPrimary   , vector<string> &primary,
           map<string,vector<int> > &mSecondary , vector<string> &secondary)
{
    for (int i=n-1;i>=0;i--)
    {
        if (!mPrimary[primary[i]].empty())
        {
            // файл нужно удалить из рассмотрения
            if (mPrimary[primary[i]].size() == 1)
            {
                // удаляем последнюю асооцицию с этим именем
                delItem(mPrimary[primary[i]],i);
                // удаляем ассоциацию с расширением
                delItem(mSecondary[secondary[i]],i);
            }
        }
    }
}
void solve()
{
    for (int i=0;i<m;i++)
    {
        if (i&1)
            check(mName,name, mExp, exp);
        else
            check(mExp, exp, mName, name);
    }
}
int findAnswer(bool isOutput)
{
    int amount = 0;
    for (int i=0;i<n;i++)
    {
        if (!mName[name[i]].empty() && !mExp[exp[i]].empty())
        {
            amount++;
            if (isOutput)
                cout<<fullName[i]<<endl;
        }
    }
    return amount;
}
void output()
{
    cout<<findAnswer(false)<<endl;
    findAnswer(true);
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    output();
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться