Witam
mam do napisania funkcję, która dla danej liczby n ustali dwie takie liczby a i b, że a>=0 i b>=0 oraz
a+b==n;
i suma cyfr liczby a i liczby b jest największa z możliwych.
n<=10e10
Czy mam kolejno tzn a=0 i b = n, a=1 b=n-1, a = 2 b=n-2 przeglądać wszystkie możliwości i ustalać dla nich sumę cyfr czy może jest jakiś szybszy algorytm na zrobienie tego zadania?
0
2
Na pewno jest. Samo zrobienie 10^10 iteracji zajmie wieki.
Na Twoim miejscu to bym na razie zrobił bruta i wypisał sobie wyniki dla np. n od 1-1000. Potem sobie na spójrz i może dostrzeżesz jakąś regularność w wynikach.
0
A to przypadkiem nie jest tak, że dla liczby N suma cyfr liczb A i B=(N-A) zawsze jest taka sama, gdy A i B nie zawierają zer?
4
A jednak nie jest. Ale da się znaleźć inną zależność:
n = 17
a = 0 , b = 17 , digits-sum = 8
a = 1 , b = 16 , digits-sum = 8
a = 2 , b = 15 , digits-sum = 8
a = 3 , b = 14 , digits-sum = 8
a = 4 , b = 13 , digits-sum = 8
a = 5 , b = 12 , digits-sum = 8
a = 6 , b = 11 , digits-sum = 8
a = 7 , b = 10 , digits-sum = 8
a = 8 , b = 9 , digits-sum = 17
a = 9 , b = 8 , digits-sum = 17
a = 10 , b = 7 , digits-sum = 8
a = 11 , b = 6 , digits-sum = 8
a = 12 , b = 5 , digits-sum = 8
a = 13 , b = 4 , digits-sum = 8
a = 14 , b = 3 , digits-sum = 8
a = 15 , b = 2 , digits-sum = 8
a = 16 , b = 1 , digits-sum = 8
n = 18
a = 0 , b = 18 , digits-sum = 9
a = 1 , b = 17 , digits-sum = 9
a = 2 , b = 16 , digits-sum = 9
a = 3 , b = 15 , digits-sum = 9
a = 4 , b = 14 , digits-sum = 9
a = 5 , b = 13 , digits-sum = 9
a = 6 , b = 12 , digits-sum = 9
a = 7 , b = 11 , digits-sum = 9
a = 8 , b = 10 , digits-sum = 9
a = 9 , b = 9 , digits-sum = 18
a = 10 , b = 8 , digits-sum = 9
a = 11 , b = 7 , digits-sum = 9
a = 12 , b = 6 , digits-sum = 9
a = 13 , b = 5 , digits-sum = 9
a = 14 , b = 4 , digits-sum = 9
a = 15 , b = 3 , digits-sum = 9
a = 16 , b = 2 , digits-sum = 9
a = 17 , b = 1 , digits-sum = 9
n = 22
a = 0 , b = 22 , digits-sum = 4
a = 1 , b = 21 , digits-sum = 4
a = 2 , b = 20 , digits-sum = 4
a = 3 , b = 19 , digits-sum = 13
a = 4 , b = 18 , digits-sum = 13
a = 5 , b = 17 , digits-sum = 13
a = 6 , b = 16 , digits-sum = 13
a = 7 , b = 15 , digits-sum = 13
a = 8 , b = 14 , digits-sum = 13
a = 9 , b = 13 , digits-sum = 13
a = 10 , b = 12 , digits-sum = 4
a = 11 , b = 11 , digits-sum = 4
a = 12 , b = 10 , digits-sum = 4
a = 13 , b = 9 , digits-sum = 13
a = 14 , b = 8 , digits-sum = 13
a = 15 , b = 7 , digits-sum = 13
a = 16 , b = 6 , digits-sum = 13
a = 17 , b = 5 , digits-sum = 13
a = 18 , b = 4 , digits-sum = 13
a = 19 , b = 3 , digits-sum = 13
a = 20 , b = 2 , digits-sum = 4
a = 21 , b = 1 , digits-sum = 4
n = 27
a = 0 , b = 27 , digits-sum = 9
a = 1 , b = 26 , digits-sum = 9
a = 2 , b = 25 , digits-sum = 9
a = 3 , b = 24 , digits-sum = 9
a = 4 , b = 23 , digits-sum = 9
a = 5 , b = 22 , digits-sum = 9
a = 6 , b = 21 , digits-sum = 9
a = 7 , b = 20 , digits-sum = 9
a = 8 , b = 19 , digits-sum = 18
a = 9 , b = 18 , digits-sum = 18
a = 10 , b = 17 , digits-sum = 9
a = 11 , b = 16 , digits-sum = 9
a = 12 , b = 15 , digits-sum = 9
a = 13 , b = 14 , digits-sum = 9
a = 14 , b = 13 , digits-sum = 9
a = 15 , b = 12 , digits-sum = 9
a = 16 , b = 11 , digits-sum = 9
a = 17 , b = 10 , digits-sum = 9
a = 18 , b = 9 , digits-sum = 18
a = 19 , b = 8 , digits-sum = 18
a = 20 , b = 7 , digits-sum = 9
a = 21 , b = 6 , digits-sum = 9
a = 22 , b = 5 , digits-sum = 9
a = 23 , b = 4 , digits-sum = 9
a = 24 , b = 3 , digits-sum = 9
a = 25 , b = 2 , digits-sum = 9
a = 26 , b = 1 , digits-sum = 9
n = 28
a = 0 , b = 28 , digits-sum = 10
a = 1 , b = 27 , digits-sum = 10
a = 2 , b = 26 , digits-sum = 10
a = 3 , b = 25 , digits-sum = 10
a = 4 , b = 24 , digits-sum = 10
a = 5 , b = 23 , digits-sum = 10
a = 6 , b = 22 , digits-sum = 10
a = 7 , b = 21 , digits-sum = 10
a = 8 , b = 20 , digits-sum = 10
a = 9 , b = 19 , digits-sum = 19
a = 10 , b = 18 , digits-sum = 10
a = 11 , b = 17 , digits-sum = 10
a = 12 , b = 16 , digits-sum = 10
a = 13 , b = 15 , digits-sum = 10
a = 14 , b = 14 , digits-sum = 10
a = 15 , b = 13 , digits-sum = 10
a = 16 , b = 12 , digits-sum = 10
a = 17 , b = 11 , digits-sum = 10
a = 18 , b = 10 , digits-sum = 10
a = 19 , b = 9 , digits-sum = 19
a = 20 , b = 8 , digits-sum = 10
a = 21 , b = 7 , digits-sum = 10
a = 22 , b = 6 , digits-sum = 10
a = 23 , b = 5 , digits-sum = 10
a = 24 , b = 4 , digits-sum = 10
a = 25 , b = 3 , digits-sum = 10
a = 26 , b = 2 , digits-sum = 10
a = 27 , b = 1 , digits-sum = 10
n = 134
a = 0 , b = 134 , digits-sum = 8
a = 1 , b = 133 , digits-sum = 8
a = 2 , b = 132 , digits-sum = 8
a = 3 , b = 131 , digits-sum = 8
a = 4 , b = 130 , digits-sum = 8
a = 5 , b = 129 , digits-sum = 17
a = 6 , b = 128 , digits-sum = 17
a = 7 , b = 127 , digits-sum = 17
a = 8 , b = 126 , digits-sum = 17
a = 9 , b = 125 , digits-sum = 17
a = 10 , b = 124 , digits-sum = 8
a = 11 , b = 123 , digits-sum = 8
a = 12 , b = 122 , digits-sum = 8
a = 13 , b = 121 , digits-sum = 8
a = 14 , b = 120 , digits-sum = 8
a = 15 , b = 119 , digits-sum = 17
a = 16 , b = 118 , digits-sum = 17
a = 17 , b = 117 , digits-sum = 17
a = 18 , b = 116 , digits-sum = 17
a = 19 , b = 115 , digits-sum = 17
a = 20 , b = 114 , digits-sum = 8
a = 21 , b = 113 , digits-sum = 8
a = 22 , b = 112 , digits-sum = 8
a = 23 , b = 111 , digits-sum = 8
a = 24 , b = 110 , digits-sum = 8
a = 25 , b = 109 , digits-sum = 17
a = 26 , b = 108 , digits-sum = 17
a = 27 , b = 107 , digits-sum = 17
a = 28 , b = 106 , digits-sum = 17
a = 29 , b = 105 , digits-sum = 17
a = 30 , b = 104 , digits-sum = 8
a = 31 , b = 103 , digits-sum = 8
a = 32 , b = 102 , digits-sum = 8
a = 33 , b = 101 , digits-sum = 8
a = 34 , b = 100 , digits-sum = 8
a = 35 , b = 99 , digits-sum = 26
a = 36 , b = 98 , digits-sum = 26
a = 37 , b = 97 , digits-sum = 26
a = 38 , b = 96 , digits-sum = 26
a = 39 , b = 95 , digits-sum = 26
a = 40 , b = 94 , digits-sum = 17
a = 41 , b = 93 , digits-sum = 17
a = 42 , b = 92 , digits-sum = 17
a = 43 , b = 91 , digits-sum = 17
a = 44 , b = 90 , digits-sum = 17
a = 45 , b = 89 , digits-sum = 26
a = 46 , b = 88 , digits-sum = 26
a = 47 , b = 87 , digits-sum = 26
a = 48 , b = 86 , digits-sum = 26
a = 49 , b = 85 , digits-sum = 26
a = 50 , b = 84 , digits-sum = 17
a = 51 , b = 83 , digits-sum = 17
a = 52 , b = 82 , digits-sum = 17
a = 53 , b = 81 , digits-sum = 17
a = 54 , b = 80 , digits-sum = 17
a = 55 , b = 79 , digits-sum = 26
a = 56 , b = 78 , digits-sum = 26
a = 57 , b = 77 , digits-sum = 26
a = 58 , b = 76 , digits-sum = 26
a = 59 , b = 75 , digits-sum = 26
a = 60 , b = 74 , digits-sum = 17
a = 61 , b = 73 , digits-sum = 17
a = 62 , b = 72 , digits-sum = 17
a = 63 , b = 71 , digits-sum = 17
a = 64 , b = 70 , digits-sum = 17
a = 65 , b = 69 , digits-sum = 26
a = 66 , b = 68 , digits-sum = 26
a = 67 , b = 67 , digits-sum = 26
a = 68 , b = 66 , digits-sum = 26
a = 69 , b = 65 , digits-sum = 26
a = 70 , b = 64 , digits-sum = 17
a = 71 , b = 63 , digits-sum = 17
a = 72 , b = 62 , digits-sum = 17
a = 73 , b = 61 , digits-sum = 17
a = 74 , b = 60 , digits-sum = 17
a = 75 , b = 59 , digits-sum = 26
a = 76 , b = 58 , digits-sum = 26
a = 77 , b = 57 , digits-sum = 26
a = 78 , b = 56 , digits-sum = 26
a = 79 , b = 55 , digits-sum = 26
a = 80 , b = 54 , digits-sum = 17
a = 81 , b = 53 , digits-sum = 17
a = 82 , b = 52 , digits-sum = 17
a = 83 , b = 51 , digits-sum = 17
a = 84 , b = 50 , digits-sum = 17
a = 85 , b = 49 , digits-sum = 26
a = 86 , b = 48 , digits-sum = 26
a = 87 , b = 47 , digits-sum = 26
a = 88 , b = 46 , digits-sum = 26
a = 89 , b = 45 , digits-sum = 26
a = 90 , b = 44 , digits-sum = 17
a = 91 , b = 43 , digits-sum = 17
a = 92 , b = 42 , digits-sum = 17
a = 93 , b = 41 , digits-sum = 17
a = 94 , b = 40 , digits-sum = 17
a = 95 , b = 39 , digits-sum = 26
a = 96 , b = 38 , digits-sum = 26
a = 97 , b = 37 , digits-sum = 26
a = 98 , b = 36 , digits-sum = 26
a = 99 , b = 35 , digits-sum = 26
a = 100 , b = 34 , digits-sum = 8
a = 101 , b = 33 , digits-sum = 8
a = 102 , b = 32 , digits-sum = 8
a = 103 , b = 31 , digits-sum = 8
a = 104 , b = 30 , digits-sum = 8
a = 105 , b = 29 , digits-sum = 17
a = 106 , b = 28 , digits-sum = 17
a = 107 , b = 27 , digits-sum = 17
a = 108 , b = 26 , digits-sum = 17
a = 109 , b = 25 , digits-sum = 17
a = 110 , b = 24 , digits-sum = 8
a = 111 , b = 23 , digits-sum = 8
a = 112 , b = 22 , digits-sum = 8
a = 113 , b = 21 , digits-sum = 8
a = 114 , b = 20 , digits-sum = 8
a = 115 , b = 19 , digits-sum = 17
a = 116 , b = 18 , digits-sum = 17
a = 117 , b = 17 , digits-sum = 17
a = 118 , b = 16 , digits-sum = 17
a = 119 , b = 15 , digits-sum = 17
a = 120 , b = 14 , digits-sum = 8
a = 121 , b = 13 , digits-sum = 8
a = 122 , b = 12 , digits-sum = 8
a = 123 , b = 11 , digits-sum = 8
a = 124 , b = 10 , digits-sum = 8
a = 125 , b = 9 , digits-sum = 17
a = 126 , b = 8 , digits-sum = 17
a = 127 , b = 7 , digits-sum = 17
a = 128 , b = 6 , digits-sum = 17
a = 129 , b = 5 , digits-sum = 17
a = 130 , b = 4 , digits-sum = 8
a = 131 , b = 3 , digits-sum = 8
a = 132 , b = 2 , digits-sum = 8
a = 133 , b = 1 , digits-sum = 8
Gdy jedna z cyfr zawiera maksymalną liczbę 9, to suma wygląda na maksymalną. W zasadzie to ta zależność wygląda na subtelniejszą, ale to powinno wystarczyć.
0
Wg mnie jedna z liczb ma składać się z serii 9-tek na końcu.
Kod sprawdzający tezę:
#include <sstream>
#include <string>
#include <iostream>
using namespace std;
unsigned sum(unsigned a,unsigned b)
{
unsigned sum=0;
stringstream s;
s<<a<<b;
for(char ch:s.str()) sum+=ch-'0';
return sum;
}
unsigned divide(unsigned value) // wg tezy
{
unsigned ret=0;
for(unsigned add=9;ret+add<value;ret+=add) add*=10;
return sum(ret,value-ret);
}
unsigned brutal(unsigned value)
{
unsigned ret=sum(0,value);
for(unsigned i=(value>>1);i>0;--i)
{
unsigned alt=sum(i,value-i);
if(ret<alt) ret=alt;
}
return ret;
}
int main()
{
for(unsigned v=1;v;++v)
{
unsigned d=divide(v);
unsigned b=brutal(v);
if(d!=b) cout<<" "<<v<<":\t"<<d<<"<>"<<b<<"\n";
else if(!(v&0xFF)) cout<<" "<<v<<":\t"<<d<<"\r";
}
return 0;
}
0
0
Moje rozwiązanie (w sumie to zadanie dobre na algorekrutację, aż musiałem sobie zanotować):
using System;
public class Program
{
public static void Main()
{
int[] testNumbers = { 0, 1, 2, 3, 4, 5, 11, 13, 17, 20, 55, 56, 120, 555, 69932, 1000329, 5555555, 99999 };
foreach (var n in testNumbers) {
Console.WriteLine("Example: {0}", n);
var (a1, b1) = bruteForce(n);
var (a2, b2) = findDecomposition(n);
if (a1 != a2 || b1 != b2 || (a1 + b1) != n) {
Console.WriteLine("Failed: {0} vs {1}", (a1, b1), (a2, b2));
}
else {
Console.WriteLine("OK: {0}", (a1, b1));
}
}
}
static (int a, int b) findDecomposition(int n) {
if (n < 10) {
// Single digit
return (0, n);
}
var n10 = n / 10;
var lastDigit = n % 10;
var canUseCarry = (n10 > 0) && (lastDigit != 9);
if (canUseCarry) {
var (a, b) = findDecomposition(n10 - 1);
return (a*10 + (lastDigit + 1), b*10 + 9);
}
else {
var (a, b) = findDecomposition(n10);
return (a*10, b*10 + lastDigit);
}
}
static (int a, int b) bruteForce(int n) {
var (a, b) = (-1, -1);
var max = -1;
for (int i = 0; i < n/2+1; i++) {
int j = n - i;
var sum = digitsSum(i) + digitsSum(j);
if (sum > max) {
max = sum;
(a, b) = (i, j);
}
}
return (a, b);
}
static int digitsSum(int n) {
var sum = 0;
while (n > 0) {
sum += (n % 10);
n /= 10;
}
return sum;
}
}
EDIT: A dzisaj ranem popatrzyłem na to i wygląda że da się jeszcze bardziej uprościć:
static (int a, int b) findDecomposition(int n) {
var b = 0;
while ((b*10 + 9) <= n) {
b = b*10 + 9;
}
var a = n - b;
return (a, b);
}
0
Wypisanie wszystkich wariantów podziału dających maksymalny wynik (wypisywana tylko wartość a):
#include <iostream>
#include <vector>
using namespace std;
struct node
{
ushort low,gen,high;
node(ushort low,ushort high):low(low),gen(low),high(high) {}
bool inc()
{
bool more=(gen>=high);
gen=more?low:gen+1;
return more;
}
};
void maxdivlist(int value)
{
vector<node> arr;
arr.reserve(32);
for(ushort next=0;value;value=next)
{
next=value/10;
if(next) --next;
ushort sum=value-10*next,low=sum>9?sum-9:0;
arr.push_back(node(low,sum-low));
}
for(size_t p=0;p<arr.size();)
{
value=0;
for(size_t p=arr.size();p>0;--p) (value*=10)+=arr[p-1].gen;
cout<<value<<endl;
p=0;
while((p<arr.size())&&(arr[p].inc())) ++p;
}
}
int main()
{
maxdivlist(134);
return 0;
}
0
Poniższy kod buraczy mi się na jednym teście nie wiem gdzie jest błąd
int sum(long a)
{
int result;
for(result=0;a!=0;a/=10)
result+=a%10;
return result;
}
int solve(const long n) {
int digits=(int)log10(n);
int i=0;
char *tmp=(char*)malloc(sizeof(char)*digits+1);
long a,b;
for(i=0;i<digits;i++)
tmp[i]='9';
tmp[i]='\0';
a=atol(tmp);
b=n-a;
free(tmp);
return sum(a)+sum(b);
}
błąd expected 144 submitted 72
0
O jedną za dużo 9-tek