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

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?

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

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

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

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

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

Edited by author 01.04.2016 23:55

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

Edited by author 20.02.2016 16:49

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.

def SUM(n):
    ans=0
    while n:
        ans+=n%10
        n/=10
    return ans



def main():
    n=int(raw_input())
    n/=2

    m={}

    for i in range(0,10**n):
        try:
            m[SUM(i)]+=1
        except:
            m[SUM(i)]=1
    ans=0

    for i in m:
        ans+=m[i]*(m[i])
        #print i, m[i]
    print ans
main()

I used dictionary ( in c/c++ it's map)

Edited by author 25.07.2014 18:56

Edited by author 25.07.2014 18:57

#include <iostream>
using namespace std;

int main() {

    int arr[4] = {10, 670, 55252, 4816030};
    short m;

    cin >> m;
    cout << arr[m / 2 - 1];
    return 0;
}

//hey; can you guess how i got these values?(think of the simplest solution)

Edited by author 15.02.2013 04:31

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

Regards
Anupam

Good morning Timus

Edited by author 27.12.2011 13:02

Edited by author 27.12.2011 13:03

I used dp to get ac in this problem.
I am wondering is there any simple solution??

thanks in advance.

#include <stdio.h>

    int main()
    {
     int N;
     scanf("%d", &N);
     switch(N)
     {
      case 2: printf("10\n"); return 0;
      case 4: printf("670\n"); return 0;
      case 6: printf("55252\n"); return 0;
      case 8: printf("4816030\n"); return 0;
      default: return 0;
     }
     return 0;
    }