Question

B. Очистка данных Ограничение времени: 1.0 секунды Ограничение памяти: 64 МБ Прежде чем применить к данным методы машинного обучения, проводится процесс очистки данных. Необходимость очистки связана с тем, что в данных могут быть аномальные элементы: дубли, ошибки ввода и выбросы. Если очистка данных не будет выполнена, то методы анализа данных могут дать неправильный результат! Рассмотрим интеллектуальную систему предсказания погоды. Такая система постоянно получает данные о текущей температуре воздуха с множества метеостанций. Каждая метеостанция передает последовательно данные о температуре в виде пары целых чисел. Первое число – это время, которое измеряется количеством секунд, прошедших с начала суток. Второе число – это температура в градусах Цельсия. Очистка данных производится в три этапа. Сначала удаляются дубли – когда информация об одном и том же времени измерения и той же температуре воздуха повторилась несколько раз подряд (первый элемент в такой последовательности одинаковых данных дублем не считается). После удаления дублей из последовательности удаляются ошибки ввода времени - когда время в новой паре не превосходит время в предыдущей паре или превышает количество секунд в сутках. На третьем этапе из последовательности удаляются выбросы – пары с аномальным значением температуры, когда измеренная температура по модулю больше 40 градусов или отличается от предыдущего значения более чем на 10 градусов. Вам нужно написать программу, которая будет определять в исходной последовательности данных количество удаляемых дублей, выбросов и ошибок. Можете считать, что самая первая пара в последовательности не относится к аномальным. Исходные данные В первой строке входных данных записано целое число n – количество измерений (1 ≤ n ≤103). В следующих n строках записаны целые числа t и T, разделенные пробелом – время измерения и значение температуры воздуха. Все числа по модулю не превосходят 109. Результат Выведите три целых числа, разделенных пробелами – количество дублей, ошибок ввода времени и выбросов в последовательности исходных данных. Пример исходные данные результат 6 10 5 8 5 8 5 8 5 12 25 13 10 2 1 1 Замечания 8 5 дублируется трижды. После удаления двух копий остается одна пара 8 5, которая является ошибкой ввода (т.к. время 8 меньше 10 из предыдущей пары). После ее удаления остается последовательность из трех пар 10 5, 12 25, 13 10, в которой 12 25 – выброс (t = 25 более чем на 10 превышает 5). После удаления выброса остается очищенная последовательность 10 5, 13 10 В этой задаче есть тесты, в которых присутствуют только дубли (суммарно 20 баллов), ошибки ввода (также 20 баллов) и выбросы (еще 20 баллов). Оставшиеся тесты включают разные типы аномальных элементов (40 баллов).

Answer 1

PascalABC.NET 3.4.2, сборка 1884 от 24.11.2018

Внимание! Если программа не работает, обновите версию!

begin

 var n := ReadInteger;

 var L := new List<(integer, integer)>;

 loop n do

 begin

   L.Add(ReadInteger2)

 end;

 var k := L.Count;

 L := L.Distinct.ToList; // этап 1

 var k1 := L.Count;

 Print(k - k1);

 (k, k1) := (k1, 0); // этап 2

 var St := new Stack<integer>;

 var m := L.First[0]; // время

 for var i := 1 to k - 1 do

   if L[i][0] <= m then

   begin

     St.Push(i);

     Inc(k1)

   end

   else m := L[i][0];

 for var i := 1 to k1 do

   L.RemoveAt(St.Pop);

 Print(k1);

 (k, k1) := (L.Count, 0); // этап 3

 m := L.First[1]; // температура

 for var i := 1 to k - 1 do

   if Abs(L[i][1] - m) > 10 then

   begin

     St.Push(i);

     Inc(k1)

   end

   else m := L[i][1];

 for var i := 1 to k1 do

   L.RemoveAt(St.Pop);

 Println(k1);

end.

Пример

6

10 5

8 5

8 5

8 5

12 25

13 10

2 1 1

Answer 2

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

Вот псевдокод решения:

1. Инициализировать переменные для хранения количества дублей, ошибок и выбросов.
2. Прочитать входные данные.
3. Пройти по входным данным начиная со второй пары (индекс 1).
4. На каждом шаге сравнить текущую пару с предыдущей:
   • Если они равны, увеличить счетчик дублей.
   • Если текущее время меньше или равно предыдущему времени, увеличить счетчик ошибок.
   • Если температура аномальна (по модулю больше 40 или отличается от предыдущей более чем на 10), увеличить счетчик выбросов.
   • Обновить предыдущую пару на текущую.
5. Вывести значения счетчиков дублей, ошибок и выбросов.

Ниже представлена реализация на Python:

pythonCopy code
def data_cleaning(n, data):
    duplicates = 0
    input_errors = 0
    outliers = 0

    prev_time, prev_temp = data[0]

    for i in range(1, n):
        curr_time, curr_temp = data[i]

        if (curr_time, curr_temp) == (prev_time, prev_temp):
            duplicates += 1
        elif curr_time <= prev_time:
            input_errors += 1
        elif abs(curr_temp) > 40 or abs(curr_temp - prev_temp) > 10:
            outliers += 1

        prev_time, prev_temp = curr_time, curr_temp

    return duplicates, input_errors, outliers

# Чтение входных данных
n = int(input())
data = [tuple(map(int, input().split())) for _ in range(n)]

# Вычисление результатов
result = data_cleaning(n, data)

# Вывод результатов
print(*result)

Примечание: Входные данные в коде читаются с помощью функции input(). Для тестирования программы следует предоставить входные данные в описанном формате.