Ограничение памяти: 128 М байт
Марк и Максим играют между собой шахматный матч. Вероятность того, что в одной партии победит Марк, равна a /( a + b + c ). Вероятность того, что в одной партии победит Максим, равна b /( a + b + c ). Соответственно вероятность ничьей равна c /( a + b + c ). Мальчики договорились, что матч будет состоять не более, чем из N партий. Но если кто-то из них вырвется вперёд на K очков, то матч сразу заканчивается. Ваша задача – найти ожидаемую продолжительность шахматного матча.
Вход
Во входном файле записаны пять целых чисел – a, b, c, N, K (1 ≤ a, b, c ≤ 106, 3 ≤ N ≤ 10, 1 ≤ K < N).
Выход
Запишите в выходной файл ожидаемое количество партий, которые будут сыграны в матче, с четырьмя дробными цифрами.
Примеры входа и выхода
| chess . in | chess.out |
| 1 2 1 5 5 | 5.0000 |
| 1 2 1 5 4 | 4.9336 |
| 1 2 1 5 2 | 3.6133 |
| 1 2 1 5 1 | 1.3320 |
Пояснение
Победитель партии получает 1 очко, проигравший – 0 очков, если партия заканчивается вничью, то оба игрока получают по ½ очка.
Решение на C : 
#include <stdio.h>
#include <string.h>
int gamesCount, difference;
double winF, winS, draw, res = 0;
void SOLVE (int countG, int pointF, int pointS, double value) {
if (countG == gamesCount || pointF - pointS >= difference || pointS - pointF >= difference) {
res += countG * value;
}
if (countG < gamesCount && pointF - pointS < difference && pointS - pointF < difference) {
SOLVE(countG + 1, pointF + 1, pointS, value * winF);
SOLVE(countG + 1, pointF, pointS + 1, value * winS);
SOLVE(countG + 1, pointF, pointS, value * draw);
}
}
int main (void) {
//freopen("input.txt", "r", stdin);
freopen("chess.in", "r", stdin);
freopen("chess.out", "w", stdout);
int i;
double a, b, c;
scanf("%lf %lf %lf %d %d", &a, &b, &c, &gamesCount, &difference);
winF = a / (a + b + c);
winS = b / (a + b + c);
draw = c / (a + b + c);
SOLVE(0, 0, 0, 1);
printf("%.4lf", res);
return 0;
}
Вывод: Используя язык программирования С, мы решили поставленную задачу методом полного перебора, а также сделали это эффективно с точки зрения времени выполнения программы и использованной памяти.
Лабораторная работа №4.
Целью работы является написание эффективного, по времени и памяти, алгоритма решения задачи методом полного перебора.
Задача. ”Волшебник”
Ограничение времени: 1 секунда на тест
Ограничение памяти: 256 М байт
Волшебник имеет N магических предметов (1 ≤ N ≤ 30), каждый из которых характеризуется своей ценностью vi (0 < vi ≤ 10000). Он может произнести M заклинаний (1 ≤ M ≤ 10), изменяющих ценность имеющихся предметов. Каждое заклинание может быть произнесено не более одного раза. Произнесенное заклинание действует на все имеющиеся предметы. Заклинания делятся на 2 типа. После сотворения заклинания первого типа с номером j стоимость предмета i изменяется в Dij раз (если 1 < Dij ≤ 100, абсолютная величина стоимости увеличивается, при 0 ≤ Dij < 1 уменьшается, при Dij = 1 остается неизменной). Заклинание второго типа с номером j изменяет стоимость предмета i на Rij (если Rij > 0, стоимость увеличивается, при Rij < 0 - уменьшается, при Rij = 0 остается неизменной). Волшебник должен с помощью известных ему заклинаний добиться того, чтобы суммарная ценность имеющихся предметов была максимальной.
Вход
Текстовый файл WIZARD.IN содержит M + 2 строки. Первая строка содержит значения N и M. Следующая строка содержит значения vi (i = 1, ..., N). Наконец, каждая из последних M строк соответствует одному заклинанию. Для заклинания первого типа эта строка содержит символ * и значения Dij (i = 1, ..., N). Для заклинания второго типа она содержит символ + и значения Rij (i = 1, ..., N). Данные в строках входного файла разделяются одним или несколькими пробелами.
Выход
Выходные данные помещаются в текстовый файл WIZARD.OUT и содержат две строки. Первая строка содержит получившуюся суммарную стоимость предметов (с точностью до 0.001), вторая - M разделенных одним пробелом чисел tj (j = 1, ..., M), где tj = k, если заклинание j было произнесено k-м по счету, и tj = 0, если заклинание не было произнесено.
Примеры входа и выхода
| WIZARD.IN | WIZARD.OUT |
| 4 2 2 2 2 2 * 3 2 1 2 * 0.5 1 1 5 | 29.000 1 2 |
Решение на С :
#include <stdio.h>
#include <string.h>
#define NMAX1 35
#define NMAX2 15
int optimal[NMAX2];
int optimalCopy[NMAX2];
double magic[NMAX2][NMAX1];
double price[NMAX1];
char type[NMAX2];
int itemCount, spellCount;
double maxPrice = 0;
void makeMagic (int number, double* A) {
int i;
if (type[number] == '*') {
for (i=0; i<itemCount; i++) {
A[i]*=magic[number][i];
}
}
if (type[number] == '+') {
for (i=0; i<itemCount; i++) {
A[i]+=magic[number][i];
}
}
}
double getPrice (double* A) {
int i;
double sum = 0;
for (i=0; i<itemCount; i++) sum+=A[i];
return sum;
}
void SOLVE (int count, double currPrice) {
int i, j;
double prev[NMAX1];
if (currPrice > maxPrice) {
maxPrice = currPrice;
for (j=0; j<spellCount; j++) optimal[j] = optimalCopy[j];
}
for (i=0; i<spellCount; i++) {
if (optimalCopy[i] == 0) {
optimalCopy[i] = count;
memcpy(prev, price, NMAX1*sizeof(double));
makeMagic(i, price);
SOLVE(count+1, getPrice(price));
memcpy(price, prev, NMAX1*sizeof(double));
optimalCopy[i] = 0;
}
}
}
int main (void) {
//freopen("input.txt", "r", stdin);
freopen("wizard.in", "r", stdin);
freopen("wizard.out", "w", stdout);
int i, j, k;
scanf("%d %d\n", &itemCount, &spellCount);
for (i=0; i<itemCount; i++) scanf("%lf", &price[i]);
for (i=0; i<spellCount; i++) {
scanf("\n");
scanf("%c", &type[i]);
for (j=0; j<itemCount; j++) {
scanf("%lf", &magic[i][j]);
if (magic[i][j] == '*') magic[i][j] == 1;
if (magic[i][j] == '+') magic[i][j] == 0;
}
}
SOLVE(1, getPrice(price));
printf("%.3lf\n", maxPrice);
for (i=0; i<spellCount; i++) printf("%d ", optimal[i]);
return 0;
}
Вывод: Используя язык программирования С, мы решили поставленную задачу методом полного перебора, а также сделали это эффективно с точки зрения времени выполнения программы и использованной памяти.
Лабораторная работа №5.
Целью работы является написание эффективного, по времени и памяти, алгоритма компьютерной геометрии, который находит площадь простого многоугольника.
Задача. «Многоугольник»
Входной файл: polygon .in
Выходной файл: polygon .out
Дата: 2019-05-28, просмотров: 167.
