Задача \"Золотой песок\" icon

Задача "Золотой песок"



НазваниеЗадача "Золотой песок"
Дата конвертации21.04.2013
Размер96.38 Kb.
ТипЗадача


Задача 1. "Золотой песок"

Имеется три вида золотого песка различной стоимости. Один килограмм песка первого вида стоит А1 рублей, второго вида - А2 рублей, а третьего - A3 рублей. Требуется заполнить этими видами песка три емкости, вмещающими B1, B2 и B3 килограммов золотого песка так, чтобы выполнялись условия:

  • в одной емкости может содержаться только один вид золотого песка;

  • емкости заполняются полностью;

  • суммарная стоимость золотого песка в емкостях максимальна.

Разработать программу, вычисляющую максимальную стоимость золотого песка в емкостях.

Технические требования:

Имя входного файла: INPUT.TXT

Имя выходного файла: OUTPUT.TXT

Ограничение по времени тестирования: 1 секунда на один тест.

Формат входных данных:

Входной файл INPUT.TXT содержит 6 натуральных чисел А1, А2, А3, B1, B2, B3, записанных в одной строке через пробел. Все числа не превосходят 200.

Формат выходных данных:

Выходной файл OUTPUT.TXT должен содержать единственное целое число – стоимость золотого песка в трех емкостях в рублях.

Примеры файлов входных и выходных данных:

INPUT.TXT

OUTPUT.TXT

1 2 3 3 2 1

14

Максимальная оценка – 10 баллов


Задача 2. "Расшифровка"

Компания по защите интеллектуальной собственности решила повысить уровень защищенности своих операционных систем путем шифрования всех сообщений, передаваемых внутри ее локальных сетей. Любое допустимое в компании сообщение представляет собой строку S = s1s2...sn, состоящую из любых символов. Шифрование сообщения осуществляется в К фаз. На каждой фазе строка S заменяется строкой, в которой сначала располагаются все символы строки S, стоящие на позициях с номерами, являющимися простыми числами (первый блок), а затем – все остальные символы (второй блок). Напомним, что число называется простым, если оно - натуральное и имеет ровно два натуральных делителя. Относительный порядок символов в каждом из двух блоков остается неизменным. Например, строка S = abcdefgh на первой фазе шифруется в строку S = bcegadfh. Если осуществляется вторая фаза шифрования, то строка S примет вид S = ceafbgdh. После передачи зашифрованного сообщения по сети оно должно быть дешифровано, чтобы получатель смог прочитать исходную запись.

Требуется написать программу, осуществляющую дешифрование заданной строки, являющейся результатом шифрования строки S после К фаз.

^ Технические требования:

Имя входного файла: INPUT.TXT

Имя выходного файла: OUTPUT.TXT

Ограничение по времени тестирования: 1 секунда на один тест.

Формат входных данных:

В первой строке входного файла INPUT.TXT содержит натуральные числа n и К (1<100), разделенные пробелом. Вторая строка содержит сообщение S после К фаз шифрования, состоящее из n символов.

Формат выходных данных:

Выходной файл OUTPUT.TXT содержит только одну дешифрованную строку S.

Примеры файлов входных и выходных данных:

INPUT.TXT

OUTPUT.TXT

^ 8 2

CEaFBGdH

aBCdEFGH

13 1

рие,с!Пвт Вая

Привет, Вася!

Максимальная оценка – 25 баллов


Задача 3. "Многозадачность"

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

Поскольку на переключение с одного процесса на другой тратится время, используют установку параметра К-максимального времени ожидания процессом очередного кванта времени своей работы. В этом случае возможны различные варианты исполнения процессов.

П
^ АААВВВ

ААВАВВ


ААВВАВ

АВААВВ

АВАВАВ

АВВААВ

усть должны исполняться два процесса - А и В, каждый из которых требует N единиц времени для своего завершения. В первый квант времени начинает исполняться процесс А, а в последний квант времени завершается исполнение процесса В. Никакой процесс не должен ожидать начала продолжения своей работы более К единиц времени. Например, для N = 3 и К = 3 существует 6 таких возможных расписаний выполнения процессов (см. рисунок слева). Если же К = 2, то таких расписаний будет 5, так как расписание АААВВВ станет недопустимым.

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

Технические требования:

Ввод N и K – с клавиатуры (1 < N,K< 11); вывод количества расписаний – на экран монитора.

Ограничение по времени тестирования: 5 секунд на каждый тест

Максимальная оценка: 30 баллов.

Задача 4. "Дорога из школы"

Город нефтяников состоит из N пронумерованных площадей, некоторые пары которых соединены улицами. Не существует такой улицы, которая соединяет площадь саму с собой. По любой улице можно двигаться в двух направлениях, между любой парой площадей существует не более одной улицы.

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

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

Технические требования:

Имя входного файла: INPUT.TXT; имя выходного файла: OUTPUT.TXT

Ограничение по времени тестирования: 2 секунды на один тест.

Формат входных данных:

В первой строке входного файла INPUT.TXT записаны три целых числа - N, М, К (1
Формат выходных данных:

В выходной файл OUTPUT.TXT необходимо вывести наибольшее расстояние, которое одноклассники смогут пройти вместе от школы по пути к своим домам.

Примеры файлов входных и выходных данных:

Пример 1

Пример 2

^ INPUT. TXT

OUTPUT. TXT

INPUT. TXT

OUTPUT. TXT

4 5 2

2 3

1 4 1

4 2 1

4 3 1

1 2 2

1 3 2

1

4 5 2

2 3

1 4 1

4 2 1

4 3 1

1 2 1

1 3 1

0

Максимальная оценка – 35 баллов.

Задача 5. Максимальное число

Задано натуральное число N, состоящее из k цифр и целое число M (0M
Технические требования:

  • исходные данные хранятся в текстовом файле INPUT.TXT;

  • решение задачи сохранить в текстовом файле OUTPUT.TXT;

  • время тестирования задачи – 1 сек.

Формат входных данных

Входной файл INPUT.TXT содержит две строки:

  • первая – число M;

  • вторая – число N (длиной 2k250 цифр).

Формат выходных данных

Выходной файл OUTPUT.TXT содержит одну строку, в которой перечислены через пробел M номеров удаленных цифр.

Пример файлов входных и выходных данных:

INPUT.TXT

OUTPUT.ТХТ

3

275691

1 3 4

Максимальная оценка: 20 баллов.

Задача 6. "Корпорация"

С
труктура некоторой корпорации такова, что каждый служащий, кроме служащих нижнего звена, является непосредственным начальником не менее чем одного другого служащего (возможно, служащего нижнего звена). Во главе компании стоит Президент, которому подчиняются либо непосредственно, либо по должностной иерархии все остальные служащие. Каждый служащий (разумеется, кроме Президента) имеет одного непосредственного начальника. Все служащие в этой структуре имеют индивидуальные номера от 1 до N (2 < N < 10000). Пример описания такой структуры приведен на рисунке, где сотрудник с номером 3 является Президентом и непосредственным начальником сотрудников с номерами 1 и 4, а сотрудник с номером 4 является непосредственным начальником сотрудника с номером 2. Структура корпорации является корпоративной тайной и строго охраняется.

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

Требуется написать программу, которая по сведениям, доступным на сайте, восстанавливает структуру корпорации.

Технические требования:

Имя входного файла: INPUT.ТХТ; имя выходного файла: OUTPUT.ТХТ

Ограничение по времени тестирования: 1 секунда на один тест.

Формат входных данных:

Во входном файле INPUT.TXT на одной строке содержится последовательность чисел, определяющая все пути следования писем от Президента до каждого служащего нижнего звена. Каждый путь описывается соответствующими номерами служащих, разделенных пробелами. Например, для приведенной на рисунке структуры таких путей будет два: 3-4-2 и 3-1. Пути в последовательности указываются в произвольном порядке.

Формат выходных данных:

Выходной файл OUTPUT.TXT должен содержать N строк. В каждой i-ой строке (1 < i < N) должны располагаться в порядке увеличения номеров все номера служащих, непосредственно подчиненных i-му служащему. Все числа в строке разделены пробелом. Последним в каждой строке должно быть число 0. Если решений несколько, необходимо вывести любое. (Продолжение задачи 6 см. на следующей странице).


Пример файлов входных и выходных данных:

INPUT.TXT

OUTPUT.ТХТ

3 4 2 3 1

0

0

1 4 0

2 0

Максимальная оценка – 35 баллов.

Задача 7. Соты

П
челиная семья строит соты по следующему алгоритму: сначала строится центральная ячейка; затем вокруг нее пчелы строят первый слой ячеек, вокруг первого – второй и т.д. Для более эффективного строительства и обслуживания сот все ячейки последовательно пронумерованы, начиная от центральной, и, далее, по слоям (по часовой стрелке). На рисунке показаны соты с тремя слоями. Нумерация слоя начинается с ячейки, расположенной непосредственно под начальной ячейкой или под последней пронумерованной ячейкой предыдущего слоя (на рисунке это ячейки 2, 8 и 20). При обслуживании сот пчелы могут перемещаться в соседнюю ячейку только через одну из шести граней текущей ячейки.

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

Технические требования

  • Входной файл – INPUT.TXT; выходной файл: OUTPUT.TXT

  • Ограничение по времени тестирования: 2 секунды на один тест.

Формат входных данных:

Файл INPUT.TXT содержит одну строку с тремя целыми числами N, B, F, разделенными пробелами, где N – число слоев вокруг центральной ячейки (1 ≤ N ≤ 1000); В – номер начальной ячейки; F – номер конечной ячейки.

Формат выходных данных:

Файл OUTPUT.TXT имеет следующий формат:

- первая строка – целое число L, содержащее длину маршрута;

- вторая строка – L номеров ячеек, образующих кратчайший маршрут, разделенных пробелами.

Пример файлов входных и выходных данных:

INPUT.TXT

OUTPUT.TXT

3 14 20

6

14 5 6 7 8 20

Максимальная оценка решения: 45 баллов



Похожие:

Задача \"Золотой песок\" iconИгротека для младших школьников
Песок''. Предложить детям набрать в руки воображаемый песок /на вдохе/, сильно сжав пальцы в кулак, удержать песок /задержка дыхания/,...
Задача \"Золотой песок\" iconПрограмма «Золотой ключик» решает следующие задачи
Деятельность педагогического коллектива и уникальность программы «Золотой ключик» в 2007 году отмечена в «Золотой книге Красноярского...
Задача \"Золотой песок\" iconЗадерживает появление водорослей на 3-4 недели
Обычно на дно бассейна кладут плодородную гумусовую почву (10-30 см), на который насыпаем песок 3-4 см и сверху тонкий слой гравия....
Задача \"Золотой песок\" iconОбзор применяемых в мире систем заканчивания для предотвращения пескопроявления
Этот песок содержит до 5 нефти, и при его удалении возникают проблемы — загрязняется окружающая среда; песок отлагается в трубопроводах,...
Задача \"Золотой песок\" iconЗадача 1 задача 2 задача 3 задача 4 задача 5
Вычислить момент инерции твёрдого тела y(x) при х изменяющемся от a и b. Построить график этой функциональной зависимости на интервале...
Задача \"Золотой песок\" iconОглавление Задача №1 стр Задача №2 стр Задача №3 стр Задача №4 стр Задача №5 стр
Даны действительные числа X, y. Определить, принадлежит ли точка с координатами (X, y) заштрихованной области
Задача \"Золотой песок\" iconЗадача №1 Задача №2 Задача №3 Задача №4 Задача №5
Число оборотов двигателя зависит от температуры x. Вычислить число оборотов двигателя y(x) при температуре a и b. Построить график...
Задача \"Золотой песок\" iconЗадача №1 задача №2 задача №3 задача №4 задача №5
Число оборотов двигателя y функционально зависит от температуры x. Вычислить число оборотов двигателя y(x) при температуре a и b....
Задача \"Золотой песок\" iconЛабораторная работа по информатике Excel студентка гр. Экл-31 Ковалева Диана Оглавление Задача №1 Задача №2 Задача №3

Задача \"Золотой песок\" iconТема 13. Деконволюция цифровых сигналов если дом красив, то мы понимаем, что он был выстроен для хозяев, а не для мышей
Деконволюция сходна с археологией. Задача – восстановить дом из развалин. Обнадеживает, если обломки на месте. Но если только песок,...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib.podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы