Вчера был на олимпиаде по програмированию вот все задаче сделал токо вот эту не могу ((((она в прикрепленном файле) Подскажыте сам алгоритм ее решения... А то у меня почти ни каких соображений по этому поводу нету((( Есть матрица : 1 1 3 5 1 3 3 2 0 3 3 0 3 2 3 3 3 3 1 1 Каждая сторока,столбец,диагональ расматриваються как 5 цифр составляющие простое число. Сторки, диагонали(обе) читаються слева на право. Столбцы сверху вних. (------------------------------------------------------------------------------------------------------------) Во входном файле in.txt два числа: Сумма цифр в простых числах и заданая цыфра вверхнем левом углу матрицы. Числа розделены пробелом или символом конца сроки. Для заданых исходных данных есть всегда хотя бы одно решение. (-----------------------------------------------------------------------------------------------) Пример входние данные: 11 1 В файл out.txt для каждого найденого варианта решения записать 5 строк искомой матрицы, каждая из которых содержыт 5-значное простое число. Вот пример выходных данных , если входные данные 11-сумма цифр, 1 - число в левом верхнем углу матр. 1 1 3 5 1 1 4 0 3 3 3 0 3 2 3 5 3 2 0 1 1 3 3 1 3 1 1 3 5 1 3 3 2 0 3 3 0 3 2 3 1 4 0 3 3 3 3 3 1 1 1 3 3 1 3 1 3 0 4 3 3 2 3 0 3 5 0 2 3 1 1 3 3 3 1 (-----------------------------------------------------------------------------------------------------------) Требования и ограничения: 1.Простые числа в строках,столбцах,диагоналях должны иметь одинакомую сумму(например 11) 2.Матр. может содержать одинаковые простые числа. 3.Вслучаии нескольких вариантов решения выдать все. 4.Простое число не может начинаться с 0(00003 не являеться простым 5-значним числом)
1. Найти все 5-значные простые числа с заданной суммой цифр. 2. Перебрать все возможные квадраты из этих чисел.
Вариантов для перебора и не так много. Все пятизначные простые числа с заданной суммой чисел, можно заранее найти, их достаточно мало, что матрицу в лоб искать: count(4)=4 count(5)=12 count(7)=28 count(8)=45 count(10)=95 count(11)=143 count(13)=236 count(14)=272 count(16)=411 count(17)=479 count(19)=630 count(20)=664 count(22)=742 count(23)=757 count(25)=741 count(26)=706 count(28)=580 count(29)=528 count(31)=379 count(32)=341 count(34)=205 count(35)=166 count(37)=84 count(38)=62 count(40)=34 count(41)=13 count(43)=4 count(44)=2
делаем список, как писал Proteus, для ускорения можно сразу и повыделять разряды. кроме того делаем булевый массив по количеству чисел вообще, от минимального и до максимального используемого простого. в позиции используемых простых отмечаем. после - просто перебираем, скажем только ряды. по рядам вычисляем колонки и диагонали и сразу проверяем на подходящесть по булевому массиву. все должно быть достаточно быстро
