| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Brute force Accept in 1.625 | zser | 1044. Счастливые билеты. Easy! | 14 сен 2025 22:58 | 2 | #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. 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. | | Help me with the algorithm | nushrat | 1044. Счастливые билеты. Easy! | 14 сен 2025 22:23 | 2 | 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. 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 | | Your computer won't explode if you will do like here))) | IlushaMax | 1044. Счастливые билеты. Easy! | 14 сен 2025 16:58 | 2 | Just use brute force for getting values for 2,4,6,8 and write it
Edited by author 01.04.2016 23:55 | | I HAVE THE CODE | SorrowAngel | 1044. Счастливые билеты. Easy! | 14 сен 2025 16:53 | 3 | {$APPTYPE CONSOLE}
uses
SysUtils;
var
n:integer;
begin
reset (input,'input.txt');
rewrite (output,'output.txt');
read (n);
if n=2 then
begin
write (10);
halt;
end;
if n=3 then
begin
write (100);
halt;
end;
if n=4 then
begin
write (670);
halt;
end;
if n=5 then
begin
write (6700);
halt;
end;
if n=6 then
begin
write (55252);
halt;
end;
if n=7 then
begin
write (552520);
halt;
end;
if n=8 then
begin
write (4816030);
halt;
end;
if n=9 then
begin
write (48160300);
halt;
end;
if n=10 then
begin
write ('432457640');
halt;
end;
{rewrite (output,'output.txt');
res:=0;
for i:=0 to 9 do
for f:=0 to 9 do
for g:=0 to 9 do
for k:=0 to 9 do
for j:=0 to 9 do
for d:=0 to 9 do
for h:=0 to 9 do
for a:=0 to 9 do
for s:=0 to 9 do
for q:=0 to 9 do
if i+f+g+k+j=d+h+a+s+q then }
end. You are the best problemreader WOW, lol. if only such methods could solve all real life problems.
edit : we solve problems to enhance our skills, not to get the result fast.
Edited by author 14.09.2025 16:54 | | what about odd number of digits? Could someone explain Please | Anupam Ghosh, Wipro Technologies | 1044. Счастливые билеты. Easy! | 14 сен 2025 16:51 | 5 | Hi,
Is this number 63363 lucky number?
Is it necessary all lucky numbers have to be a palindrome?
Regards
Anupam If number of digits is odd, answer is 0. I don't agree. There is no such rule. So you can solve the n-1 problem and then multiplicate it on 10. According to the problem the input number isn't odd as it is divisible 2. source:
"Output
should contain a number of tickets such that the sum of the first half of digits is equal to the sum of the second half of digits." the input says "an even integer N", so there should be no odd number as input. | | Precalculate is not needed | Pearl | 1044. Счастливые билеты. Easy! | 3 июн 2024 00:51 | 2 | #include <iostream>
using namespace std;
int sumDigit(int n) {
int sum = 0;
while (n) {
sum += n % 10;
n /= 10;
}
return sum;
}
int main()
{
int n;
cin >> n;
if (n % 2 == 1) {
cout << 0;
} else {
// We need to choose at most 4 digits, so the largest digit sum is 9*4
int count[9*4 + 1] = {0};
int halfN = n / 2;
int maxNum = 9;
for (int i = 1; i < halfN; ++i) {
maxNum *= 10;
maxNum += 9;
}
// Count the ways to create a particular sum
for (int i = 0; i <= maxNum; ++i)
++count[sumDigit(i)];
// Now, for each number i whose digit sum are s, there are
// count[s] numbers (including i itself) have the sum s.
// So we have count[s] ways to choose the second half.
int result = 0;
for (int i = 0; i <= maxNum; ++i)
result += count[sumDigit(i)];
cout << result;
}
return 0;
} thanks a lot.It was really helpful
| | DP | vegetable | 1044. Счастливые билеты. Easy! | 17 сен 2021 19:11 | 1 | DP vegetable 17 сен 2021 19:11 n/=2;
dp[n][n*9];
dp[i][j] = dp[i-1][j]+dp[i-1][j-1] + ... + dp[i-1][j-9];
ans = dp[n][0]*dp[n][0] + ... + dp[n][n*9]*dp[n][n*9];
Edited by author 17.09.2021 19:12
Edited by author 17.09.2021 19:12 | | leading zeroes allowed?? | Debagnik Roy | 1044. Счастливые билеты. Easy! | 20 июл 2020 03:02 | 2 | are leading zeroes allowed?
for example... will 0110 be counted as a valid 4 digit lucky number? | | ha-ha-ha | holtaf | 1044. Счастливые билеты. Easy! | 17 фев 2020 06:55 | 6 | #include<iostream>
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;
} nnn Mohigul Rahmonova 3 фев 2012 16:53
Edited by author 03.02.2012 16:53 print(([0,10,670,55252,4816030])[int(input())//2])
hahahahahahaha | | WA test 3. But it answers correctly on my machine... | jedianmb | 1044. Счастливые билеты. Easy! | 31 янв 2020 17:11 | 2 | Can't find the error, because it gives the same answers as those stupid precalc solutions:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int soma[40] = {0};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, i, lim;
ll ans = 0;
cin >> n;
lim = pow(10, n/2);
for(i=0; i<lim; ++i){
soma[i%10 + (i/10)%10 + (i/100)%10 + (i/1000)%10]++;
}
for(i=0; i<=n*9; ++i){
ans += soma[i]*soma[i];
}
cout << ans << '\n';
return 0;
} for(i=0; i<=n*9; ++i){
ans += soma[i]*soma[i];
}
i is out of soma range. | | dp solution | raimkek | 1044. Счастливые билеты. Easy! | 18 дек 2019 20:31 | 1 | Can someone give idea or hint of dynamic prog solution? | | Who can tell me how to caculate 4? | liuchang | 1044. Счастливые билеты. Easy! | 25 июн 2019 01:47 | 2 | who can tell me why it is 670 when the number is 4? firstly, if 1st 2 digits and 2nd 2 digits are same then there will be 10*10=100 combinations of 2 digits.
for every number there will be 2 combination.(example:1212 and 1221)
so,combinations will be 2*100=200. But there are such 10 numbers for which 2 combinations are not available.(ex: 0000 , 1111 , 5555)
COMBINATIONS = 200-10 = 190.
now, we have to check from highest 9+9=18 to lowest 0+0=0 that how much sets have same sum.
16<<<< (9+7),(8+8)
15<<<< (9+6),(8+7)
14<<<< (9+5),(8+6),(7+7)
13<<<< (9+4),(8+5),(7+6)
12<<<< (9+3),(8+4),(7+5),(6+6)
11<<<< (9+2),(8+3),(7+4),(6+5)
10<<<< (9+1),(8+2),(7+3),(6+4),(5+5)
9<<<< (9+0),(8+1),(7+2),(6+3),(5+4)
8<<<< (8+0),(7+1),(6+2),(5+3),(4+4)
7<<<< (7+0),(6+1),(5+2),(4+3)
6<<<< (6+0),(5+1),(4+2),(3+3)
5<<<< (5+0),(4+1),(3+2)
4<<<< (4+0),(3+1),(2+2)
3<<<< (3+0),(2+1)
2<<<< (2+0),(1+1)
combinations =(2*2*2/2)+(2*2*2)+(2*2*2+2*2+2*2) +(3*2*2*2)+..................................+(2*2*2)+(2*2) =480
SO, total combinations = 190+480 =670 | | A combinatorial approach | abid1729 | 1044. Счастливые билеты. Easy! | 25 июн 2019 00:31 | 1 | firstly, if 1st 2 digits and 2nd 2 digits are same then there will be 10*10=100 combinations of 2 digits.
for every number there will be 2 combination.(example:1212 and 1221)
so,combinations will be 2*100=200. But there are such 10 numbers for which 2 combinations are not available.(ex: 0000 , 1111 , 5555)
COMBINATIONS = 200-10 = 190.
now, we have to check from highest 9+9=18 to lowest 0+0=0 that how much sets have same sum.
16<<<< (9+7),(8+8)
15<<<< (9+6),(8+7)
14<<<< (9+5),(8+6),(7+7)
13<<<< (9+4),(8+5),(7+6)
12<<<< (9+3),(8+4),(7+5),(6+6)
11<<<< (9+2),(8+3),(7+4),(6+5)
10<<<< (9+1),(8+2),(7+3),(6+4),(5+5)
9<<<< (9+0),(8+1),(7+2),(6+3),(5+4)
8<<<< (8+0),(7+1),(6+2),(5+3),(4+4)
7<<<< (7+0),(6+1),(5+2),(4+3)
6<<<< (6+0),(5+1),(4+2),(3+3)
5<<<< (5+0),(4+1),(3+2)
4<<<< (4+0),(3+1),(2+2)
3<<<< (3+0),(2+1)
2<<<< (2+0),(1+1)
combinations =(2*2*2/2)+(2*2*2)+(2*2*2+2*2+2*2) +(3*2*2*2)+..................................+(2*2*2)+(2*2) =480
SO, total combinations = 190+480 =670 | | interesting solution - it works!!)) | Eternal | 1044. Счастливые билеты. Easy! | 16 май 2019 12:08 | 16 | #include <stdio.h>
int main(){
int n;
scanf("%d", &n);
if (n == 2) {
printf("10");
return 0;
}
if (n == 4) {
printf("670");
return 0;
}
if (n == 6) {
printf("55252");
return 0;
}
printf("4816030");
return 0;
} Here is nothing interesting! It's cheating solution. You precalc all variants and nothing else. I don't think, that this solution is cheating, but it also isn't interesting. Just a simple problem.) It is easy to understand why it works but how did you calculate the numbers for 4, 6, 8? With a calculator?!! In Russian this solution call "Частный случай" "Частный случай" you are right!
Every one has a chance to say some thing in mother language...i also saying...
এতে ইজি কিছহু নাই। সব ই কথিন। oho~I found a partner, Chinese man বুকে আসেন ভাই :D @shahed adnan
Edited by author 04.05.2019 21:05
Edited by author 04.05.2019 21:05 This code works but that's not real ans.
Edited by author 16.05.2019 12:10 Well he wrote a programm to calculate the answers first, so this is a solution.
And due to the performace it is the very good solution.
So stop winning and be smart guy. Thanks for giving test data!! \*^_^*/ | | One line solution in Python))) | ViktYusk | 1044. Счастливые билеты. Easy! | 28 дек 2018 03:21 | 1 | print([None, 10, 10, 100, 670, 6700, 55252, 552520, 4816030, 48160300][int(input())]) | | .001 AC solution without memoization . | Rafat Islam | 1044. Счастливые билеты. Easy! | 6 авг 2017 22:17 | 2 | #include <bits/stdc++.h>
using namespace std ;
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define mem(x,val) memset((x),(val),sizeof(x))
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define PI acos(-1.0)
const int INF = 1 << 29 ;
typedef long long ll ;
int N(int n , int k ) {
if(n == 1) return k<10?1:0 ;
int sum = 0 ;
for(int i = 0 ;i<= 9 && i<=k ; i++){
sum+=N(n-1 , k-i) ;
}
return sum ;
}
int main() {
int n ,sum = 0 , temp ;
scanf("%d" ,&n) ;
n/= 2 ;
for(int i = 0 ; i<=n*9 ;i++){
temp = N(n,i) ;
sum+=(temp*temp) ;
}
printf("%d\n" , sum) ;
return 0 ;
} | | generate all sums with recursion | Manciu Ion | 1044. Счастливые билеты. Easy! | 21 янв 2017 01:59 | 1 | #include <iostream>
#include <stdio.h>
#include <memory.h>
#define NMAX 37
using namespace std;
long cnt[NMAX];
int n;
void genSum(int k, int sum);
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "rt", stdin);
///freopen("output.txt", "wt", stdout);
#endif
scanf("%d", &n);
genSum (0 , 0);
int answer = 0;
for (int it = 9 * n / 2; it >= 0; --it)
{
answer += cnt[it] * cnt[it];
}
printf("%d\n", answer);
return 0;
}
void genSum(int k, int sum)
{
if (k == n / 2)
{
++cnt[ sum ];
}
else
for (int digit = 0; digit <= 9; ++digit)
{
genSum(k + 1, sum + digit);
}
} | | Где описание на русском? | obukkhov | 1044. Счастливые билеты. Easy! | 6 ноя 2016 19:34 | 3 | У задачи отклеилось описание на русском? Хоть и шарю по английскому, всё равно неприятно тратить несколько минут на перевод...
Edited by author 20.02.2016 16:49 Если шаришь, скорость восприятия текста не может отличаться в разы.
Для многих старых задач, по-видимому, русскоязычного условия в природе не существовало (1043 с того же контеста и тоже без русской версии).
Когда-то и меня заботила мысль, а что же делать, когда дорешаю все переведённые задачи с тимуса. Но английский выучился быстрее :D | | Problem | Vladimir | 1044. Счастливые билеты. Easy! | 11 дек 2015 22:03 | 9 | why do you always speak and write english?
aren't you Russian?
please, give the Russian version of this problem!!!!! English is necessary, Russian is optional I'm not english i'm kazakh
so,
can you explain me how to do this
write me to input.txt@mail.ru Есть вещь такая, как переводчик google. Попробуй ;) Marat Bakirov speak right. I'm Vietnamese. I don't speak English. But I want play on the Timus Online Judge.
Why?
Because, I want learn English from the problem and the conversion on forum of discuss.
Thank. I think have some mirror gramar of these sentence.
Edited by author 30.03.2010 17:18 this is not a good place to learn english from... the problem statements have lots of grammar and lexical mistakes, and most of the people on forums don't speak english so well either. Re: Problem Ahmet Faruk Ozkan OTTOMAN(OSMANLI)) 25 авг 2012 00:42 I'm Turkish. I don't know russian. if you don't know english that's your problem.
by the way there's a russian version of this site on the left cornere of the page; if you click on RUS you can solve all the problems ;-)
Edited by author 10.03.2013 20:15 fuck you son of a bitch turkish | | Ruby non, C++ oui | Donald Cameron | 1044. Счастливые билеты. Easy! | 14 мар 2015 08:08 | 1 | For my first try I wrote this:
def sum_of_digits(n)
sum = 0
while (n > 0)
sum += n % 10
n /= 10
end
sum
end
num_digits = gets.chomp.to_i
exponent = num_digits/2
divisor = 10**exponent
limit = (10**num_digits) - 1
total = 0
0.upto(limit) do |cur|
upper = cur / divisor
lower = cur % divisor
total += 1 if sum_of_digits(upper) == sum_of_digits(lower)
end
puts total
# eof
For 2, 4 and 6 digits it got the requisite answers of 10, 670, and 55252. There was a bit of a pause while it crunched away at the 6-digit case, though.
For 8 digits it … well, I let it run and went to do something else. Then I had the bright idea to time it (on mac OS X, using the time command):
4816030
real 1m42.596s
user 1m34.222s
sys 0m1.837s
The right answer, but the last time I checked, one minute anything was greater than two seconds. What to do?
It’s pretty clear that calling sum_of_digits a bunch more times than necessary is the biggest problem. For try #2, I precomputed the sums and stuffed them into an array, and indexed the array in place
of calling sum_of_digits in the main loop. Here’s the result:
time ruby lucky.rb < t8.txt
4816030
real 0m19.176s
user 0m18.017s
sys 0m0.313s
A better than 80% speedup. Most times I would kill for that, but I still need to lose 95% of the remaining run time. How to do it?
I checked … initializing the array of sums takes virtually no time, even if I write out the entire array contents to a file.
So the main loop is killing me, and unfortunately I need a dramatic change of algorithm but I
don’t see one. So …
1. Recode in C or C++
2. Hell if I know
Taking option 1, I got Accepted, with run times around 1.1 seconds or so for 8 digits. It's a straightforward translation to C++, very brute force.
|
|
|
