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

Имя

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

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

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

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

Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов «Большой линейный коллайдер» (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.

В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон е^–, либо положительно заряженную частицу — позитрон е⁺. В эксперименте i-я частица исходно размещается в точке с координатой x_i. После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: е^– частицы перемещаются по направлению уменьшения координаты, а е⁺ частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.

Если в процессе перемещения частицы е^– и е⁺ оказываются в одной точке, то они взаимодействуют и обе исчезают, при этом они не влияют на дальнейшее поведение остальных частиц.

Ученые выбрали m различных моментов времени t₁, t₂, …, t_m, для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени t_j, не должны учитываться при подсчете количества частиц для этого момента времени.

Требуется написать программу, которая по описанию исходного расположения и типов частиц, а также заданным моментам времени, определяет для каждого из моментов количество частиц, которое будет находиться в БЛК непосредственно после этого момента.

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

Первая строка входного файла содержит число n — количество частиц (1 ≤ n ≤ 200 000). Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа x_i и v_i — координату i-й частицы и ее тип соответственно (–10⁹ ≤ x₁ < x₂ < … <x_n ≤ 10⁹, v_i равно –1 или 1). Частица е^– описывается значением v_i = –1, а частица е⁺ описывается значением v_i = 1.

Следующая строка содержит целое число m — количество моментов времени, которые выбрали ученые (1 ≤ m ≤ 200 000). Последняя строка содержит m целых чисел: t₁, t₂, …, t_m (0 ≤ t₁ < t₂ < … < t_m ≤ 10⁹).

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

Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.

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

linear.in	linear.out
4 -1 1 0 -1 1 1 5 -1 4 0 1 2 3	4 2 0 0

 

Решение на С :

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define NMAX 200005

long long sign[NMAX];

long long pos[NMAX];

long long time[NMAX];

long long queue[NMAX];

long long dest[NMAX];

int n, m, countProt = -1, destroyed = 0;

void getData() {

int i;

long long p, t;

scanf("%d", &n);

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

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

    pos[i] = p * 2;

}

scanf("%d", &m);

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

    scanf("%I64d", &t);

    time[i] = t * 2;

}

}

void printData() {

int i;

printf("%d\n", n);

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

    printf("%I64d %I64d\n", pos[i], sign[i]);

}

printf("%d\n", m);

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

    printf("%I64d ", time[i]);

}

}

void sort(long long* A, int a,int b){

long long tmp1, tmp2, m, k, l, r;

if (a>=b) return;

m = a+rand()%(b-a+1);

k = A[m];

l = a-1;

r = b+1;

while (1){

   while (A[++l]<k);

   while (A[--r]>k);

   if (l>=r) break;

   tmp1 = A[l];

   A[l]=A[r];

   A[r]=tmp1;

}

sort(A,a,r);

sort(A,r+1,b);

}

void SOLVE() {

int i, help = 0;

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

    if (sign[i] == 1) {

         countProt++;

         queue[countProt] = pos[i];

    }

    if (sign[i] == -1) {

         if (countProt >= 0) {

              dest[destroyed] = llabs(queue[countProt] - pos[i])/2;

              destroyed++;

              countProt--;

         }

    }

}

sort(dest, 0, destroyed - 1);   

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

    while (dest[help] <= time[i] && help != destroyed) {

         n -= 2;

         help++;

    }

    printf("%d\n", n);

}

}

 

int main (void) {

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

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

getData();

SOLVE();

// printf("\n")

// printData();

return 0;

}

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

 

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

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

Задача. «Шахматный матч»

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

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