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

are leading zeroes allowed?
for example... will 0110 be counted as a valid 4 digit lucky number?

#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;
}

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;
}

Can someone give idea or hint of dynamic prog solution?

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

#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;
}

print([None, 10, 10, 100, 670, 6700, 55252, 552520, 4816030, 48160300][int(input())])

#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;
}

#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 ;
}

#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);
    }
}

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.

У задачи отклеилось описание на русском? Хоть и шарю по английскому, всё равно неприятно тратить несколько минут на перевод...

Edited by author 20.02.2016 16:49

Just use brute force for getting values for 2,4,6,8 and write it

Edited by author 01.04.2016 23:55

{$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.

why do you always speak and write english?
aren't you Russian?
please, give the Russian version of this problem!!!!!

Hi,
   Is this number 63363 lucky number?
Is it necessary all lucky numbers have to be a palindrome?

Regards
Anupam

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.

Can anybody explain the combinatorial approach of this problem ???
  Greetings