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

С++ для начинающих

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

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

23.05.2013, 23:35. Просмотров 2088. Ответов 15
Метки нет (Все метки)

Ребята, помогите решить задачку на зачет.

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

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

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

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

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

Школьная олимпиада. Задача с кубиками (самая сложная из всех задач) - C++
Очки на игральных кубиках распологаются так, чтобы совпадали суммы чисел на противоположных гранях: 1+6 = 2+ 5 = 7. Составьте программу,...

Олимпиадная задача с кубиками - Pascal
Не могли бы вы мне помочь? Юный математике Матвей интересуется теорией вероятностей, и по этой причине у него всегда есть с собой...

Головоломка с кубиками - Delphi
Головоломка с кубиками. Имеется 4 кубика ,грани которых раскрашены в четыре цвета: белый, зеленый, синий, красный. Необходимо...

Видеокарта, после подключения телевизора начала воспроизводить всё полосатыми кубиками - Видеокарты
Если ВЫ ещё в сети, помогите решить проблемку. Добавлено через 2 минуты 53 секунды Видеокарта, после подключения телевизора начала...

Когда делаю видео в GIF то размытые фоны у видео становятся кубиками, или превращаются в отделенные цвета - Видеопрограммы
Когда делаю видео в GIF то размытые фоны у видео становятся кубиками, или превращаются в отделенные цвета. Это такой формат? Или есть...

Задача: В некотором государстве ввели компьютерный паспорт гражданина.(задача) - Pascal
Доброго времени суток,форумчане. Хотелось бы попросить помощи в решении одной задачи от умных голов. Задача: В некотором...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
gazlan
3131 / 1906 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 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
---|---|---|---|---|-------
Если в квадратной подматрице размера имени есть хотя бы одна незаполненная строка, задача не имеет решения.
Если строки и столбцы матрицы можно переставить так, что будет заполнена главная диагональ подматрицы размера имени, то любая такая перестановка будет решением.
2
Jenya18
0 / 0 / 0
Регистрация: 29.04.2013
Сообщений: 13
24.05.2013, 18:41  [ТС] #3
да я понял сам алгоритм, а вот закодить не получается(
ребят, может кто сможет помочь? через потоковые алгоритмы
0
gazlan
3131 / 1906 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
24.05.2013, 19:30 #4
Цитата Сообщение от Jenya18 Посмотреть сообщение
понял сам алгоритм ... через потоковые алгоритмы
Не похоже, что поняли.

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

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

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

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

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

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

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

Важно другое: заданная размерность (up to 100) настолько велика, что без специальных ухищрений и решения "по частям" ее ни впихнуть ни в компьютер, ни в нашу Вселенную. Поэтому все, что может уменьшить число вариантов перебора, должно быть использовано.
1
Jenya18
0 / 0 / 0
Регистрация: 29.04.2013
Сообщений: 13
25.05.2013, 00:24  [ТС] #10
А если тут попробовать методом ветвей и границ? На сколько я помню метод на много меньше чем полным перебором
0
gazlan
3131 / 1906 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
25.05.2013, 08:23 #11
Цитата Сообщение от Jenya18 Посмотреть сообщение
методом ветвей и границ
Как вариант, если можете формализовать задачу. Вероятно, должно быть похоже на задачу коммивояжера.
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
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
0
Jenya18
0 / 0 / 0
Регистрация: 29.04.2013
Сообщений: 13
26.05.2013, 01:15  [ТС] #13
А может кто-то знает как решить данную задачу через потоковые алгоритмы?
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
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 Посмотреть сообщение
А может кто-то знает как решить данную задачу через потоковые алгоритмы?
Что это такое? В гугле по такому запросу нахожу только алгоритмы шифрования и тп.
0
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/ один из этих алгоритмов.
Задача стоит именно с помощью этих алгоритмов развязать задачу
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.05.2013, 16:07
Привет! Вот еще темы с ответами:

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника - PascalABC.NET
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он уплатил по 31 талеру, а за каждого быка по...

Задача на k-тую цифру последовательности, задача на схему Горнера. - Pascal
Ну, собственно опять прошу помощи... Задача 1: Определить k-тую цифру последовательности 1234567891011121314…, в которой выписаны подряд...

Первая смешанная задача для волнового уравнения на отрезке (задача о колебаниях ограниченной струны) методом Фурье - Дифференциальные уравнения
Решить первую смешанную задачу для волнового уравнения на отрезке (задача о колебаниях ограниченной струны) методом Фурье ...

Задача о размещении весов по ящикам (задача о рюкзаках) - Delphi
Есть упорядоченный по невозрастанию набор весов предметов w1..wn, которые необходимо распределить по ящикам способным выдержать вес V,...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
26.05.2013, 16:07
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru