Форум » Обработка числовых последовательностей » 27- задача 58 » Ответить
27- задача 58
lucie: Мое решение дает ответ 350, а не 351 from itertools import combinations f = open('27-58a.txt') n = int(f.readline()) a = [int(f.readline()) for i in range(n)] count = 0 for i in range(1,n): for x in combinations(a,i): if sum(x)%3== 0: count += 1 print(count) Где ошибка?
Ответов - 1
Serov Sergej: День добрый. Вы решаете на Питоне ПОЛНЫМ ПЕРЕБОРОМ ВСЕХ ВАРИАНТОВ!!! Для файла 27-58b это точно не пройдет. Решение должно использовать динамическое программирование. Я на Питоне не работаю. Если интересно, то могу выложить решение на СИ++ с подробными комментариями. [pre2] #include <iostream> #include <fstream> using namespace std; int main() { ifstream cin; cin.open("input_27-58b.txt"); long long int n,i,a,b,k[3],x0,x1,x2; k[0]=0; k[1]=0; k[2]=0;//kol-vo naborov, ostatok ot delenija ih summ na 3 raven 0, 1, 2 cin>>n; for (i=0;i<n;i++){ cin>>a; b=a%3;// b - ostatok ot delenija na 3 vnov postupivshego chisla if (b==0){ k[0]=2*k[0]+1;//esli b=0, to dobaviv ego ko vsem naboram s takim she ostatkom, my udvoim ih kol-vo plus samo eto chislo k[1]=k[1]*2;//a esli dobavljat k naboram s ostatkami 1 ili 2, to prosto udvaivaem ih kol-vo k[2]=k[2]*2; } if (b==1){ x1=k[1]+k[0]+1;//esli b=1, to dobaviv ego ko vsem naboram s ostatkom 0, poluchim nabory s ostatkom 1 plus samo eto chislo x2=k[2]+k[1];//dobaviv ego ko vsem naboram s ostatkom 1, poluchim nabory s ostatkom 2 x0=k[0]+k[2];//dobaviv ego ko vsem naboram s ostatkom 2, poluchim nabory s ostatkom 0 k[0]=x0; k[1]=x1; k[2]=x2;//no chtoby ne "portit' chisla massiva k, vychislenija delaem } //v peremennye õ0, õ1, õ2, kotorye potom "vernem" v massiv k if (b==2){ x2=k_s[2]+k_s[0]+1;//esli b=2, to dobaviv ego ko vsem naboram s ostatkom 0, poluchim nabory s ostatkom 2 plus samo eto chislo x0=k_s[0]+k_s[1];//dobaviv ego ko vsem naboram s ostatkom 1, poluchim nabory s ostatkom 0 x1=k_s[1]+k_s[2];//dobaviv ego ko vsem naboram s ostatkom 2, poluchim nabory s ostatkom 1 k_s[0]=x0; k_s[1]=x1; k_s[2]=x2; } } cout<<k_s[0]<<endl;//otvet v peremennoj, gde oststok 0 } [/pr2]
полная версия страницы