ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при поддержке
ЦПМ
Подтемы:
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 3475 3476 3477 3478 3479 3480 3481 >> [Всего задач: 21755]      



Задача 98602

Темы:   [ Последовательности (прочее) ]
[ НОД и НОК. Взаимная простота ]
[ Принцип Дирихле (прочее) ]
[ Четность и нечетность ]
Сложность: 4
Классы: 10,11

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

Прислать комментарий     Решение

Задача 98621

Темы:   [ Итерации ]
[ Многочлены (прочее) ]
[ Предел функции ]
[ Монотонность и ограниченность ]
Сложность: 4
Классы: 10,11

Дан многочлен P(x) с действительными коэффициентами. Бесконечная последовательность различных натуральных чисел a1, a2, a3, ... такова, что
P(a1) = 0,  P(a2) = a1,  P(a3) = a2,  и т.д. Какую степень может иметь P(x)?

Прислать комментарий     Решение

Задача 98625

Темы:   [ Числовые таблицы и их свойства ]
[ Правило произведения ]
[ Инварианты ]
[ Линейная и полилинейная алгебра ]
Сложность: 4
Классы: 10,11

В каждой клетке таблицы размером 4×4 стоит знак "+" или "–". Разрешено одновременно менять знаки на противоположные в любой клетке и во всех клетках, имеющих с ней общую сторону. Сколько разных таблиц можно получить, многократно применяя такие операции?

Прислать комментарий     Решение

Задача 98674

 [Ожерелье]
Тема:   [ Сортировка массива ]
Сложность: 4
Классы: 8,9,10,11

Имя входного файла:

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

Прислать комментарий     Решение

Задача 98695

 [Сократи векторы]
Тема:   [ Векторы ]
Сложность: 4
Классы: 8,9,10,11

Максимальное время работы на одном тесте: 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

Прислать комментарий     Решение

Страница: << 3475 3476 3477 3478 3479 3480 3481 >> [Всего задач: 21755]      



© 2004-... МЦНМО (о копирайте)
Пишите нам