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

---

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

   Решение

---

На доске записано число 61. Каждую минуту число стирают с доски и записывают на это место произведение его цифр, увеличенное на 13. После первой минуты на доске записано 19  (6·1 + 13 = 19).  Какое число можно будет прочитать на доске через час?

   Решение

---

  а) Головоломка "Ханойская башня" представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трёх колышков. Требуется переместить всю башню на другой колышек, перенося каждый раз только один диск и не помещая больший диск на меньший. Докажите, что головоломка имеет решение. Какой способ будет оптимальным (по числу перекладываний дисков)?

  б) Занумеруем колышки числами 1, 2, 3. Требуется переместить диски с 1-го колышка на 3-й. Сколько понадобится перекладываний, если прямое перемещение диска с 1-го колышка на 3-й и с 3-го на 1-й запрещено (каждое перекладывание должно производиться через 2-й колышек)?

  в) Сколько понадобится перекладываний, если в условии пункта а) добавить дополнительное требование: первый (самый маленький) диск нельзя класть на 2-й колышек?

   Решение

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

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

---

Задача 60314  (#01.041)

Темы:   [ Разрезания на части, обладающие специальными свойствами ] [ Индукция (прочее) ]

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

Из квадрата клетчатой бумаги размером 16×16 вырезали одну клетку. Докажите, что полученную фигуру можно разрезать на "уголки'' из трех клеток.

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

Решение

---

Задача 60315  (#1.42, 1.43, 1.44)  [Ханойская башня I]

Темы:   [ Индукция (прочее) ] [ Классическая комбинаторика (прочее) ] [ Рекуррентные соотношения ]

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

  а) Головоломка "Ханойская башня" представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трёх колышков. Требуется переместить всю башню на другой колышек, перенося каждый раз только один диск и не помещая больший диск на меньший. Докажите, что головоломка имеет решение. Какой способ будет оптимальным (по числу перекладываний дисков)?

  б) Занумеруем колышки числами 1, 2, 3. Требуется переместить диски с 1-го колышка на 3-й. Сколько понадобится перекладываний, если прямое перемещение диска с 1-го колышка на 3-й и с 3-го на 1-й запрещено (каждое перекладывание должно производиться через 2-й колышек)?

  в) Сколько понадобится перекладываний, если в условии пункта а) добавить дополнительное требование: первый (самый маленький) диск нельзя класть на 2-й колышек?

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

Решение

---

Задача 60318  (#01.045)

Темы:   [ Разрезания на части, обладающие специальными свойствами ] [ Индукция в геометрии ]

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

Докажите, что квадрат можно разрезать на n квадратов для любого n, начиная с шести.

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

Решение

---

Задача 60319  (#01.046)

Темы:   [ Разрезания на части, обладающие специальными свойствами ] [ Индукция в геометрии ]

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

Докажите, что правильный треугольник можно разрезать на n правильных треугольников для любого n, начиная с шести.

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

Решение

---

Задача 60320  (#01.047)  [Золотая цепочка]

Темы:   [ Геометрическая прогрессия ] [ Упорядочивание по возрастанию (убыванию) ] [ Классическая комбинаторика (прочее) ]

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

   а) На постоялом дворе остановился путешественник, и хозяин согласился в качестве уплаты за проживание брать кольца золотой цепочки, которую тот носил на руке. Но при этом он поставил условие, чтобы оплата была ежедневной: каждый день хозяин должен был иметь на одно кольцо больше, чем в предыдущий. Замкнутая в кольцо цепочка содержала 11 колец, а путешественник собирался прожить ровно 11 дней, поэтому он согласился. Какое наименьшее число колец он должен распилить, чтобы иметь возможность платить хозяину?

   б) Из скольких колец должна состоять цепочка, чтобы путешественник мог прожить на постоялом дворе наибольшее число дней при условии, что он может распилить только n колец?

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

Решение

---

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

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