Решение задачи "Кубики" с Acmp

С пояснением   Просмотров: 13


Родители подарили Пете набор детских кубиков. Поскольку Петя скоро пойдет в школу, они купили ему кубики с буквами. На каждой из шести граней каждого кубика написана буква.

Теперь Петя хочет похвастаться перед старшей сестрой, что научился читать. Для этого он хочет сложить из кубиков ее имя. Но это оказалось довольно сложно сделать – ведь разные буквы могут находиться на одном и том же кубике и тогда Петя не сможет использовать обе буквы в слове. Правда одна и та же буква может встречаться на разных кубиках. Помогите Пете!

Дан набор кубиков и имя сестры. Выясните, можно ли выложить ее имя с помощью этих кубиков и если да, то в каком порядке следует выложить кубики.

Код

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
 
using namespace std;
 
void del_zeros(vector< vector< char > > &a)
{
    for(unsigned i = 0; i < a.size() - 1; ++i) {
        unsigned k = 0;
        for(unsigned j = 0; j < a.at(i).size() - 2; ++j) {
            k += a.at(i).at(j);
        }
        if(!k)
            a.erase(a.begin() + i--);
    }
}
 
void del_r_c(unsigned row, unsigned col, vector< vector< char > > &a)
{
    a.erase(a.begin() + row);
    for(unsigned i = 0; i < a.size() - 1; ++i) {
        if(a.at(i).at(col))
            --a.at(i).at(a.at(i).size() - 2);
        if(!a.at(i).at(a.at(i).size() - 2))
            a.erase(a.begin() + i);
        else
            a.at(i).erase(a.at(i).begin() + col);
    }
    a.at(a.size() - 1).erase(a.at(a.size() - 1).begin() + col);
}
 
int main()
{
    unsigned n;
    string name, str;
    ifstream fin("input.txt");
    fin >> n;
    fin >> name;
    vector< vector< char > > m;
    vector< string > chars;
    vector< char > t;
    vector< unsigned > result(name.size());
    for(unsigned i = 0; i < n; ++i) {
        fin >> str;
        chars.push_back(str);
    }
    for(unsigned i = 0; i < n; ++i) {
        t.clear();
        int k = 0;
        for(unsigned j = 0; j < name.size(); ++j) {
            if(chars[i].find(name[j]) + 1) {
                t.push_back(1);
                ++k;
            }
            else
                t.push_back(0);
        }
        t.push_back(k); t.push_back(i);
        m.push_back(t);
    }
    t.clear();
    for(unsigned j = 0; j < name.size(); ++j)
                t.push_back(j);
    m.push_back(t);
    del_zeros(m);
 
    bool t1 = 1;
    bool t2 = m.size() - 1 && m.size() - 1 >= m.at(0).size() - 2 && t1;
    while(t2) {
        unsigned ini = 0, inj = 0;
        for(unsigned i = 1; i < m.size() - 1; ++i) {
            if(m.at(ini).at(m.at(ini).size() - 2) > m.at(i).at(m.at(i).size() - 2)) {
                ini = i;
            }
        }
        for(unsigned j = 0; j < m.at(ini).size(); ++j) {
            if(m.at(ini).at(j)) {
                inj = j;
                break;
            }
 
        }
        result.at(m.at(m.size() - 1).at(inj)) =
            m.at(ini).at(m.at(ini).size() - 1) + 1;
        del_r_c(ini, inj, m);
 
        bool t3 = 0;
        for(unsigned i = 0; i < result.size(); ++i)
            if(!result.at(i))
                t3 = 1;
        t1 = t3;
        t2 = m.size() - 1 && m.size() - 1 >= m.at(0).size() - 2 && t1;
 
 
    }
    bool t3 = 1;
    for(unsigned i = 0; i < result.size(); ++i)
        if(!result.at(i)) {
            t3 = 0;
            break;
    }
    if(t3) {
        cout << "Yes" << endl;
        for(auto i : result)
            cout << i << " ";
    } else
        cout << "No";
    return 0;
}

         

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


Увы, неполное решение. Если вы решите данную задачу загрузите его на нашем сайте

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

Комментарии

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