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

Счастливые билеты - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.88
Zheka91
4 / 4 / 1
Регистрация: 22.11.2010
Сообщений: 101
09.11.2011, 11:56     Счастливые билеты #1
найти колличество счастливых билетов, колличество цыфр в билетах может быть до N (N<=100), помогите пожалуйсто, или хотябы подскажите...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.11.2011, 11:56     Счастливые билеты
Посмотрите здесь:

6-значные счастливые числа C++
C++ Программа про счастливые билеты. Не работает.
C++ Задача на счастливые билеты
C++ Счастливые числа
C++ Счастливые билеты
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
09.11.2011, 12:00     Счастливые билеты #2
Вы хоть условие нормально сформируйте, что за счастливые билеты, какие цифры, сколько выбирают этих билетов, а на данный момент можно дать ответ на Ваш вопрос:
стакан гвоздей стоит 3 рубля 50 копеек, а журавли улетают на юг.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.11.2011, 12:01     Счастливые билеты #3
Есть такая задачка на ********... Исходник есть только на java. На с++ придется писать длинную арифметику.
P.S. задача на динамическое программирование + длинная арифметика.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
09.11.2011, 12:04     Счастливые билеты #4
Прогуглил и всё равно не понял что за счастливые билеты, разве что на вики есть счастливые билеты с шестизначными номерами http://ru.wikipedia.org/wiki/Счастливый_билет, там же есть и реализация на с++.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.11.2011, 12:06     Счастливые билеты #5
Цитата Сообщение от Gepar Посмотреть сообщение
Прогуглил и всё равно не понял что за счастливые билеты, разве что на вики есть счастливые билеты с шестизначными номерами
Ну это числа, у которых сумма левой половины цифр совпадает с правой половиной.
Например, 1524(4-значный) или 12340550(8-значный)
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
09.11.2011, 12:27     Счастливые билеты #6
Это явно олимпиадная задача
Так что сам решай

Добавлено через 3 минуты
Хотя конечно все тупо
Половина билета - это N/2 == 50 цифр
минимальная половина - это 0...0 ( сумма цифр 0 )
максимальная половина - это 9...9 ( сумма цифр 450 )
Значит достаточно посчитать массив int sum[451] и заполнить его нужным образом
После этого ответ очевиден
int count= 0;
for ( i=0; i<=450; i++ ) { count+= sum[i]*sum[i]; }
printf( "%d\n", count );

Добавлено через 51 секунду
Хотя тут потребуется длинная арифметика
Похоже ответ не влазит в int64_t

Добавлено через 1 минуту
Достаточно посчитать только половину массива sum[]
Так как очевидно что массив симметричен
В частности например вариант с суммой цифр 0 единственный
то есть sum[0]= 1
И вариант со всеми 9-ками тоже единственный
то есть sum[450]= 1

Добавлено через 8 минут
Определение sum[]
sum[i] = кол-во чисел, сумма цифр которых равна i

Чтобы посчитать массив sum[] нужно использовать метод динамического программирования

Так что вполне себе подъемная задача - можно решить
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
09.11.2011, 12:46     Счастливые билеты #7
diagon прав, длинная арифметика нужна. Для случая 6-значных счастливых билетов можно так оптимально решить:
http://www.cyberforum.ru/showthread.php?p=1897091
kazak
 Аватар для kazak
3029 / 2350 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
09.11.2011, 14:21     Счастливые билеты #8
Цитата Сообщение от odip Посмотреть сообщение
Достаточно посчитать только половину массива sum[]
Так как очевидно что массив симметричен
Если это справедливо, тогда не
Цитата Сообщение от odip Посмотреть сообщение
for ( i=0; i<=450; i++ ) { count+= sum[i]*sum[i]; }
а for ( i=0; i<=225; i++ ) { count+= 2*sum[i]; }
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.11.2011, 17:42     Счастливые билеты #9
Цитата Сообщение от odip Посмотреть сообщение
Это явно олимпиадная задача
Так что сам решай

Добавлено через 3 минуты
Хотя конечно все тупо
Половина билета - это N/2 == 50 цифр
минимальная половина - это 0...0 ( сумма цифр 0 )
максимальная половина - это 9...9 ( сумма цифр 450 )
Значит достаточно посчитать массив int sum[451] и заполнить его нужным образом
После этого ответ очевиден
int count= 0;
for ( i=0; i<=450; i++ ) { count+= sum[i]*sum[i]; }
printf( "%d\n", count );

Добавлено через 51 секунду
Хотя тут потребуется длинная арифметика
Похоже ответ не влазит в int64_t

Добавлено через 1 минуту
Достаточно посчитать только половину массива sum[]
Так как очевидно что массив симметричен
В частности например вариант с суммой цифр 0 единственный
то есть sum[0]= 1
И вариант со всеми 9-ками тоже единственный
то есть sum[450]= 1

Добавлено через 8 минут
Определение sum[]
sum[i] = кол-во чисел, сумма цифр которых равна i

Чтобы посчитать массив sum[] нужно использовать метод динамического программирования

Так что вполне себе подъемная задача - можно решить
Да, у вас верная идея.
Примерно так получиться(пока без длинки):

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
#include <iostream>
#include <vector>
#include <cstdlib>
 
typedef unsigned long long bigInt;
typedef std::vector< std::vector< bigInt > > matrix_t;
 
int main()
{
    int n;
    std::cin >> n;
    
    if ( n % 2 != 0 || n < 2 )
    {
        std::cerr << "Incorrect input!\n";
        return EXIT_FAILURE;
    }
    
    n /= 2;
    
    matrix_t dinamic(n + 1, std::vector< bigInt > (n * 9 + 1) );
    
    /* dinamic[i][j] - количество i-значных билетов с суммой цифр, равной j */
    
    /* количество однозначных билетов с суммой цифр i (0 <= i <= 9) равно 1 */
    for (int i = 0; i <= 9 ; ++i)
        dinamic.at(1).at(i) = 1; 
        
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j <= i * 9 ; ++j)
        {
            for ( int k = std::max( j - 9, 0 ) ; k <= j  ; ++k)
            {
                dinamic.at(i).at(j) += dinamic.at(i - 1).at(k);
            }
        }
    }
    
    bigInt answer = 0;
    
    for (int i = 0 ; i <= n * 9 / 2 ; ++i)
        answer += 2 * dinamic.at(n).at(i) * dinamic.at(n).at(i);
        
    std::cout << answer;
}
Zheka91
4 / 4 / 1
Регистрация: 22.11.2010
Сообщений: 101
09.11.2011, 17:49  [ТС]     Счастливые билеты #10
Цитата Сообщение от diagon Посмотреть сообщение
Да, у вас верная идея.
Примерно так получиться(пока без длинки):

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
#include <iostream>
#include <vector>
#include <cstdlib>
 
typedef unsigned long long bigInt;
typedef std::vector< std::vector< bigInt > > matrix_t;
 
int main()
{
    int n;
    std::cin >> n;
    
    if ( n % 2 != 0 || n < 2 )
    {
        std::cerr << "Incorrect input!\n";
        return EXIT_FAILURE;
    }
    
    n /= 2;
    
    matrix_t dinamic(n + 1, std::vector< bigInt > (n * 9 + 1) );
    
    /* dinamic[i][j] - количество i-значных билетов с суммой цифр, равной j */
    
    /* количество однозначных билетов с суммой цифр i (0 <= i <= 9) равно 1 */
    for (int i = 0; i <= 9 ; ++i)
        dinamic.at(1).at(i) = 1; 
        
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j <= i * 9 ; ++j)
        {
            for ( int k = std::max( j - 9, 0 ) ; k <= j  ; ++k)
            {
                dinamic.at(i).at(j) += dinamic.at(i - 1).at(k);
            }
        }
    }
    
    bigInt answer = 0;
    
    for (int i = 0 ; i <= n * 9 / 2 ; ++i)
        answer += 2 * dinamic.at(n).at(i) * dinamic.at(n).at(i);
        
    std::cout << answer;
}
я написал тоже с одного сайта скачал длинные числа тока чето ни как не могу их применить, мошь поможите...
Вложения
Тип файла: rar билеты.rar (3.6 Кб, 32 просмотров)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.11.2011, 08:00     Счастливые билеты #11
Нет, у меня где-то есть баг, ответ выдает неверный. Доделаю, когда ******** заработает, а то мне тестировать не на чем.

Добавлено через 1 час 15 минут
Написал свою длинку с блекджеком и прочим.
Должно работать, но не помешало бы протестировать =\ А ******** до сих пор лежит.
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>
#include <string>
#include <iomanip>
#include <cstdlib>
 
class BigInteger
{
protected:
 
    std::vector<int> value;
    static const int base = 1e9;
    static const int count_of_digits = 9;
    
public:
 
    BigInteger();   
    BigInteger( const std::string& );
    BigInteger( long long );
    
    BigInteger& operator = ( const BigInteger& );
    BigInteger& operator += ( const BigInteger& );
    BigInteger& operator *= ( const BigInteger& );
    
    friend BigInteger operator + ( const BigInteger&, const BigInteger& );
    friend BigInteger operator * ( const BigInteger&, const BigInteger& );
    
    friend std::istream& operator >> ( std::istream&, BigInteger& );
    friend std::ostream& operator << ( std::ostream&, const BigInteger& );
};
 
 
typedef BigInteger bigInt;
typedef std::vector< std::vector< bigInt > > matrix_t;
 
int main()
{
    int n;
    std::cin >> n;
    
    if ( n % 2 != 0 || n < 2 )
    {
        std::cerr << "Incorrect input!\n";
        return EXIT_FAILURE;
    }
    
    n /= 2;
    
    matrix_t dinamic(n + 1, std::vector< bigInt > (n * 9 + 1) );
    
    /* dinamic[i][j] - количество i-значных билетов с суммой цифр, равной j */
    
    /* количество однозначных билетов с суммой цифр i (0 <= i <= 9) равно 1 */
    for (int i = 0; i <= 9 ; ++i)
        dinamic.at(1).at(i) = 1; 
        
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j <= i * 9 ; ++j)
        {
            for ( int k = 0 ; k <= std::min( j, 9 ) ; ++k)
            {
                dinamic.at(i).at(j) += dinamic.at(i - 1).at(j - k);
            }
        }
    }
    
    bigInt answer = 0;
    
    for (int i = 0 ; i <= n * 9  ; ++i)
        answer += dinamic.at(n).at(i) * dinamic.at(n).at(i);
        
    std::cout << answer;
}
 
BigInteger::BigInteger( const std::string& str )
{
    for (int i = str.length() ; i > 0 ; i -= count_of_digits)
    {
        if ( i < count_of_digits )
        {
            value.push_back( atoi( str.substr(0, i).c_str() ) );
        }
        else
        {
            value.push_back( atoi( str.substr(i - count_of_digits, count_of_digits).c_str() ) );
        }
    }
}
 
BigInteger::BigInteger()
{
    value.push_back(0);
}
 
BigInteger::BigInteger( long long x )
{
    std::ostringstream ost;
    ost << x;
    std::string str = ost.str();
    
    for (int i = str.length() ; i > 0 ; i -= count_of_digits)
    {
        if ( i < count_of_digits )
        {
            value.push_back( atoi( str.substr(0, i).c_str() ) );
        }
        else
        {
            value.push_back( atoi( str.substr(i - count_of_digits, count_of_digits).c_str() ) );
        }
    }
    
}
 
BigInteger& BigInteger::operator += ( const BigInteger& b )
{
    for ( int temp = 0, i = 0; i < (int) std::max( this->value.size(), b.value.size() ) || temp != 0 ; ++i)
    {
        if ( i == (int) value.size() )
            value.push_back( 0 );
        
        value[i] += temp + ( i < (int) b.value.size() ? b.value[i] : 0 );
        temp = value[i] >= base;
        
        if ( temp != 0 )
            value[i] -= base;
    }
    
    return *this;
}
 
BigInteger operator + ( const BigInteger& a, const BigInteger& b )
{
    BigInteger c = a;
    c += b;
    return c;
}
 
std::istream& operator >> ( std::istream& stream, BigInteger& big )
{
    std::string str;
    std::cin >> str;
    big = BigInteger(str);
    
    return stream;  
}
 
std::ostream& operator << ( std::ostream& stream, const BigInteger& big )
{
    if ( big.value.empty() )
        stream << 0;
    else
        stream << big.value.back();
        
    for (int i = (int) big.value.size() - 2; i >= 0; --i)
    {
        stream << std::setfill('0') << std::setw(BigInteger::count_of_digits) << big.value[i];
    }
    
    return stream;
}
 
BigInteger& BigInteger::operator = ( const BigInteger& big )
{
    this->value = big.value;
    
    return *this;
}
 
BigInteger operator * ( const BigInteger& a, const BigInteger& b )
{
    BigInteger c;
    c.value.resize( a.value.size() + b.value.size() );
    
    for (int i = 0; i < (int) a.value.size(); ++i)
    {
        for (int j = 0, carry = 0 ; j < (int) b.value.size() || carry != 0 ; ++j)
        {
            long long cur = c.value[i + j] + a.value[i] * 1ll * ( j < (int) b.value.size() ? b.value[j] : 0 ) + carry;
            
            c.value[i + j] = int( cur % BigInteger::base );
            
            carry = int ( cur / BigInteger::base );         
        }   
    }
    
    while ( c.value.size() > 1 && c.value.back() == 0 )
    {
        c.value.pop_back();
    }
    
    return c;
}
 
BigInteger& BigInteger::operator *= ( const BigInteger& big )
{
    BigInteger a = *this;
    *this = a + big;
    return *this;
}

Не по теме:

Час всего ушел х) Я думал часа 3 уже пишу, не меньше.



P.S. ассимптотика решения - http://www.cyberforum.ru/cgi-bin/latex.cgi?O({n}^{2})

Добавлено через 12 часов 17 минут
******** заработал - Accepted
0.08 на самом большом тесте работает
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.11.2011, 07:56     Счастливые билеты
Еще ссылки по теме:

C++ Счастливые билеты
C++ Счастливые числа
C++ Счастливые билетики

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

Или воспользуйтесь поиском по форуму:
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
18.11.2011, 07:56     Счастливые билеты #12
Да, у вас верная идея.
Ну так не первую задачу на ******** решаю
Yandex
Объявления
18.11.2011, 07:56     Счастливые билеты
Ответ Создать тему
Опции темы

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