Обсуждение @ 1044. Счастливые билеты. Easy! @ Timus Online Judge

Alexey Shestakov Для тех, у кого нет идей к решению // Задача 1044. Счастливые билеты. Easy! 20 июн 2026 15:53

zser Brute force Accept in 1.625 [1] // Задача 1044. Счастливые билеты. Easy! 8 июн 2025 20:41

#include <bits/stdc++.h>
using namespace std;

int cal(int x){
    int ret = 0;
    while (x > 0){
        ret += x % 10;
        x /= 10;
    }
    return ret;
}

bool lucky(int x, int mm){
    int a = x / mm;
    int b = x % mm;
    if (cal(a) == cal(b)) return true;
    return false;
}

int main(){
    int n;
    cin >> n;
    int nn = round(pow(10, n)) - 1;
    int mm = round(pow(10, n / 2));
    int tot = 0;
    for (int i = 0; i <= nn; i++){
        if (lucky(i, mm)) tot++;
    }
    cout << tot << endl;
}

if your code is simple and fast enough, brute force can work.

codeJutsu Re: Brute force Accept in 1.625 // Задача 1044. Счастливые билеты. Easy! 14 сен 2025 22:58

the input N consists of only even numbers, meaning the number of digits won't be odd.
moreover, input range is limited between 2 and 8, meaning the only possible inputs are 2, 4, 6 and 8.

now this would be my approach :

lets say, the input number is 4 digits in length. meaning, the sum of the first 2 digits need to be equal to the sum of the last 2 digits.

what i'd do is, i'd check for all 2-digit numbers starting from 00 all the way to 99, and store the sum of their digits in an array (in this particular case there are total 100 numbers so that'd be the array length).

after storing the sums in an array, i'd run nested loops through the array. the outer loop would take a sum value from an index. the inner loop would search through all elements in the array from the beginning to the end (including that index from the outer loop too) to see if any sum value matches the outer loop's index sum value. if there's a match, the count increases by 1. the final value of the count is the answer. this process of nested loops is time consuming, so we can sort the array first and then only run the inner loop as long as the next sum values match with the current sum value. this will only improve the performance slightly, as there will still be cases that need the inner loop to run for longer.

a far better approach would be to find the maximum possible value of the sums, and then take an array of that size plus 1. for our example of 4-digit numbers, the maximum possible sum of 2-digit numbers would be 9+9=18 (or 9x2=18) because 99 is the largest 2-digit number. thus the array size here would be 18+1=19 (so that we can access from array[0] all the way to array[18] when needed).

initially, all index values of this array would be 0. as we go through all the 2-digit numbers, we'll find the sum of their digits and raise the value of the corresponding index in the array by 1. this way, we'll immediately know how many times a particular sum has occurred by just looking at that sum's index value, instead of running nested loops. for example, if array[4]=5, then the sum 4 has occurred 5 times in all 2-digit numbers (04, 13, 22, 31, 40). again, if array[5]=6, then the sum 5 has occurred 6 times (05, 14, 23, 32, 41, 50). all we need to do then is find the total sum of all the individual sum count's squares from the entire array.

in case someone doesn't understand why we need to square the individual sum counts : we only counted the sums for 2-digits in our example. but all the possible cases of the 2-digits for a particular sum will occur in both the left half and the right half of a 4-digit number. lets say, the sum value was 4 and a total of 5 cases were found where the 2-digits sum up to 4. then, for each of these 5 cases in one side, all of these 5 cases will occur too in the other side. thus, there will be 5x5=25 total cases where a 4-digit number will have the sum of its left half digits as 4 and the sum of its right half digits as 4 as well. if the sum value was 5, then we'd find 6x6=36 total such 4-digit numbers. that's why we square the individual sum counts before adding them up to the total sum.

there might be even better approaches that i'm not familiar with just yet. maybe an alien would be able to help you with such superior alien concepts.

nushrat Help me with the algorithm [1] // Задача 1044. Счастливые билеты. Easy! 19 ноя 2016 07:11

Hi,

I need desperate help with building the algo. It seemed easy at first, but I am getting all confused. Can anyone explain the step for calculation ?

Suppose the input is 4 digits, so that means I have to fill up 4 spaces with 9 digits(0-9) for each space and from the combinations, find the one that has equal sum for first 2 and last 2 digits.

If someone can help me with the steps, I think I can figure out the rest.

Thanks in advance.

codeJutsu Re: Help me with the algorithm // Задача 1044. Счастливые билеты. Easy! 14 сен 2025 22:23

the input N consists of only even numbers, meaning the number of digits won't be odd.
moreover, input range is limited between 2 and 8, meaning the only possible inputs are 2, 4, 6 and 8.

now this would be my approach :

lets say, the input number is 4 digits in length. meaning, the sum of the first 2 digits need to be equal to the sum of the last 2 digits.

what i'd do is, i'd check for all 2-digit numbers starting from 00 all the way to 99, and store the sum of their digits in an array (in this particular case there are total 100 numbers so that'd be the array length).

after storing the sums in an array, i'd run nested loops through the array. the outer loop would take a sum value from an index. the inner loop would search through all elements in the array from the beginning to the end (including that index from the outer loop too) to see if any sum value matches the outer loop's index sum value. if there's a match, the count increases by 1. the final value of the count is the answer. this process of nested loops is time consuming, so we can sort the array first and then only run the inner loop as long as the next sum values match with the current sum value. this will only improve the performance slightly, as there will still be cases that need the inner loop to run for longer.

a far better approach would be to find the maximum possible value of the sums, and then take an array of that size plus 1. for our example of 4-digit numbers, the maximum possible sum of 2-digit numbers would be 9+9=18 (or 9x2=18) because 99 is the largest 2-digit number. thus the array size here would be 18+1=19 (so that we can access from array[0] all the way to array[18] when needed).

initially, all index values of this array would be 0. as we go through all the 2-digit numbers, we'll find the sum of their digits and raise the value of the corresponding index in the array by 1. this way, we'll immediately know how many times a particular sum has occurred by just looking at that sum's index value, instead of running nested loops. for example, if array[4]=5, then the sum 4 has occurred 5 times in all 2-digit numbers (04, 13, 22, 31, 40). again, if array[5]=6, then the sum 5 has occurred 6 times (05, 14, 23, 32, 41, 50). all we need to do then is find the total sum of all the individual sum count's squares from the entire array.

in case someone doesn't understand why we need to square the individual sum counts : we only counted the sums for 2-digits in our example. but all the possible cases of the 2-digits for a particular sum will occur in both the left half and the right half of a 4-digit number. lets say, the sum value was 4 and a total of 5 cases were found where the 2-digits sum up to 4. then, for each of these 5 cases in one side, all of these 5 cases will occur too in the other side. thus, there will be 5x5=25 total cases where a 4-digit number will have the sum of its left half digits as 4 and the sum of its right half digits as 4 as well. if the sum value was 5, then we'd find 6x6=36 total such 4-digit numbers. that's why we square the individual sum counts before adding them up to the total sum.

there might be even better approaches that i'm not familiar with just yet. maybe an alien would be able to help you with such superior alien concepts.

Edited by author 14.09.2025 22:42

IlushaMax Your computer won't explode if you will do like here))) [1] // Задача 1044. Счастливые билеты. Easy! 1 апр 2016 23:55

SorrowAngel I HAVE THE CODE [2] // Задача 1044. Счастливые билеты. Easy! 23 апр 2008 13:13

anupam ghosh what about odd number of digits? Could someone explain Please [4] // Задача 1044. Счастливые билеты. Easy! 28 дек 2011 19:38

Pearl Precalculate is not needed [1] // Задача 1044. Счастливые билеты. Easy! 30 сен 2018 18:01

vegetable DP // Задача 1044. Счастливые билеты. Easy! 17 сен 2021 19:11

Debagnik Roy leading zeroes allowed?? [1] // Задача 1044. Счастливые билеты. Easy! 1 май 2019 11:03

holtaf ha-ha-ha [5] // Задача 1044. Счастливые билеты. Easy! 14 ноя 2010 15:18

jedianmb WA test 3. But it answers correctly on my machine... [1] // Задача 1044. Счастливые билеты. Easy! 31 янв 2020 16:03

_RaIM_ dp solution // Задача 1044. Счастливые билеты. Easy! 18 дек 2019 20:31

liuchang Who can tell me how to caculate 4? [1] // Задача 1044. Счастливые билеты. Easy! 23 авг 2003 14:54

Abid29 A combinatorial approach // Задача 1044. Счастливые билеты. Easy! 25 июн 2019 00:31

Nikolay Makarov interesting solution - it works!!)) [15] // Задача 1044. Счастливые билеты. Easy! 30 янв 2007 22:16

ViktYusk One line solution in Python))) // Задача 1044. Счастливые билеты. Easy! 28 дек 2018 03:21

Rafat Islam .001 AC solution without memoization . [1] // Задача 1044. Счастливые билеты. Easy! 2 ноя 2016 20:29

Manciu Ion generate all sums with recursion // Задача 1044. Счастливые билеты. Easy! 21 янв 2017 01:59

obukkhov Где описание на русском? [2] // Задача 1044. Счастливые билеты. Easy! 20 фев 2016 16:47

Vladimir Problem [8] // Задача 1044. Счастливые билеты. Easy! 7 окт 2002 13:05

Обсуждение задачи 1044. Счастливые билеты. Easy!