Опубликовал решение на PasteBin и тут, поскольку суда криво копируются символы таба, и потом нельзя нормально скопировать код. https://pastebin.com/kWSChLsh
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct State {
vector<pair<string, int>> candidates; // кандидаты в этом штате
string state; // название штата
int weight; // "вес" штата
State(string state = " ", int weight = 0) : state(state), weight(weight) {
Таким образом, , и для всех остальных коэффициентов
В ответ нужно вывести все коэффициенты для j = n.
Алгоритм: создадим список из n + 1 элемента, проинициализируем его так: a, b, 0, 0, ..., 0 (всего n - 1 ноль). Это коэффициенты разложения для j = 1. Затем в цикле будем обновлять значения, начиная с больших i.
Код (python 3):
a, b, n = map(int, input().split())
c = [a, b] + [0] * (n - 1)
for j in range(2, n + 1):
c[j] = b * c[j - 1]
for i in range(j - 1, 0, -1):
c[i] = a * c[i] + b * c[i - 1]
c[0] = a * c[0]
print(*c)
Пример ввода:
1 1 4
Пример вывода:
1 4 6 4 1
___________________________________________-
Можно сразу написать выражение для . Тогда, если вы умеете считать биномиальные коэффициенты, всё получается короче (и быстрее):
Опубликовал решение на PasteBin и тут, поскольку суда криво копируются символы таба, и потом нельзя нормально скопировать код. https://pastebin.com/kWSChLsh
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct State {
vector<pair<string, int>> candidates; // кандидаты в этом штате
string state; // название штата
int weight; // "вес" штата
State(string state = " ", int weight = 0) : state(state), weight(weight) {
}
void vote(string candidate) { // принимаем голос избирателя
if (candidates.size() == 0) {
candidates.push_back({ candidate, 1 });
return;
}
for (int i = 0; i < candidates.size(); ++i) {
if (candidates[i].first == candidate) {
++candidates[i].second;
break;
}
else if (i == candidates.size() - 1) {
candidates.push_back({ candidate, 0 });
}
}
}
string getResultOfElections() {
if (candidates.size() == 1) {
return candidates[0].first;
}
sort(candidates.begin(), candidates.end(), // сортировка по голосам
[](pair<string, int>& a, pair<string, int>& b) {
return (a.second > b.second);
});
int last = -1;
for (int i = 1; i < candidates.size(); ++i) { // убираем проигравших
if (candidates[i].second != candidates[0].second) {
last = i;
break;
}
}
if (last != -1)
candidates.erase(candidates.begin() + last);
sort(candidates.begin(), candidates.end(), // лексографическая сортировка
[](pair<string, int>& a, pair<string, int>& b) {
return strcmp(a.first.c_str(), b.first.c_str()) < 0;
});
return candidates[0].first; // победитель
}
};
int main() {
setlocale(LC_ALL, "Russian");
cout << "Введите количество штатов: ";
vector<State> states;
int nOfStates = 0;
cin >> nOfStates;
cin.ignore();
cout << "Введите данные о состоянии штатов в формате Название_штата Значимость_Штата: ";
for (int i = 1; i <= nOfStates; ++i) {
string input, buffer, name, weight;
getline(cin, input);
name = input.substr(0, input.find(' '));
weight = input.substr(input.find(' '));
states.push_back(State(name, stoi(weight)));
}
cout << "Количество голосов: ";
int nOfVotes = 0;
cin >> nOfVotes;
cin.ignore();
cout << "Данные о голосах в формате Штат Кандидат: ";
for (int i = 0; i < nOfVotes; ++i) {
string input, state, candidate;
getline(cin, input);
state = input.substr(0, input.find(' '));
candidate = input.substr(input.find(' ') + 1);
for (int j = 0; j < nOfStates; ++j) {
if (states[j].state == state) {
states[j].vote(candidate);
}
}
}
vector<pair<string, int>> winners;
for (int i = 0; i < states.size(); ++i) {
string result = states[i].getResultOfElections();
if (winners.size() == 0) {
winners.push_back({ result, states[i].weight });
continue;
}
for (int j = 0; j < winners.size(); ++j) {
if (winners[j].first == result) {
winners[j].second += states[i].weight;
break;
}
else if (j == winners.size() - 1) {
winners.push_back({ result, 0 });
}
}
}
cout << endl;
for (int i = 0; i < winners.size(); ++i) {
cout << winners[i].first << " " << winners[i].second << endl;
}
}
Пусть
— коэффициент в разложении 
при 
, то есть
Выразим коэффициенты для j + 1 через j:
Таким образом,
, 
и для всех остальных коэффициентов 
В ответ нужно вывести все коэффициенты для j = n.
Алгоритм: создадим список из n + 1 элемента, проинициализируем его так: a, b, 0, 0, ..., 0 (всего n - 1 ноль). Это коэффициенты разложения для j = 1. Затем в цикле будем обновлять значения, начиная с больших i.
Код (python 3):
a, b, n = map(int, input().split())
c = [a, b] + [0] * (n - 1)
for j in range(2, n + 1):
c[j] = b * c[j - 1]
for i in range(j - 1, 0, -1):
c[i] = a * c[i] + b * c[i - 1]
c[0] = a * c[0]
print(*c)
Пример ввода:
1 1 4
Пример вывода:
1 4 6 4 1
___________________________________________-
Можно сразу написать выражение для
. Тогда, если вы умеете считать биномиальные коэффициенты, всё получается короче (и быстрее):
from math import comb
a, b, n = map(int, input().split())
for i in range(n + 1):
print(comb(n, i) * a**i * b**(n - i), end=" ")