Кратчайший путь Есть 7 городов, обозначенных буквами английского алфавита A, B, C, D, E, F, G. Вы хотите посетить эти все города ровно по одному разу каждый и вернуться в начальную точку своего путешествия. Для этого вы можете воспользоваться самолётами: между двумя любыми городами есть прямой авиарейс. Стоимость перелёта между парой городов приведена в следующей таблице. A B C D E F G A - 5 2 4 1 6 3 B 5 - 4 6 3 8 7 C 2 4 - 5 8 3 1 D 4 6 5 - 2 7 8 E 1 3 8 2 - 4 6 F 6 8 3 7 4 - 5 G 3 7 1 8 6 5 - Необходимо построить замкнутый маршрут, проходящий через все города по одному разу, стоимость перелёта по которому была бы минимально возможной. В ответе укажите какую-то перестановку из 7 букв A, B, C, D, E, F, G в том порядке, в котором вы будете посещать города. Каждая буква должна встречаться ровно по одному разу. Чем короче будет найденный вами маршрут, тем больше баллов вы получите. Обратите внимание, при расчёте стоимости маршрута также учитывается перелёт из последнего города вашего ответа в первый город. Путешествие Данис живёт на клетчатой плоскости и может перемещаться по плоскости в одном из четырёх направлений: направо, налево, вверх, вниз. За один шаг он перемещается на единицу длины. Ось OX (первая координата) направлено вправо, ось OY (вторая координата) направлена вверх. Данис начинает путь в точке (0; 0). Например, если он выполнит четыре команды перемещения «направо», «вниз», «налево», «вверх», то посетит следующие точки: (1; 0), (1; -1), (0; -1), (0; 0). Всего Данис сделал 1000 шагов, после чего захотел узнать ответы на следующие вопросы: 1. Сколько раз Данис прошёл через точку (-11; 9)? 2. Какое количество различных точек посетил Данис? 3. В какой точке Данис побывал больше всего раз? В ответе координаты разделяйте пробелом. 4. Какая посещённая им точка находится ближе всего к точке (10; 6)? Расстоянием между точками считается количество ходов, которые нужно сделать для того, чтобы попасть из одной точки в другую, то есть так называемое «манхэттенское расстояние». В ответе координаты разделяйте пробелом. Для выполнения задания вы можете использовать электронные таблицы из офисного пакета или любые другие средства вашего компьютера. Вы можете скачать файл с данными для выполнения этого задания в одном из двух форматов: Microsoft Excel (XLSX)data.xlsx LibreOffice Calc (ODS) data.ods. В этой таблице в единственном столбце с данными A содержится последовательность перемещений Даниса. В ответе запишите четыре строки: ответы на четыре вопроса. В первой и второй строке должно быть по одному целому числу, в третьей и четвёртой строке - по два целых числа, через пробел (координаты точек). Если вы не знаете ответ на какой-нибудь вопрос, запишите вместо него любое число или любую точку (два числа). Качели Трое друзей — Аня, Боря и Саша — пришли на детскую площадку, чтобы покачаться на качелях-балансире. Качели представляют собой длинную балку, закреплённую в центре, на которую дети садятся с разных концов. Массы детей равны A , B и C кг. Чтобы держать баланс на качелях, разница масс на двух концах качелей должна быть не более D кг. Друзьям повезло: рядом с площадкой оказалась груда достаточно тяжёлых камней. Один из детей может взять с собой любой камень, чтобы сделать разность масс на концах качелей допустимой. Помогите друзьям определить минимальную массу камня, благодаря которому они смогут покачаться на качелях. Условия выполнения Правила автоматической проверки Ограничения: Время выполнения: < 500 ms Выделяемая память 256 mb Входные данные Программа получает на вход три числа A , B , C , записанных в отдельных строках, — массы друзей. В четвёртой строке записано число D — наибольшая допустимая разница масс на концах качелей. Все числа — целые, положительные и не превосходящие 10 9 . Выходные данные Программа должна вывести одно целое число — минимальную необходимую массу камня, которую нужно добавить на одну из сторон качелей, чтобы друзья смогли покачаться на них, сев оптимально. Если камень им не понадобится, программа должна вывести число 0 . Система оценки Решения, правильно работающие, когда все входные числа не превосходят 10 5 , будут оцениваться в 40 баллов. Примечание: В первом примере Аня и Саша сядут на одну сторону, их суммарная масса будет равна 65 кг. На другую сторону сядет Боря, взяв 15-килограммовый камень, тогда масса Бори с камнем составит 55 кг. Разница весов на концах качелей примет значение 10 кг. Во втором примере Аня и Боря сядут на одну сторону (50 кг), Саша — на другую сторону (45 кг). Разница весов будет равна 5 кг, поэтому камень не понадобится. Примеры № Входные данные Выходные данные Примечание 1 30 40 35 10 15 2 30 20 45 10 0 Фонари Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины. Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на расстоянии Y (включительно). В частности, при X=0 или Y=0 такой фонарь освещает только тот дом, у которого он установлен. Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно. Условия выполнения Правила автоматической проверки Ограничения: Время выполнения: < 1000 ms Выделяемая память 256 mb Входные данные Первая строка входных данных содержит целое число N ( 1≤N≤10 5 ). Следующие четыре строки содержат целые неотрицательные числа A , X , B и Y соответственно, которые не превосходят 10 5 . Выходные данные Программа должна вывести столько строк, сколько фонарей необходимо установить. Каждая строка должна содержать два целых числа через пробел — координату фонаря и расстояние, которое он освещает (то есть одно из чисел X или Y ). Координаты представляют из себя целые числа от 1 до N , рядом с каждым домом можно поставить только один фонарь. При наличии нескольких правильных ответов можно вывести любой из них. Если ответа не существует, программа должна вывести одно число −1 . Система оценки Решения, правильно работающие при A=0 или B=0 , будут оцениваться в 30 баллов. Решения, правильно работающие при A  =0 , B  =0 , n≤1000 , будут оцениваться в 40 баллов. Примечание: В ответе к первому примеру фонарь у дома 2 освещает также дома 1 и 3, фонарь у дома 5 — также дома 3, 4, 6 и 7, а фонарь у дома 9 — также дома 8 и 10. В результате все дома освещены. Во втором примере фонарей недостаточно. Примеры № Входные данные Выходные данные Примечание 1 10 3 1 1 2 2 1 5 2 9 1 2 10 1 1 1 2 -1 Деление шоколадки У Маши есть прямоугольная шоколадка, состоящая из m×n квадратных долек. Маша хочет разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на k кусочков, то есть каждому другу достанется прямоугольный кусочек шоколадки. У Юры сегодня день рождения, поэтому Маша хочет разделить шоколадку так, чтобы Юре достался самый большой кусок (содержащий как можно больше долек). Определите число долек в этом куске. Условия выполнения Правила автоматической проверки Ограничения: Время выполнения: < 1000 ms Выделяемая память 256 mb Входные данные Программа получает на вход три натуральных числа, каждое в отдельной строке: m , n и k . Все числа — целые положительные, при этом m и n не превосходят 10 6 , а k≤mn . Обратите внимание на то, что значение mn , а, значит, и значение k в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). Выходные данные Программа должна вывести одно целое число — максимально возможное количество долек в том прямоугольном куске, который получит Юра. Система оценки Решения, правильно работающие при m≤1000 и n≤1000 , будут оцениваться в 60 баллов. Примечание: В примере из условия нужно разделить шоколадку 4×5 на 4 кусочка. Самый большой кусочек будет состоять из 16 долек, как показано на картинке. Примеры № Входные данные Выходные данные Примечание 1 4 5 4 16