Форум программистов, компьютерный форум CyberForum.ru

Задача с кубиками - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
Jenya18
0 / 0 / 0
Регистрация: 29.04.2013
Сообщений: 13
23.05.2013, 23:35     Задача с кубиками #1
Ребята, помогите решить задачку на зачет.

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

Ввод:
В первой строке входного файла находится число N (1 <N <100) - количество кубиков в наборе у Пети. Во второй строке записано имя Петиной сестры - слово, состоящее только из заглавных латинских букв, не более 100 символов. Следующие N строк содержат по 6 букв (только большие латинские буквы), которые написаны на соответствующем кубике.

Вывод:
В первой строке выходного файла выведите YES, если выложить имя Петина сестры данным кубиками можно, и N0 - в противном случае. Если ответ YES, то во второй строке выведите М различных чисел из диапазона l ... N, где М - количество букв в имени Петиной сестры, и-e число должно быть номером кубика, который следует положить на i-e место при составлении имени Петина сестры . Кубики нумеруются с 1, в том порядке, в котором они заданы во входном файле. Если решений несколько, выведите любое. Разделяйте числа пробелами.

Пример ввода
4
ANN
ANNNNN
BCDEFG
HIJKLM
NOPQRS

Пример вывода NO
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2013, 23:35     Задача с кубиками
Посмотрите здесь:

C++ Школьная олимпиада. Задача с кубиками (самая сложная из всех задач)

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
24.05.2013, 03:08     Задача с кубиками #2
Строится матрица. Для каждого кубика отмечаем все позиции, на которых он может стоять.

C++
1
2
3
4
5
6
7
8
9
10
   | A | N | N |   | 
---|---|---|---|---|-------
 1 | + | + | + |   | ANNNNN
---|---|---|---|---|-------
 2 |   |   |   |   | BCDEFG
---|---|---|---|---|-------
 3 |   |   |   |   | HIJKLM
===|===|===|===|===|-------
 4 |   | + | + |   | NOPQRS
---|---|---|---|---|-------
Если в квадратной подматрице размера имени есть хотя бы одна незаполненная строка, задача не имеет решения.
Если строки и столбцы матрицы можно переставить так, что будет заполнена главная диагональ подматрицы размера имени, то любая такая перестановка будет решением.
Jenya18
0 / 0 / 0
Регистрация: 29.04.2013
Сообщений: 13
24.05.2013, 18:41  [ТС]     Задача с кубиками #3
да я понял сам алгоритм, а вот закодить не получается(
ребят, может кто сможет помочь? через потоковые алгоритмы
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
24.05.2013, 19:30     Задача с кубиками #4
Цитата Сообщение от Jenya18 Посмотреть сообщение
понял сам алгоритм ... через потоковые алгоритмы
Не похоже, что поняли.

И с учетом размера (1 <N <100), полный перебор невозможен. Почитайте про Поиск с возвратом.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
24.05.2013, 21:30     Задача с кубиками #5
Мне кажется, что эту задачу можно решить через графы
http://www.cyberforum.ru/attachment....1&d=1369416467
Думаю, что идея понятна. Другое вопрос реализация...
Миниатюры
Задача с кубиками  
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
24.05.2013, 21:35     Задача с кубиками #6
Цитата Сообщение от gazlan Посмотреть сообщение
Если в квадратной подматрице размера имени есть хотя бы одна незаполненная строка, задача не имеет решения.
Если строки и столбцы матрицы можно переставить так, что будет заполнена главная диагональ подматрицы размера имени, то любая такая перестановка будет решением.
Допустим длина имени = 5, количество кубиков, на которых есть хотя бы одна буква из имени = 20, тогда нужно выбрать 5 кубиков без повторений (из всех 20) (таких сочетаний = 20! / ( 5! * (20 - 5)! ) и для всех вариантов расстановки этих пяти кубиков проверить диагональ (проверок = 5! = 120) и если диагональ заполнена, то эта комбинация подходит. Если нет, то выбрать следующие 5 кубиков и повторить. Правильный ход мыслей?
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
24.05.2013, 22:04     Задача с кубиками #7
1. Граф или матрица - неважно, это эквивалентные представления.

2. Я думаю, тут возможны сокращающие перебор оптимизации.

Например, можно вычеркнуть все кубики, не содержащие ни одной буквы имени.
Для всех кубиков, содержащих только одну букву имени, их место уже определено.
Можно убедиться, что "разных" кубиков не меньше чем разных букв в имени.

Т.е., при "удачном" раскладе можно убедиться, что решения нет, без фактического решения задачи.
Ну и, любой отброшенный кубик сокращает число вариантов для перебора.

3. Мне кажется, удобнее работать с деревом выбора. На каждом i-ом шаге есть r[i] (r < N) вариантов выбора кубика (т.е. r[i] дочерних узлов). Строим дерево и рекурсивно обходим его в глубину.

Если на каком-то маршруте удалось построить имя - задача решена, выводим решение. Если нет - возвращаемся назад (по стеку) и пробуем следующий маршрут. Если обойдено все дерево и не удалось построить имя - нет решения.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
24.05.2013, 22:55     Задача с кубиками #8
Цитата Сообщение от gazlan Посмотреть сообщение
3. Мне кажется, удобнее работать с деревом выбора. На каждом i-ом шаге есть r[i] (r < N) вариантов выбора кубика (т.е. r[i] дочерних узлов). Строим дерево и рекурсивно обходим его в глубину.
А что делать с кубиками которые содержат больше одной буквы из имени ?
Имя: ANN
Кубики:
ANNNNN
BCDEFG
HIJKLM
NOPQRS
AAAAAA

В таком случае под букву "А" можно взять как первый, так и последний, но если брать последний, то решение существует.
Так что же делать с такими кубиками(которые могут заменить более одной буквы) в дереве?
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
24.05.2013, 23:18     Задача с кубиками #9
Цитата Сообщение от Olivеr Посмотреть сообщение
что же делать с такими кубиками(которые могут заменить более одной буквы)
IMHO, здесь возможен только перебор - то есть, как было написано, обход дерева либо до первого решения, либо до исчерпания вариантов (если решения нет).

Важно другое: заданная размерность (up to 100) настолько велика, что без специальных ухищрений и решения "по частям" ее ни впихнуть ни в компьютер, ни в нашу Вселенную. Поэтому все, что может уменьшить число вариантов перебора, должно быть использовано.
Jenya18
0 / 0 / 0
Регистрация: 29.04.2013
Сообщений: 13
25.05.2013, 00:24  [ТС]     Задача с кубиками #10
А если тут попробовать методом ветвей и границ? На сколько я помню метод на много меньше чем полным перебором
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
25.05.2013, 08:23     Задача с кубиками #11
Цитата Сообщение от Jenya18 Посмотреть сообщение
методом ветвей и границ
Как вариант, если можете формализовать задачу. Вероятно, должно быть похоже на задачу коммивояжера.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
25.05.2013, 15:43     Задача с кубиками #12
вот мое решение (перебор с возвратом)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//http://www.cyberforum.ru/cpp-beginners/thread876533.html
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <unordered_set>
#include <unordered_map>
#include <queue>
//#define DEBUG
 
using namespace std;
 
int main()
{
//входные данные и подготовка
    string sname, chars;
    ifstream file("data.txt");
    file >> sname;
    unordered_map<char, unordered_set<int>> cubes;
    string cube;
    int cube_idx = 0;
    file.get();
         
    while (getline(file, cube)) {
//все неподходящие кубики пропускаем
        if ( any_of( begin(cube), end(cube), [&](char c) { return sname.find(c) != string::npos; } ) )
            for (auto c : cube)
                if ( sname.find(c) != string::npos )
                    cubes[c].insert(cube_idx);
        cube_idx++;
    }
    file.close();
//подготовка завершена, теперь поиск перешния   
    
    vector<queue<int>> q(sname.size(), queue<int>());
    vector<int> path(sname.size(), -1);
 
    #ifdef DEBUG
    for (auto &v : cubes) {
        cout << v.first;
        for (auto i : v.second)
            cout << " " << i;
        cout << endl;
    }
    #endif
 
    for ( auto &x : cubes[sname[0]] )
        q[0].push(x);
    int pos = 0, v;
 
    while (true) {
        v = q[pos].front();
        q[pos].pop();
        path[pos] = v;
 
        if ( pos + 1 == sname.size() ) {
            if (!q[pos].empty()) continue;
            cout << "Path is ";
            for (auto &x : path) cout << x << ' ';
            return 0;
        }
 
        for (auto &x : cubes[ sname[pos + 1] ])
            if ( find( begin(path), end(path), x) == end(path) )
                q[pos + 1].push(x);
 
        if (!q[pos + 1].empty())
            ++pos;
        else {
            while ( q[pos].empty() )
                if (!pos--) return -1;
            fill( begin(path) + pos, end(path), -1 );
        }
    }
    return 0;
}
Первая строчка в файле - это имя, остальные - кубики.
Пример:
ANNJYTBYFT
ANNNNN
BCDEFG
HIJKLM
NOPQRS
KGNYFU
KJBNGU
BYFTYF
HTRSSF
GFJYYU
KJIOJM
LNYIHU
Результат: Path is 0 10 3 9 8 7 5 4 1 6
Jenya18
0 / 0 / 0
Регистрация: 29.04.2013
Сообщений: 13
26.05.2013, 01:15  [ТС]     Задача с кубиками #13
А может кто-то знает как решить данную задачу через потоковые алгоритмы?
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
26.05.2013, 12:28     Задача с кубиками #14
Исправил найденную ошибку и добавил предварительную проверку на количество кубиков.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <unordered_set>
#include <unordered_map>
#include <queue>
 
using namespace std;
 
int main()
{
    string      sname, chars;
    ifstream    file("data.txt");
    file >> sname;
    file.get();
    unordered_map<char, unordered_set<int>> cubes;
    string cube;
    int cube_idx = 0, good_cubes_count = 0;
 
    while (getline(file, cube)) {
        if ( any_of( begin(cube), end(cube), [&](char c) { return sname.find(c) != string::npos; } ) ) {
            good_cubes_count++;
            for (auto c : cube)
                if ( sname.find(c) != string::npos )
                    cubes[c].insert(cube_idx);
        }
        cube_idx++;
    }
    file.close();
 
    if (good_cubes_count < sname.size()) return -1;
 
    vector<queue<int>>  q(sname.size(), queue<int>());
    vector<int>         path(sname.size(), -1);
    int pos = 0;
 
    for ( auto &x : cubes[sname[0]] )
        q[0].push(x);
 
    while (true) {
 
        if ( pos + 1 == sname.size() && !q[pos].empty() ) {
            cout << "Path is ";
            path[pos] = q[pos].front();
            for (auto &x : path) cout << x << ' ';
            return 0;
        }
 
        path[pos] = q[pos].front();
        q[pos].pop();
 
        for (auto &x : cubes[ sname[pos + 1] ])
            if ( find( begin(path), end(path), x) == end(path) )
                q[pos + 1].push(x);
 
        if (!q[pos + 1].empty())
            ++pos;
        else {
            while ( q[pos].empty() )
                if (!pos--) return -1;
            fill( begin(path) + pos, end(path), -1 );
        }
    }
    return 0;
}


Цитата Сообщение от Jenya18 Посмотреть сообщение
А может кто-то знает как решить данную задачу через потоковые алгоритмы?
Что это такое? В гугле по такому запросу нахожу только алгоритмы шифрования и тп.
Jenya18
0 / 0 / 0
Регистрация: 29.04.2013
Сообщений: 13
26.05.2013, 16:07  [ТС]     Задача с кубиками #15
Мы сейчас проходим по программированию 4 потоковых алгоритма -
1) Эдмондса-Карпа - http://ru.wikipedia.org/wiki/Алгоритм_Эдмондса_—_Карпа
2)Алгоритм поиска увеличувающей цепи - http://on2.docdat.com/docs/19885/ind...1.html?page=11
3)Алгоритм поиска потока минимальной стоимости - http://ru.wikipedia.org/wiki/Поток_м...ьной_стоимости
4)и Алгоритмы нахождения максимального потока - http://algolist.manual.ru/maths/graphs/maxflows/ один из этих алгоритмов.
Задача стоит именно с помощью этих алгоритмов развязать задачу
jenyakirmiza
0 / 0 / 0
Регистрация: 13.02.2013
Сообщений: 90
30.05.2013, 16:48     Задача с кубиками #16
Эта задача сводится к нахождению максимального паросочетания в двудольном графе.
Назовем кубики и буквы имени сестры вершинами нашего графа и соединим кубик ребром с буквой, если эта буква написана на этом кубике. Заметим, что граф действительно двудольный, а выбор кубиков для выкладывания имени эквивалентен по строению паросочетания. Поскольку число ребер в паросочетании не превышает числа вершин в меньшей доле, то искомое паросочетание действительно максимально.
Для нахождения максимального паросочетания разработаны стандартные алгоритмы, хорошо освещенные в литературе
Yandex
Объявления
30.05.2013, 16:48     Задача с кубиками
Ответ Создать тему
Опции темы

Текущее время: 06:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru