инф. Обработка данных, вводимых из файла в виде последовательности чисел
 Скачать 0.56 Mb.
|
|
2a-4b-6 Гарантируется, что уравнение имеет «хороший» вид, все его коэффициенты определены и корни вещественные. Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая дописывает в конец файла корни уравнения. Для приведенного входного файла программа должна дописать в конец файла -1 3 В командных олимпиадах по программированию для решения предлагается не более 12 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систем соревнований. Вам предлагается написать эффективную, в том числе и по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы на проверку, чтобы определить популярность той или иной задачи. Следует учитывать, что количество запросов в списке может быть очень велико, например, когда олимпиада проводится через Интернет. перед текстом программы кратко опишите используемый вами алгоритм решения задачи. На вход программе в первой строчке подается количество пришедших запросов N. В каждой из последующих N строк записан номер задачи от 1 до 12. Пример входных данных: 6 1 2 1 1 5 2 Программа должна вывести список всех задач, встречающихся в запросах, в порядке возрастания (неубывания) количества запросов по ней с указанием этого количества запросов. Каждая задача должна быть выведена только один раз. Пример выходных данных для приведенных входных данных: 5 1 2 2 1 3 Популярная газета объявила конкурс на выбор лучшего фильма, для которого стоит снять продолжение. На выбор читателей было предложено 10 фильмов. Вам предлагается написать эффективную, в том числе и по используемой памяти, программу, которая будет статистически обрабатывать результаты sms-голосования по этому вопросу, чтобы определить популярность того или иного фильма. Следует учитывать, что количество голосов в списке может быть очень велико. На вход программе в первой строчке подается количество пришедших sms-сообщений N. В каждой из последующих N строк записано название фильма. Пример входных данных: 6 Белое солнце пустыни Бриллиантовая рука Белое солнце пустыни Белое солнце пустыни Гараж Бриллиантовая рука Программа должна вывести список всех фильмов, встречающихся в списке, в порядке убывания (невозрастания) количества отданных за них голосов с указанием этого количества голосов. Название каждого фильма должно быть выведено только один раз. Пример выходных данных для приведенных входных данных: Белое солнце пустыни 3 Бриллиантовая рука 2 Гараж 1 По каналу связи передается последовательность положительных целых чисел, все числа не превышают 1000, их количество заранее неизвестно. Каждое число передается отдельно. Признаком конца передаваемой последовательности является число 0. После числа 0 передается контрольное значение – наибольшее число R, удовлетворяющее следующим условиям: R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных, но равных по величине элементов допускаются); R делится на 6 Напишите эффективную программу, которая получает последовательность чисел и следующие за ней признак конца и контрольное значение, а также проверяет правильность контрольного значения. Программа должна напечатать отчет по следующей форме: Получено .. чисел Полученное контрольное значение: …. Вычисленное контрольное значение:… Контроль пройден (или – контроль не пройден) Размер памяти, которую использует Ваша программа, не должен зависеть от длины переданной последовательности чисел. Перед текстом программы кратко опишите используемый вами алгоритм решения задачи. Пример входных данных: 60 17 3 7 9 60 0 3600 Пример выходных данных для приведенного выше примера входных данных: Получено 6 чисел Полученное контрольное значение: 3600 Вычисленное контрольное значение: 3600 Контроль пройден. По каналу связи передается последовательность положительных целых чисел X1, X2, …; все числа не превышают 1000, их количество заранее неизвестно. Каждое число передается в виде отдельной текстовой строки, содержащей десятичную запись числа. Признаком конца передаваемой последовательности является число 0. Участок последовательности от элемента XT до элемента XT+N называется подъемом, если на этом участке каждое следующее число больше предыдущего. Высотой подъема называется разность XT+N - XT. Напишите эффективную программу, которая вычисляет наибольшую высоту среди всех подъемов последовательности. Если в последовательности нет ни одного подъема, программа выдает 0. Программа должна напечатать отчет по следующей форме: Получено ... чисел Наибольшая высота подъема: ... Размер памяти, которую использует Ваша программа, не должен зависеть от длины переданной последовательности чисел. Взаимным индексом совпадения строк2 S1 и S2, которые включают только латинские буквы, называется величина  , где n1 и n2 – длины строк S1 и S2, а  – число вхождений буквы, имеющей номер kв латинском алфавите, в строку Si. Например, индекс совпадений строк «Moloko» и «mAma» равен (одна общая буква «m» встречается 1 раз в первой строке и 2 раза во второй строке). Напишите эффективную программу, которая вводит с клавиатуры две строки, содержащие (кроме латинских букв) знаки препинания и пробелы, и вычисляет взаимный индекс совпадения этих строк. Вам необходимо написать программу распознавания чисел, записанных прописью. Сначала на вход программе подается обучающий блок, состоящий из 27 строк. Первые 9 строк содержат слова «один», «два», ..., «девять», следующие 9 строк - слова «одиннадцать», «двенадцать», ... «девятнадцать», следующие 9 строк - слова «десять», «двадцать», ..., «девяносто». Все слова записаны маленькими русскими буквами без лишних пробелов в начале и в конце строки. Затем на вход программе подается значение N - количество записей, которые необходимо обработать. Следующие N строк содержат записанные словами числа. Каждое число записано по-русски, маленькими буквами, без ошибок. Если число состоит из нескольких слов, между словами находится ровно один пробел, лишних пробелов в начале и в конце строк нет. Напишите эффективную программу, которая определит сумму тех входных чисел, которые находятся в интервале от 1 до 99. Размер памяти, которую использует Ваша программа, не должен зависеть от длины исходного списка. Перед текстом программы кратко опишите используемый вами алгоритм решения задачи. Пример входных данных (обучающий блок показан в примере с сокращениями): один два … девяносто 5 двадцать восемь два миллиона четырнадцать сто двадцать три тысяча девятьсот восемьдесят четыре Пример выходных данных для приведённого выше примера входных данных: 42 Вам необходимо написать программу анализа текста. На вход программе подаются строки, содержащие английские слова. В одной строке может быть произвольное количество слов. Все слова записаны строчными (маленькими) английскими буквами. Между словами в строке может быть один или больше пробелов, возможны пробелы в начале и в конце строки. Других символов, кроме строчных английских букв и пробелов, в строках нет. Длина каждой строки не превышает 200 символов. Количество строк неизвестно, общее количество слов не более одного миллиона. Конец ввода обозначается строкой, содержащей единственный символ «*». Напишите эффективную, в том числе по памяти, программу, которая будет определять количество слов, начинающихся на каждую букву английского алфавита, и выводить эти количества и соответствующие им буквы в порядке убывания. Если количество слов, начинающихся на какие-то буквы, совпадает, эти буквы следует выводить в алфавитном порядке. Если на какую-то букву слов нет, выводить эту букву не надо. Размер памяти, которую использует Ваша программа, не должен зависеть от размера исходного списка. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи и укажите используемый язык программирования и его версию. Пример входных данных: one two three four five a quick brown fox * Пример выходных данных для приведенного выше примера входных данных: f 3 t 2 а 1 b 1 о 1 q 1 Примечание. Английский алфавит совпадает с латинским и содержит 26 букв от а до z: abcdefghijklmnopqrstuvwxyz На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Чтобы в документации качественно отличать одну серию от другой, каждую серию решили характеризовать числом, равным минимальному произведению из всех произведений пар скоростей различных частиц. Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя искомую величину. В нашей модели скорость частицы - это величина, которая может принимать как положительные, так и отрицательные значения. Следует учитывать, что частиц, скорость которых измерена, может быть очень много, но не может быть меньше двух. Перед текстом задачи кратко опишите используемый вами алгоритм решения задачи. На вход программе в первой строке подается количество частиц N. В каждой из последующих N строк записано одно целое число со знаком (плюс или минус), по абсолютной величине не превосходящее 10000. Пример входных данных: 5 +123 +2000 +10 +3716 +10 Программа должна вывести одно число - минимальное произведение из всех произведений пар скоростей различных частиц. Пример выходных данных для приведенного выше примера входных данных: 100 На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Все скорости положительны. Чтобы в документации качественно отличать одну серию эксперимента от другой каждую серию решили характеризовать числом равным минимальной чётной сумме из всех сумм пар скоростей различных частиц. Если чётная сумма отсутствует, то характеристикой будет являться просто минимальная сумма. Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования), которая будет обрабатывать результаты эксперимента, находя искомую величину. Следует учитывать, что частиц, скорость которых измерена, может быть очень много, но не может быть меньше двух. Перед текстом программы кратко опишите используемый вами алгоритм решения задачи. На вход программе в первой строке подается количество частиц N. В каждой из последующих N суток записано одно натуральное число не превышающее 30000. Пример входных данных: 5 123 1000 12 2548 12 Программа должна вывести характеристику данной серии экспериментов. Пример выходных данных для приведенного выше примера входных данных: 24 На электронную почту Вам пришло письмо, подписанное аббревиатурой (первыми буквами фамилии, имени и отчества (далее - ФИО) отправителя). Аббревиатура оказалась Вам незнакома. У Вас есть список всех предполагаемых отправителей, взятый из ранее полученных писем, среди которых различных людей с такой аббревиатурой не больше 10. Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка, например Borland Pascal 7.0), которая определит всех вероятных адресатов – людей, ФИО которых можно сократить до нужной аббревиатуры. ФИО следует выдать в порядке убывания частоты их встречаемости в списке. На вход программе в первой строке подается аббревиатура – строка, состоящая из трех заглавных латинских букв. Во второй строке находится число N – количество ФИО, полученных в результате анализа почты, не все из них подходят под указанную аббревиатуру. Значение N может быть очень велико. В каждой из следующих N строк записано три слова: Фамилия Имя Отчество соответствующего человека. Слова разделяются одним пробелом. В конце и в начале строки пробелов нет. Все слова записаны заглавными латинскими буквами. Длина ФИО не превышает 100 символов. Гарантируется, что хотя бы один человек с нужной аббревиатурой есть. Пример входных данных: IPI 4 IVANOV PETR IVANOVICH PETROV IVAN IVANOVICH IVANOV PETR IVANOVICH ILYIN PETR ILYICH Программа должна вывести предполагаемых отправителей письма с указанием частоты их встречаемости в списке (в порядке убывания частоты). Пример выходных данных для приведенного выше примера входных данных: IVANOV PETR IVANOVICH 2 ILYIN PETR ILYICH 1 На вход программе подаются сведения о пассажирах, желающих сдать свой багаж в камеру хранения на заранее известное время до полуночи. В первой строке сообщается число пассажиров N, которое не меньше 3, но не превосходит 1000; во второй строке – количество ячеек в камере хранения K, которое не меньше 10, но не превосходит 1000. Каждая из следующих N строк имеет следующий формат: <Фамилия> <время сдачи багажа> <время освобождения ячейки>, где <Фамилия> – строка, состоящая не более чем из 20 непробельных символов; <время сдачи багажа> – через двоеточие два целых числа, соответствующие часам (от 00 до 23 – ровно 2 символа) и минутам (от 00 до 59 – ровно 2 символа); <время освобождения ячейки> имеет тот же формат. <Фамилия> и <время сдачи багажа>, а также <время сдачи багажа> и <время освобождения ячейки> разделены одним пробелом. Время освобождения больше времени сдачи. Сведения отсортированы в порядке времени сдачи багажа. Каждому из пассажиров в камере хранения выделяется свободная ячейка с минимальным номером. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит, не дожидаясь освобождения одной из них. Требуется написать программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет выводить на экран для каждого пассажира номер ему предоставленной ячейки (можно сразу после ввода данных очередного пассажира). Если ячейка пассажиру не предоставлена, то его фамилия не печатается. Пример входных данных: 3 10 Иванов 09:45 12:00 Петров 10:00 11:00 Сидоров 12:00 13:12 Результат работы программы на этих входных данных: Иванов 1 Петров 2 Сидоров 1 На плоскости дан набор точек с целочисленными координатами. Необходимо найти треугольник наибольшей площади с вершинами в этих точках, одна из сторон которого лежит на оси OX. Напишите эффективную, в том числе по памяти, программу, которая будет решать эту задачу. Размер памяти, которую использует Ваша программа, не должен зависеть от длины переданной последовательности чисел. Укажите используемый язык программирования и его версию. В первой строке вводится одно целое положительное число – количество точек N. Каждая из следующих N строк содержит два целых числа – сначала координата х, затем координата у очередной точки. Программа должна вывести одно число – максимальную площадь треугольника, удовлетворяющего условиям задачи. Если такого треугольника не существует, программа должна вывести ноль. Пример входных данных: 6 0 0 2 0 0 4 3 3 5 5 -6 -6 Пример выходных данных для приведенного выше примера входных данных: |