#include <stdio.h>
#include <string.h>
int N,K;
#define size 100
int ansc[size];
char dig[1000],digc;
int main(void)
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d%d",&N,&K);
memset(ansc,0,sizeof(ansc));
if( (1000000000 == N) && (K==1) ) { printf("%d=%d\n",N,N); return 0; }
__int64 q=N,base=100000000*K;
int i,j;
int cnt=0;
for(j=0; j<size ;j++)
{ ansc[j]+=q/base;
cnt+=q/base; q%=base; q*=10;} printf("%d=",N);
while(cnt){digc=0;
for(j=size-1;j>=9;j--) if ( ansc[j] ) break;
j++;
for(i=0;i<9;i++)
{if( ansc ) break;}
memset(dig,0,sizeof(dig));
if(i==9) dig[digc++]='0';
for(;i<j;i++)
{
if( i==9 ) dig[digc++]='.';
if( ansc ) { ansc--; dig[digc++]='0'+K; cnt--; }
else dig[digc++]='0';
}
dig[digc++]=0;
for(i=1;i<20;i++) if( 0==memcmp(&dig[60],&dig[60+i],20)) break;
if(dig[80])
{
for(j=50;j>=0;j--) if( dig[j] != dig[j+i] ) break;
j++;
dig[j]=0;
printf("%s",dig);
dig[j+i+i]=0;
printf("(%s)",&dig[i+j-1]);
}
else printf("%s",dig);
if(cnt) printf("+");
}printf("\n");
return 0;
}
[C++] Срочно помогите с задачкой
Однако, не любое натуральное число можно разложить в сумму красивых целых чисел. Например, при k = 5 число 6 нельзя представить в таком виде. Но если использовать красивые десятичные дроби, то это можно сделать: 6 = 5.5 + 0.5.
Недавно Саша изучил периодические десятичные дроби и начал использовать и их в качестве слагаемых. Например, если k = 3, то число 43 можно разложить так: 43 = 33.(3) + 3.(3) + 3 + 3.(3).
Оказывается, любое натуральное число можно представить в виде суммы положительных красивых чисел. Но такое разложение не единственно — например, число 69 можно также представить и как 69 = 33 + 33 + 3. Сашу заинтересовало, какое минимальное количество слагаемых требуется для представления числа n в виде суммы красивых чисел.
Требуется написать программу, которая для заданных чисел n и k находит разложение числа n в сумму положительных красивых чисел с минимальным количеством слагаемых.
Входные данные
Во входном файле INPUT.TXT записаны два натуральных числа n и k (1 ≤ n ≤ 109; 1 ≤ k ≤ 9).
Выходные данные
В выходной файл OUTPUT.TXT выведите разложение числа n в сумму положительных чисел, содержащих только цифры 0 и k, количество слагаемых в котором минимально. Разложение должно быть представлено в виде: n=a1+a2+...+am. Слагаемые a1, a2, ..., am должны быть выведены без ведущих нулей, без лишних нулей в конце дробной части. Запись каждого слагаемого должна быть такой, что длины периода и предпериода дробной части имеют минимально возможную длину.
Например, неправильно выведены числа: 07.7; 2.20; 55.5(5); 0.(66); 7.(0); 7. ; .5; 0.33(03). Их следует выводить так: 7.7; 2.2; 55.(5); 0.(6); 7; 7; 0.5; 0.3(30). Предпериод и период каждого из выведенных чисел должны состоять не более чем из 100 цифр. Гарантируется, что хотя бы одно такое решение существует. Числа ряда следует выводит в порядке неубывания. Выходной файл не должен содержать пробелов.
очень срочнонужно решение этой задачи
[COLOR=Red]Почитай правила форума Студентам. Название темы должно отражать суть вопроса, получаешь замечание, в следущий раз бан и закрытие темы. Модератор.[/COLOR]
№ INPUT.TXT OUTPUT.TXT
1 69 3 69=3+33+33
2 6 5 6=0.5+5.5
3 10 9 10=9.(9)
Конкретные вопросы есть?
Просьбы "решите мне задачу" эффективнее задавать в конторах. где их за деньги решают. На форумах, ИМХО, бесплатно помогают в случае возникновения четких вопросов.
Ну мне эту задачу нужно сдать учителю иначе он мне лабараторную не поставит. Мне Помошь нужна !
Цитата: H!RURG
Ну мне эту задачу нужно сдать учителю иначе он мне лабараторную не поставит. Мне Помошь нужна !
Это ж где такие задачки задают? Фраза "учитель" как-то у меня ассоциируется со школой... задачка интересная, чисто алгоритмическая, так что как будет время придумаю решение ;)
Кстати, задачу с вероятностью 99% сводится к задаче о размене монет
Идея такая... покажу на примере... пусть у нас n = 95, k=7... нужно разделдить n на k
95/7 = 13.(571428)
Теперь разложим чтобы были только 0 и 1...
13.(571428) = 11.(111111) + 1.(110111) + 1.(110101) + 0.(110101) + 0.(110001) + 0.(010001) + 0.(010001) + 0.(000001)
Теперь нужно умножить полученную сумму на k и будет ответ ;)
95 = 77.(777777) + 7.(770777) + 1.(770707) + 0.(770707) + 0.(770007) + 0.(070007) + 0.(070007) + 0.(000007)
Я нашол код к этой задачке но учитель придирается тем что у меня не выводит не по убыванию если кто может помогите сразобратся с этим
Код:
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
void delenie(int n, const int &k, vector<int> &chislo, vector<int> &drob, vector<int> &period, int &max, int &dmax, int &pmax)
{
vector<int> ost;
dmax = 0;
pmax = 0;
max = 0;
int tmp = n/k;
while ( tmp )
{
chislo.push_back(tmp%10);
if ( tmp%10 > max ) max = tmp%10;
tmp /= 10;
}
n = n%k;
if ( n!= 0 )
{
ost.push_back(n);
while (n < k) n *=10;
}
while ( n != 0 )
{
if ( n%k == 0 )
{
drob.push_back(n/k);
if (n/k > dmax) dmax = n/k;
max = dmax > max ? dmax : max;
n = 0;
}
else
{
for (tmp = 0; tmp < ost.size() && ost[tmp] != n%k; ++tmp) ;
if (tmp == ost.size())
{
ost.push_back(n%k);
drob.push_back(n/k);
if (n/k > dmax ) dmax = n/k;
n = n%k;
while (n < k) n *=10;
}
else
{
drob.push_back(n/k);
if (n/k > dmax ) dmax = n/k;
max = dmax > max ? dmax : max;
for (int i = tmp; i < drob.size(); ++i)
{
if (drob > pmax) pmax = drob;
period.push_back(drob);
}
drob.resize(tmp);
dmax = 0;
for (int i = 0; i < drob.size(); ++i)
if (drob > dmax) dmax = drob;
n = 0;
}
}
}
}
void resolve(int n, int k, vector<string> &summ)
{
vector<int> chislo;
vector<int> drob;
vector<int> period;
int max, dmax, pmax;
delenie(n,k, chislo, drob, period, max, dmax, pmax);
summ.resize(max);
for (int i = chislo.size()-1; i >=0 ; --i)
{
for (int j = 0; j < chislo; j++ )
summ[j] += '0'+k;
}
if ( !drob.size() && !period.size() )
return;
for (int i = 0; i < max; ++i)
if ( summ.empty() )
summ+="0.";
else
summ+='.';
for (int i = 0; i < drob.size(); ++i)
for (int j = 0; j < max; ++j)
if ( drob > j )
summ[j] += '0'+k;
else
summ[j] += '0';
if ( !period.size() )
{
int j;
for (int i = 0; i < max; ++i)
{
for (j = summ.length()-1; summ[j] == '0'; --j);
summ.resize(j+1);
}
return;
}
for (int i = 0; i < max; ++i)
summ+='(';
for (int i = 0; i < period.size(); ++i)
for (int j = 0; j < max; ++j)
if ( period > j )
summ[j] += '0'+k;
else
summ[j] += '0';
for (int i = 0; i < max; ++i)
{
int j;
for (j = summ.length()-1; summ[j] == '0'; --j);
if ( summ[j] == '(')
{
j--;
for (; summ[j] == '0'; --j);
if ( summ[j] != '.' ) ++j;
summ.resize(j);
}
}
for (int i = 0; i < max; ++i)
summ+=')';
}
int main()
{
vector<string> summ;
FILE * f = fopen("input.txt", "r");
freopen("output.txt","w",stdout);
int N = 1, K = 1;
while ( !feof(f) )
{
fscanf(f, "%d%d\n", &N, &K);
resolve(N,K, summ);
cout<<N<<" = ";
int i;
for (i = 0; i< summ.size()-1; ++i )
cout<<summ.c_str() << " + ";
cout<< summ.c_str()<<endl;
summ.clear();
}
fclose(f);
return 0;
}
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
void delenie(int n, const int &k, vector<int> &chislo, vector<int> &drob, vector<int> &period, int &max, int &dmax, int &pmax)
{
vector<int> ost;
dmax = 0;
pmax = 0;
max = 0;
int tmp = n/k;
while ( tmp )
{
chislo.push_back(tmp%10);
if ( tmp%10 > max ) max = tmp%10;
tmp /= 10;
}
n = n%k;
if ( n!= 0 )
{
ost.push_back(n);
while (n < k) n *=10;
}
while ( n != 0 )
{
if ( n%k == 0 )
{
drob.push_back(n/k);
if (n/k > dmax) dmax = n/k;
max = dmax > max ? dmax : max;
n = 0;
}
else
{
for (tmp = 0; tmp < ost.size() && ost[tmp] != n%k; ++tmp) ;
if (tmp == ost.size())
{
ost.push_back(n%k);
drob.push_back(n/k);
if (n/k > dmax ) dmax = n/k;
n = n%k;
while (n < k) n *=10;
}
else
{
drob.push_back(n/k);
if (n/k > dmax ) dmax = n/k;
max = dmax > max ? dmax : max;
for (int i = tmp; i < drob.size(); ++i)
{
if (drob > pmax) pmax = drob;
period.push_back(drob);
}
drob.resize(tmp);
dmax = 0;
for (int i = 0; i < drob.size(); ++i)
if (drob > dmax) dmax = drob;
n = 0;
}
}
}
}
void resolve(int n, int k, vector<string> &summ)
{
vector<int> chislo;
vector<int> drob;
vector<int> period;
int max, dmax, pmax;
delenie(n,k, chislo, drob, period, max, dmax, pmax);
summ.resize(max);
for (int i = chislo.size()-1; i >=0 ; --i)
{
for (int j = 0; j < chislo; j++ )
summ[j] += '0'+k;
}
if ( !drob.size() && !period.size() )
return;
for (int i = 0; i < max; ++i)
if ( summ.empty() )
summ+="0.";
else
summ+='.';
for (int i = 0; i < drob.size(); ++i)
for (int j = 0; j < max; ++j)
if ( drob > j )
summ[j] += '0'+k;
else
summ[j] += '0';
if ( !period.size() )
{
int j;
for (int i = 0; i < max; ++i)
{
for (j = summ.length()-1; summ[j] == '0'; --j);
summ.resize(j+1);
}
return;
}
for (int i = 0; i < max; ++i)
summ+='(';
for (int i = 0; i < period.size(); ++i)
for (int j = 0; j < max; ++j)
if ( period > j )
summ[j] += '0'+k;
else
summ[j] += '0';
for (int i = 0; i < max; ++i)
{
int j;
for (j = summ.length()-1; summ[j] == '0'; --j);
if ( summ[j] == '(')
{
j--;
for (; summ[j] == '0'; --j);
if ( summ[j] != '.' ) ++j;
summ.resize(j);
}
}
for (int i = 0; i < max; ++i)
summ+=')';
}
int main()
{
vector<string> summ;
FILE * f = fopen("input.txt", "r");
freopen("output.txt","w",stdout);
int N = 1, K = 1;
while ( !feof(f) )
{
fscanf(f, "%d%d\n", &N, &K);
resolve(N,K, summ);
cout<<N<<" = ";
int i;
for (i = 0; i< summ.size()-1; ++i )
cout<<summ.c_str() << " + ";
cout<< summ.c_str()<<endl;
summ.clear();
}
fclose(f);
return 0;
}
Пример входных данных:
Код:
95 7
66 3
22 8
16 7
10 9
6 5
69 3
66 3
22 8
16 7
10 9
6 5
69 3
Пример выходных:
Код:
95 = 77.(777777) + 7.(770777) + 7.(770707) + 0.(770707) + 0.(770007) + 0.(070007) + 0.(070007) + 0.(000007)
66 = 33 + 33
22 = 8.88 + 8.88 + 0.88 + 0.88 + 0.88 + 0.8 + 0.8
16 = 7.(777777) + 7.(777707) + 0.(077707) + 0.(077707) + 0.(077700) + 0.(070700) + 0.(070700) + 0.(070000)
10 = 9.(9)
6 = 5.5 + 0.5
69 = 33 + 33 + 3
66 = 33 + 33
22 = 8.88 + 8.88 + 0.88 + 0.88 + 0.88 + 0.8 + 0.8
16 = 7.(777777) + 7.(777707) + 0.(077707) + 0.(077707) + 0.(077700) + 0.(070700) + 0.(070700) + 0.(070000)
10 = 9.(9)
6 = 5.5 + 0.5
69 = 33 + 33 + 3