2009 г. Теоретическая часть icon

2009 г. Теоретическая часть




Скачати 43.39 Kb.
Назва2009 г. Теоретическая часть
Дата конвертації29.11.2012
Розмір43.39 Kb.
ТипДокументи
1. /Семинар_16_11_2010/Винница2009/Solution_1.docx
2. /Семинар_16_11_2010/Сайты подготовки.docx
3. /Семинар_16_11_2010/Ярославль2009/Теоретическая часть.doc
4. /Семинар_16_11_2010/Ярославль2009/Условие.doc
Задания и решения1-го тура Netoi-2009
Олимпиады по программированию, г. Москва Олимпиады в области точных наук, г. Санкт-Петербург Олимпиады по информатике, г. Санкт-Петербург
2. Обмануть обманщика
2009 г. Теоретическая часть

2009 г.

Теоретическая часть

1. Алгоритм

Что делает данный алгоритм?

алгоритм ДУМА(целые: n,k)

начало алгоритма

n:=0

i:=0

цикл:пока i < k выполнить:

n:=n + 2*i + 1

i:=i+1

конец цикла

конец алгоритма

Ответ обосновать. (Предполагается, что на вход алгоритма подаются два целых числа – n и k. Считать, что переменная i является целочисленной.)


2. Обмануть обманщика

Коля загадал натуральное число от 1 до 30, а Петя пытается угадать его. Для этого Петя задает Коле несколько вопросов, на каждый из которых возможен ответ либо «да», либо «нет». После того, как заданы все вопросы, Петя должен назвать загаданное число. Однако при ответах на вопросы Коле разрешается не более одного раза солгать, то есть на один из задаваемых вопросов (конечно же, не указывая, на какой именно по счету) разрешается дать противоположный ответ. За какое наименьшее количество вопросов и каким именно образом Петя сможет гарантированно определить загаданное Колей число?


3.Зазеркалье

Имеется множество из N точек плоскости (указаны их координаты). Опишите алгоритм, проверяющий, является ли это множество точек центрально-симметричным.


4. Коллективный разум

Подземелье замка Черного Властелина представляет собой квадрат 4x4, ячейками которого являются 16 комнат. В каждой комнате-ячейке в заточении сидит добрый волшебник. Каждый из них знает одну часть заклинания (причем каждый свою), но выбраться из подземелья волшебники могут только тогда, когда каждый из них будет знать все 16 частей заклинания. За один день волшебник может либо сообщить в соседнюю (за стеной) комнату все части заклинания, которые знает на данный момент, либо получить от одного из своих соседей (через стенку) известные тому части заклинания. За какое количество дней и каким образом все волшебники смогут получить все части заклинания?

5. Чудо инженерной мысли

На плоскости собрали некий механизм, состоящий из шестеренок с одинаковым шагом (т.е. расстоянием между соседними зубьями). Все шестеренки пронумерованы и для каждой из них известны номера шестеренок, с которыми она зацеплена. Описать алгоритм, определяющий, можно ли привести весь механизм в движение, вращая какую-нибудь из шестеренок.


6. Нить Ариадны

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


Практическая часть

Программы будут проверены на комплекте тестов в полуавтоматическом режиме (внимательно следите за форматами выходных файлов: несоответствие формата выходного файла может привести к тому, что результат прохождения теста не будет засчитан).

Входные данные берутся из текстового файла input.txt, результат выполнения программы выводится в файл output.txt в установленном формате.

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


1. Проще простого

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

Вход:файл input.txt, в котором записано единственное число N

Ограничения: 1
Выход: файл output.txt, содержащий единственное число (минимальное количество групп)

Пример:

input.txt

output.txt

18

3

Примечание к примеру: числа от 1 до 18 можно разбить на три группы с нужным свойством (например, 1+3+4+5+6+18, 2+7+8+9+10+11+12+13+14+17 и 15+16 с суммами 103, 37 и 31), на меньшее число групп, как легко показать, нельзя.


2. Острова

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

Вход: файл input.txt, имеющий следующую структуру: в первой строке входного файла записано число N – количество островов в архипелаге. Далее идет N строк с описанием островов. В каждой строке описывается один остров, который задаётся числом вершин (первое число строки) и далее их координатами в порядке обхода по часовой стрелке (у каждой вершины первой идет абсцисса, а второй - ордината). Координаты внутри строки разделяются пробелами.

Ограничения: число N – натуральное от 2 до 50 (включительно), для каждого острова число вершин не превосходит 20, все координаты – целые числа, не превосходящие по модулю 30000.

Выход: файл output.txt, содержащий два числа (по одному в строке), первая строка ¬- число: количество мостов; второе строка - число: суммарная длина мостов с точностью до 0.001


Примеры:

Пример 1.

Пример 2.

Входной файл input.txt содержит:
2
4 –2 –2 –2 2 2 2 2 –2

3 3 –2 3 2 6 0

Результат (файл output.txt):
1
1

Входной файл input.txt содержит:
3
4 –2 –2 –2 2 2 2 2 –2

3 -3 0 –5 –1 –5 1

3 6 –5 8 –4 8 -5

Результат (файл output.txt):
2
6


3. Шифр Цезаря

Некоторый русский текст, хранящийся в файле, зашифрован следующим образом: каждая буква текста циклически сдвигается на одно и тоже количество символов, а все остальные символы (знаки препинания и пробелы) остаются неизменными. При шифровке большие буквы переходят в большие, а маленькие в маленькие. Будем для простоты считать, что русский алфавит состоит из 32 букв (за буквой «е» следует буква «ж»). Требуется написать программу автоматической расшифровки текста.

Вход: файл input.txt c зашифрованным текстом.

Ограничения: длина текста не превосходит 250 символов.

Выход: Файл output.txt с расшифрованным текстом.

Пример:

input.txt

output.txt

А сбвпубя, оп а фтубм

Я работаю, но я устал

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




Схожі:

2009 г. Теоретическая часть iconКонтрольная работа по дисциплине «Web-дизайн» теоретическая часть (варианты вопросов)
В контрольной должны быть ответы на 2 вопроса. Первый – по списку в журнале, второй – по списку + 10 (пример: 1 и 10)
2009 г. Теоретическая часть iconВопросы для модуля №2 Теоретическая часть
Объект преступления. Классификация объектов. Соотношение предмета и объекта преступления. Потерпевший как факультативный признак...
2009 г. Теоретическая часть iconЗадача №6. Расчет фаршемешалки теоретическая часть
В верхней части его имеются отверстие для подачи подлежащего обработке продукта и загрузочная воронка. Изнутри к стенкам загрузочной...
2009 г. Теоретическая часть iconЗадания к контрольной работе по дисциплине «Экономический анализ»
Теоретическая часть контрольной работы излагается в виде системы теоретических положений, связанных логической последовательностью....
2009 г. Теоретическая часть iconЗадача №4. Расчет картофелеочистительной машины периодического действия теоретическая часть
С нижней стороны конус имеет кольцевой выступ для предотвращения попадания отходов к вращающемуся валу и две вертикальные лопасти...
2009 г. Теоретическая часть iconЗадача расчет посудомоечной машины непрерывного действия теоретическая часть
Мму-2000 (рис. 2) – конвейерная, туннельного типа. Она осуществляет следующие технологические операции: струйную очистку посуды от...
2009 г. Теоретическая часть iconКонспект лекций В. А. Ерофеева, В. А. Пискунов, Т. А. Битюкова
Гк – Гражданский кодекс Российской Федерации: часть первая от 30. 11. 1994 №51-фз; часть вторая от 26. 01. 1996 №14-фз
2009 г. Теоретическая часть iconДокументи
1. /Теоретическая магия.txt
2009 г. Теоретическая часть iconКнига на сайте: Сканирование и распознавание текста: сайт «Ирпенская буквица» 'Часть I
Издание: Н. И. Околитенко, Н. Д. Колбун. Вич в свете законов природы: альтернативный взгляд. Киев, 2009, «Літопис-хх»
2009 г. Теоретическая часть iconКнига на сайте: Сканирование и распознавание текста: сайт «Ирпенская буквица» 78 Часть II басня о пустыннике и Медведе
Издание: Н. И. Околитенко, Н. Д. Колбун. Вич в свете законов природы: альтернативный взгляд. Киев, 2009, «Літопис-хх»
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи