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; } Edited by author 03.02.2012 16:53 print(([0,10,670,55252,4816030])[int(input())//2]) hahahahahahaha 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? 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 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; } 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 "Частный случай" hmm... [:||||:] "Частный случай" you are right! Every one has a chance to say some thing in mother language...i also saying... এতে ইজি কিছহু নাই। সব ই কথিন। Chinese: 卑鄙啊 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!! \*^_^*/ 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 Если шаришь, скорость восприятия текста не может отличаться в разы. Для многих старых задач, по-видимому, русскоязычного условия в природе не существовало (1043 с того же контеста и тоже без русской версии). Когда-то и меня заботила мысль, а что же делать, когда дорешаю все переведённые задачи с тимуса. Но английский выучился быстрее :D 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. You are the best problemreader 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. 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 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." 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 the solution is very simple, combinatory isn't needed ;) I think it is coz brute force would be a good pain in ass with n > 9. But if u find a general solution with combinatorics it would be very efficient. I could not find one, though. |
|