| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| DP? | ajay jadhav | 1206. Сумма цифр суммы чисел | 21 дек 2020 06:01 | 2 |
DP? ajay jadhav 30 апр 2020 12:20 Can anybody post DP approach, if any exists? Re: DP? Anier Velasco Sotomayor 21 дек 2020 06:01 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. |
| very good tusk | Arrias | 1206. Сумма цифр суммы чисел | 22 сен 2018 14:01 | 1 |
Edited by author 22.09.2018 14:02 |
| accepted | Mikhail | 1206. Сумма цифр суммы чисел | 16 июн 2018 15:43 | 2 |
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) |
| Wrong answer test 4 in Java 1.7 please help me | Axmadjon | 1206. Сумма цифр суммы чисел | 9 июн 2017 14:32 | 2 |
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 |
| Proof | Noob | 1206. Сумма цифр суммы чисел | 7 фев 2014 01:51 | 4 |
Proof Noob 12 май 2012 03:16 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. 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). |
| No subject | svg2003 | 1206. Сумма цифр суммы чисел | 13 дек 2013 11:25 | 1 |
Edited by author 13.12.2013 11:36
Edited by author 13.12.2013 11:36 |
| You use BigIntegers or strings | Adhambek | 1206. Сумма цифр суммы чисел | 21 июн 2013 21:05 | 1 |
because ,
input:
n = 50
Length of output is 87 digits
output :
682455418022864824778975492858747729001539122984270520078098343219608068466186523437500
Edited by author 21.06.2013 21:07 |
| WA5... | Phil | 1206. Сумма цифр суммы чисел | 11 фев 2013 19:48 | 2 |
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. |
| Problem 1206 "Sum of digits". New tests have been added (+) | Vladimir Yakovlev (USU) | 1206. Сумма цифр суммы чисел | 17 окт 2012 10:41 | 4 |
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 |
| Easytask!!!!!! | Anastas | 1206. Сумма цифр суммы чисел | 15 окт 2012 20:41 | 8 |
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 |
| And is it very easy to use long arithmetic. I was writing it.But then I saw that this is going to be very long.And I thought to myself this way isn't true. | Qafqaz_Ferhad Cebiyev | 1206. Сумма цифр суммы чисел | 15 июл 2010 21:38 | 1 |
|
| How to use long aritmetics in C++? I haven't use it before. | Qafqaz_Ferhad Cebiyev | 1206. Сумма цифр суммы чисел | 15 июл 2010 21:26 | 1 |
How to use long aritmetics in C++? I haven't use it before. |
| non correct statement? | Mansurov Artur | 1206. Сумма цифр суммы чисел | 17 сен 2008 21:46 | 3 |
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 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 |
| WHY WA on TEST 5 ?!?!? C++ | sim40 | 1206. Сумма цифр суммы чисел | 26 апр 2008 22:45 | 2 |
#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;
} |
| long arithmetic | jagatsastry | 1206. Сумма цифр суммы чисел | 18 фев 2008 23:25 | 3 |
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 ;) |
| Some hints (DONT read this if you want to think yourself) | Fokysnik | 1206. Сумма цифр суммы чисел | 23 июл 2007 17:54 | 2 |
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. |
| AC in 0.001 (with precalculations) | Black^n^White | 1206. Сумма цифр суммы чисел | 2 янв 2007 15:16 | 3 |
[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 ...:) |
| The text is wrong!!!!! | Darth Niculus | 1206. Сумма цифр суммы чисел | 11 май 2003 18:47 | 1 |
What is K's role in this problem because it has no link to the rest
of the problem. |
| What's the mean of K? | hongyan | 1206. Сумма цифр суммы чисел | 26 ноя 2002 13:04 | 2 |
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 "К". |
