Can anybody post DP approach, if any exists? Dp[i][diff][c]: amount of pairs of numbers (A, B) of size i where S(A+B)-S(A)-S(B)=diff and we carry c from the sum of A and B Here we consider also number with leading zeroes, we can notice that **diff** is in the range [-460, 900] -maybe we can make it narrower- and that **c** is either 0 or 1. Edited by author 22.09.2018 14:02 ans1 = 0 ans2 = 0 for i in range(1, 10) : for j in range(1, 10) : if i + j < 10 : ans1 += 1 for i in range(0, 10) : for j in range(0, 10) : if i + j < 10 : ans2 += 1 n = int(input()) for i in range (1, n) : ans1 *= ans2 print(ans1) import java.util.Scanner; public class _1206 { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = 36; long k = s.nextInt(); while (k > 1) { n *= 55; k--; } System.out.println(n); } } Edited by author 05.05.2014 17:02 I've solved it using bruteforce for small K and then guessing the formula. But I still don't know the proof. Can anybody write it? S(A + B) = S(A) + S(B) is equal to that that for every pair of corresponding digits of A and B their sum is lower then 10 (1). For example: 12 and 13 :1+1<10;2+3<10 it means S(A + B) = S(A) + S(B) 18 and 19: 8+9>10 it means S(A + B) = S(A) + S(B) is wrong here. Then for every pair of digits from A and B you just count how many varints of pair suits (1) and multiply these quantities for all pairs. thanks Another way to go at it is to think of the number (A+B) as a bunch of stacked blocks, each stack representing a digit. Here is 43 for example: _ |_| _ |_||_| |_||_| |_||_| Now, to find all the A's and B's that can form S(A+B) = S(43), for example 12+31 or 22+21, etc, we can represent this as chopping each stack into two parts, for example in the case of 12+31: _ |_| _ _ |_| |_||_| |_| _ |_||_| Now, if we take the general case of having two digits, if the first digit is 1, we can't split the first digit in two since the first digit of A or B can't be 0. However, if the first digit is 2, we can split it in one way (in the middle), and then we can split the second digit depending on what digit it is. If it is 2, we can split it in 3 different ways ( (0,2),(1,1),(2,0) ). If it is 3, we can split it in 4 different ways, etc. So, if the first digit of the two-digit number is 2, we can split the whole number in 1*(1+2+3+4+5+6+7+8+9+10)=1+(10*11/2) different ways. If the first digit is 3, we can split the whole number in 2*(1+2+3+4+5+6+7+8+9+10)=2*(10*11/2) different ways, etc. If we sum everything we get (8*9)/2*(10*11)/2 ways to split a two digit number. For an n digit number continuing the same way we get (8*9)/2*((10*11)/2)^(n-1). Edited by author 13.12.2013 11:36 Edited by author 13.12.2013 11:36 because , input: n = 50 Length of output is 87 digits output : 682455418022864824778975492858747729001539122984270520078098343219608068466186523437500
Edited by author 21.06.2013 21:07 I used long arithmetics and calculated "36*pow(55,k-1);". But I have WA5. Please, say why or give that test... Maybe you write wrong long arithmetics. I think you forgot leading zeroes. I had the same mistake. Use this test: 9 3014421764062500 Sorry for my poor English. New tests were added to the problem. All possible inputs are checked now :) Problem statement was updated: limitation "0 < K <= 50" was replaced by "2 <= K <= 50". There wasn't a case K=1 in the tests. AC submissions were rejudged, 44 of them lost AC. I think who write true program with long arithmetics hasn,t lost ACC!!! Thanks. I know why I wa 1 Just use long arithmetics and calculate 36*pow(55,k-1); How did u get the formula What are the libraries and functions u use for long arithmetic in c++. There are no such libraries! You must write long arithmetics by yourself ;) Thank finaly something extra ordinary good. Thanks allot. I was searching for this for so long time. Thanks, thanks, thanks... This program explain how get 36 and 55. #include <iostream> using namespace std; __int64 s( __int64 x ){ __int64 ans = 0; while( x ){ ans += x % 10; x /= 10; } return ans; } int main(){ __int64 kol = 0; for( __int64 i = 0; i <= 9; ++i ){ for( __int64 j = 0; j <= 9; ++j ){ if( s(i+j) == s(i)+s(j) && i+j<=9 ){ cout << " " << i << " " << j << " s=" << s(i+j) << endl; ++kol; } } cout << "-------------------------" << endl; } cout << "kol = " << kol << endl; kol = 0; for( __int64 i = 1; i <= 9; ++i ){// последний разряд без нулей т.к. число must be без ведущих нулей for( __int64 j = 1; j <= 9; ++j ){ if( s(i+j) == s(i)+s(j) && i+j<=9 ){ cout << " " << i << " " << j << " s=" << s(i+j) << endl; ++kol; } } cout << "-------------------------" << endl; } cout << "kol = " << kol << endl; return 0; } Edited by author 23.11.2011 03:11 Edited by author 23.11.2011 03:12 Edited by author 23.11.2011 03:12 How to use long aritmetics in C++? I haven't use it before. for K=2 we can get 1980 only if we assume that pairs A=12 B=12 A=12 B=12 are two different pairs like A=11 B=12 A=12 B=11 I think u are not right. Yes, see this programm: #include <iostream> #include <math.h> using namespace std; int Sum (int n) { int s=0; while (n) { s+=n%10; n/=10; } return s; } int main() { int k=0; for (int i=10; i<100; i++) { for (int j=10; j<100; j++) { if (Sum(i)+Sum(j)==Sum(i+j)) { k++; cout<<i<<" "<<j<<"\n"; } } } cout<<k; return 0; } It returns 1980, but you can easily see that if i=j this pair wasn't counted twice #include<iostream> using namespace std; unsigned long long n=36; int k; int main() { cin>>k; while(k>1) { n*=55; k--; } cout<<n<<endl; } How do we perform long arithmetic calculations in c++? Is there any builtin library with g++? I'd googled for it only to find all external(out of standard g++) libraries. If anyone has written a class for this purpose, please share the code here or mail it to me. Thanks. No, such library doesn't exist. You've got three options: 1. Write it yourself. 2. Use Java, if you know it well. 3. Say «Well, it is definitely not my problem». I would recommend option number two ;) The equality holds when the sum of i-th digits of numbers A and B (A[i]+B[i]<=9) Using this write a simple program. It will be a TL program but... try running it for k=1,2,3,4,5,6,7 and you should notice a rule how the answer for k+1 is formed. And one more thing. You should use long arithmetics. For k=50 answer has 87 digits. Good luck. [code deleted] Edited by moderator 02.01.2007 18:52 I have ACC 0.015 204 КБ, but I use long arithmetics, that's why my program is more universal!!! Edited by author 02.01.2007 13:00 And now your program sucks ...:) What is K's role in this problem because it has no link to the rest of the problem. It is the number of digits. In the output specification, there was erroneously placed the russian letter "K", which looks exactly like the latin one, but has another code and may be displayed as "К". |
|