Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | DP | vegetable | 1044. Счастливые билеты. Easy! | 17 сен 2021 19:11 | 1 | DP vegetable 17 сен 2021 19:11 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 | leading zeroes allowed?? | Debagnik Roy | 1044. Счастливые билеты. Easy! | 20 июл 2020 03:02 | 2 | are leading zeroes allowed? for example... will 0110 be counted as a valid 4 digit lucky number? | ha-ha-ha | holtaf | 1044. Счастливые билеты. Easy! | 17 фев 2020 06:55 | 6 | #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; } nnn Mohigul Rahmonova 3 фев 2012 16:53 Edited by author 03.02.2012 16:53 print(([0,10,670,55252,4816030])[int(input())//2]) hahahahahahaha | WA test 3. But it answers correctly on my machine... | jedianmb | 1044. Счастливые билеты. Easy! | 31 янв 2020 17:11 | 2 | 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. | dp solution | raimkek | 1044. Счастливые билеты. Easy! | 18 дек 2019 20:31 | 1 | Can someone give idea or hint of dynamic prog solution? | Who can tell me how to caculate 4? | liuchang | 1044. Счастливые билеты. Easy! | 25 июн 2019 01:47 | 2 | 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 | A combinatorial approach | abid1729 | 1044. Счастливые билеты. Easy! | 25 июн 2019 00:31 | 1 | 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 | interesting solution - it works!!)) | Eternal | 1044. Счастливые билеты. Easy! | 16 май 2019 12:08 | 16 | #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 "Частный случай" "Частный случай" you are right! Every one has a chance to say some thing in mother language...i also saying... এতে ইজি কিছহু নাই। সব ই কথিন। 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!! \*^_^*/ | One line solution in Python))) | ViktYusk | 1044. Счастливые билеты. Easy! | 28 дек 2018 03:21 | 1 | print([None, 10, 10, 100, 670, 6700, 55252, 552520, 4816030, 48160300][int(input())]) | Precalculate is not needed | Pearl | 1044. Счастливые билеты. Easy! | 30 сен 2018 18:01 | 1 | #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; } | .001 AC solution without memoization . | Rafat Islam | 1044. Счастливые билеты. Easy! | 6 авг 2017 22:17 | 2 | #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 ; } | generate all sums with recursion | Manciu Ion | 1044. Счастливые билеты. Easy! | 21 янв 2017 01:59 | 1 | #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); } } | Help me with the algorithm | nushrat | 1044. Счастливые билеты. Easy! | 19 ноя 2016 07:11 | 1 | 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. | Где описание на русском? | obukkhov | 1044. Счастливые билеты. Easy! | 6 ноя 2016 19:34 | 3 | У задачи отклеилось описание на русском? Хоть и шарю по английскому, всё равно неприятно тратить несколько минут на перевод... Edited by author 20.02.2016 16:49 Если шаришь, скорость восприятия текста не может отличаться в разы. Для многих старых задач, по-видимому, русскоязычного условия в природе не существовало (1043 с того же контеста и тоже без русской версии). Когда-то и меня заботила мысль, а что же делать, когда дорешаю все переведённые задачи с тимуса. Но английский выучился быстрее :D | Your computer won't explode if you will do like here))) | IlushaMax | 1044. Счастливые билеты. Easy! | 1 апр 2016 23:55 | 1 | Just use brute force for getting values for 2,4,6,8 and write it Edited by author 01.04.2016 23:55 | I HAVE THE CODE | SorrowAngel | 1044. Счастливые билеты. Easy! | 1 апр 2016 22:29 | 2 | {$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 | Problem | Vladimir | 1044. Счастливые билеты. Easy! | 11 дек 2015 22:03 | 9 | 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. Re: Problem Ahmet Faruk Ozkan OTTOMAN(OSMANLI)) 25 авг 2012 00:42 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 | what about odd number of digits? Could someone explain Please | Anupam Ghosh, Wipro Technologies | 1044. Счастливые билеты. Easy! | 8 июн 2015 22:15 | 4 | 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." | Ruby non, C++ oui | Donald Cameron | 1044. Счастливые билеты. Easy! | 14 мар 2015 08:08 | 1 | 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. | Combinatorial | _UnderScore | 1044. Счастливые билеты. Easy! | 7 мар 2015 12:51 | 3 | 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. |
|
|