Страница 3 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; } for(i=0; i<=n*9; ++i){ ans += soma[i]*soma[i]; } i is out of soma range. 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 Если шаришь, скорость восприятия текста не может отличаться в разы. Для многих старых задач, по-видимому, русскоязычного условия в природе не существовало (1043 с того же контеста и тоже без русской версии). Когда-то и меня заботила мысль, а что же делать, когда дорешаю все переведённые задачи с тимуса. Но английский выучился быстрее :D 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. according to the language of question sum of 1st 3 digits must be equal to the sum of last three digits for a number to be lucky. so am i missing some point? please help! According to statement digit count must be divisible by 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." Страница 2 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 if we are not too creative to calculate this on paper and there is no forum to take solution just do backtracking it works fine 1 second and something #include <iostream> using namespace std; int x[10], n, cont = 0; void back(int k) { if(k == n) { int s1 = 0, s2 = 0; for(int i = 0; i < n / 2; i++) { s1 += x[i]; } for(int i = n / 2; i <= n; i++) { s2 += x[i]; } if(s2 == s1) cont++; } else for(int i = 0; i <= 9; i++) { x[k] = i; back(k + 1); } } int main () { cin >> n; back(0); cout << cont; return 0; } 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." 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. Hey, Can you please send me your dp solution? I am trying to solve it with recursion; however, I am stuck in it. 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; } Delete your code Habib!!!! its too easy, the problem is how generate all combinations possibles, can you tell me!!!!!!... Страницы: 3 2 1 Предыдущая |
|