Главная страница => просто задачи => Volume #2
Сержант #1 (NetOI-2000)
Команда новобранцев прибыла в часть. Сержант велел им выстроится в колонну по одному для движения церемониальным маршем в баню. Новобранцы, не имея должной выучки, выстроились не по росту, а как кому на душу пришлось. Особенно возмутило сержанта то, что в колонне просматривались участки, явно бросающие вызов всем уставам строевой службы - новобранцы стояли в строю так, что вслед за низеньким находился высокорослый, за ним - пониже ростом, а потом опять повыше, и т.д., или наоборот - вслед за высоким - пониже него, потом опять повыше, потом - пониже: Возмущение сержанта стимулировало концентрацию математических способностей и он тут же велел выйти из строя тем новобранцам, которые образовали самую длинную "зубчатую" цепочку. Сколько человек вышло из строя?
Ввод-вывод:
Вы вводите с клавиатуры в первой строке количество новобранцев, а во второй- рост каждого. Числа разделены пробелами.
Вы выводите на экран число солдат, вышедших из строя
Пример
Ввод: 20
Ввод: 4 5 2 3 1 6 7 8 3 9 4 6 2 6 7 8 4 8 8 8
Вывод: 8
Ограничения
Новобранцев не более 10000, рост их измеряется натуральными числами не более 255. Если несколько цепочек имеют максимальную длину, то из строя выходит только одна из них.
Веревки (NetOI-2000)
В прошлом - колхозник, а теперь землевладелец Наливайко получил сертификат на владение землей. Сельсовет выдал ему схему участка. На схеме дом имел координаты в декартовой системе, а участок представлял собой окружность известного радиуса, центр которой, естественно, совпадал с положением дома. Все было б ничего, если б соседка Наливайко, знатная прачка, не имела странной привычки натягивать веревки для сушки белья невзирая ни на какие границы, привязывая концы веревки к чему угодно. Да еще одна странность была у прачки - веревки всегда были натянуты параллельно какой-либо из осей той самой системы координат. Наливайко обратился ко мне с жалобой, что веревка проходит через его землевладения. Отрезок веревки какой длинны действительно проходил через земли Наливайко, если известны координаты ее начала и конца во все той же системе координат?
Ввод-вывод : в первой строке ввода - два вещественных числа, разделенные пробелом- координаты центра окружности, во второй строке - вещественный радиус окружности, в третьей - 4 вещественных числа, разделенные пробелом, - координаты начала (х1 , y1) и конца (х2,y2) веревки. В строке вывода вы выводите на экран результат с точностью до 2-х знаков.
Пример:
Ввод: 10.0 5.0
Ввод: 5.0
Ввод: 3.0 8.0 12.0 8.0
Вывод: 6.00
Ограничения: координаты и радиус по модулю не более 1000.00
A to B (NetOI-2000)
Задача решена!
Я загадаю целое число из интервала [A,B]. Напишите программу, которая за минимальное число вопросов отгадает это число. Играть будем так. Я сообщаю программе числа A и B, программа выводит свою версию ответа. Если это меньше задуманного мною, я сообщу программе об этом числом -1, если больше - числом 1, а если угадано - числом 0. Так будет продолжаться, пока программа не угадает число (естественно, я буду играть честно!). Постарайтесь, чтобы ваша программа угадала число за минимальное число ходов.
Ввод-вывод: В первой строке вводите с клавиатуры два целых числа через пробел - границы диапазона. Программа на экран выводит свою версию в новой строке. С новой строки вы вводите "-1", "1" или "0" ( без кавычек). Так продолжается до того момента, пока число не будет угадано (т.е. ваш ответ "0" должен завершить работу программы).
Пример:
( я задумал число 2)
Ввод: 1 6
Вывод: 3
Ввод: 1
Вывод: 2
Ввод: 0
Ограничения : -100000<=A<=B<=100000
Матрица-домино (NetOI-2000)
Один наш активист Семен Семенович Настойкин, коротая время в ожидании очереди на игру, учудил следующее. Из стандартного набора домино он изъял все кости, на одной половинке которых есть более чем N точек. Из оставшихся костей он сложил на столе прямоугольник, а потом начертил все это в виде таблицы, каждая ячейка которой - половинка кости домино, а содержимое - число точек на этой половинке. Семен Семенович показал нам рисунок и предложил сложить исходную картинку из костей, которыми мы играли. Ненужные кости мы отложили в сторону быстренько, а вот разложить оставшиеся не можем уж который день. Даже в "козла" забросили играть - все раскладываем. Помогите нам.
Ограничения:
1<=N<=6. Решение всегда существует. Если существует несколько решений, достаточно найти любое из них.
Ввод/вывод:
Программа должна прочитать с клавиатуры: с первой строки - число N, со второй строки - размеры таблицы H и W, а со следующих H строк по W чисел - количество точек на половинке кости домино.
Программа должна вывести на экран H строк по W чисел в каждой. Каждое число - код той кости домино, которой принадлежит половинка, находящаяся в данной клеточке таблицы. Кость "X:Y" кодируется числом X*10+Y, если X<=Y.
Пример:
Ввод: 2
Ввод: 3 4
Ввод: 0 0 1 2
Ввод: 0 1 1 1
Ввод: 0 2 2 2
Вывод: 0 1 11 12
Вывод: 0 1 11 12
Вывод: 2 2 22 22
Игра в 2..9 (NetOI-2000)
Предлагаю Вашей программе поиграть со мной в такую игру. Я (или Ваша программа) называет натуральное число от 2 до 9, противник умножает его на любое натуральное число от 2 до 9, тот, кто начинал - опять умножает результат на натуральное число от 2 до 9, и т.д. Выигрывает тот, кто первый получит произведение, больше заданного положительного числа С.
Ограничения:
10<=C<=50000
Ввод/вывод:
Сперва программа должна прочитать с клавиатуры два числа: C и P, где P равно 1, если программа должна начинать игру, или 2, когда программа должна играть за второго игрока. Затем программа должна поочередно выводить свой ход или вводить ход противника с клавиатуры. Программа должна закончить работу, когда игра завершится.
Пример:
Ввод: 50 1
Вывод: 3
Ввод: 4
Вывод: 5
[Программа начала игру и победила, получив последним ходом произведение 3*4*5=60>50]
Сосиска в шоколаде #1 (NetOI-2000)
Получил я вчера задание нарисовать картинку размером H на W пикселей, обертку для конфет "Сосиска в шоколаде". Творчество - процесс тонкий, вдохновение требуется. А тут - как топором отрубило, ничего не выходит: От безысходности я нарисовал на белом экране красную замкнутую линию, толщиной в один пиксель. Сколько пикселей оказалось в области, ограниченной красной линией?
Для тех, кто не знаком с компьютерной графикой - пиксель имеет форму квадратика.
Ограничения:
1
Каждый красный пиксель имеет общие стороны ровно с двумя красными пикселями.
Ввод/вывод:
Программа должна прочитать с клавиатуры: с первой строки - два числа H и W, а со следующих H строчек по W чисел. Красный пиксель обозначается единицей, белый - нулем.
Программа должна вывести на экран результат - число пикселей, ограниченных линией.
Пример:
Ввод: 5 7
Ввод: 0 0 0 1 1 1 0
Ввод: 0 1 1 1 0 1 0
Ввод: 0 1 0 0 0 1 0
Ввод: 0 1 1 1 1 1 0
Ввод: 0 0 0 0 0 0 0
Вывод: 4
Сосиска в шоколаде #2 (NetOI-2000)
Картинка размером H на W пикселей, обертка для конфет "Сосиска в шоколаде" по-прежнему не придумывалась... На экране была все та же красная замкнутая линия толщиной в 1 пиксель. Творческий кризис прогрессировал... Ткнул я мышкой в точку внутри области, ограниченной красной линией -- появился одинокий синий пиксель. Я от нечего делать стал ставить синие точки, образующие сплошную линию, пока последняя из них не перекрасила красную точку. После этого, естественно, обертка не получилась... Вернув все в начальный вид, я повторил эти же действия для всех остальных точек внутри области, каждый раз возвращая в исходное состояние картинку после "перекрашивания" красной точки.
Сколько за это время я поставил синих точек, если каждый раз количество поставленных точек было минимальным? Для тех, кто не знаком с компьютерной графикой -пиксель имеет форму квадратика.
Ограничения:
1
Пиксели, составляющие цветную линию (кроме начального и конечного), имеют общие стороны ровно с двумя пикселями того же цвета.
Ввод/вывод:
Программа должна прочитать с клавиатуры: с первой строки - два числа H и W, а со следующих H строчек по W чисел. Красный пиксель обозначается единицей, белый - нулем. Программа должна вывести на экран число поставленных синих точек.
Пример:
Ввод: 6 7
Ввод: 0 0 1 1 1 0 0
Ввод: 0 1 1 0 1 1 1
Ввод: 0 1 0 0 0 0 1
Ввод: 0 1 0 0 0 0 1
Ввод: 0 1 1 1 1 1 1
Ввод: 0 0 0 0 0 0 0
Вывод: 19
В этом примере для 8 внутренних пикселей поставлено 2 точки и для одного - 3. Всего получилось 2*8+3=19.
Памятник до небес (NetOI-2000)
В нашем городе решили возвести до небес памятник Александру Македонскому. Постамент поручили строить моей бригаде. По проекту он представлял собой прямоугольную призму 4х4 метра в основании и высотой N метров (личность уж больно историческая!). Для постройки мы завезли достаточное количество бетонных блоков 1х1х1, 2х2х2, 3х3х3 и 4х4х4 метра. Сколькими различными способами рабочие могут уложить блоки при постройке постамента?
Ограничения: 1<=N<=1000.
Ввод/вывод:
Программа должна прочитать с клавиатуры число N и вывести на экран ответ.
Пример:
Ввод: 2
Вывод: 35
Сильно ломаная (NetOI-2000)
Для вычерчивания некоторых ломаных линий у меня есть набор картонных равносторонних треугольников всевозможных размеров. Я приложил их одной стороной к длинной деревянной линейке, зафиксировал и карандашом обрисовал получившийся контур, начиная от крайней левой точки самого левого треугольника и заканчивая самой правой точкой правого. Отличная получилась ломаная! Найдите координаты ее вершин, включая первую и последнюю точки. Считайте, что ось абсцисс совпадает с линейкой, а ось ординат направлена в ту же сторону, что и треугольники.
Ограничения:
Число треугольников не превышает 10000. Координаты вершин треугольников находятся в отрезке [0.00, 100.00].
Ввод/вывод:
Программа должна прочитать с клавиатуры: с первой строки - количество треугольников M, а со следующих M строк по два числа -- координаты левой и правой вершин треугольника, лежащих на линейке. Программа должна вывести на экран: в первой строке - число вершин ломаной N, а в следующих N строках по два числа - координаты вершин ломаной.
Ответ должен быть получен с точностью до 0.01.
Пример:
Ввод: 3
Ввод: 4.00 9.00
Ввод: 10.00 12.50
Ввод: 2.00 6.00
Вывод: 8
Вывод: 2.00 0.00
Вывод: 4.00 3.46
Вывод: 5.00 1.73
Вывод: 6.50 4.33
Вывод: 9.00 0.00
Вывод: 10.00 0.00
Вывод: 11.25 2.17
Вывод: 12.50 0.00