Алтайский государственный технический университет им. И.И. Ползунова

      2000

Задача 1. "Фибина заначка" 60 баллов

Жил да был бухгалтер по имени Фиба со стажем работы N лет. Честный был да грамотный. Грамотный - потому что знал, что если не воровать, то заподозрят, что скрывается от честного народа, а сам загребает несчитано-немерено. А честный - потому что воровал немного, каждый год по K условных единиц.

А в той стране, где он жил, была инфляция. Поэтому деньги и измеряли в условных единицах. Ну и Фиба, стало быть, доход свой нелегальный с точки зрения никому не нужного закона так же измерял. Хорошо жил Фиба, хорошо да долго, - дай Бог каждому! А Бог, кстати, не жадный, - только питаться надо правильно да спортом заниматься. Глядишь, и проживешь лет триста - четыреста. А как пришла к Фибе старость, решил он свою заначку потратить. Долго думал, как, да и решил: "Куплю мерс шестисотый да проеду по всей стране, посмотрю, как люди живут!" Пришел в фирму, а там прайс-лист не имеет графы "условные единицы", - только одни безусловные цены и есть. А Фиба, надо сказать, шибко был грамотный мужик по компьютерной части. Попросил он у парней в фирме разрешения посидеть за компьютером полчаса, да и написал программу, которая перевела его заначку в безусловные единицы. Другой бы, небось, и не справился бы, но Фиба-то давно подметил, что инфляция у него на родине растет по тому же закону, что и числа Фибоначчи у математиков:

1, 1, 2, 3, 5, 8, 13, ...

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

Исходная информация.

Файл input.txt содержит два целых числа K и N; K < 2000, N< 400. K - ежегодно уворованное Фибой количество условных единиц, N - число лет.

Результирующая информация.

Целое число - результат работы программы, написанной Фибой.

Задача 2. "Музейный вор" 30 баллов

Система охраны знаменитого на весь город Барнаул музея использует лазерные лучи в детекторах движения. Лучи направлены таким образом, что образуют выпуклый многоугольник. Темной ночью вор прокрался в музей, чтобы украсть бесценный клинок Мухаммеда. Он смог добраться до клинка, перешагивая через лучи. Но, выходя с клинком обратно, случайно уронил его.

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

Исходная информация.

Файл input.txt содержит: N - кол-во точек пересечения лучей (целое число 0..30),

L - длина клинка (целое число, не превышающее 64000),остальные N строк содержат целые координаты x и y точек пересечения лучей, разделенные пробелами. Значение каждой координаты не превышает по модулю 64000.

Результирующая информация.

Файл output.txt содержит число 1 или 0. Число 1 означает, что клинок может упасть так, что не сработает сигнализация . Число 0 означает, что такая ситуация невозможна.

Задача 3 "Крестики - нолики" 20 баллов

Компания TinyWare разрабатывает компьютерные игры. Одна ее из последних разработок - игра "крестики - нолики". Вы, как один из работников компании, тоже участвуете в проекте. Ваша задача - разработать программу, которая по заданной последовательности ходов определяет победителя.

Исходная информация.

Входные данные находятся в файле input.txt. каждая строка этого файласодержит два целых числа, изменяющихся в пределах от 0 до 2 - координаты очередного хода.Ходить всегда начинают "крестики" и игра идет либо до победы, либо до заполнения всего игрового поля.

Результирующая информация.

Выход: текст "Победили крестики", "Победили нолики", "Ничья"

Задача 4. "Проблема на заводе" 70 баллов

На заводе по производству телевизоров “Сигнал” закупили новое оборудование по производству коробок для телевизоров. В это оборудование входит машина для высечки из больших листов картона разверток для дальнейшего производства коробок. Но т.к. руководство завода “Сигналхотело сэкономить деньги, то оборудование было китайского производства и, вследствие этого, инструкция по эксплуатации машины тоже была на китайском языке. А на заводе, как ни странно, не оказалось специалиста по китайскому языку и пришлось разбираться с машиной методом “научного тыка”. Это привело к тому, что с конвейера стали сходить развертки произвольной формы, т.е. получались такие развертки, которые потом нельзя было бы свернуть в коробку.

Пример разверток, которые высекла машина:

           
           
           
           
           
           

а)

           
           
           
           
           
           

б)

           
           
           
           
           
           

в)

Очевидно, что первая развертка правильная, а вторая и третья - нет.

Ваша задача, помочь работникам завода разобраться, какая развертка правильная, а какая - нет.

Примечание: Развертка состоит из квадратов, т.е. коробка должна быть кубом. А также помните, что руководство завода “Сигнал” купила эту машину, для того, чтобы сэкономить деньги, и поэтому лишних отходов быть не должно, т.е. ничего лишнего, кроме требуемой развертки, машина не должна вырезать. Именно по этой причине развертка, приведенная на втором рисунке, является неправильной.

Исходная информация.

Входные данные в файле “input.txt”:

Файл состоит из шести строк по шесть символов, после шести символов идет перевод строки.

Встречающиеся символы: “.” и “*” соответствуют свободной и заятой клетке.

Результирующая информация.

Выходные данные в файле “output.txt”:

Выходной файл должен содержать: “Yes.” - т.е. развертка правильная; “No.” - т.е. развертка не правильная.

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

Input.txt:

.*....

***...

.*....

.*....

......

......

Output.txt:

Yes.

Input.txt:

..*...

.***..

..*...

..*...

..*...

......

Output.txt:

No.

Input.txt:

.....*

...*.*

...***

......

......

.**...

Output.txt:

No.

Задача 5. "Мышонок, который любил гулять" 100 баллов

Жил был мышонок, который очень любил гулять в новогоднюю ночь. Но, как известно, в новогоднюю ночь очень холодно и по этой причине мышонок все лето заготавливал хворост по всему полю. Потом на новый год он гулял и, когда замерзал, то он доходил до кучки хвороста, зажигал костер и грелся. Так должно было быть и в новогоднюю ночь 1999 года. Но, к сожалению, в эту ночь был очень сильный мороз, а пропускать начало 2000 года не хотелось. Поэтому мышонок решил прогуляться так, чтобы только обойти все кучки хвороста и вернуться в норку. Это стало возможно благодаря тому, что у мышонка была отменная память, и он точно помнил места, где он заготавливал хворост. Но вот в какой последовательности нужно обходить будущие костры, он не знал. Помогите мышонку прогуляться. Но помните, что очень холодно и мышонок должен пройти минимально расстояние, иначе он замерзнет. И т.к. он каждый раз сжигал весь хворост, то он не может дважды возвращаться к одному месту.

Исходная информация.

Входные данные в файле “input.txt”:

Файл состоит из целых положительных чисел.

Первое число в этом файле задает n – число точек, через которые должен пройти мышонок ( это норка и n-1 кучек хвороста ).

Далее следует n пар чисел, задающих координаты X и Y этих точек.

Координаты первой точки - это координаты норки. Следующие n-1 координат (x,y) - это координаты кучек хвороста.

Мышонок начинает прогулку из норки и там же должен ее закончить.

Результирующая информация.

Выходные данные в файле “output.txt”:

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

Пример:

Input.txt:

2

2 2

1 3

Input.txt:

3

2 2

1 3

3 4

Input.txt:

3

1 3

2 2

1 4

Output.txt:

1 2

Output.txt:

1 2 3

Output.txt:

1 2 3

 

Задача 6. "Новые разработки НАТО" 120 баллов

Военные конструкторы НАТО разработали новый цифровой детектор движения. Его особенностью является то, что он имеет две независимых полосы детектирования (угла). Солдаты, которые пользуются этим прибором, хотят знать, какой суммарный (непрерывный) угол охватывает детектор. С этой целью в приборе установлена Flush микросхема памяти для программы, которая вычисляла бы суммарно охватываемый угол. Ваша задача состоит в разработке программного обеспечения для этого прибора. Заметьте, что если суммарный угол получается из двух частей, т.е. углы не пересекаются, то возможно скрытое проникновение противника, и в этом случае программа должна сказать: “ВНИМАНИЕ! Есть слепая зона!”. Если суммарный угол 360° или больше, Ваша программа должна сказать: “Полная безопасность!”.

Исходная информация.

Входные данные в файле “input.txt”. Файл состоит из 4-х целых чисел от -360 до 360.

Первые два числа задают первый угол. Вторые два числа задают второй угол.

1-ое число каждой пары задает начальный луч в градусах, а 2-ое – смещение конечного луча относительно начального в градусах.

Результирующая информация.

Выходные данные в файле “output.txt”:

Файл должен содержать, либо два целых числа от 0 до 360, либо одну их строк:

“ВНИМАНИЕ! Есть слепая зона!” или “Полная безопасность!”.

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

Пример:

Input.txt:

10 10 10 10

Input.txt:

-350 10 0 10

Input.txt:

10 10 10 -10

Input.txt:

10 10 15 10

Input.txt:

10 10 0 5

Output.txt:

10 10

Output.txt:

0 20

Output.txt:

0 20

Output.txt:

10 15

Output.txt:

ВНИМАНИЕ! Есть слепая зона!

Задача 7. "Васин мячик" 8 баллов

Жил-был Вася. Однажды на День Рождения ему подарили мячик. Обрадованный Вася сразу побежал на улицу играть. Расшалившись, Вася бросил мяч и попал в окно второго этажа. Так как окно высоко, Васе не видно, разбилось ли оно. Определить, что случилось с окном, зная, что если центр меча попал за пределы окна или на его границу, оно не разобьется. Если мяч целиком попал в окно, оно разобьется. В противном случае в окне образуется трещина.

Исходная информация.

Файл input.txt содержит координаты окна: левого нижнего и правого верхнего углов, координаты центра мяча и радиус мяча.

Результирующая информация.

Файл output.txt должен содержать одну из фраз: Окно разбито. - если оно разбилось. Трещина. - если стекло треснуло. Мяч отскочил. - если мяч отскочил.

Пример:

input.txt0,0,10,10,5,5,1

output.txt

Окно разбилось.

 

Задача 8. "Квартирный номер" 40 баллов

Строительная фирма г.Барнаула решила заказать в металлолитейной мастерской номера на двери для квартир в новом небоскребе. Для того, чтобы снизить стоимость заказа за счет уменьшения количества литейных форм, было решено каждый номер для квартиры выполнить из отдельных цифр. Для составления заказа была написана программа, которая сначала записала все номера квартир, начиная с 1, по порядку, а затем последовательно каждой цифре в этой записи поставила в соответствие уникальные номера, также начиная с 1. То есть бланк заказа имел следующий вид:

1 1

2 2

3 3

4 4

5 5

6 6

7 7

8 8

9 9

1 10

0 11

1 12

1 13

1 14

2 15

  1. 16

3 17

...

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

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

Вы должны написать программу, которая сможет вычислить это значение.

Исходная информация.

Файл Input.txt содержит единственное число - уникальный номер потерянной цифры.Результирующая информация.

Файл Output.txt должен содержать цифру, соответствующую указанному номеру.

Пример 1

input.txt output.txt

1 1

Пример 2

input.txt output.txt

15 2

Задача 9. "Скобки для Microsoft LISP" 60 баллов

Компания Microsoft изменила политику и объявила языком будущего LISP (Lots of Idiotic Silly Parentheses), который должен был стать встроенным языком новой версии Windows. Естественно, компания сделала язык более наглядным, т.е. ввела кроме обычных скобок '(', ')' еще несколько видов:

'[', ']', '{', '}', '<', '>'.

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

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

Исходная информация.

Выражение на языке Microsoft LISP.

Результирующая информация.

Для правильных выражений нужно выдать строку "Все скобки расставлены верно.", а для неправильных - "Ошибка в столбце X.", где X - номер столбца (начиная с 1), в котором была обнаружена первая ошибка.

Пример 1input.txt

<(a+b) - [c-d]> - правильное выражение.

output.txtВсе скобки расставлены верно.

Пример 2input.txt

(a+b} - неправильное выражение!

output.txt

Ошибка в столбце 5.