vnyalla68's blog

By vnyalla68, history, 6 weeks ago, In English

https://codeforces.com/problemset/problem/72/A

hello everyone im a newbie and im having a doubt in this question im coding in c++ pls i need hlp in this thnq

 
 
 
 
  • Vote: I like it
  • -20
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't this just an alternative version of the coin change problem? Just sieve to find all primes. While taking input, check if the number is not a prime (in case it is prime, the answer is trivial). Then apply the standard coin change algorithm to it, either greedily or using dynamic programming.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's do dp: dp[x] — Is x a good number. So, how we can count dp[x]: Let's scan over prime numbers <= x: a — current prime number. If dp[x — a] is true => dp[x] is true. Then we retrieve the answer.