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

Лотерея - C++

Восстановить пароль Регистрация
 
Entii
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 3
18.11.2013, 16:20     Лотерея #1
Задание:
Кликните здесь для просмотра всего текста
На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо M-значного числа в системе счисления с основанием K (то есть, по сути, каждый участник называет M цифр, каждая из которых лежит в диапазоне от 0 до K–1). Ведущие нули в числах допускаются.
В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также M-значное число в K-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере A1 рублей. Те, у кого совпали первые две цифры числа — получают A2 рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают A3 рублей. И так далее. Угадавшие все число полностью получают AM рублей. При этом если игрок угадал t первых цифр, то он получает At рублей, но не получает призы за угадывание t–1, t–2 и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.
Напишите программу, которая по известным ставкам, сделанным телезрителями, находит число, которое должна назвать телеведущая, чтобы фирма-организатор розыгрыша выплатила в качестве выигрышей минимальную сумму. Для вашего удобства ставки, сделанные игроками, уже упорядочены по неубыванию.
Входные данные

В первой строке входного файла INPUT.TXT задаются числа N (количество телезрителей, сделавших свои ставки, 1<=N<=100000), M (длина чисел 1<=M<=10) и K (основание системы счисления 2<=K<=10). В следующей строке записаны M чисел A1, A2, …, AM, задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (1<=A1<=A2<=…<=AM<=100000). В каждой из следующих N строк либо в одной строке через пробел записано по одному M-значному K-ичному числу. Числа идут в порядке неубывания.
Выходные данные

В выходной файл OUTPUT.TXT выведите наименьшую сумму, которую придется выплатить в качестве выигрыша.

Есть идеи?
На ум приходит только обход в ширину, что вряд ли пройдет по скорости.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2013, 16:20     Лотерея
Посмотрите здесь:

Лотерея) Pascal
напишите программу лотерея Pascal
Лотерея Pascal ABC
Лотерея Pascal ABC
Pascal Лотерея - Найдите результат проверки компьютером билета
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
18.11.2013, 16:56     Лотерея #2
решается жадно. сортируйте подсчетом и дальше понятно.
Entii
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 3
18.11.2013, 17:04  [ТС]     Лотерея #3
Если бы было понятно, не спрашивал бы
Entii
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 3
19.11.2013, 22:49  [ТС]     Лотерея #4
UP
Решил таки, однако проблема оказалась не со скоростью( хотя и с ней тоже, но не такая ужасная), а с памятью. Используется BFS:


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
#include <iostream> 
#include <fstream> 
#include <string> 
#include <vector> 
using namespace std; 
struct node  
    { 
        vector<string> v; //числа, которые должна просмотреть наша нода(node) 
        int p;//сколько денег будет потрачено при случае с текущей нодой 
        string t;//само значение ноды 
        node(vector<string> a,int b,string c){v=a;p=b;t=c;} 
    }; 
int a,m,n,p[100]; 
long long mn=999999999999; 
vector<string> k; 
vector<node> nodes; 
ifstream in("input.txt"); ofstream out("output.txt"); 
 
 
 
int main() 
{ 
    in>>a>>m>>n;//считываем данные из файла. а - количество названных чисел, м - длина числа, н - основание системы счисления  
    for (int i=0; i<m; i++) 
        in>>p[i];//считываем цену за угаданную цифру 
    for (int i=0; i<a; i++) 
        {string temp=""; in>>temp; k.push_back(temp);} // считываем сами числа 
    node nd(k,0,""); 
    nodes.push_back(nd);//создаем и пихаем в вектор первую пустую ноду 
    int *pr= new int[n];//массив возможных следующих цен 
    vector<string> *z=new vector<string>[n];//массив возможные следующих списков для перебора ноды 
    for (int i=0; i<nodes.size(); i++) 
    { 
 
        node temp=nodes[i];//текущая нода 
        int d =temp.t.size();//длина значения текущей ноды 
 
        for (int j=0; j<n; j++) 
            {z[j].clear(); pr[j]=temp.p;}//обнуляем наши массивы 
        if (d!=m)//если мы не дошли до максимальной длины числа 
        { 
        for (int j=0; j<temp.v.size(); j++) 
        { 
            z[int(temp.v[j][d]-'0')].push_back(temp.v[j]); 
            pr[int(temp.v[j][d]-'0')]+=p[d]-(d>0?p[d-1]:0);//кидаем наши варианты в массивы. 
        } 
        } 
        for (int j=0; j<n; j++) 
        { 
            if (z[j].size()==0 || d==m || temp.p>mn)//если мы дошли до максимума, или вариантов больше нету, или цена уже точно не подходит 
            { 
                if (mn>temp.p) mn=temp.p;//сохраняем новую лучшую цену 
            } 
            else 
            { 
                nodes.push_back(node(z[j],pr[j],(temp.t+char(j+'0'))));// иначе пихаем новую ноду в вектор 
            } 
        } 
        nodes.erase(nodes.begin());//удаляем текущую ноду 
        i--; 
    } 
    out<<mn; 
}
Решение через DFS сильно упиралось в скорость.
Как работает добавление вариантов в массив:
000 010 100 110
Запускаем программу, она создает первую пустую ноду.
Потом циклом смотрит на v[j][d] - то есть на d цифру у варианта j. А d у нас равно длине значения нашей ноды. Значит, если значение ноды пустое, d=0, значит смотрим на первую цифру. В следующих нодах d увеличивается, тем самым мы смотрим уже следующие цифры.

Как можно оптимизировать сие детище? Либо же здесь деревья совсем не подойдут?
P.S. переменные называются так убого из-за оценки кода по количеству символов.
Yandex
Объявления
19.11.2013, 22:49     Лотерея
Ответ Создать тему
Опции темы

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