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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.88
Zheka91
4 / 4 / 1
Регистрация: 22.11.2010
Сообщений: 101
#1

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

09.11.2011, 11:56. Просмотров 3484. Ответов 11
Метки нет (Все метки)

найти колличество счастливых билетов, колличество цыфр в билетах может быть до N (N<=100), помогите пожалуйсто, или хотябы подскажите...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.11.2011, 11:56
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Счастливые билеты (C++):

Счастливые билеты - C++
Знаю, что вопрос довольно распространенный и решений можно найти много, но у меня ограниченное задание: нужно найти сумму всех счастливых...

Счастливые билеты - C++
Здравствуйте, имеется интересная задачка. Вводится первое и последнее возможные числа билетовЮ, нужно посчитать сколько счастливых...

Задача на счастливые билеты C++ - C++
Найдите кол-во счастливых билетов типа - XXXXXX Счастливым является билет у которого три первые цифры равны трём последним Первый билет...

Задача на счастливые билеты - C++
Уважаемые господа ! Будте добры , помогите решить задачку. Имееться билет с шестизначным номером(числом). Билет считаеться счастливым...

Программа про счастливые билеты. Не работает. - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;clocale&gt; using namespace std; void Input(int &amp;N1, int &amp;N2) { cout &lt;&lt;...

Счастливые числа - C++
Счастливым будем считать такое число из шести цифр, кортом сумма левых трех цифр равна сумме правых трех цифр. Найти все счастливые билеты...

11
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
09.11.2011, 12:00 #2
Вы хоть условие нормально сформируйте, что за счастливые билеты, какие цифры, сколько выбирают этих билетов, а на данный момент можно дать ответ на Ваш вопрос:
стакан гвоздей стоит 3 рубля 50 копеек, а журавли улетают на юг.
1
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.11.2011, 12:01 #3
Есть такая задачка на ********... Исходник есть только на java. На с++ придется писать длинную арифметику.
P.S. задача на динамическое программирование + длинная арифметика.
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
09.11.2011, 12:04 #4
Прогуглил и всё равно не понял что за счастливые билеты, разве что на вики есть счастливые билеты с шестизначными номерами http://ru.wikipedia.org/wiki/Счастливый_билет, там же есть и реализация на с++.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.11.2011, 12:06 #5
Цитата Сообщение от Gepar Посмотреть сообщение
Прогуглил и всё равно не понял что за счастливые билеты, разве что на вики есть счастливые билеты с шестизначными номерами
Ну это числа, у которых сумма левой половины цифр совпадает с правой половиной.
Например, 1524(4-значный) или 12340550(8-значный)
0
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
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[] нужно использовать метод динамического программирования

Так что вполне себе подъемная задача - можно решить
1
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
09.11.2011, 12:46 #7
diagon прав, длинная арифметика нужна. Для случая 6-значных счастливых билетов можно так оптимально решить:
http://www.cyberforum.ru/showthread.php?p=1897091
0
kazak
3048 / 2369 / 160
Регистрация: 11.03.2009
Сообщений: 5,436
Завершенные тесты: 1
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]; }
0
diagon
Higher
1930 / 1196 / 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;
}
0
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;
}
я написал тоже с одного сайта скачал длинные числа тока чето ни как не могу их применить, мошь поможите...
0
Вложения
Тип файла: rar билеты.rar (3.6 Кб, 32 просмотров)
diagon
Higher
1930 / 1196 / 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 на самом большом тесте работает
1
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
18.11.2011, 07:56 #12
Да, у вас верная идея.
Ну так не первую задачу на ******** решаю
0
18.11.2011, 07:56
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.11.2011, 07:56
Привет! Вот еще темы с ответами:

Счастливые числа - C++
Как-то не могу вникнуть в суть кода :( Назовем число счастливым, если сумма цифр на четных позициях равня сумме цифр на нечетных...

Счастливые числа - C++
Вот мой код: #include &lt;stdio.h&gt; int main() { int T,count,i,s,k,l,r; s = 0; k = 0;

Счастливые билетики - C++
Знаю что задача довольна распространена, но решения для моего случая не нашел. Необходимо найти количество всех счастливых билетов(сумма...

6-значные счастливые числа - C++
Здравствуйте, прошу помощи! Тема: Функции. Получить все 6-значные счастливые числа, т.е. те, у которых сумма первых трех цифр...


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

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