lt;номер команды> <код задачи> A|R
Инструкция участнику
Получите у организатора свой индивидуальный четырехзначный код. Файлы – решения должны быть названы следующим образом:zкод участника_номер задачи.расширение
В качестве расширения допустимо использовать dpr для текстов на pascal или cpp для текстов на C++
Во время автоматической проверки решений будут использованы следующие компиляторы:
| Язык программирования | Компилятор | Командная строка |
| Паскаль | Borland Delphi 7.0 | dcc32 –cc !.dpr |
| Си | Microsoft Visual C++ .NET 2003 | cl !.cpp |
Например, Ваш код 2301 и Вы пишете на паскале. Тогда решением четвертой задачи должен быть файл z2301_4.dpr (если расширение вашего файла с текстом на Pascal отличается от dpr, то во время сдачи задания замените расширение на dpr).
У Вас есть возможность письменно задать во время олимпиады вопросы членам жюри. Вопросы должны подразумевать ответы «Да» или «Нет». Записывая вопрос укажите свою фамилию и имя.
Сдавая решение, убедитесь, что сдаваемый на проверку файл является исходным текстом программы!
Требования к решениям
Программа должна полностью содержаться в одном файле, использование своих модулей не допускается. Разрешается использование библиотеки STL (для С++).
Программа должна читать входные данные только один раз из файлов, указанных в условии задачи и выводить результат в выходные файлы, указанные в условии задачи. ВНИМАНИЕ имена файлов должны быть точно такими, как в условии. Проследите, чтобы у входных и выходных файлов не было расширений “txt”! Программа должна считать, что эти файлы находятся в текущемкаталоге – не прописывайте пути к файлам в своих программах!
Результаты работы программы проверяются автоматически по тестам и ответам к ним, поэтому программа должна точно соблюдать формат ввода и вывода, указанный в условии.
Если Вы работаете в проводнике и не видите расширения файлов, то снимите галочку в меню Сервис – Свойства папки – Вид – Дополнительные параметры – Скрывать расширения для зарегистрированных типов файлов (для Windows 7 меню появляется при нажатии на клавишу alt).
Гарантируется, что входные файлы будут соответствовать формату, указанному в условии.
Ввод с клавиатуры и вывод на экран строго запрещен.
Во всех задачах будет указано максимальное время работы на одном тесте. Программа, превысившая допустимый предел времени работы прерывается. Во всех задачах будет указан максимальный размер доступной памяти. Программа, превысившая допустимый предел памяти прерывается.
Жюри не рекомендует использовать во время олимпиады среду программирования Pascal ABC. Если Вы, однако, с разрешения организатора, воспользовались этой средой, то, как минимум, не используйте функции strtoint и inttostr.
Программа не должна:
· использовать расширенную память и защищенный режим процессора при использовании 16-битных компиляторов;
· осуществлять чтение и запись векторов прерываний;
· осуществлять любой ввод/вывод, кроме открытия, закрытия, чтения и записи файлов, указанных в условии задачи, в том числе программа не должна создавать подкаталоги, изменять текущий каталог и осуществлять ввод/вывод через порты;
· осуществлять запуск других программ и создавать новые процессы;
· создавать или работать с любыми GUI объектами (окнами, диалогами и т.д.);
· работать с внешними устройствами (принтером, сканером и т.д.);
· иметь код завершения, отличный от нулевого.
Пример программы, которая считывает из входного файла “sum.in” два числа и выводит в выходной файл “sum.out” сумму этих чисел.
| Pascal | C++ |
| Program Summa; Const InFile = ‘sum.in’; OutFile = ‘sum.out’; Var A, B : LongInt; Begin Assign(InPut, InFile); ReSet(InPut); Assign(OutPut, OutFile); ReWrite(OutPut); Read(A, B); Write(A + B); Close(Output); End. | #include <vector> #include <string> #include <algorithm> #include <iostream> #include <fstream> #include <sstream> #include <cmath> using namespace std; int main() { ifstream infile ("sum.in"); ofstream outfile ("sum.out"); long a, b; infile >> a >> b; outfile << a + b; return 0; } |
Задача 1. Олимпиада MCA. 100 баллов.
| Входной файл | test.in |
| Выходной файл | test.out |
| Ограничение по времени | 1 секунда на тест |
| Ограничение по памяти | 16 мегабайт |
Всякому известен регламент ACM, по этому регламенту проходит Всероссийская командная олимпиада школьников по программированию и информатике. Менее известен альтернативный регламент MCA. Согласно этому регламенту каждая задача оценивается определённым количеством баллов. Правильно решённая задача даёт команде именно столько баллов. Выигрывает команда, набравшая наибольшее количество баллов. Если две или более команд набирают одинаковое количество баллов, то выигрывает команда, решившая наименьшее количество задач. Если и таких команд оказывается несколько, то выигрывает команда, имеющая наименьшее количество попыток сдать задачи (как успешных, так и безуспешных). Если по-прежнему победитель не определился, то выигрывает команда с наименьшим номером. Ваша задача - по итогам MCA турнира составить итоговую таблицу.
Формат входного файла.
В первой строке входного файла содержатся два целых числа T - количество команд и P - количество задач (1 T 10, 1 P 10). Команды пронумерованы от 1 до T, задачи названы первыми P заглавными буквами латинского алфавита. Во второй строке записаны P целых чисел из отрезка [1,100] - количество баллов, которым оценены задачи. Третья строка содержит одно целое число S (1 S 200) - суммарное количество сдач за время турнира. В следующих S строках записаны результаты сдач в формате
lt;номер команды> <код задачи> A|R
буква A (Accepted) означает, что задача принята, буква R (Rejected) означает, что задача не принята. Данные в этих строках разделены ровно одним пробелом.
Формат выходного файла.
Запишите в выходной файл итоговую таблицу турнира. Таблица должна занимать T строк, в каждой из которых должен быть записан номер команды и набранное командой количество баллов.
Примеры файлов входных и выходных данных:
| test.in | test.out | test.in | test.out | |
| 2 2 5 10 1 A A 2 B A | 2 10 1 5 | 2 2 5 10 1 B A 2 B A 1 A R | 2 10 1 10 | |
| test.in | test.out | test.in | test.out | |
| 3 3 5 5 5 1 A A 1 B R 2 B A 2 C R 3 C A | 3 5 1 5 2 5 | 2 3 5 5 10 1 A A 1 B A 2 C A | 2 10 1 10 |
Задача 2. Таблица для первого класса. 100 баллов.
| Входной файл | add.in |
| Выходной файл | add.out |
| Ограничение по времени | 1 секунда на тест |
| Ограничение по памяти | 16 мегабайт |
У Дениса есть маленький брат Миша, который только что пошел в школу в первый класс. Миша на уроках чтения изучил все буквы и научился читать. На уроке математики Миша научился считать. Учительница Миши при изучении арифметики использует так называемые таблицы сложения. Миша получает, например, такую таблицу:
Дома Миша должен заполнить пустые ячейки, записав туда сумму числа, записанного в первом столбце данной строки, и числа, записанного в первой строке данного столбца. То есть, если Миша правильно все сделает, то он должен получить такую таблицу:
Дениса заинтересовала эта задача и он решил написать программу, которая по известной таблице восстанавливает первую строку и первый столбец
Ваша задача более простая, проверить, является ли квадратная таблица размером N на N таблицей сложения.
Формат входного файла.
В первой строке входного файла записано число N (1 N 1000). Затем построчно записана таблица размером N. Числа в таблице по модулю не превосходят 10000.
Формат выходного файла.
Если таблица из входного файла является таблицей сложения, запишите в выходной файл слово "YES", в противном случае запишите в выходной файл слово "NO".
Примеры файлов входных и выходных данных:
| add.in | add.out |
| 4 -1 6 7 2 9 1 -4 3 | YES |
| add.in | add.out |
| 1 4 3 5 | NO |
| add.in | add.out |
| 3 6 2 5 | YES |
Напоминаем, что Жюри олимпиады вправе запустить Вашу программу на одних и тех же тестах несколько раз и выбрать худший результат.
Задача 3. Задача младшего брата. 100 баллов.
| Входной файл | number.in |
| Выходной файл | number.out |
| Ограничение по времени | 1 секунда на тест |
| Ограничение по памяти | 16 мегабайт |
Миша на математике изучил тему многозначные числа. И теперь он придумывает различные числа, обладающие каким–либо свойством, и производит с ними различные манипуляции. Недавно он придумал «двухцифровые числа». Денис заинтересовался математическими опытами младшего брата и, немного модернизировав задачу, предложил своему учителю задачу для кружка «Буки информатики». Натуральное число назовем двояким, если в его десятичной записи встречается не более двух различных цифр. Например, числа 1, 22, 30303 двоякие, а число 453 – нет. Ваша задача – найти ближайшее к заданному числу N двоякое число. Если таких чисел два, выберите меньшее из них.
Формат входного файла.
Во входном файле записано натуральное число N <= 30000.
Формат выходного файла.
Запишите в выходной файл найденное двоякое число.
Примеры файлов входных и выходных данных:
| number.in | number.out |
| number.in | number.out |
| number.in | number.out |
Задача 4. Наибольший квадрат. 100 баллов.
| Входной файл | sqr.in |
| Выходной файл | sqr.out |
| Ограничение по времени | 1 секунда на тест |
| Ограничение по памяти | 16 мегабайт |
Денис очень любит математику и считает ее самым важным предметом в школе. На уроке биологии Денис начертил прямоугольник размером n на m клеток, пронумеровал его по строкам и столбцам. И случайным образом заполнил все клетки нулями и единицами. Далее Денис искал «максимально получившийся» квадрат, состоящий только из цифр 1.
Ваша задача в таблице c N строками и M столбцами, состоящей из 0 и 1 найти левый верхний угол квадратного блока максимального размера, состоящего только из единиц. Если таких квадратов несколько, то следует выбрать самый верхний. Если в одной строке «начинаются» несколько квадратов одинаково максимального размера, то следует выбрать наименьший столбец. Например, если квадраты одинакового размера начинаются в точках (2, 20) и (20, 2), то в ответ следует написать 2 20.
Формат входного файла.
В первой строке входного файла через пробел записано два натуральных числа N и M (N,M<= 1000).
Далее записано N строк по M чисел разделенных пробелами.
Формат выходного файла.
В выходной файл вывести координаты левого верхнего угла квадрата наибольшего размера.
Примеры файлов входных и выходных данных:
| sqr.in | Sqr.out |
| 3 3 0 1 1 1 1 1 0 1 0 | 1 2 |
Задача 5. Архиватор. 100 баллов.
| Входной файл | arh.in |
| Выходной файл | arh.out |
| Ограничение по времени | 1 секунда на тест |
| Ограничение по памяти | 16 мегабайт |
Денис очень хочет занять свое место в программировании. С недавних пор он увлекся архивированием файлов, и даже написал свой архиватор, который архивирует пока только текстовые файлы. Архивировать Денис может пока только английские тексты из заглавных букв. Кроме букв архиватор распознает и работает с символами «пробел» - 27ой символ в кодовой таблице и символ «запятая» - 28ой символ в кодовой таблице. Суть алгоритма сжатия файлов заключается в следующем:
1. для архивирования каждой строки создается временно нулевой двухмерный массив из n строк и 28 столбцов.
2. При чтении текстового файла в первую строку массива, обозначающую номер символа в предложении, в столбце соответствующем номеру буквы в алфавите записывается 1.
3. Далее во второй строке массива появляется 1 в столбце, соответствующем номеру второго символа предложения в алфавите (в кодовой таблице) и т д.
При окончании предложения архиватор, переводит, начиная с последних строк, последовательности из n нулей и единиц (снизу вверх), как числа, из двоичной системы в десятичную и записывает по порядку в двумерный массив десятичные числа. Количество строк в полученном массиве соответствует количеству предложений. А количество столбцов 28. Полученный массив представляет собой содержимое Денисова архива.
Ваша задача - написать программу, которая будет распаковывать Денисовы архивы.
Формат входного файла.
В первой строке файла arh.in записано одно число n (0<n<10) - число предложений в архивном файле.
В последующих n строках записано по 28 чисел, разделенных пробелами.
Гарантировано что число букв в предложении не превышает 30. В конце каждого предложения необходимо добавлять точку.
Формат выходного файла.
Восстановленный текст.
Примеры файлов входных и выходных данных:
| arh.in | arh.out |
| 0 0 0 0 16416 0 0 8192 1 0 0 4 1152 0 2056 0 0 32768 0 4096 0 16 0 0 256 0 578 0 | I LOVE MY MOTHER. |
| arh.in | arh.out |
| 0 0 0 0 2 0 0 1 0 0 0 12 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | HELLO. |
В первом примере числа не поместились на бумаге в одну строку. В файле это одна строка.