Версия для печати
Убрать все задачи

---

Вычислите функции g_k,l(x) при  0 ≤ k + l ≤ 4  и покажите, что все они являются многочленами.
Определение многочленов Гаусса g_k,l(x) можно найти в справочнике.

   Решение

---

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

Задание

Напишите программу MATCHES, которая по количеству квадратов N, которые необходимо составить, находит минимальное необходимое для этого количество спичек.

Входные данные

Единственная строка входного файла MATCHES.DAT содержит одно целое число N (1≤N≤10⁹).

Выходные данные

Единственная строка выходного файла MATCHES.SOL должна содержать одно целое число - минимальное количество спичек требуемых для составления заданного количества квадратов.

Пример входных и выходных данных

MATCHES.DAT	MATCHES.SOL
4	12

   Решение

---

Докажите, что у многочлена 2T_n(^x/₂) старший коэффициент равен единице, а все остальные коэффициенты – целые числа.
Здесь T_n – многочлен Чебышёва, смотри задачу 61099.

   Решение

---

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

   Решение

---

Задана квадратная доска размером N×N. Известно, что на ней играли в интеллектуальную игру, вследствие чего клеточки оказались окрашенными в белый, чёрный и зеленый цвета. Раскраска клеточек может быть разной (ведь это интеллектуальная игра!), но все клеточки самого верхнего ряда белые, а самого нижнего - чёрные.

Чтобы выявить победителя, необходимо подсчитать количество клеточек в белой и количество клеточек в черной области. Белая область - это как можно большая (по количеству клеточек) часть квадрата, которая ограничена сверху верхней стороной квадрата, а с других сторон - непрерывной границей, которая проходит только через белые клеточки и никакая клеточка не встречается больше одного раза. Белая граница представляет собой последовательность белых соседних клеточек (соседние клеточки имеют общую сторону). Концами этой границы должны быть левая верхняя и правая верхняя клеточки квадрата.

Определение чёрной области выглядит аналогично: она ограничена снизу нижней стороной квадрата, с других сторон - чёрной границей, которая проходит только через чёрные клеточки, а концы этой границы - левая нижняя и правая нижняя клеточки квадрата.

Задание

Напишите программу SCORE, которая по раскраске квадрата находит количество клеточек в белой и чёрной областях.

Входные данные

Первая строка входного файла SCORE.DAT содержит единственное целое число N - размер квадрата (5≤N?250). Каждая из следующих N строк содержит по N символов "G", "W" или "B" (записанных без пробелов), которые обозначают зелёный, белый и чёрный цвет, соответственно.

Выходные данные

Первая строка выходного файла SCORE.SOL должна содержать количество клеточек в белой области, а вторая строка - количество клеточек в чёрной области.

Пример входных и выходных данных

SCORE.DAT	SCORE.SOL
7 WWWWWWW WGWWBWG WWWWGWW BBGWWWB GWBBWGB BBBBGBB BBBBBBB	22 15

Вид белой и чёрной областей для примера из условия представлен на рисунке.

   Решение

---

K членов Жюри Десятой Всероссийской олимпиады школьников по информатике решили отметить столь круглую годовщину в одном из лучших ресторанов на Невском проспекте. На десерт вниманию Жюри предложили торт, имеющий форму прямоугольной призмы с выпуклым N-угольником в основании. Жюри вооружается десертными ножами и собирается справедливо разделить торт на K частей равного объема. Ножами можно проводить прямые вертикальные разрезы от одной границы торта до другой; различные разрезы могут иметь общие точки лишь в своих концевых вершинах.

Напишите программу, помогающую членам Жюри построить требуемые K-1 разрезов.

Входные данные
В первой строке входного файла содержатся два целых числа K и N (1 ≤ K, N ≤ 50). Далее следуют N пар вещественных чисел – координаты
последовательно расположенных вершин N-угольника.

Выходные данные
Каждый из K-1 разрезов в выходном файле должен быть представлен четверкой чисел – координатами своих концов. Все числа должны быть разделены пробелами и/или символами перевода строки.

Пример входного файла
4 3
2 1
0 0.5
4 0.5

Пример выходного файла
2 1 1 0.5
2 1 2 0.5
2 1 3 0.5

   Решение

---

Проверьте, что многочлены Чебышёва T_n(x) и U_n(x) (см. задачу 61099) удовлетворяют начальным условиям
T₀(x) = 1,   T₁(x) = x;   U₀(x) = 1,   U₁(x) = 2x,   и рекуррентным формулам   T_n+1(x) = 2xT_n(x) – T_n–1(x),   U_n+1(x) = 2xU_n(x) – U_n–1(x).

   Решение

Страница: 1 2 3 4 5 >> [Всего задач: 21]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 61521

Темы:   [ Многочлены Гаусса ] [ Разложение на множители ]

Сложность: 2 Классы: 10,11

Вычислите функции g_k,l(x) при  0 ≤ k + l ≤ 4  и покажите, что все они являются многочленами.
Определение многочленов Гаусса g_k,l(x) можно найти в справочнике.

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

Решение

---

Задача 61522

Темы:   [ Многочлены Гаусса ] [ Рекуррентные соотношения (прочее) ]

Сложность: 2+ Классы: 10,11

Докажите следующие свойства функций g_k,l(x) (определения функций g_k,l(x) смотри здесь):
  а)  g_k,l(x) = ,  где  h_m(x) = (1 – x)(1 – x²)...(1 – x^m)   (h₀(x) = 1);
  б)  g_k,l(x) = g_l,k(x);
  в)   g_k,l(x) = g_k–1,l(x) + x^kg_k,l–1(x) = g_k,l–1(x) + x^lg_k–1,l(x);
  г)  g_k,l+1(x) = g_0,l(x) + xg_1,l(x) + ... + x^kg_k,l(x);
  д)  g_k,l(x) – многочлен степени kl.
  Многочлены g_k,l(x) называются многочленами Гаусса. Их свойства во многом аналогичны свойствам биномиальных коэффициентов. В частности, среди многочленов они играют ту же роль, что и биномиальные коэффициенты среди чисел.

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

Решение

---

Задача 61100

Темы:   [ Многочлены Чебышева ] [ Тригонометрия (прочее) ] [ Рекуррентные соотношения (прочее) ]

Сложность: 3 Классы: 9,10,11

Проверьте, что многочлены Чебышёва T_n(x) и U_n(x) (см. задачу 61099) удовлетворяют начальным условиям
T₀(x) = 1,   T₁(x) = x;   U₀(x) = 1,   U₁(x) = 2x,   и рекуррентным формулам   T_n+1(x) = 2xT_n(x) – T_n–1(x),   U_n+1(x) = 2xU_n(x) – U_n–1(x).

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

Решение

---

Задача 61101

Темы:   [ Многочлены Чебышева ] [ Рекуррентные соотношения (прочее) ]

Сложность: 3+ Классы: 9,10,11

Докажите, что у многочлена 2T_n(^x/₂) старший коэффициент равен единице, а все остальные коэффициенты – целые числа.
Здесь T_n – многочлен Чебышёва, смотри задачу 61099.

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

Решение

---

Задача 61523

Темы:   [ Многочлены Гаусса ] [ Треугольник Паскаля и бином Ньютона ]

Сложность: 3+ Классы: 10,11

а) Определение (смотри в справочнике) функций g_k,l(x) не позволяет вычислять их значения при  x = 1.  Но, поскольку функции g_k,l(x) являются многочленами, они определены и при  x = 1.  Докажите равенство  

б) Какие свойства биномиальных коэффициентов получаются, если в свойства б) – г) из задачи 61522 подставить значение  x = 1?

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

Решение

---

Страница: 1 2 3 4 5 >> [Всего задач: 21]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями