Все источники
>>
Книги, журналы
>>
Алфутова Н.Б., Устинов А.В., Алгебра и теория чисел
>>
глава 10. Неравенства
>>
параграф 1. Различные неравенства
Фильтр
Выбрано 15 задач Убрать все задачи
Максимальное время работы на одном тесте: 1 секунда
На плоскости задано N векторов - направленных отрезков, для каждого из которых известны координаты начала и конца (вектор, у которого начало и конец совпадают, называется нуль-вектором, можно считать, что нуль-вектор лежит на любой прямой, которая через него проходит). Введем следующие три операции над направленными отрезками на плоскости:
1) Направленные отрезки ненулевой длины, лежащие на пересекающихся прямых, можно заменить на их сумму, причем единственным образом. В этом случае отрезки переносятся вдоль своих прямых так, чтобы их начала совпадали с точкой пересечения прямых, и складываются по правилу сложения векторов (правилу параллелограмма, при этом началом результирующего вектора является точка пересечения прямых):
2) Направленные отрезки, лежащие на одной прямой, также можно заменить на их сумму. Для этого один из отрезков (любой) нужно перенести в начало второго из них и сложить по правилу сложения векторов на прямой:
Это правило применимо и в случае, когда один из векторов, или даже оба, являются нуль-векторами.
Заметим, что если складываемые векторы противоположно направлены и имеют одну и ту же длину, то результатом их сложения является нуль-вектор.
3) В любой точке плоскости можно породить два противоположно направленных отрезка равной (в том числе и нулевой) длины:
Будем говорить, что некоторая система векторов B эквивалентна системе A, если от системы A можно перейти к B с помощью конечной последовательности перечисленных выше операций.
Требуется получить любую систему векторов, эквивалентную заданной, состоящую из минимально возможного числа векторов.
Формат входных данных
В первой строке входного файла f.in записано число N - количество заданных векторов (1 < N ≤ 1000). В каждой из следующих N строк через пробел записаны четыре числа, обозначающие координаты начала и конца каждого из векторов соответственно. Все координаты - целые числа, по модулю не превосходящие 1000.
Формат выходных данных
В первой строке входного файла f.out следует записать число M - количество векторов в полученной системе (1 ≤ M ≤ N). В каждой из следующих M строк через пробел должны находиться четыре числа, обозначающие координаты начала и конца каждого из векторов соответственно. Все координаты - вещественные числа, записанные с 6 цифрами после точки.
Примеры
|
f.in |
f.out |
|
3 1 1 1 3 3 3 3 1 5 1 7 1 |
1 3.000000 3.000000 5.000000 3.000000 |
|
2 2 4 5 10 -2 -4 -5 -10 |
1 2.000000 4.000000 2.000000 4.000000 |
Парламент некоторой страны принял новый закон о праздничных днях. Согласно этому закону первые K дней года, а также 23 февраля и 8 марта объявляются праздничными, а все остальные праздники отменяются. При этом все выходные (субботы и воскресенья), попавшие на праздничные дни, переносятся на следующие за этими праздниками рабочие дни.
В зависимости от того, на какой день недели приходится 1 января, количество нерабочих дней, которые идут подряд, может меняться.
Требуется определить, какое наибольшее количество нерабочих дней может идти подряд.
Формат входных данных
Во входном файле a.in записано единственное число K (1 £ K £ 50).
Формат выходных данных
В выходной файл a.out требуется записать единственное число - наибольшее количество нерабочих дней, идущих подряд.
Примеры
|
a.in |
a.out |
|
2 |
4 |
|
10 |
16 |
|
Имя входного файла: |
stalker.in |
|
Имя выходного файла: |
stalker.out |
|
Максимальное время работы на одном тесте: |
2 секунды |
|
Максимальный объем используемой памяти: |
128 мегабайт |
В городе Н при невыясненных обстоятельствах территория одного из заводов превратилась в аномальную зону. Все подъезды к территории были перекрыты, а сама она получила название промзоны. В промзоне находятся N зданий, некоторые из них соединены дорогами. По любой дороге можно перемещаться в обоих направлениях.
Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.
В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.
Требуется написать программу, которая вычисляет минимальную сумму расходов, необходимую сталкеру, чтобы добраться от входа в промзону до склада.
Формат входных данных
В первой строке входного файла находятся два натуральных числа N и K (2 ≤ N ≤ 2000; 1 ≤ K ≤ 2000) - количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад - в здании с номером N.
В последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число ri - количество дорог, обозначенных на i-ой карте. Затем идут ri строк, содержащие по два натуральных числа a и b (1 ≤ a, b ≤ N; a ≠ b), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (r1 + r2 + ... + rK ≤ 300 000).
Формат выходных данных
В выходной файл необходимо вывести одно число - минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число -1.
Примеры
|
stalker.in |
stalker.out |
stalker.in |
stalker.out |
|
|
5 3 1 3 4 3 1 2 1 3 2 4 1 4 5 |
2 |
5 3 2 3 2 4 5 1 2 1 2 1 3 5 4 |
-1 |
|
Имя входного файла: |
numbers.in |
|
Имя выходного файла: |
numbers.out |
|
Максимальное время работы на одном тесте: |
1 секунда |
|
Максимальный объем используемой памяти: |
64 мегабайта |
|
Максимальная оценка за задачу: |
100 баллов |
Саша считает красивыми числа, десятичная запись которых не содержит других цифр, кроме 0 и k (1 ? k ? 9). Например, если k = 2, то такими числами будут 2, 20, 22, 2002 и т.п. Остальные числа Саше не нравятся, поэтому он представляет их в виде суммы красивых чисел. Например, если k = 3, то число 69 можно представить так: 69 = 33 + 30 + 3 + 3.
Однако, не любое натуральное число можно разложить в сумму красивых целых чисел. Например, при k = 5 число 6 нельзя представить в таком виде. Но если использовать красивые десятичные дроби, то это можно сделать: 6 = 5.5 + 0.5.
Недавно Саша изучил периодические десятичные дроби и начал использовать и их в качестве слагаемых. Например, если k = 3, то число 43 можно разложить так: 43 = 33.(3) + 3.(3) + 3 + 3.(3).
Оказывается, любое натуральное число можно представить в виде суммы положительных красивых чисел. Но такое разложение не единственно - например, число 69 можно также представить и как 69 = 33 + 33 + 3. Сашу заинтересовало, какое минимальное количество слагаемых требуется для представления числа n в виде суммы красивых чисел.
Требуется написать программу, которая для заданных чисел n и k находит разложение числа n в сумму положительных красивых чисел с минимальным количеством слагаемых.
Формат входных данных
Во входном файле записаны два натуральных числа n и k (1 ≤ n ≤ 109; 1≤ k ≤ 9).
Формат выходных данных
В выходной файл выведите разложение числа n в сумму положительных чисел, содержащих только цифры 0 и k, количество слагаемых в котором минимально. Разложение должно быть представлено в виде:
n=a1+a2+...+am
Слагаемые a1, a2, ..., am должны быть выведены без ведущих нулей, без лишних нулей в конце дробной части. Запись каждого слагаемого должна быть такой, что длины периода и предпериода дробной части имеют минимально возможную длину. Например, неправильно выведены числа: 07.7; 2.20; 55.5(5); 0.(66); 7.(0); 7. ; .5; 0.33(03). Их следует выводить так: 7.7; 2.2; 55.(5); 0.(6); 7; 7; 0.5; 0.3(30).
Предпериод и период каждого из выведенных чисел должны состоять не более чем из 100 цифр. Гарантируется, что хотя бы одно такое решение существует. Если искомых решений несколько, выведите любое. Порядок слагаемых может быть произвольным.
Выходной файл не должен содержать пробелов.
Примеры
|
numbers.in |
numbers.out |
|
69 3 |
69=33+33+3 |
|
6 5 |
6=5.5+0.5 |
|
10 9 |
10=9.(9) |
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти: 64 мегабайта
Как показывает опыт, для создания успешной футбольной команды важны не только умения отдельных ее участников, но и сплоченность команды в целом. Характеристикой умения игрока является показатель его профессионализма (ПП). Команда является сплоченной, если ПП каждого из игроков не превосходит суммы ПП любых двух других (в частности, любая команда из одного или двух игроков является сплоченной). Перед тренерским составом молодежной сборной Москвы была поставлена задача сформировать сплоченную сборную с максимальной суммой ПП игроков (ограничений на количество игроков в команде нет).
Ваша задача состоит в том, чтобы помочь сделать правильный выбор из N человек, для каждого из которых известен его ПП.
Формат входных данных
В первой строке входного файла e.in записано целое число N (0 £ N £ 30000). В последующих N строках записано по одному целому числу Pi (0 £ Pi £ 60000), представляющему собой ПП соответствующего игрока.
Формат выходных данных
В первой строке выходного файла e.out через пробел выведите число игроков, отобранных в команду, и их суммарный ПП. В последующих строках выведите номера игроков, вошедших в команду, в произвольном порядке - по одному числу в строке. Нумерация игроков должна соответствовать порядку перечисления игроков во входном файле. Если ответов несколько, выведите любой из них.
Примеры
|
e.in |
e.out |
|
4 1 5 3 3 |
3 11 2 3 4 |
|
5 100 20 20 20 20 |
2 120 1 2 |
Максимальное время работы на одном тесте: 1 секунда
После того, как к удивлению тетушки Полли, ее забор был покрашен, она поручила Тому Сойеру обновить краску на плитках, которыми был вымощен их квадратный двор. Двор был покрыт N´ N одинаковыми квадратными плитками, каждая из которых когда-то давно была покрашена в один из K цветов (K < N). Краска на плитках потускнела и Тому Сойеру поручили их покрасить, на этот раз в один любой цвет (из тех же К цветов). Покрасить нужно все плитки, в том числе и те, которые уже были покрашены в этот цвет раньше.
Окунув кисть в ведро с краской один раз, можно перекрасить один горизонтальный или вертикальный ряд плиток. Чтобы разнообразить свою работу, Том придумал, что ряд плиток можно красить только цветом, которым на данный момент уже покрашены (старой или новой краской) по крайней мере две плитки выбранного ряда (вертикального или горизонтального). За один раз Том собирается красить допустимым цветом весь ряд целиком, независимо от того, были ли уже перекрашены какие-либо его плитки ранее. Помогите Тому определить, какое минимальное число раз ему придется обмакнуть кисть, чтобы перекрасить все плитки, следуя придуманным правилам, и в какой цвет окажутся окрашены все плитки.
Формат входных данных
В первой строке входного файла b.in записаны через пробел два числа: N - количество плиток в одном ряду (1 < N ≤ 200) и K (1 ≤ K < N). В каждой из следующих N строк записаны N натуральных чисел, обозначающих номера цветов красок, в которые когда-то были выкрашены соответствующие плитки данного горизонтального ряда. Номера цветов - натуральные числа в диапазоне от 1 до K.
Формат выходных данных
В выходной файл b.out выведите два числа: L - какое минимальное число раз придется окунать кисть в ведро с краской, и номер краски С, в которую в результате окажутся перекрашены все плитки двора. Если таких красок может быть несколько, то выведите номер любой из них.
Если перекрасить все плитки, следуя придуманным Томом правилам, нельзя, выведите два раза число 0.
Примеры
|
b.in |
b.out |
|
3 2 1 2 1 2 1 1 1 2 2 |
4 1 |
|
2 1 1 1 1 1 |
2 1 |
|
Имя входного файла: |
necklace.in |
|
Имя выходного файла: |
necklace.out |
|
Максимальное время работы на одном тесте: |
1 секунда |
|
Максимальный объем используемой памяти: |
64 мегабайта |
|
Максимальная оценка за задачу: |
100 баллов |
В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.
Продавец хочет упорядочить колечки так, чтобы они располагались по возрастанию номеров вдоль нити по часовой стрелке. Снимать ожерелье с манекена нельзя.
Требуется написать программу, которая по заданному начальному расположению колечек находит последовательность протаскиваний колечек одно через другое, приводящую исходное расположение колечек в желаемое.
Формат входных данных
В первой строке входного файла записано число N (2 ≤ N ≤ 50).
Во второй строке через пробел следуют N различных чисел от 1 до N - номера колечек, расположенных вдоль нити по часовой стрелке.
Формат выходных данных
Выходной файл должен содержать описание процесса упорядочения.
В каждой строке, кроме последней, должны быть записаны через пробел два числа, указывающие номера колечек, протаскиваемых друг через друга. В последней строке должен стоять ноль.
Количество строк выходного файла не должно превышать 50000.
Если требуемого упорядочения колечек достичь не удается, в выходной файл нужно вывести одно число √1.
Пример
|
necklace.in |
necklace.out |
|
4 3 2 4 1 |
1 3 2 4 1 4 0 |
Максимальное время работы на одном тесте: 1 секунда
В процессе установки турникетов в автобусах, разработчики столкнулись с проблемой проверки подлинности билета. Для ее решения был придуман следующий способ защиты от подделок.
Информация, записанная на билете, кодируется K числами (0 или 1). При этом непосредственно на билете записывается последовательность из N чисел (N ³ K) так, что числа, записанные на расстоянии K, совпадают. Таким образом, для проверки подлинности билета достаточно проверить, что все числа на расстоянии K совпадают. К сожалению, при считывании информации с билета иногда могут происходить ошибки - считается, что одно из чисел может исказиться (то есть 0 заменится на 1, или 1 - на 0). Такой билет все равно нужно считать подлинным. Во всех остальных случаях билет считается поддельным.
Напишите программу, которая по информации, считанной с билета, устанавливает его подлинность, и указывает, при считывании какого из чисел могла произойти ошибка.
Формат входных данных
В первой строке входного файла d.in записаны числа N и K (1 £ N £ 50000, 1 £ K £ 1000, K £ N). Во второй строке записано N чисел, каждое из которых является 0 или 1 - информация, считанная с билета.
Формат выходных данных
В первой строке выходного файла d.out должно быть записано одно из двух сообщений - OK или FAIL (первое сообщение обозначает, что билет признан подлинным, второе - поддельным). В случае, если билет подлинный, во второй строке выведите 0, если все числа были считаны правильно, или номер числа, в котором при считывании произошла ошибка. Если возможных ответов несколько, выведите любой из них (в частности, если для признания билета подлинным можно считать, что ошибок при считывании не было, а можно считать, что была ошибка в одном из чисел - правильным является любой из вариантов ответа).
Примеры
|
d.in |
d.out |
|
6 2 1 0 1 0 1 0 |
OK 0 |
|
6 2 1 1 1 0 1 0 |
OK 2 |
|
6 2 1 1 1 0 0 0 |
FAIL |
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти: 64 мегабайта
По случаю введения больших новогодних каникул устраивается великий праздничный бал-маскарад. До праздника остались считанные дни, поэтому срочно нужны костюмы для участников. Для пошивки костюмов требуется L метров ткани. Ткань продается в N магазинах, в которых предоставляются скидки оптовым покупателям. В магазинах можно купить только целое число метров ткани. Реклама магазина номер i гласит: "Мы с радостью продадим Вам метр ткани за Pi бурлей, однако если Вы купите не менее Ri метров, то получите прекрасную скидку - каждый купленный метр обойдется Вам всего в Qi бурлей". Чтобы воплотить в жизнь лозунг "экономика страны должна быть экономной", правительство решило потратить на закупку ткани для костюмов минимальное количество бурлей из государственной казны. При этом ткани можно купить больше, чем нужно, если так окажется дешевле. Ответственный за покупку ткани позвонил в каждый магазин и узнал, что:
1) реклама каждого магазина содержит правдивую информацию о ценах и скидках;
2) магазин номер i готов продать ему не более Fi метров ткани.
Ответственный за покупку очень устал от проделанной работы и поэтому поставленную перед ним задачу <закупить ткань за минимальные деньги> переложил на своих помощников. Напишите программу, которая определит, сколько ткани нужно купить в каждом из магазинов так, чтобы суммарные затраты были минимальны.
Формат входных данных
В первой строке входного файла c.in записаны два целых числа N и L (1 £ N £ 100, 0 £ L £ 100). В каждой из последующих N строк находится описание магазина номер i - 4 целых числа Pi, Ri, Qi, Fi (1 £ Qi £ Pi £ 1000, 1 £ Ri £ 100, 0 £ Fi £ 100).
Формат выходных данных
Первая строка выходного файла c.out должна содержать единственное число - минимальное необходимое количество бурлей.
Во второй строке выведите N чисел, разделенных пробелами, где i-е число определяет количество метров ткани, которое нужно купить в i-м магазине. Если в i-м магазине ткань покупаться не будет, то на i-м месте должно стоять число 0. Если вариантов покупки несколько, выведите любой из них.
Если ткани в магазинах недостаточно для пошивки костюмов, выходной файл должен содержать единственное число -1.
Примеры
|
c.in |
c.out |
|
2 14 7 9 6 10 7 8 6 10 |
88 10 4 |
|
1 20 1 1 1 1 |
-1 |
|
Имя входного файла: |
net.in |
|
Имя выходного файла: |
net.out |
|
Максимальное время работы на одном тесте: |
1 секунда |
|
Максимальный объем используемой памяти: |
64 мегабайта |
|
Максимальная оценка за задачу: |
100 баллов |
Петя и Вася нашли на чердаке остатки рыболовной сети своего деда. Часть веревок давно сгнила, и сеть распалась на большое число кусков, каждый из которых состоит не более чем из 50 веревочек единичной длины.
Так как использовать по назначению остатки данной сети было уже нельзя, братья разложили один из найденных кусков на прямоугольном столе так, что веревочки оказались параллельны сторонам стола, и стали играть в следующую игру.
Братья делают ходы по очереди, Петя ходит первым. Своим ходом игрок находит веревочку, являющуюся стороной некоторой целой единичной квадратной ячейки сети (все четыре образующие ее веревочки целы), и перерезает выбранную веревочку. Проигрывает тот из братьев, который не может сделать очередной ход.
Требуется написать программу, которая по описанию куска сети на столе определяет, может ли Петя выиграть при любой игре Васи, и если да, то какой первый ход он должен для этого сделать.
Формат входных данных
В первой строке входного файла задано число N (1 ≤ N ≤ 50) - количество веревочек единичной длины, из которых состоит кусок сети. Следующие N строк входного файла содержат по две пары целых чисел - координаты концов веревочек. Каждая четверка чисел описывает отрезок единичной длины, параллельный одной из осей координат.
Координаты всех точек неотрицательны и не превосходят 50.
Формат выходных данных
Первая строка выходного файла должна содержать число 1, если Петя может выиграть при любой игре Васи, и число 2, если нет. В случае выигрыша Пети вторая строка должна содержать номер веревочки, которую он должен перерезать первым ходом. Если возможных выигрышных ходов несколько, выведите любой. Веревочки пронумерованы, начиная с 1, в том порядке, в котором они заданы во входном файле.
Примечание
Максимальная оценка за решение задачи при N ≤ 13 равна 40 баллам.
Пример
|
net.in |
net.out |
|
11 1 1 1 2 2 3 2 4 3 1 3 2 1 2 1 3 1 1 2 1 2 1 2 2 2 1 3 1 1 2 2 2 2 2 3 2 1 3 2 3 2 3 3 3 |
1 6 |
В треугольнике ABC проведены биссектрисы BB1 и CC1. Известно, что центр описанной окружности треугольника BB1C1 лежит на прямой AC. Найдите угол C треугольника.
В квадрате со стороной 1 проведено конечное количество отрезков, параллельных его сторонам. Отрезки могут пересекать друг друга. Сумма длин проведенных отрезков равна 18. Докажите, что среди частей, на которые разбивается квадрат этими отрезками, найдётся такая, площадь которой не меньше 0,01.
В некотором городе разрешаются только парные обмены квартир (если две семьи
обмениваются квартирами, то в тот же день они не имеют права участвовать в
другом обмене). Докажите, что любой сложный обмен квартирами можно осуществить за два дня.
(Предполагается, что при любых обменах каждая семья как до, так и после обмена занимает одну квартиру, и что семьи при этом сохраняются).
Докажите неравенство ≤
для положительных значений переменных.
Докажите, что ≥
.
Задачи Страница: 1 2 3 4 5 6 7 >> [Всего задач: 48]
Задача 30861 (#10.001) |
|
|
Докажите, что x + 1/x ≥ 2 при x > 0.
|
|
Решение |
Задача 61353 (#10.002)[Неравенство между средним квадратичным и средним арифметическим] |
|
|
Докажите, что ≥
.
|
|
Решение |
Задача 61354 (#10.003) |
|
|
Докажите неравенство для положительных значений переменных: (a + b + c + d)² ≤ 4(a² + b² + c² + d²).
|
|
|
Решение |
Задача 61355 (#10.004) |
|
|
Докажите неравенство для положительных значений переменных:
≥
+
.
|
|
|
Решение |
Задача 61356 (#10.005) |
|
|
Докажите неравенство ≤
для положительных значений переменных.
|
|
|
Решение |
Страница: 1 2 3 4 5 6 7 >> [Всего задач: 48]
