Решение задачи Lucky Tickets. Easy! с Timus

Без пояснения   Просмотров: 47


The public transport administration of Ekaterinburg is anxious about the fact that passengers don’t like to pay for passage doing their best to avoid the fee. All the measures that had been taken (hard currency premiums for all of the chiefs, increase in conductors’ salaries, reduction of number of buses) were in vain. An advisor especially invited from the Ural State University says that personally he doesn’t buy tickets because he rarely comes across the lucky ones (a ticket is lucky if the sum of the first three digits in its number equals to the sum of the last three ones). So, the way out is found — of course, tickets must be numbered in sequence, but the number of digits on a ticket may be changed. Say, if there were only two digits, there would have been ten lucky tickets (with numbers 00, 11, …, 99). Maybe under the circumstances the ratio of the lucky tickets to the common ones is greater? And what if we take four digits? A huge work has brought the long-awaited result: in this case there will be 670 lucky tickets. But what to do if there are six or more digits?
Администрация общественного транспорта Екатеринбурга обеспокоена тем, что пассажиры не хотят платить за проезд, делая все возможное, чтобы избежать платы. Все принятые меры (надбавки в твердой валюте для всех руководителей, повышение зарплаты кондукторов, сокращение количества автобусов) были тщетными. Консультант, специально приглашенный из Уральского государственного университета, говорит, что лично он не покупает билеты, потому что он редко сталкивается с счастливчиками (билет счастлив, если сумма первых трех цифр в его номере равна сумме трех последних из них). Итак, выход найден - конечно, билеты должны быть пронумерованы по порядку, но число цифр в билете может быть изменено. Скажем, если бы было только две цифры, было бы десять счастливых билетов (с номерами 00, 11, ..., 99). Может быть, в этих условиях отношение счастливых билетов к обычным больше? А что если мы возьмем четыре цифры? Огромная работа принесла долгожданный результат: в этом случае будет 670 счастливых билетов. Но что делать, если есть шесть или более цифр?

Код

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    switch(n){
        case 2: cout << 10; break;
        case 4: cout << 670; break;
        case 6: cout << 55252; break;
        case 8: cout << 4816030; break;
    }
    return 0;
}

Ниже приведена программа, как я всё это высчитал, не считая чисел, которые начинаются с нуля.

#include<bits/stdc++.h>

using namespace std;
bool solve(string n)
{
    int s = 0, s1 = 0;
    for(int i = 0; i < n.size()/2; ++i)
        s += n[i] - 48;
    for(int i = n.size()/2; i < n.size(); ++i)
        s1 += n[i] - 48;
    if(s == s1)
        return true;
    return false;
}
int main()
{
    system("chcp 1251");
    int k = 0;
    for(int i = 10; i < 100; ++i){
        if(solve(to_string(i)))
            ++k;
    }
    cout << "Кол-во 2 значных счатливых бидетов - " << k << endl;

    k = 0;
    for(int i = 1000; i < 10000; ++i){
        if(solve(to_string(i)))
            ++k;
    }
    cout << "Кол-во 4 значных счатливых бидетов - " << k << endl;

    k = 0;
    for(int i = 100000; i < 1000000; ++i){
        if(solve(to_string(i)))
            ++k;
    }
    cout << "Кол-во 6 значных счатливых бидетов - " << k << endl;

    k = 0;
    for(int i = 10000000; i < 100000000; ++i){
        if(solve(to_string(i)))
            ++k;
    }
    cout << "Кол-во 8 значных счатливых бидетов - " << k << endl;
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться