Задачи для олимпиады по информационным технологиям

Первый тур

1. Исправна ли лампочка
На проводе между лампой и источником питания три выключателя, соединённых последовательно:
(питание) - (выключатель) - (выключатель) - (выключатель) - (лампочка)

Каждый выключатель может находиться в двух состояниях: выключен и включён. Но по внешнему виду состояние выключателя определить нельзя. Известно, что все выключатели исправны.

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

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

2. Прогрессивные налоги
В Тридевятом царстве ввели следующую прогрессивную налоговую шкалу. Первая заработанная в году тысяча золотых налогом не облагается. С суммы до второй тысячи берётся налог в 1%. До третьей - 2%, до четвёртой тысячи - 3% и т.д., до сотой тысячи берётся налог в 99%, а всё, что превышает 100 000 просто забирается государством.

Разработайте алгоритм и программу для вычисления оставшейся у подданного Тридевятого царства суммы после выплаты налогов.

Пример. Если заработано 4500 золотых, то с 1000 налог не берётся, ещё с 1000 нужно уплатить 1%, т.е. 10 золотых, ещё с 1000 - 2;, т.е. 20 золотых, ещё с 1000 - 3%, т.е. 30 золотых, и с 500 нужно уплатить 4%, т.е. 20 золотых. Всего нужно уплатить 10+20+30+20  = 80 золотых и у подданного останется 4500-80 = 4420 золотых.

3. Рулетка
Смоделируйте следующий процесс и создайте программу. У игрока имеется некоторая сумма денег. Игрок вводит случайное целое число от 0 до 36. Компьютер определяет случайное число от 0 до 36. Если числа игрока и компьютера совпадают, то сумма денег игрока увеличивается на 3600. В противном случае она уменьшается на 100.
Продолжать процесс загадывания числа можно до тех пор, пока сумма денег у игрока не меньше 100.

Свои решения присылайте на izvalov.klanau [at] gmail.com