Простые задачи на перебор


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 33366. Список делителей - 02
Темы: Простые задачи на перебор   

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [289039; 311993] числа,  у которых ровно 8 различных натуральных делителей, не считая 1 и самого числа. Для каждого найденного числа выведите эти 8 делителей с новой строки в порядке возрастания суммы этих 8 делителей. Делители должны следовать в порядке возрастания.

ID 33367. Список делителей - 03
Темы: Простые задачи на перебор   

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [108933; 132757] числа, у которых ровно 2 различных натуральных делителя, не считая 1 и самого числа. Для каждого найденного числа выведите эти 2 делителя с новой строки в порядке возрастания произведения этих 2 делителей. Делители должны следовать в порядке возрастания.

ID 33368. Список делителей - 04
Темы: Простые задачи на перебор   

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [102438; 124698] числа, у которых ровно 7 различных натуральных делителей, не считая 1 и самого числа. Для каждого найденного числа выведите эти 7 делителей с новой строки в порядке возрастания произведения этих 7 делителей. Делители должны следовать в порядке возрастания.

ID 38234. Список простых - 01
Темы: Простые задачи на перебор   

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [2385177; 2385437] простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку (каждое число с номером выводите с новой строки). 

ID 38334. Простой квадрат
Темы: Простые задачи на перебор    Перебор   

У Пети имеется игровое поле размером 33, заполненное числами от 1 до 9. В начале игры он может поставить фишку в любую клетку поля. На каждом шаге игры разрешается перемещать фишку в любую соседнюю по стороне клетку, но не разрешается посещать одну и ту же клетку дважды. Петя внимательно ведет протокол игры, записывая в него цифры в том порядке, в котором фишка посещала клетки. Пете стало интересно, какое максимальное число он может получить в протоколе. Помогите ему ответить на этот вопрос.

Входные данные
Входной файл содержит описание поля — 3 строки по 3 целых числа, разделенных пробелами. Гарантируется, что все девять чисел различны и лежат в диапазоне от 1 до 9.

Выходные данные
Выведите одно целое число — максимальное число, которое могло получиться в протоколе при игре на данном поле.

Ответ можно выводить не в виде числа, а в виде строки или в виде последовательности отдельных цифр (но не разделяя их пробелами).

Примеры
Входные данные Выходные данные
1 1 2 3
4 5 6
7 8 9
987456321

ID 38435. Раскопки
Темы: Простые задачи на перебор   

Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них. После долгих исследований ученые пришли к выводу, что надписи на них на самом деле могли быть обычными числовыми равенствами. Если бы этот вывод оказался верным, это доказало бы не только то, что на Марсе много лет назад были разумные существа, но и то, что они уже умели считать…
Ученые смогли понять, что в этом случае означают найденные символы, и перевели эти равенства на обычный язык — язык цифр, скобок, знаков арифметических действий и равенства. Кроме того, из других источников было получено веское доказательство того, что марсиане знали только три операции — сложение, умножение и вычитание (марсиане никогда не использовали “унарный минус”: вместо “–5” они писали “0–5”). Также ученые доказали, что марсиане не наделяли операции разным приоритетом, а просто вычисляли выражения (если в них не было скобок) слева направо: например, 3 + 3*5 у них равнялось 30, а не 18.
К сожалению, символы арифметических действий марсиане почему-то наносили специальными чернилами, которые, как оказалось, были не очень стойкими, и поэтому в найденных листках между числами вместо знаков действий были пробелы. Если вся вышеизложенная теория верна, то вместо этих пробелов можно поставить знаки сложения, вычитания и умножения так, чтобы равенства стали верными. Например, если был найден лист бумаги с надписью “18=7 (5 3) 2”, то возможна такая расстановка знаков: “18=7+(5–3)*2” (помните про то, в каком порядке марсиане вычисляют выражения!). В то же время, если попался лист с надписью “5=3 3”, то марсиане явно не имели в виду числового равенства, когда писали это…
Вы должны написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует.

Формат входных данных
Первая строка входного файла состоит из натурального (целого положительного) числа, не превосходящего 230, знака равенства, и последовательности натуральных чисел (не более десяти), произведение которых также не превосходит 230. Некоторые группы чисел (одно или более) могут быть окружены скобками. Длина входной строки не будет превосходить 80 символов, и других ограничений на количество и вложенность скобок нет. Между двумя соседними числами, не разделенными скобками, всегда будет хотя бы один пробел, во всех остальных местах может быть любое (в том числе и 0) число пробелов (естественно, внутри числа пробелов нет).

Формат выходных данных
В выходной файл необходимо вывести одну строку, содержащую полученное равенство (т.е., исходное равенство со вставленными знаками арифметических действий). В случае если требуемая расстановка знаков невозможна, вывести строку, состоящую из единственного числа “–1”. Выходная строка не должна содержать пробелов.
 

Примеры
Входные данные Выходные данные
1 18=7 (5 3) 2 18=7+(5–3)*2
2   5= 3 3 -1

ID 38587. Алмазные Черепашки
Темы: Простые задачи на перебор    Цикл for   

Весельчак У любит дарить алмазных черепашек. У него в сумке лежат черепашки либо трех цветов: розовый, белый и зеленый, либо четырех цветов: розовый, белый, зеленый и желтый. Он по очереди дарил черепашек из сумки, цвет i-й черепашки был Si. Цвета представлены следующим образом: - розовый, W - белый, G - зеленый, Y - желтый. Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four

Входные данные
В первой строке записано число N (\(1<=N<=100\)) - количество Черепашек, которое вынимал Весельчак У. Во второй строке содержатся N символов Si - цвета, вынимаемых черепашек. Каждый символ Si равен P, W, G или Y. Всегда существуют такие i, j и k, что Si = 'P', Sj = 'W' и Sk = 'G'.

Выходные данные
Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four

 

Примеры
Входные данные Выходные данные
1 6
G W Y P Y W
Four
2 9
G W W G P W P G G
Three
3 8
P Y W G Y W Y Y
Four

ID 38618. Теорема Лагранжа
Темы: Простые задачи на перебор   

Теорема Лагранжа утверждает, что любое натуральное число можно представить в виде суммы четырех точных квадратов. По данному числу n найдите такое представление: напечатайте от 1 до 4 натуральных чисел, квадраты которых дают в сумме данное число.

Входные данные
Программа получает на вход одно натуральное число n < 10000.

Выходные данные
Программа должна вывести от 1 до 4 натуральных чисел, квадраты которых дают в сумме данное число.

Примеры
Входные данные Выходные данные
1 3 1 1 1
2 7 2 1 1 1

ID 38620. Сумма двух кубов
Темы: Простые задачи на перебор   

Представьте данное число n в виде суммы двух кубов.

Входные данные
Программа получает на вход одно натуральное число n (n <= 1028).

Выходные данные
Программа должна вывести 2 целых неотрицательных числа (в порядке убывания), сумма кубов которых равна n. Если это невозможно, выведите строку impossible.
 

Примеры
Входные данные Выходные данные
1 9 2 1
2 3 impossible

ID 38632. Издевательство
Темы: Способы задания графа    Простые задачи на перебор   

Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
 - Издевается! - подумал Борман.
 - Кольцевая! - догадался Штирлиц.


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

Естественно, что Штирлицу хочется проезжать мимо точки, в которой, как он воображает, стоит Борман, как можно чаще. Для этого, естественно, выбранный Штирлицем маршрут должен быть как можно короче. Напишите программу, которая выберет оптимальный для Штирлица маршрут.

Входные данные
В первой строке задается  число N (3 <= N <= 100). В последующих строках содержится матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

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

Примеры
Входные данные Выходные данные
1 5
0 1 9 9 2
1 0 9 9 9
9 9 0 9 9
9 9 9 0 9
2 9 9 9 0
1 2 5

ID 38653. Множество формул
Темы: Простые задачи на перебор    Строки   

Вам дана строка S, состоящая из цифр от 1 до 9 включительно. Вы можете вставить символ + в некоторые позиции (возможно, ни в одну) между двумя цифрами в этой строке. Здесь знак + не должен появляться последовательно после вставки (т.е. не должно быть два и больше знака подряд). Все строки, которые можно получить таким образом, можно оценить как формулы. Оцените все возможные формулы и распечатайте сумму результатов, полученных при вычислении всех возможных формул.

Входные данные
На вход подается непустая строка S, состоящая из цифр от 1 до 9 включительно. Длина строки не более 10 символов.

Выходные данные
Выведите сумму результатов, полученных при вычислении всех возможных формул.
 

 

Примеры
Входные данные Выходные данные Пояснение
1 125 176 Всего можно получить 4 формулы: 125, 1 + 25, 12 + 5 и 1 + 2 + 5.
Результат после вычисления каждой формулы:
125
1 + 25 = 26
12 + 5 = 17
1 + 2 + 5 = 8
Таким образом, сумма 125 + 26 + 17 + 8 = 176.
2 9999999999 12656242944  

 

ID 38795. Уравнение по возрастанию
Темы: Простые задачи на перебор   

Дана функция \(z(x) = ax^3 + bx^2 + cx + d\). Для заданных чисел a, b, c и d, выведите все целые значения x из диапазона от 0 до 1000, при которых функция z(x) принимает нулевое значение.

Входные данные
Программа получает на вход 4 числа: a, b, c и d. Каждое число записано в отдельной строке.

Выходные данные
Выведите все значение x, которые удовлетворяют условию задачи в порядке возрастания. 
 

Примеры
Входные данные Выходные данные
1 1
-5
6
0
0 2 3

ID 18728. Троллейбусы
Темы: Вложенные циклы    Простые задачи на перебор   

Троллейбусы одного маршрута проходят через остановку каждые k (1<=k<=500) минут. Известны времена прихода пассажиров на эту остановку. Если пассажир приходит на остановку в момент прихода троллейбуса, то он успевает уехать на нем.
 
Напишите программу, которая бы определяла, во сколько должен пройти первый троллейбус (это время от 0 до k-1), чтобы:
1) Суммарное время ожидания троллейбуса для всех пассажиров было минимально.
2) Максимальное из времен ожидания троллейбуса было минимально.
 
Входные данные
В строке записано сначала число k, затем - число N (0<=N<=100000). Затем идет N чисел, задающих времена прихода пассажиров 
на остановку. Каждое из этих чисел - целое от 0 до 100000.
 
Выходные данные
Запишите два числа, являющиеся ответами на первый и второй вопросы задачи соответственно. 
Если решений несколько, выведите любое из них.

Примеры
Входные данные Выходные данные
1
100 5
0 210 99 551 99
10
51
 
 

ID 38919. Раскраска в три цвета
Темы: Обход в глубину    Простые задачи на перебор   

Петя нарисовал на бумаге n кружков и соединил некоторые пары кружков линиями. После этого он раскрасил каждый кружок в один из трех цветов – красный, синий или зеленый.

Теперь Петя хочет изменить их раскраску. А именно – он хочет перекрасить каждый кружок в некоторый другой цвет так, чтобы никакие два кружка одного цвета не были соединены линией. При этом он хочет обязательно перекрасить каждый кружок, а перекрашивать кружок в тот же цвет, в который он был раскрашен исходно, не разрешается.

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

Входные данные
В первой строке вводятся два целых числа n и m – количество кружков и количество линий, которые нарисовал Петя, соответственно (1 ≤ n ≤ 1 000, 0 ≤ m ≤ 20 000).
Следующая строка содержит n символов из множества {'R', 'G', 'B'} – i-й из этих символов означает цвет, в который раскрашен i-й кружок ('R' – красный, 'G' – зеленый, 'B' – синий).
Далее в m строках задается по два целых числа – пары кружков, соединенных отрезками.

Выходные данные
Выведите  одну строку, состоящую из n символов из множества {'R', 'G', 'B'} – цвета кружков после перекраски. Если решений несколько, выведите любое.
Если решения не существует, выведите  слово "Impossible''.
 

Примеры
Входные данные Выходные данные
1 4 5
RRRG
1 3
1 4
3 4
2 4
2 3
BBGR
2 4 5
RGRR
1 3
1 4
3 4
2 4
2 3
Impossible

ID 39387. Королевское путешествие
Темы: Гамильтонов цикл    Гамильтонов цикл    Простые задачи на перебор   

Его Величество Король Бубей Второй пожелал объехать свои владения. При этом к маршруту есть следующие пожелания:

1) маршрут должен занимать наименьшее возможное время (королевское время – вещь очень ценная и его надо беречь);

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

3) маршрут должен начинаться и заканчиваться в столице государства (объехав свои владения, король должен сразу приступить к делам). Столица входит в маршрут ровно 2 раза: как пункт отбытия и как пункт назначения, она не может являться промежуточным населенным пунктом маршрута.

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

Входные данные
сначала вводится число N (натуральное, не превышает 10) – количество населенных пунктов королевства. Затем следует N строк по N чисел в каждой – время пути между населенными пунктами (время – целое неотрицательное число, не превышает 500; если время = 0, то это означает, что пути между какими-то населенными пунктами нет). Населенный пункт №1 является столицей государства.

Выходные данные
выведите наименьшее суммарное время, которое Его Величество потратит на объезд своих владений, или число -1, если построить маршрут с заданными свойствами невозможно.

Примеры
Входные данные Выходные данные
1 1
0
0
2 2
0 1
1 0
2
3 2
0 85 
85 0 
170

ID 39390. Социальное дистанцирование I
Темы: Разбор случаев    Условный оператор    Простые задачи на перебор   

Ужасная болезнь поражает коров. Фермер Джон хочет их защитить.
Амбар ФД - это узкое длинное здание, содержащее N стойл в ряд (2≤N≤105). Некоторые из этих стойл уже заняты коровами, некоторые - свободны. Прочитав о необходимости социального дистанцирования, ФД хочет максимизировать D, где D, это расстояние между двумя ближайшими занятыми стойлами. Например, если стойла 3 и 8 ближайшие, которые заняты, тогда D=5.

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

Входные данные
Первая строка ввода содержит N. Следующая строка содержит строку длиной N из 0 и 1, описывающая последовательность стойл в амбаре. 0 означает пустое стойло, 1 означает занятое стойло. В строке имеется как минимум два нуля, что достаточно для размещения двух коров.
Выходные данные
Выведите наибольше значение D (наименьшее расстояние между двумя занятыми стойлами), которое ФД может получить добавлением двух новых коров оптимальным образом.

Примеры
Входные данные Выходные данные  
1 14
10001001000010
2 В этом примере ФД может добавить коров так: 10x010010x0010 где x показывает новых коров. В этом случае D=2. Невозможно разметить коров так, чтобы получить D больше.