Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Задачи Секции А

А0. Сосуды

В вашем распоряжении два сосуда A и B емкостью M и N литров соответственно. Написать программу, показывающую последовательность операций, с помощью которой можно получить в одном из сосудов Q литров жидкости. M , N , Q — целые положительные числа меньше 100. Разрешены операции:

Опорожнение сосуда — (A–, B–); Наполнение сосуда до отказа — (A+, B+); Переливание из сосуда в сосуд, пока первый не опорожнится или второй не наполнится — (A–>B, B–>A)

Ввод:      три числа M , N и Q, разделенные пробелом.

Вывод: последовательность действий. Каждый шаг в новой строке. Если невозможно, вывести «NO».

  Дополнительное задание: Выполнить задание минимумом действий.

Пример

Ввод: 2 5 1  

 

 

  

Вывод : B+

               B >A

                A

                B >A  

 

А1. Освоение полюса

Один из проектов глобального исследования и освоения полярной шапки предполагает создание некоторого количества (до 50) станций, расположенных по всей территории ледника. При переезде от одной станции к другой необходимо составлять маршрут, так чтобы расстояние между соседними станциями-остановками не превышало (≤)Х км. Считать пути между соседними станциями прямыми. Найти К(<100) самых коротких путей от станции А до станции B и вывести их в неубывающем по длине порядке. Если количество путей не превышает К, найти  их все.

Ввод:      N — кол-во станций, A, B, K, X. Затем N пар целых чисел — координат (в км) станций. Все числа разделены пробелами или символами новой сроки.

Вывод:  K (или, если количество путей M<K, то М) различных маршрутов, представляющие последовательность номеров станций, начиная с начальной и заканчивая конечной. Станции отделяются пробелами, маршруты — символами новой строки.

  Пример

Ввод: 4

           1 4 2 55

            40 40 

           10 0

          -15 0

           -20 -30

Вывод : 1 2 4

               1 2 3 4

 

 

 

 

А2. Коррумпированное государство

В тридевятом царстве в тридесятом государстве для получения лицензии на проведение любых исследований необходимо разрешение председателя Комиссии по наукоемким технологиям. В комиссии N<=100 чиновников. Соответственно, у каждого чиновника (кроме самого главного №1) есть 1 непосредственный  начальник и могут быть подчиненные (как непосредственные, так и подчиненные его подчиненных).  Согласно естественным правилам бюрократической системы каждый чиновник, кроме самых младших, на заявлении может потребовать на заявлении подписи одного или нескольких своих прямых подчиненных и взятку, как за то, чтобы можно было обойти нижестоящих чиновников, так и просто за свою подпись.  Для каждого чиновника известен непустой список возможных наборов «виз» (подписей своих подчиненных) и соответствующая каждому набору взятка (достаточно наличие только одного набора). Пустой набор означает, что данный чиновник не требует виз в данном случае. В какую минимальную сумму обойдется лицензия на проведение исследований?

Ввод:     Ν , в следующих строках: <номер чиновника (1..N)> <взятка — целое число меньше 10000> <набор виз (может быть пустым) — номера чиновников, разделенные пробелом> (Замечание: для каждого чиновника можно записать несколько таких строк). Количество виз в наборе не превосходит 50. Количество наборов для каждого чиновника не превосходит 15.

Вывод:              <Сумма взяток>

  Пример

Ввод: 4

            3 100

            1 300

            1 100 2 3

            4 20

            3 50 4

            2 50

           1 200 2

Вывод : 220

 

 

 

 

 

 

 

 

А3. Загадочная функция

 Рассмотрим дискретную функцию F(n1,n2,...,nM),  где n1, n2,...,nM — целые и 1<=n1,n2,...,nM<=M,  1<=M<=100. Функция задана на всей области определения следующим образом: F(1,2,3,4,...,M-1,M)=1 и  F(n1,n2,...,nM) меняет знак при перестановке любых двух аргументов: F(n1,...,nI,...,nJ,...,nM)= -F(n1,...,nJ,...,nI,...,nM) .

Например:  F(1,2,3,4,...,M,M-1)= -1.

Вычислить сумму S всех возможных квадратов F(n1,n2,...,nM)2.

Ввод:      M

Вывод:  S

Пример

Ввод: 3

Вывод : 6

 

A 4. Программа передач

Телепузик очень любит днем смотреть интересные передачи по телевизору. Беда в том, что очень часто они идут в одно и то же время по разным каналам. Помогите ему просмотреть наибольшее их количество (полностью!). Примечание: считать, что если одна передача заканчивается в 10:00, а другая начинается в 10:00, то можно посмотреть обе.

Ввод:     N (0<N<1000) строк формата ЧЧ:ММ ЧЧ:MM название  (время начала и окончания передачи, название короче 10 символов).

Вывод: M строк с названиями передач, которые Телепузик посмотрит (названия передач не повторяются).

Пример

Ввод: 16:00 18:00 TOMORROW

            16:30 17:15 NUPOGODI

             17:15 18:30 BRAINRING    

Вывод : NUPOGODI

                BRAINRING

 

A 5. Окружности

На плоскости заданы N различных точек посредством пары целых декартовых координат. Необходимо определить максимальное число M точек,через которые можно провести(одну)окружность.Ограничения:-1000<=Xi,Yi<= 1000и1<=N<=16. Вычисления производить с абсолютной точностью.

Ввод:      В первой строке число N. В следующих N строках по два действительных числа, отделенных пробелами — координаты Xi,Yi.

Вывод:  M

Пример

Ввод: 5

           2 -1

           2 3

           4 1

         -100 0

           0 1

    Вывод : 4

 

 

 

 

A6.Замечательные числа

Число  R = pnpn-1...p1 (pi-цифры) называется замечательным тогда и только тогда, когда число Q= pmpm-1...p1, состоящее из последних m цифр числа R — простое (для любого m<= n). Число  Q может иметь произвольное число нулей в начале. Дано целое число S (1<=S<= 32000). Найти все замечательные числа меньшие S.

Ввод:      S

Вывод:  В первой строке число замечательных чисел, а на следующей строке — сами числа, в возрастающем порядке.

Ввод: 100 

   

Вывод :  15

                 2 3 5 7 13 17 23 37 43 47 53 67 73 83 97

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика