Получение зачета по ускоренной схеме

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

• решить "вступительную" задачу (срок сдачи — сентябрь);
• решить основную задачу (срок сдачи — октябрь);
• сдать автоматизированный зачет (зачетная неделя).

Отказ от данной схемы возможен в любой момент. Пропуск срока сдачи равносилен добровольному отказу от данной схемы.

Требования к программам

• Программа должна быть написана на языке Си и компилироваться без предупреждений компилятором gcc при использовании ключей компиляции, которые приведены здесь.
• Текст программы должен быть оформлен в соответствии с выбранным стилем.
• Все заимствования кода, если таковые присутствуют в тексте, должны быть явно указаны и обоснованы.
• Программа должна освобождать используемые ресурсы системы (динамическую память, файловые дескрипторы и т.п.).
• При обработке входных данных должны учитываться возможные ошибки.
• Если исходные данные содержат ошибку, и это приводит к аварийному завершению программы или получению какого-то результата, то такая программа не засчитывается.
• Вместе с программой должны быть подготовлены тесты. Количество и состав тестов вы определяете самостоятельно.

Порядок сдачи

• Сдача программ производится на компьютерах в дисплейном классе.
• Для сдачи предоставляется три попытки.
• Попытка считается использованной, если:
  • программа не соответствует указанным выше требованиями;
  • получен неправильный ответ на дополнительный вопрос о реализованном алгоритме или тексте программы.

Условия задач

"Вступительная" задача

Задана матрица неотрицательных целых чисел A размера N (число строк) на M (число столбцов) и положительное целое число K. Для пары индексов (n, m) определена функция S(n, m), которая некоторым образом вычисляет символьную строку. Конкретная функция S определяется вариантом задачи.

Триграммой называется последовательность из трех подряд идущих символов строки. Требуется найти минимальное значение n для которого среди строк S(n, 0), S(n, 1), ..., S(n, M-1) найдется по крайней мере [n/2]+1 строк, в каждой из которых количество различных триграмм не меньше K.

Входные данные записаны в текстовом файле. Имя входного файла должно передаваться через аргумент командной строки. Во входном файле записаны числа K, N, M и по крайней мере N*M положительных целых чисел.

Результат работы записывается в выходной файл с именем "output.txt". Формат выходного файла: значение n, индексы столбцов матрицы A, в возрастающем порядке, для которых выполняются условия задачи. Если для любого n условие задачи не выполняется, то в выходной файл записывается значение -1.

В случае успешной обработки входного файла возвращаемое значение функции main должно быть 0. В остальных случаях программа должна вывести сообщение об ошибке в поток stderr и вернуть значение -1.

Вариант 1: S(n, m) получается последовательным записыванием цифр десятичной записи элементов A(n, m), A(n, m+1), ..., A(n, M-1), A(n, 0), ..., A(n, m-1).

Вариант 2: S(n, m) порождает символьную строку, которая является десятичной записью максимального числа, которое можно составить приписыванием элементов A(n, 0), A(n, 1), ..., A(n, m-1), A(n, m+1), ... A(n, M-1). Например, [5, 51, 59, 9] ==> "959551"

Вариант 3: S(n, m) есть символьная строка, которая получается записыванием обращенных строковых представлений A(n, m), A(n, m+1), ..., A(n, M-1), A(n, 0), ..., A(n, m-1). Например, [324, 14, 93] ==> "4234139".

Вариант 4: S(n, m) есть символьная строка, которая является десятичной записью числа, равного остатку от деления на 2¹⁸-1 суммы всех элементов n-ой строки матрицы A за исключением элемента с индексами (n, m).

Вторая задача

Вторые задачи выдаются из раздела 5 третьей части обычных задач.