Тесты и результаты. [831] В магазине имеются гири массой m1, m2,, mk, при этом ровно две гири каждой массы

1) 18, 389, 20, 64, 24, 25; n=6; k=3; t=3. 938+18+24+20=1000.

2) 65, 10, 31, 586, 24, 35, 36; n=7; k=4; t=3. 865+36+24+10+65=1090.

[831] В магазине имеются гири массой m1, m2,..., mk, при этом ровно две гири каждой массы. Найдите все способы, которыми можно взвесить данную массу m0.

[832] Имеется k гирь с массами ml, m2,..., mk. Напечатайте все, массы, которые можно взвесить при помощи данных гирь, пронумеровав полученные массы в порядке возрастания. Гири можно класть только на одну чашку.

[833] Даны k чисел. Выделите из них группы, содержащие от 1 до k элементов, каждая из которых имеет суммой число, содержащее в своем двоичном разложении только одни единицы.

Тест. 2, 5, 10, 8, 16, 41, 22.

Результат. 2+5=7; 5+10=15; 5+10+16=31; 41+22=63;...

[834] Распечатайте все различные тройки элементов одномерно­го массива, если в данном массиве могут быть одинаковые элементы.

Третий уровень

[835] Задан массив A(N), заполненный всеми натуральными числами от 1 до N. Напечатайте все перестановки этих чисел в таком порядке, чтобы каждая следующая получалась из предыдущей пе­рестановкой ровно двух чисел.

[836] Задан массив A(N), заполненный всеми натуральными чис­лами от 1 до N. Напечатайте все перестановки этих чисел в таком порядке, чтобы каждая следующая получалась из предыдущей пе­рестановкой двух соседних чисел.

[837] Даны k натуральных чисел. В большем из них разрешается произвольным образом переставлять цифры. К образовавшемуся числу любым способом слева и справа дописываются все осталь­ные. Получившаяся запись состоит из нескольких чисел, записан­ных подряд. Найдите все палиндромы, которые можно получить в результате.

Тесты. 1) 7622, 3, 37; 2) 1, 9825, 1982.

Результаты. 1) 37, 2627, 3; 2) 1982, 5289, 1.

[838] Даны два числа k и n. Количество цифр в них неизвестно. В каждом из них произвольно переставили цифры и сложили резуль­таты. Найдите все случаи, когда полученные суммы делятся на 131.

Тест. 145, 3546.

Результат. 1) 415+4563; 2) 145+3654; 3) 154+3645; 4) 514+5643.

[839] Дано натуральное число k. Число цифр в нем неизвестно. Найдите такую перестановку его цифр, чтобы полученное число в пятеричной системе счисления состояло только из одинаковых цифр.

Тест. 6125. Результат. 1562=22222₅.

[840] Массив содержит 100 целых чисел. Найдите в этом массиве k чисел, где 1< =k< =100, сумма которых нацело делится на 100. Дос­таточно найти лишь одно множество из k чисел.

[841] Имеются n гирь массой m1, m2,...mn и k предметов массой p1, p2,...pk. Какие группы предметов можно взвесить, если гири можно класть только на одну чашку весов, а предметы только на другую?

[842] В романе n глав, в i-й главе Ai страниц. Требуется издать роман в k томах так, чтобы объем самого большого тома был мини­мален. Определите, каким будет толщина самого толсто! 'о тома, ес­ли делить главы по разным томам нельзя.

[843] У покупателя k монет достоинством p1< =p2< =...< =pk, а у продавца s монет достоинством r1< =r2< =…< =rs. Какова максималь­ная стоимость книги, если она по средствам покупателю, но он не может ее купить из-за отсутствия сдачи у продавца.

[844] " Точные квадраты". Из цифр данного натурального числа n нужно образовать всевозможные комбинации. При этом каждая цифра берется не более k раз, если в данном числе она встречается k раз. Не обязательно использовать вес цифры. Порядок расположе­ния может отличаться от порядка цифр данного числа. Получите, таким образом, все числа, являющиеся точными квадратами

Тест. n=462341.

Результат. Получаем точные квадраты: 1, 4, 16, 36, 144, 441, 361, 1236.

[845] Школьники изучают 10 предметов двух циклов, Первый цикл: математика, физика, информатика, химия, биология. Второй цикл: физкультура, ОБЖ, музыка, литература, история. При состав­лении расписания предметы двух циклов строго чередуются: один урок первого цикла, другой - второго. В данный день не включают­ся два предмета - х и у. Учебный день должен содержать n уроков. Из них первый - z, последний -t. Составьте все возможные расписа­ния данного учебного дня и подсчитайте количество различных ва­риантов расписания.

[846] Имеются элементы, которые можно расположить в n ячей­ках на плате. Число соединений между парами элементов задается матрицей С, в которой C(i, j) - число связей между i-м и j-м элемен­тами. Расстояние между парами ячеек задается матрицей D, в кото­рой D(k, 1) - расстояние между k-й и 1-й ячейками. Таким образом, в терминах общей длины использование провода при размещении i-го элемента в k-й ячейке и j-го элемента в 1-й ячейке стоит C(i, j)*D(k, l). В каждой ячейке можно разместить только один элемент, и каждый элемент можно разместить только в одной ячейке. Найдите разме­щение элементов в ячейках, соответствующее наименьшей длине использованного провода.1

[847] Спортсмены на старте имеют номера 1, 2, 3,..., n. Первым стартует спортсмен с номером k. В дальнейшем за спортсменом с простым номером стартует спортсмен с составным номером, и на­оборот: спортсмен с номером 1 может стартовать в любом месте за любым спортсменом. Выдайте на печать все варианты последова­тельности стартов и количество их возможных вариантов.

[848] Напечатайте все представления заданного натурального числа суммой натуральных чисел. Суммы, различающиеся поряд­ком слагаемых, считают одинаковыми.

[849] Напечатайте все представления заданного натурального числа k суммой натуральных чисел. Количество слагаемых равно n; n< k. Суммы, различающиеся порядком слагаемых, считают одина­ковыми.

[850] Если рассмотреть числа от 0 до 2^n-1, переводя каждое из них в двоичную систему счисления, то можно получить все сочета­ния из n элементов по О, 1, 2,..., n; при этом единицы указывают, ка­кие элементы входят в данную группу. Распечатайте числа и их двоичные представления, указывая в скобках, какому виду сочета­ний соответствует данное двоичное представление. Результат дол­жен быть представлен по образцу, приведенному в примере.

Например, n=5.

0) 00000 [0]; 1)00001 [1]; 2) 00010 [1]; 3)00011 [2];

4) 00100 [1]; 5) 00101 [2]; 6) 00110 [2]; 7) 00111 [3];

8) 01000 [1]; 9) 01001 [2]: 10) 01010 [2]; 11)01011 [3];

12)01100 [2]; 13) 01101 [3]; 14) 01110 [3]; 15) 01111 [4];

16)10000 [1]; 17) 10001 [2]; 18) 10010 [2]; 19) 10011 [3];

20)10100 [2]; 21) 10101 [3]; 22) 10110 [3]; 23) 10111 [4];

24)11000 [2]; 25) 11001 [3]; 26) 11010 [3]; 27) 11011 [4];

28)11100 [3]; 29) 11101 [4]; 30) 11110 [4]; 31)11111 [5].

1+5+10+10+5+7=32.

Г Р А Ф Ы.

Первый уровень

[851] Найдите вершину графа, из которой выходит наибольшее число ребер.

[852] Найдите вершину графа, у которой наибольшая сумма длин ребер, выходящих из этой вершины.

[853] Упорядочите ребра графа по возрастанию цен ребер. В ре­зультате укажите цену и через тире - номер вершин, которые содер­жат данное ребро.

[854] Упорядочите вершины графа по возрастанию количества ребер, выходящих из этой вершины. Результат дайте в следующем виде: номер вершины и рядом (в круглых скобках) число, выра­жающее количество выходящих из этой вершины ребер.

Второй уровень

[855] Найдите три вершины графа такие, чтобы сумма цен связы­вающих их ребер была максимальна.

[856] Имеется семь городов, соединенных некоторой сетью до­рог. В каком городе необходимо провести конференцию так, чтобы суммарный путь всех делегатов, по одному из каждого города, был минимален.

[857] Удалите одно ребро графа таким образом, чтобы получи­лись два не связных между собой графа.

Третий уровень

[858] Найдите кратчайший путь от данного источника графа до любой конечной точки, используя алгоритм Форда-Беллмана.

[859] Найдите кратчайшее расстояние от вершины S графа до вершины Р, если при этом нужно пройти через вершину Q.

[860] В данном графе найдите кратчайший путь от вершины А до вершины В, если заходить в вершину С нельзя.

[861] Дан граф. Найдите кратчайшее расстояние от вершины NA до вершины KON, если при этом нужно пройти через вершины Р и Q.

[862] Пусть сумма кратчайших расстояний от источника S до всех остальных вершин графа будет равна SUM. Определите вершину, которая, будучи источником, имеет наименьшее значение SUM.

[863] Несколько городов соединены сетью дорог, заданной в виде графа. В каждом городе машина может дозаправиться некото­рым, постоянным для данного города, объемом горючего. Единица заправки соответствует единице расстояния. Найдите путь из ука­занного города, позволяющий обойти наибольшее число городов, если известен объем заправка в каждом городе.

[864] " Селения". Имеется k селений. Если в селении i располо­жить пункт скорой помощи, то поездка в селение j займет время А(i, j)+A(i, j) где (1< =i, j< =k). Найдите номер селения i, от которого поездка в самое удаленное селение (по времени) заняла бы мини­мальное время. Массив A(k, k) задан. В нем все A(i, J)> 0, и элемент A(i, J) может быть не равен элементу A(J, i).

[865] Пусть n - количество вершин графа. Найдите самый нужный путь от заданного источника S до конечной вершины KON за количество шаговое превышающее n-1. При этом разрешается лю­бое ребро проходить несколько раз.

[866] Найдите все возможные пути между двумя заданными вершинами графа и отметьте кратчайший путь между ними. Прохо­дить дважды через одну вершину нельзя.

[867] Найдите все возможные пути между тремя несмежными площадями и определите кратчайший путь между ними, если на­чальная и конечная точки движения совпадают.

[868] " Магазины в поселках". Построено k новых поселков, не­которые из которых соединены дорогами. Нужно построить мини­мальное количество магазинов в поселках так, чтобы из каждого поселка можно было добраться до магазина, проезжая не более од­ной дороги, и сумма длин дорог для всех поселков, необходимых для проезда в магазин, была минимальной.

[869] Найдите наименьший замкнутый путь в графе, проходя­щий через все вершины графа.

[870] Найдите наименьший замкнутый путь в графе, если при этом заходить в вершины A1, A2,...Ak запрещено, а в остальных нужно побывать только один раз.

[871] В трех вершинах графа нужно разместить три завода так, чтобы сумма минимальных расстояний до всех остальных вершин была минимальной.

[872] ] Дан неориентированный граф. Определите вершины, из которых можно дойти до любой другой вершины графа, минуя не более двух ребер графа.

[873] Дан неориентированный граф. Определите вершины, из которых можно дойти до любой другой вершины графа, минуя не более трех ребер графа.

[874] Дан неориентированный граф. Определите те вершины графа, из которых можно достичь любой другой вершины графа, проходя не более, чем два ребра, если дополнительно добавить еще одно ребро. Укажите недостающее ребро для каждого такого слу­чая.

[875] В данном графе найдите тройку вершин А1, А2, A3 такую, чтобы все три вершины A1, A2, A3 были бы попарно связаны реб­рами графа, причем сумма длин ребер А1А2, А1А3, А2А3 была бы минимальной среди всех троек вершин данного графа, которые по­парно связаны между собой. Аналогично найдите тройку вершин В1, В2, ВЗ с максимальной суммой длин ребер. Из тройки A1, A2, A3 выбирается вершина NA, противолежащая большему ребру " треугольника" А1А2АЗ, а из тройки вершин В1, В2, В3 выделяется вершина KON, противолежащая меньшему ребру " треугольника" В1В2ВЗ. Найдите кратчайший путь между вершинами NA и KON и длину этого пути.

[876] (По условию задачи 25). В " минимальном треугольнике" найдите вершину, в которой сходятся два самых коротких ребра этого " треугольника".

[877] (По условию задачи 25). В " максимальном треугольнике'' найдите вершину, в которой сходятся два самых длинных ребра ^то­го " треугольника".

[878] (По условию задачи 25). Сосчитайте в графе количество " треугольников", то есть таких троек вершин А, В, С, для которых имеются ребра АВ, АС, ВС.

[879] Сосчитайте в графе количество " четырехугольников", то есть таких четверок вершин А, В, С, D, что существует четыре " последовательных" ребра, например, ребра АВ, ВС, CD, DA. Вы­пишите вершины всех " четырехугольников" и найдите " четырехугольник" с максимальным и минимальным периметром.

[880] Сосчитайте в графе количество " мнимых четырехугольни­ков", то есть таких четверок вершин А, В, С, D, для которых суще­ствуют соединяющие их ребра такие, чтобы две любые вершины этой четверки были связаны между собой без участия других вер­шин. Выпишите вершины всех " мнимых четырехугольников" и найдите среди них " четырехугольник" с минимальным " периметром".

[881] " Раскраска вершин графа". Задан неориентированный граф. Необходимо раскрасить вершины в минимальное число цветов так, чтобы любые две соседние связанные вершины были рас­крашены в разные цвета.

[882] " Время встречи роботов". Пункты с номерами 1, 2,...n (n< =50) связаны сетью дорог, длины которых равны 1. Дороги про­ходят на разной высоте и пересекаются только в данных пунктах. В начальный момент времени 0 в некоторых пунктах находятся робо­ты, общее количество которых равно m (m=2 или m=3). Роботы на­чинают двигаться от пункта к пункту с постоянной скоростью неза­висимо друг от друга, меняя направление только в пунктах. Оста­новка роботов запрещена. Скорость i-ro робота равна 1 или 2. Робо­ты управляются таким образом, чтобы минимизировать время до встречи всех роботов в одном месте.

1) Требуется найти минимальное время t1, через которое может произойти встреча всех роботов в одном пункте, указать этот пункт или определить, что встреча всех m роботов в одном месте невоз­можна ни в какой момент времени (t> =0).

2) Если встреча возможна, то найдите время t2< =t1, через ко­торое встреча может произойти и вне пунктов.

3) Пусть роботам запрещена какая-либо остановка, а их ско­рость равна 1 или 2. При этих условиях найдите минимальное время 1, через которое произойдет встреча всех роботов в одном пункте, или сообщите, что встреча невозможна.

Вводится: n, m - связи между пунктами, скорости и пункты началь­ного расположения роботов.

Выводится: минимальное время и возможные пункты встречи, либо указание того, что встреча произойти не может.

[885] " Размещение заводов". Имеется k городов, связанных ме­жду собой сетью дорог. В них нужно разместить k заводов, выпус­кающих m1, m2,... mk продукции. Продукция, производимая заво­дом в данном пункте, поровну распределяется между данным пунк­том и всеми пунктами, которые имеют прямую дорогу связи с дан­ным. Как расположить заводы, чтобы минимизировать транспорт­ные расходы.

И Г Р Ы.

Первый уровень

[884] На экране написано несколько чисел. За один ход можно стереть любое количество чисел и записать вместо них их среднее арифметическое. Процесс закончится, когда останется одно число. Чтобы последнее число было максимальным, необходимо каждый раз стирать два наименьших числа и заменять их на среднее ариф­метическое.