ОТЧЁТ
По учебной практике
(Учебная практика по получению первичных профессиональных умений и навыков)
Подготовил: Парахин Алексей Витальевич
Студентка 1 курса направления подготовки «Прикладная математика и информатика»
Профиль: Высокопроизводительные вычисления и технологии параллельного программирования
Сроки практики: с 1.09.2017 г. по 31.12.2017 г.
Руководитель: _________ к.ф.-м.н., доцент Григорьев С.А.
«____» __________________2017 г.
Калининград
Г.
Оглавление
Введение……………………………………………………………………………………………...3
Лабораторная работа №1………………………………………………………………………………...10
Лабораторная работа №2………………………………………………………………………………...14
Лабораторная работа №3………………………………………………………………………………...20
Лабораторная работа №4………………………………………………………………………………...22
Лабораторная работа №5………………………………………………………………………………...26
Введение
Вид практики - учебная практика по получению первичных профессиональных умений и навыков (далее Учебная практика).
Цель учебной практики: получение первичных профессиональных умений и навыков.
Задачи учебной практики:
- Закрепление и углубление теоретических знаний по программированию;
- Приобретение и развитие первичных профессиональных навыков и умений по прикладной математике и информатике.
Индивидуальное задание на практику:
Задача. Кампус
| Имя входного файла: | 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 ≤ 109, 1 ≤ k ≤ n, 1 ≤ x, y ≤ 109). Соседние числа разделены ровно одним пробелом.
Вторая строка входного файла содержит натуральное число q — количество номеров комнат, для которых требуется определить этаж (1 ≤ q ≤ 1000).
Третья строка содержит q целых чисел a1, a2, …, aq — номера комнат (1 ≤ ai ≤ 1018). Можно считать, что в здании так много подъездов, что все комнаты с заданными номерами существуют.
Формат выходного файла
Требуется вывести q чисел, по одному на строке. Для каждого номера комнаты во входном файле требуется вывести номер этажа, на котором она находится.
Пример входных и выходных файлов
| building.in | building.out |
| 7 3 2 3 4 1 19 20 50 | 1 7 1 5 |
Задача. Большой линейный коллайдер
| Имя входного файла: | linear.in |
| Имя выходного файла: | linear.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 256 мегабайт |
Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов «Большой линейный коллайдер» (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.
В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон е–, либо положительно заряженную частицу — позитрон е+. В эксперименте i-я частица исходно размещается в точке с координатой xi. После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: е– частицы перемещаются по направлению уменьшения координаты, а е+ частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.
Если в процессе перемещения частицы е– и е+ оказываются в одной точке, то они взаимодействуют и обе исчезают, при этом они не влияют на дальнейшее поведение остальных частиц.
Ученые выбрали m различных моментов времени t1, t2, …, tm, для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени tj, не должны учитываться при подсчете количества частиц для этого момента времени.
Требуется написать программу, которая по описанию исходного расположения и типов частиц, а также заданным моментам времени, определяет для каждого из моментов количество частиц, которое будет находиться в БЛК непосредственно после этого момента.
Формат входного файла
Первая строка входного файла содержит число n — количество частиц (1 ≤ n ≤ 200 000). Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа xi и vi — координату i-й частицы и ее тип соответственно (–109 ≤ x1 < x2 < … <xn ≤ 109, vi равно –1 или 1). Частица е– описывается значением vi = –1, а частица е+ описывается значением vi = 1.
Следующая строка содержит целое число m — количество моментов времени, которые выбрали ученые (1 ≤ m ≤ 200 000). Последняя строка содержит m целых чисел: t1, t2, …, tm (0 ≤ t1 < t2 < … < tm ≤ 109).
Формат выходного файла
Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.
Примеры входных и выходных файлов
| linear.in | linear.out |
| 4 -1 1 0 -1 1 1 5 -1 4 0 1 2 3 | 4 2 0 0 |
Задача. «Шахматный матч»
Входной файл: chess . in
Выходной файл: chess . out
Вход
Во входном файле записаны пять целых чисел – 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 очков, если партия заканчивается вничью, то оба игрока получают по ½ очка.
Задача. ”Волшебник”
Вход
Текстовый файл 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 |
Задача. «Многоугольник»
Входной файл: polygon .in
Выходной файл: polygon .out
Вход
Во входном файле записана последовательность букв 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 ≤ 109, 1 ≤ k ≤ n, 1 ≤ x, y ≤ 109). Соседние числа разделены ровно одним пробелом.
Вторая строка входного файла содержит натуральное число q — количество номеров комнат, для которых требуется определить этаж (1 ≤ q ≤ 1000).
Третья строка содержит q целых чисел a1, a2, …, aq — номера комнат (1 ≤ ai ≤ 1018). Можно считать, что в здании так много подъездов, что все комнаты с заданными номерами существуют.
Формат выходного файла
Требуется вывести 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.
Целью работы является написание эффективного, по времени и памяти, алгоритма решения задачи, используя алгоритм быстрой сортировки.
Лабораторная работа №3.
Целью работы является написание эффективного, по времени и памяти, алгоритма решения задачи методом полного перебора.
Задача. «Шахматный матч»
Входной файл: chess . in
Выходной файл: chess . out
Вход
Во входном файле записаны пять целых чисел – 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.
Целью работы является написание эффективного, по времени и памяти, алгоритма решения задачи методом полного перебора.
Задача. ”Волшебник”
Вход
Текстовый файл 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
Вход
Во входном файле записана последовательность букв L, R, U и D. Длина последовательности не превосходит 100 символов.
Выход
Запишите в выходной файл площадь многоугольника.
Примеры входа и выхода
| polygon .in | polygon .out |
| DLULDDRRRUUULD | 6 |
| UUUULLLLDDDDRRRR | 16 |
Решение на С++:
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 105
struct point{
int x;
int y;
};
string movement;
int pointsAmount;
point P[NMAX];
void getData() {
cin >> movement;
pointsAmount = movement.size() + 1;
P[0].x = 0;
P[0].y = 0;
for (int i = 1; i < pointsAmount; ++i) {
if (movement[i - 1] == 'U') {
P[i].x = P[i - 1].x;
P[i].y = P[i - 1].y + 1;
}
else if (movement[i - 1] == 'D') {
P[i].x = P[i - 1].x;
P[i].y = P[i - 1].y - 1;
}
else if (movement[i - 1] == 'R') {
P[i].x = P[i - 1].x + 1;
P[i].y = P[i - 1].y;
}
else if (movement[i - 1] == 'L') {
P[i].x = P[i - 1].x - 1;
P[i].y = P[i - 1].y;
}
}
}
void printData() {
for (int i = 0; i < pointsAmount; ++i) {
cout << P[i].x << " " << P[i].y << "\n";
}
}
int calcTriangleOrSquare(point p1, point p2, point p3) {
return ((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y));
}
int solve() {
int result = 0;
point zero;
zero.x = 0;
zero.y = 0;
for (int i = 0; i < pointsAmount - 1; ++i) {
result += calcTriangleOrSquare(zero, P[i], P[i + 1]);
}
return abs(result / 2);
}
int main() {
// freopen ("input.txt", "r", stdin);
// freopen ("output.txt", "w", stdout);
freopen ("polygon.in", "r", stdin);
freopen ("polygon.out", "w", stdout);
getData();
// printData();
cout << solve();
return 0;
}
Вывод: Используя язык программирования С++, мы находим площадь простого многоугольника, а также делаем это эффективно с точки зрения времени выполнения программы и использованной памяти.
Заключение
В ходе учебной практики были выполнены следующие задачи:
- Закрепление и углубление теоретических знаний по программированию;
- Приобретение и развитие первичных профессиональных навыков и умений по прикладной математике и информатике.
ОТЧЁТ
По учебной практике
(Учебная практика по получению первичных профессиональных умений и навыков)
Подготовил: Парахин Алексей Витальевич
Студентка 1 курса направления подготовки «Прикладная математика и информатика»
Профиль: Высокопроизводительные вычисления и технологии параллельного программирования
Сроки практики: с 1.09.2017 г. по 31.12.2017 г.
Руководитель: _________ к.ф.-м.н., доцент Григорьев С.А.
«____» __________________2017 г.
Калининград
Г.
Оглавление
Введение……………………………………………………………………………………………...3
Лабораторная работа №1………………………………………………………………………………...10
Лабораторная работа №2………………………………………………………………………………...14
Лабораторная работа №3………………………………………………………………………………...20
Лабораторная работа №4………………………………………………………………………………...22
Лабораторная работа №5………………………………………………………………………………...26
Введение
Вид практики - учебная практика по получению первичных профессиональных умений и навыков (далее Учебная практика).
Цель учебной практики: получение первичных профессиональных умений и навыков.
Задачи учебной практики:
- Закрепление и углубление теоретических знаний по программированию;
- Приобретение и развитие первичных профессиональных навыков и умений по прикладной математике и информатике.
Индивидуальное задание на практику:
Задача. Кампус
| Имя входного файла: | 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 ≤ 109, 1 ≤ k ≤ n, 1 ≤ x, y ≤ 109). Соседние числа разделены ровно одним пробелом.
Вторая строка входного файла содержит натуральное число q — количество номеров комнат, для которых требуется определить этаж (1 ≤ q ≤ 1000).
Третья строка содержит q целых чисел a1, a2, …, aq — номера комнат (1 ≤ ai ≤ 1018). Можно считать, что в здании так много подъездов, что все комнаты с заданными номерами существуют.
Формат выходного файла
Требуется вывести q чисел, по одному на строке. Для каждого номера комнаты во входном файле требуется вывести номер этажа, на котором она находится.
Пример входных и выходных файлов
| building.in | building.out |
| 7 3 2 3 4 1 19 20 50 | 1 7 1 5 |
Задача. Большой линейный коллайдер
| Имя входного файла: | linear.in |
| Имя выходного файла: | linear.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 256 мегабайт |
Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов «Большой линейный коллайдер» (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.
В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон е–, либо положительно заряженную частицу — позитрон е+. В эксперименте i-я частица исходно размещается в точке с координатой xi. После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: е– частицы перемещаются по направлению уменьшения координаты, а е+ частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.
Если в процессе перемещения частицы е– и е+ оказываются в одной точке, то они взаимодействуют и обе исчезают, при этом они не влияют на дальнейшее поведение остальных частиц.
Ученые выбрали m различных моментов времени t1, t2, …, tm, для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени tj, не должны учитываться при подсчете количества частиц для этого момента времени.
Требуется написать программу, которая по описанию исходного расположения и типов частиц, а также заданным моментам времени, определяет для каждого из моментов количество частиц, которое будет находиться в БЛК непосредственно после этого момента.
Формат входного файла
Первая строка входного файла содержит число n — количество частиц (1 ≤ n ≤ 200 000). Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа xi и vi — координату i-й частицы и ее тип соответственно (–109 ≤ x1 < x2 < … <xn ≤ 109, vi равно –1 или 1). Частица е– описывается значением vi = –1, а частица е+ описывается значением vi = 1.
Следующая строка содержит целое число m — количество моментов времени, которые выбрали ученые (1 ≤ m ≤ 200 000). Последняя строка содержит m целых чисел: t1, t2, …, tm (0 ≤ t1 < t2 < … < tm ≤ 109).
Формат выходного файла
Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.
Примеры входных и выходных файлов
| linear.in | linear.out |
| 4 -1 1 0 -1 1 1 5 -1 4 0 1 2 3 | 4 2 0 0 |
Задача. «Шахматный матч»
Входной файл: chess . in
Выходной файл: chess . out
Ограничение времени: 1 секунда на тест
Дата: 2019-05-28, просмотров: 405.
