Задача

Некоторые вирусы реплицируются путем замены фрагмента ДНК в живой клетке фрагментом ДНК, который вирус несет с собой. Это заставляет клетку создавать вирусы, идентичные оригинальной, зараженной клеткой. Группа биологов заинтересована в том, чтобы узнать, сколько ДНК вносит вирус в геном хозяина. Чтобы узнать об этом, они упорядочили полный геном здоровой клетки, а также идентичную клетку, инфицированную вирусом.

Геном оказался довольно большим, поэтому теперь им нужна Ваша помощь на этапе обработки данных. Имея последовательность ДНК до и после вирусной инфекции, определите длину самой маленькой одной последовательной части ДНК, которая может быть вставлена в первую последовательность, чтобы превратить ее во вторую. Один последовательный фрагмент ДНК также может быть удален из того же положения в последовательности, куда был вставлен ДНК. Небольшие изменения в ДНК могут иметь большие эффекты, поэтому вирус может вставить только несколько букв или даже ничего.

Входные данные

Состоит из двух строк, содержащих последовательность ДНК до и после вирусной инфекции, соответственно. Последовательность ДНК задается как строка, содержащая от 1 до $10^5$ букв верхнего регистра из алфавита {A, G, C, T}.

Код

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    //Инициализируем массивы, удовлетворяющие условия
    char b[100001], a[100001];
    cin >> b >> a;
    // b-строка до (before), a-строка после (after)
    int s = 0, l1 = strlen(b), l2 = strlen(a), e1 = l1, e2 = l2;
    //определяем длины первой и второй строк, без учёта нуль-символа. 
    
    // Проверяем есть ли символ в массиве b[s], 
    // Если есть и он такой же, как и в массиве a[s] - счётчик увеличивается
    // в результате мы узнаём на каком, крайнем слева, символе начинаются расхождения (s)
    for (; b[s] && b[s] == a[s]; ++s);
    
    // Цикл проходиться по массиву a и b с конца введённых в них строк
    // Цикл двигается по массиву до первого расхождения в буквах (b[e1]!=a[e2])
    // в результате мы узнаём на каком, крайнем справа, символе начинаются расхождения (e2)
    for (; e1>=0 && e2>=0 && b[e1]==a[e2]; --e1, --e2);
    
    // Считаем максимальное количество букв, которые подверглись расхождению, ища максимальное от
    // максимального между 0 и разницей в кол-ве символов второй строки от первой и
    // разницей между крайним правым и крайним левым номером элемента на котором начались расхождения + 1
    cout << max(max(0,l2-l1),e2-s+1) << endl;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

//Инициализируем массивы, удовлетворяющие условия

char b[100001], a[100001];

cin >> b >> a;

// b-строка до (before), a-строка после (after)

int s = 0, l1 = strlen(b), l2 = strlen(a), e1 = l1, e2 = l2;

//определяем длины первой и второй строк, без учёта нуль-символа.

// Проверяем есть ли символ в массиве b[s],

// Если есть и он такой же, как и в массиве a[s] - счётчик увеличивается

// в результате мы узнаём на каком, крайнем слева, символе начинаются расхождения (s)

for (; b[s] && b[s] == a[s]; ++s);

// Цикл проходиться по массиву a и b с конца введённых в них строк

// Цикл двигается по массиву до первого расхождения в буквах (b[e1]!=a[e2])

// в результате мы узнаём на каком, крайнем справа, символе начинаются расхождения (e2)

for (; e1>=0 && e2>=0 && b[e1]==a[e2]; --e1, --e2);

// Считаем максимальное количество букв, которые подверглись расхождению, ища максимальное от

// максимального между 0 и разницей в кол-ве символов второй строки от первой и

// разницей между крайним правым и крайним левым номером элемента на котором начались расхождения + 1

cout << max(max(0,l2-l1),e2-s+1) << endl;

}

Решение

Нам нужно определить длину самой маленькой одной последовательной части ДНК, которая может быть вставлена в первую последовательность, чтобы превратить ее во вторую.

В циклах for мы узнаём крайний слева и справа элемент обоих массивов, на которых буквы первой строки начинают не совпадать с буквами второй, s и e2 соответственно. Чтобы узнать результат необходимо проверить является ли l2 > l1 и больше ли l2-l1 чем e2-s1+1.

Задача на e-olymp

Код программы на ideone

Засчитанное решение

Related Images:

Задача

На прием к доктору каждый день приходит много людей. Каждый пациент находится на приеме целое число минут, однако разных пациентов доктор может принимать разное количество времени. Доктор начинает прием в момент времени $t_1$ минут и заканчивает прием в момент времени $t_2$ минут. Это означает, что любой пациент независимо от того, сколько времени его будет принимать доктор, может зайти на прием в моменты $t_1, t_1 + 1, …, t_2 − 1$. Заходить на прием к доктору в другое время или тогда, когда доктор принимает другого пациента, запрещено. Если пациент приходит в поликлинику в момент $t$, он ожидает первый момент времени $s ≥ t$ такой, что на этот момент доктор ведет прием, причем уже успел осмотреть всех пациентов, которые пришли в поликлинику раньше, то есть до момента $t$. Если доктор не успевает осмотреть всех до конца приема, то остаток пациентов должен прийти на следующий день.

Зная, в какой момент доктор начинает и заканчивает прием, те, кто и когда придут на прием в конкретный день, а также сколько времени будет осматривать доктор каждого пациента, определите момент времени, в который необходимо прийти на прием Пете Пяточкину, чтобы гарантированно попасть в этот день к доктору, и при этом ожидать приема как можно меньше. В случае, если имеется несколько альтернативных вариантов такого момента времени, Вам необходимо определить наименьший (наиболее ранний) из них.

Входные данные

В первой строке приведено три числа: количество желающих попасть на прием n, время начала приема $t_1$ и время завершения приема $t_2$, больший чем $t_1$.

Во второй строке перечислены $n$ чисел $a_1, a_2, …, a_n$ — время, когда в поликлинику зашли соответственно первый, второй, $…, n$-ый желающий попасть к доктору. Числа $a_1, a_2, …, a_n$ попарно различны и расположены в порядке возрастания.

В третьей строке перечислены n чисел $b_1, b_2, …, b_n$ — время, необходимое доктору на осмотр соответственно первого, второго, $…, n$-го пациента.

Все входные числа натуральные. Количество пациентов $n$ не больше $10^5$, остальные числа не превосходят $10^9$.

Сутки на планете, где проживает Петя Пяточкин, длятся значительно дольше, чем на Земле, поэтому время начала приема $t_1$, время завершения приема $t_2$, а также числа $a_1, a_2, …, a_n$ и $b_1, b_2, …, b_n$ могут быть большими чем 1440 — количество минут в земных сутках.

Выходные данные

Вывести наименьший момент времени, когда Петя Пяточкин должен прийти в поликлинику, чтобы гарантированно попасть к доктору, подождав приема как можно меньше времени. Если Петя придет одновременно с другим человеком, его как младшего пропустят вперед.

Тесты

№	Входные данные	Выходные данные
1	3 10 20 7 14 18 5 2 1	17
2	5 10 20 4 9 12 16 22 4 10 10 9 2	9
3	1 10 20 5 15	5

Код

#include <iostream>

using namespace std;

int a[100003], b[100003];

int main() {
    long long t1, t2, t, n, i, j, l;
    cin >> n >> t1 >> t2;
    t = 0;
    //Заполняем время прихода пациентов на приём в массив a
    for (i = 1; i <= n; i++) {
        cin >> a[i];
    }
    //Заполняем время на приём пациентов в массив b
    for (i = 1; i <= n; i++) {
        cin >> b[i];
    }
    //Проверяет приходит ли пациент в начале времени приёма или после его начала 
    if (a[1] >= t1) {
        cout << t1 << endl;
        return 0;
    }
    //Вводим точки отсчёта
    else {
        t = a[1];
        l = t1 - a[1];
        t1 += b[1];
    }
    j = 2;
    //Условие: Если разница между началом приёма и приёмом > 0; цикл не прошёл всех пациентов; приём ещё не окончен.
    while (l > 0 && j <= n && t1 < t2) {
        //Проверяет приходит ли следующий пациент к началу или уже после начала приёма врача
        if (a[j] >= t1) {
            t = t1;
            l = 0;
        } else {
            //Проверяет является ли разница между началом приёма следующего пациента и временем его прихода меньше, чем предыдущая зафиксированная разница
            if (t1 - a[j] < l) {
                t = a[j];
                l = t1 - a[j];
            }
            t1 += b[j];
        }
        j++;
    }
    //Если время приёма ещё не окончено, пациенты все прошли и прийти раньше не получилось - приходим сразу в конце приёма последнего
    if (t1 < t2 && l != 0 && j > n) {
        t = t1;
        l = 0;
    }
    cout << t << endl;
}

#include <iostream>

using namespace std;

int a[100003], b[100003];

int main() {

long long t1, t2, t, n, i, j, l;

cin >> n >> t1 >> t2;

t = 0;

//Заполняем время прихода пациентов на приём в массив a

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

cin >> a[i];

}

//Заполняем время на приём пациентов в массив b

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

cin >> b[i];

}

//Проверяет приходит ли пациент в начале времени приёма или после его начала

if (a[1] >= t1) {

cout << t1 << endl;

return 0;

}

//Вводим точки отсчёта

else {

t = a[1];

l = t1 - a[1];

t1 += b[1];

}

j = 2;

//Условие: Если разница между началом приёма и приёмом > 0; цикл не прошёл всех пациентов; приём ещё не окончен.

while (l > 0 && j <= n && t1 < t2) {

//Проверяет приходит ли следующий пациент к началу или уже после начала приёма врача

if (a[j] >= t1) {

t = t1;

l = 0;

} else {

//Проверяет является ли разница между началом приёма следующего пациента и временем его прихода меньше, чем предыдущая зафиксированная разница

if (t1 - a[j] < l) {

t = a[j];

l = t1 - a[j];

}

t1 += b[j];

}

j++;

}

//Если время приёма ещё не окончено, пациенты все прошли и прийти раньше не получилось - приходим сразу в конце приёма последнего

if (t1 < t2 && l != 0 && j > n) {

t = t1;

l = 0;

}

cout << t << endl;

}

Решение

Создаём два массива, удовлетворяющих условия, a — время прихода пациентов и b — время на их приём. Инициализируем все необходимые переменные: t_1 и t_2 — время приёма, t — время в которое Петя должен прийти, n- кол-во пациентов, i и j — счётчики, l — время между приходом пациента и началом его приёма.

Проверяем приходит ли первый пациент в самое начало приёма или после начала приёма, если в начало приёма — то приходим тогда.

В цикле while определяем минимальное время, в которое Петя может прийти на приём к врачу. Проверяем приходит ли следующий пациент до завершения приёма предыдущего. Если приходит во время завершения, или через некоторое время, то заходим после приёма предыдущего. (Нам уступают) Если нет, цикл продолжается, проверяет, является ли разница между началом приёма следующего пациента и временем его прихода меньше, чем предыдущая зафиксированная разницы. Если да — записывает её и время прихода данного пациента, и переходит к следующему пациенту.

В конце проверяем, если время приёма ещё не окончено, пациенты все прошли и прийти раньше не получилось — приходим сразу в конце приёма последнего.

Задача на e-olymp
Код программы на ideone
Засчитанное решение

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Author Archives: Євчук Даяна

e-olymp 6253. Репликация вируса

Задача

Входные данные

Выходные данные

Тесты

Код

Решение

Related Images:

e-olymp 7029. Поликлиника

Задача

Входные данные

Выходные данные

Тесты

Код

Решение

Related Images:

№	Входные данные	Выходные данные
1	AAAAA AGCGAA	3
2	GTTTGACACACATT GTTTGACCACAT	4
3	SMMSMM SMAHMA	4