Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Марк и Максим играют между собой шахматный матч. Вероятность того, что в одной партии победит Марк, равна a /( a + b + c ). Вероятность того, что в одной партии победит Максим, равна b /( a + b + c ). Соответственно вероятность ничьей равна c /( a + b + c ). Мальчики договорились, что матч будет состоять не более, чем из N партий. Но если кто-то из них вырвется вперёд на K очков, то матч сразу заканчивается. Ваша задача – найти ожидаемую продолжительность шахматного матча.

Вход

Во входном файле записаны пять целых чисел – a, b, c, N, K (1 ≤ a, b, c ≤ 10⁶, 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 очков, если партия заканчивается вничью, то оба игрока получают по ½ очка.

 

Задача. ”Волшебник”

Ограничение времени: 1 секунда на тест

Ограничение памяти: 256 М байт

Волшебник имеет N магических предметов (1 ≤ N ≤ 30), каждый из которых характеризуется своей ценностью v_i  (0 < v_i ≤ 10000). Он может произнести M заклинаний (1 ≤ M ≤ 10), изменяющих ценность имеющихся предметов. Каждое заклинание может быть произнесено не более одного раза. Произнесенное заклинание действует на все имеющиеся предметы. Заклинания делятся на 2 типа. После сотворения заклинания первого типа с номером j стоимость предмета i изменяется в D_ij раз (если 1 < D_ij ≤ 100, абсолютная величина стоимости увеличивается, при 0 ≤ D_ij < 1 уменьшается, при D_ij = 1 остается неизменной). Заклинание второго типа с номером j изменяет стоимость предмета i на R_ij (если R_ij > 0, стоимость увеличивается, при R_ij < 0 - уменьшается, при R_ij = 0 остается неизменной). Волшебник должен с помощью известных ему заклинаний добиться того, чтобы суммарная ценность имеющихся предметов была максимальной.

Вход

Текстовый файл WIZARD.IN содержит M + 2 строки. Первая строка содержит значения N и M. Следующая строка содержит значения v_i (i = 1, ..., N). Наконец, каждая из последних M строк соответствует одному заклинанию. Для заклинания первого типа эта строка содержит символ * и значения D_ij (i = 1, ..., N). Для заклинания второго типа она содержит символ + и значения R_ij (i = 1, ..., N). Данные в строках входного файла разделяются одним или несколькими пробелами.

Выход

Выходные данные помещаются в текстовый файл WIZARD.OUT и содержат две строки. Первая строка содержит получившуюся суммарную стоимость предметов (с точностью до 0.001), вторая - M разделенных одним пробелом чисел t_j (j = 1, ..., M), где t_j = k, если заклинание j было произнесено k-м по счету, и t_j = 0, если заклинание не было произнесено.

Примеры входа и выхода

WIZARD.IN	WIZARD.OUT
4 2 2 2 2 2 * 3 2 1 2 * 0.5 1 1 5	29.000 1 2

Задача. «Многоугольник»

Входной файл: polygon .in

Выходной файл: polygon .out

Ограничение времени: 1 секунда на тест

Ограничение памяти: 64 М байт

Вася рисует на листе клетчатой бумаги простой многоугольник. Он ставит точку в угол какого-нибудь квадратика, а затем проводит отрезок единичной длины влево, вправо, вверх или вниз. Из конца этого отрезка он вновь проводит отрезок в одном из четырёх направлений, и так далее, пока не вернётся в самую первую точку. Вася не допускает пересечений и касаний отрезков, так что у него всегда получается простой многоугольник. Вася записывает свои действия в виде последовательности букв L (влево), R (вправо), U (вверх), D (вниз). Напишите программу, находящую площадь многоугольника по Васиной записи.

Вход

Во входном файле записана последовательность букв L, R, U и D. Длина последовательности не превосходит 100 символов.

Выход

Запишите в выходной файл площадь многоугольника.

Примеры входа и выхода

polygon .in	polygon .out
DLULDDRRRUUULD	6
UUUULLLLDDDDRRRR	16

 

 

Задание получил:

Студент _________________________ «____»__________________2016 г.

Лабораторная работа №1.

Целью работы является написание эффективного, по времени и памяти, алгоритма решения задачи нахождения этажа, на котором находится комната в кампусе, по заданным параметрам.

Задача. Кампус

Имя входного файла:	building.in
Имя выходного файла:	building.out
Ограничение по времени:	1 секунда
Ограничение по памяти:	256 мегабайт

Новое здание кампуса Университета Байтбурга имеет n этажей, пронумерованных снизу вверх от 1 до n. Комнаты студентов расположены в нескольких подъездах.

В каждом подъезде на этажах, номер которых кратен числу k, расположено по x комнат, а на остальных этажах расположено по y комнат.

Комнаты внутри каждого подъезда пронумерованы последовательными натуральными числами. Номера комнат на первом этаже имеют наименьшие значения в этом подъезде, затем следуют номера комнат на втором этаже, и так далее. Комнаты в первом подъезде пронумерованы, начиная с 1, в каждом следующем подъезде нумерация комнат начинается с числа, следующего после максимального номера комнаты в предыдущем подъезде.

На рис. 1 показаны номера комнат в здании с n = 7 этажами, 3 подъездами, и параметрами k = 3, x = 2, y = 3.

	Подъезд 1	Подъезд 2	Подъезд 3
7 этаж	17, 18, 19	36, 37, 38	55, 56, 57
6 этаж	15, 16	34, 35	53, 54
5 этаж	12, 13, 14	31, 32, 33	50, 51, 52
4 этаж	9, 10, 11	28, 29, 30	47, 48, 49
3 этаж	7, 8	26, 27	45, 46
2 этаж	4, 5, 6	23, 24, 25	42, 43, 44
1 этаж	1, 2, 3	20, 21, 22	39, 40, 41

Рис. 1. Пример нумерации комнат в здании

Для организации расселения студентов администрация кампуса должна по номеру комнаты оперативно определять этаж, на котором она находится.

Требуется написать программу, которая по заданным числам n, k, x и y, а также по номерам комнат, определяет для каждой комнаты, на каком этаже она находится.

Формат входного файла

Первая строка входного файла содержит натуральные числа n, k, x и y (1 ≤ n ≤ 10⁹, 1 ≤ k ≤ n, 1 ≤ x, y ≤ 10⁹). Соседние числа разделены ровно одним пробелом.

Вторая строка входного файла содержит натуральное число q — количество номеров комнат, для которых требуется определить этаж (1 ≤ q ≤ 1000).

Третья строка содержит q целых чисел a₁, a₂, …, a_q — номера комнат (1 ≤ a_i ≤ 10¹⁸). Можно считать, что в здании так много подъездов, что все комнаты с заданными номерами существуют.

Формат выходного файла

Требуется вывести q чисел, по одному на строке. Для каждого номера комнаты во входном файле требуется вывести номер этажа, на котором она находится.

 

Пример входных и выходных файлов

building.in	building.out
7 3 2 3 4 1 19 20 50	1 7 1 5

 

Решение на С :

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define NMAX 1005

 

long long A[NMAX];

long long B[NMAX];

 

int main (void) {

       //freopen("inputD.txt", "r", stdin);

       //freopen("output.txt", "w", stdout);

       freopen("building.in", "r", stdin);

       freopen("building.out", "w", stdout);

           

       long long i, j, floorCount, k, x, y, roomCount, entRoom = 0, help = 0, floorInBlock = 0;

           

       scanf("%I64d %I64d %I64d %I64d\n", &floorCount, &k, &x, &y);

       scanf("%I64d\n", &roomCount);

       for (i=0; i<roomCount; i++) {

                   scanf("%I64d", &A[i]);

       }

           

       entRoom = (floorCount / k) * x + (floorCount - (floorCount / k)) * y;

           

       for (i=0; i<roomCount; i++) {

                   if (A[i]%entRoom != 0) {

                              A[i]%=entRoom;

                   }

                   else A[i] = entRoom;

                   //printf("%I64d ", A[i]);

       }

           

       help = x + (k - 1) * y;

       //printf("\n%I64d\n", help);

       for (i=0; i<roomCount; i++) {

                   if (A[i]%help != 0) {

                              B[i]=A[i]%help;

                   }

                   else B[i] = help;

       //     printf("%I64d ", B[i]);

       }

           

       for (i=0; i<roomCount; i++) {

                   if (B[i] > (k-1) * y && B[i] <= (k-1) * y + x) {

                              if (A[i] % help == 0) printf("%I64d\n", A[i]/help*k);

                              else printf("%I64d\n", ((A[i]/help) + 1)*k);

                   }

                   else if (B[i] > 0 && B[i] <= y) {

                              if (A[i]/help == 0) printf("1\n");

                              else printf("%I64d\n", (A[i]/help*k)+1);

                   }

                   else {

                              if (B[i] % y == 0) floorInBlock = B[i]/y;

                              else floorInBlock = (B[i]/y) + 1;

                              printf("%I64d\n", floorInBlock + k*(A[i]/help));

                   }

       }

           

       return 0;

}

 

Вывод: Используя язык программирования С, мы решили поставленную задачу нахождения этажа, на котором находится комната в кампусе, а также сделали это эффективно с точки зрения времени выполнения программы и использованной памяти.

 

 

Лабораторная работа №2.

Целью работы является написание эффективного, по времени и памяти, алгоритма решения задачи, используя алгоритм быстрой сортировки.