Решение систем линейных уравнений Введение Цель изучения данного материала - научиться сводить задачи к системам линейных уравнений, решать системы линейных уравнений в вещественных числах, целых числах, произвольных подмножествах целых чисел (например, в двоичных переменных), проверять необходимые и достаточные условия существования решения систем линейных уравнений. 1. Примеры задач, которые сводятся к системам уравнений 1.1. Космолет марки ВАЗ Пятое личное первенство студентов УрГУ (28 февраля 2004 года) Задача D: Космолет марки ВАЗ input.txt / output.txt / 3 сек Общеизвестно , что космолет, оснащенный гипердвигателем класса B, способен выполнять переход с любой планеты на любую другую. Однако, на Вашем корабле марки ВАЗ-2106 (Вселенский Астромобильный Завод, цифры обозначают год начала выпуска), заклинило рычаг переключения коробки передач. В результате, корабль способен перемещаться с планеты с координатами (i,j) лишь на одну из планет из следующего списка: (i+q, j+p), (i-q, j+p), (i+q, j-p), (i-q, j-p), (i+p, j+q), (i-p, j+q), (i+p, j-q), (i-p, j-q) (все координаты - целочисленные, в стандартной межгалактической системе ). Помогите капитану Вашего корабля выяснить, сможет ли он своими силами добраться до планеты назначения, или ему следует вызывать ремонтную бригаду. Ввод В первой строке входного файла даны два числа p и q (передаточные числа первой гиперпередачи сломанного корабля), разделенные пробелами. Во второй строке находится пара чисел x и y - координаты планеты, на которой произошла поломка. В третьей строке находится пара чисел x1 и y1 - координаты планеты назначения. Числа во второй и третьей строках также разделены пробелами. Все числа целые, по модулю не превосходят 2*10^9. Вывод Если капитан cможет довести корабль до планеты назначения, в выходной файл следует выдать единственную строку со словом YES. Если же нужно вызывать ремонтную бригаду, в выходном файле должна находиться единственная строка со словом NO. Примеры input.txt input.txt 4 6 4 6 0 0 0 0 10 10 9 9 output.txt output.txt YES NO Формализация постановки задачи "Космолет марки ВАЗ" Для того чтобы добраться из точки (x,y) в точку (x1,y1) нам придется сделать сколько-то ходов каждого из типов: (q, p), (-q, p), (q, -p), (-q, -p), (p, q), (-p, q), (p, -q), (-p, -q) что соответствует следующей системе уравнений L1*p + L2*p - L3*p - L4*p + L5*q + L6*q - L7*q - L8*q = x1-x L1*q - L2*q + L3*q - L4*q + L5*p - L6*p + L7*p - L8*p = y1-y Здесь предположено, что сделано L1 ходов типа ( p, q) L2 ходов типа ( p,-q) L3 ходов типа (-p, q) L4 ходов типа (-p,-q) L5 ходов типа ( q, p) L6 ходов типа ( q,-p) L7 ходов типа (-q, p) L8 ходов типа (-q,-p) Здесь L1,L2, ..., L8 - неизвестные, каждая из которых может принимать значения 0,1,2 ... Это и есть система из ДВУХ линейных (неизвестные - в первой степени) диафантовых (решения - целые числа) уравнений с ВОСЕМЬЮ неизвестными. В задаче требуется ответить на вопрос - для заданных P и Q имеет ли такая система решение. 1.2. Company Southeastern European Regional Programming Contest Bucharest, Romania, October 21, 2000 Problem B. Company input.txt / output.txt / 10 sec A company pays different hourly wages for different job types. Each week the company keeps evidence of the total number of work hours for every job type and the total amount paid to all employees for that week. In different weeks different job types can be accomplished. The hourly wage for any job type in the same company remains unchanged. The hourly wage for any job type is a positive integer and the ratio between the maximum wage and the minimum wage is less than 6. You are asked to write a program that computes the hourly wage for every job type using the data collected a period of time (one or several weeks). The number of job types is limited to 200 and the number of weeks in one data set is limited to 50. The input file contains several data sets in text format. The format for the data set is: - The number of lines for the data set; - information_for__one_or_more_weeks The format of the information for a week is the following: job_type1 number_of _hours1 job_type2 number_of _hours2 job_type3 number_of _hours3 ::::: . total_paid ( the dot marks the ending of info for a week) The job type is represented as a string of characters (limited to 20). The number of hours is a positive integer (smaller than 1E5). The total paid is a positive integer (smaller than 2E10). The program should write to standard output (for every job type involved in the data set) a line containing the job type and the hourly wage. The output for a data set ends with a line containing a dot. If the program cannot compute a unique hourly wage for every job type it will print "Incomplete data" and if it cannot compute an integer hourly wage it will print "Inconsistent data" An example is given in the following table: input output 5 Incomplete data job1 6 . job2 5 job3 20 job8 4 job2 10 job10 3 job1 30 . 100 . 13 job3 1 job2 2 . 40 job1 3 job2 1 . 100 job1 1 job3 2 job2 3 . 100 job1 1 job2 5 . 80 Коротко условие задачи может быть переформулировано следующим образом. Задано M уравнений (соответствуют неделям в постановке задачи) и имеется N неизвестных (соответствуют работам(job) в постановке задачи). Требуется выяснить, имеет ли данная система уравнений решение в целых числах (если имеет - то вывести это решение), либо существует множество решений (тогда вывести текст Incomplete data) либо решенией нет (тогда вывести текст Insonsistent Data). Например, для примеров ввода: Пример 1: Ответ 6*job1 + 5*job2 + 8*job4 + 3*job10 = 100 Множество решений (Incomplete data) Пример 2 Ответ 1*job3 + 2*job2 = 40 job3 = 20 3*job1 + 1*job2 = 100 job2 = 10 1*job1 + 2*job3 + 3*job2 = 100 job1 = 30 5*job1 + 5*job2 = 80 1.3. Shift Register CENTRAL EUROPEAN OLYMPIAD IN INFORMATICS Munster, Germany, July 5-12, 2003, Day 2: Задача 2. Shift Register register.in/register.out/1.5s/16 MB Регистр компьютера хранит биты. Сдвиговый регистр - это специальный вид регистра, в котором биты легко могут быть сдвинуты на одну позицию. Используя сдвиговый регистр и обратную связь легко сгенерировать двоичные псевдо-случайные числа, следующим образом: Изначально сдвиговый регистр размера N заполняется величинами a1, a2, :, aN. Затем на каждом такте регистр выдвигает самый правый бит, все другие биты сдвигаются на одну позицию вправо, на первую (самую левую) позицию заносится бит в соответствии с правилами: - каждый бит регистра присоединен к элементу XOR через переключатель (смотри картинку ниже). Для каждого бита i, переключатель si может иметь значение 1 или 0, который определяет, отправляется ли значение ai соответствующего бита на элемент XOR или нет. Пусть ki = si * ai. Новое значение a1 самого левого бита - это выходное значение вентиля XOR (k1,k2,:,kN). Заметим, что если в k1,k2,:,kN количество единиц нечетное, то величина выхода с XOR равна 1, иначе - равно 0. Ниже приведены формальные определения: a1 = XOR (k1, ..., kN) ai = a(i-1) для 2<=i<=N Выход = aN ---------- a1 a2 a3 a4 a5 a6 a7 output | | 0 1 0 1 1 0 0 1 - | ------------- 1 0 1 0 1 1 0 0 1 | | XOR | 2 1 0 1 0 1 1 0 0 | ------------- 3 1 1 0 1 0 1 1 0 | ^ ^ ^ ^ ^ ^ ^ 4 0 1 1 0 1 0 1 1 | o o o o o o o 5 0 0 1 1 0 1 0 1 | | | | | | 6 1 0 0 1 1 0 1 0 | o o o o o o o 7 1 1 0 0 1 1 0 1 -->1 0 1 1 0 0 1 8 0 1 1 0 0 1 1 0 9 1 0 1 1 0 0 1 1 10 0 1 0 1 1 0 0 1 11 1 0 1 0 1 1 0 0 12 1 1 0 1 0 1 1 0 13 0 1 1 0 1 0 1 1 14 0 0 1 1 0 1 0 1 В примере выше, величина a1 в момент времени 1 вычисляется следующим образом : XOR (1*1,0*0,1*1,1*1,0*0,1*0,1*1) = 0 Вам даются первые 2*N выходных величин сдвигового регистра. Зная эти значения, Вы должны определить значения переключателей si. Вход Первая строка входного файла register.in содержит размер N сдвигового регистра (1<=N<=750). Вторая строка содержит 2N чисел 0 или 1, которые задают первые 2N выходных битов сдвигового регистра. Выход Выходной файл register.out содержит ровно одну строку. Если существует установка переключателей, которая обеспечивает такой вывод из сдвигового регистра, то выведите эти значения переключателей si, начиная с s1. Если такой установки переключателей не существует, выедите -1. Примеры register.in 7 1 0 0 1 1 0 1 0 1 1 0 0 1 1 register.out 1 0 1 1 0 1 1 register.in 3 0 0 0 1 1 1 register.out -1 Формальная постановка задачи Shift Register: Коротко переформулировать условия задачи можно следующим образом: даны первые 2*N выходных величин сдвигового регистра. Определить переключатели (множители) Si. Понятно, что первые N выходных значений - это фактически состояние регистра перед началом работы - в обратном порядке: a[n], a[n-1], ..., a[1]. А следующие N выходных значений - это фактически величины, вдвигавшиеся в регистр, в прямом порядке. Обозначим их v[1],v[2],...,v[n] Тогда для нахождения S[i] требуется решить систему уравнений: v[1] = s[1]*a[1] + s[2]*a[2] + ... + s[N]*a[N] v[2] = s[1]*v[1] + s[2]*a[1] + ... + s[N]*a[N-1] v[3] = s[1]*v[2] + s[2]*v[1] + ... + s[N]*a[N-2] ... v[N] = s[1]*v[N-1] + s[2]*v[N-2] + ... + s[N]*a[1] Здесь все величины могут принимать значение либо 0, либо 1. a[i] и v[i] заданы, требуется вычислить s[i]. 1.4. Системы уравнений Украинская олимпиада 2003 года, День 2, Задача 3 Задача 3. Система уравнений (100 баллов) Пусть k-ое уравнение системы из N уравнений имеет вид X+Y=bk, где X=x1k+x2k+...+xk-1 k; Y=xk k+1+...+xk N. Таким образом, левая часть каждого уравнения имеет (N-1)-но слагаемое и каждое неизвестное встречается ровно в двух уравнениях системы. Задание Напишите программу SYSTEM, которая по заданным b1,:,bN находит одно из решений системы, при условии что неизвестные xij могут принимать только значения 0 либо 1. Входные данные В первой строке входного файла SYSTEM.DAT находится натуральное число - количество тестовых блоков. Каждый тестовий блок начинается со строки, которая содержит число N (3<=N<=50) -количество уравнений в системе. Во второй строке блока находится N целых чисел bi (0<=bi<=50). Выходные данные Для каждого тестового блока в выходной файл SYSTEM.SOL должно быть записано одно из решений системи: (N-1)-на строка, каждая k-ая из которых содержит N-k чисел - найденных значений неизвестных: x12 ... x1N x23 ... x2N x34 ... x3N ... xN-1 N Если система не имеет решений для тестового блока, в выходной файл должна быть записана строка, которая содержит единственное число -1. Пример входных и выходных данных SYSTEM.DAT SYSTEM.SOL 2 -1 3 1 1 1 0 1 2 3 0 0 1 5 1 1 3 2 3 2 2 0 Формализация постановки задачи "Системы уравнений" может вглядеть следующим образом: требуется решать систему вида a11*x1 + a12*x2 + ... a1K*xK = b[1] a21*x1 + a22*x2 + ... a2K*xK = b[2] ... aN1*x1 + aN2*x2 + ... aNK*xK = b[N] Где Xi могут принимать значения только 0 и 1. K = (N-1) + (N-2) + ...+ 1 = (1+N-1)*(N-1)/2=N*(N-1)/2 Для удобства сопоставления с неизвестными в терминологии задачи они обозначаются с двумерными индексами x12, x13, ... , x[1,N-1] x23, ... , x[2,N-1] ... x[N-1,N] b[i] заданы - и могут быть произвольными целыми числами из интервала [0,50] Aij заданы, принимают значения только 0 и 1 При этом в построении Aij имеется определенная система которую можно проиллюстрировать значениями Aij для разных N: 121323 N=3 1 1 0 x12 + x13 = b1 1 0 1 x12 + + x23 = b2 0 1 1 x13 + x23 = b3 121314232434 N=4 1 1 1 0 0 0 x12 + x13 + x14 = b1 1 0 0 1 1 0 x12 + x23 + x24 = b2 0 1 0 1 0 1 x13 + x23 + x34 = b3 0 0 1 0 1 1 x14 + x24 + x34 = b4 12131415232425343545 N=5 1 1 1 1 0 0 0 0 0 0 x12 + x13 + x14 + x15 = b1 1 0 0 0 1 1 1 0 0 0 x12 + x23 + x24 + x25 = b2 0 1 0 0 1 0 0 1 1 0 x13 + x23 + x34 + x35 = b3 0 0 1 0 0 1 0 1 0 1 x14 + x24 + x34 + x45 = b4 0 0 0 1 0 0 1 0 1 1 x15 + x25 + x35 + x45 = b5 Можно заметить, что для получения новой матрицы (N+1) из N необходимо добавить к прежней сверху строку c N-1 единицами и остальными нулями (над каждым элементом прежней матрицы). А в левой части (под добавленными в первой строке единицами) разместить единичную матрицу (единицы по диагонали, остальные элементы - нули). 1.5. Sly Number South Eastern 2002 Problem #8: Sly Number sly.in / sly.out / 25 sec Let's consider so called "sly number" which is given as an array A of N integers from set {0,1,2}. For example A[0]=1, A[1]=1, A[2]=0 and A[3]=2. A sly number is called ONE, if A[0]=1 and A[I]=0 for I=1,2,:,N-1. Consider following operation with two sly numbers A and B called 'Star Multiplication': k N - 1 -- -- C[k] = > A[i] * B[k-i] + > A[i] * B[N+k-i]. -- -- i = 0 i = k + 1 here C - the result of the operation, even also presented in an array - not necessarily sly number. This operation we will denote by <*> symbol. Moreover, there is also module operation over the results of 'Star Multiplication': (C mod Q) [i] = C[i] mod Q, where Q is a positive integer. We are given a sly number A and a module Q. We need to find such 'inverse sly number' B: (A * B) mod Q = ONE. Input The input file contains K data sets in text format. The first line of this file contains the number K of test cases. Each test consists of two lines. First line contains two integers separated by spaces: Q (2 <= Q <= 100) and N (5 <= N <= 50). Second lin e contains N integers from set {0,1,2} separated by spaces, which present sly number A. Output It should contain K lines - one line for each test case. If a solution exists, the line should contain the string "A solution can be found". In case there is no solution, the line should consist of string 'No solution'. Example input: 2 2 5 1 0 1 0 1 65 8 1 2 2 2 1 1 2 2 Example output: A solution can be found No solution Формализация постановки задачи может быть выполнена следующим образом: Пусть a0, a1, ..., a[N-1] - заданный вектор x0, x2, ..., x[N-1] - это значения, которые нам нужно найти Тогда, в соответствии с условиями задачи они являются решениями такой системы уравнений: a0*x0 + a[n-1]*x1 + a[n-2]*x2 + ... + a1*x[n-1] = 1 (mod Q) a1*x0 + a0*x1 + a[n-1]*x2 + ... + a2*x[n-1] = 0 (mod Q) a2*x0 + a1*x1 + a0*x2 + ... + a3*x[n-1] = 0 (mod Q) ... a[n-1]*x0 + a[n-2]*x1 + a[n-3]*x2 + ... + a0*x[n-1] = 0 (mod Q) И в соответствии с уловиями задачи нам требуется ответить на вопрос имеет ли решение эта система при заданных N, a[i] и Q. При этом известно, что N<=50, 2<=Q<=100, a[i] могут принимать значения только 0, 1 или 2. И все x[i] должны быть также из множества чисел {0,1,2}. 1.6. Box of Mirrors Baltic Olympiad in Informatics, 2001, День 1 Задача 1. Box of Mirrors Математик Андрис любит различные головоломки и одна из самых его любимых головоломок - "ящик с зеркалами". Если мы посмотрим на такой ящик сверху, мы увидим, что его основание содержит n*m квадратных ячеек (n строк, m столбцов). В каждой ячейке может быть установлено зеркало, расположенное по диагонали ячейки - от ее левого нижнего угла к правому верхнему углу. Обе стороны зеркала отражают свет. По краям ящика (и вертикальным и горизонтальным) есть щель, через которую луч света может попасть в ящик или выйти из ящика. Через каждую такую щель луч может подаваться только в одном направлении - перпендикулярно ребру, содержащему щель. поэтому луч, отражаясь от зеркала изменяет свое направление на 90 градусов. Если луч проходит сквозь пустую ячейку, то он не меняет свое направление. Щели пронумерованы последовательно от 1 до 2*(n+m), вокруг ящика, против часовой стрелки, начиная с левой стороны самой верхней левой ячейки и вниз. Поскольку расположение зеркал в ящике является невидимым, то единственный способ его узнать - светить лучи в некоторые щели и смотреть где выходит из ящика соответствующий луч. Напишите программу, которая: - прочитает из файла box.in размер ящика и описания мест входа и выхода лучей - определит, какие из ячеек ящика содержат зеркала, а какие - нет - выведет результат в файл box.out Если возможно несколько решений, выведите любое. Ввод Первая строка входного файла box.in содержит два положительных числа n (количество строк, 1<=n<=100) и m (количество столбцов, 1<=m<=100), разделенных одним пробелом. Каждая из последующих 2*(n+m) строк содержит одно положительное целое число. Число в строке номер i+1 указывает номер щели, через которую выйдет луч света, направленный на входе в щель с номером i. Вывод Ваша программа должна вывести в выходной файл box.out n строк, каждая из которых содержит m целых чисел, разделенных одиночными пробелами. J-тое число в i-той строке должно быть равно 1, если в ячейке с номером строки i и номером столбца j есть зеркало, и равно 0, если там зеркала нет. Пример Входной файл box.in: Правильный ответ в файле box.out 2 3 0 1 0 9 0 1 1 7 10 8 6 5 2 4 1 3 Данная задача может быть формализована следующим образом: Пусть Xij = 1, если в ячейке (i,j) стоит зеркало 0, в противном случае Здесь принято, что левая верхняя ячейка имеет номер 1,1 и номера ячеек растут вниз (первый индекс) и вправо (второй индекс). Введем величины Uij = 1, если из ячейки (i,j) луч выходит вверх 0, в противном случае Rij = 1, если из ячейки (i,j) луч выходит вправо 0, в противном случае Тогда можно заметить, что имеют место следующие равенства: ___ Uij = R[i,j-1]&Xij \/ U[i+1,j]&Xij ___ Rij = R[i,j-1]&Xij \/ U[i+1,j]&Xij То есть для первого уравнения Луч будет выходить вверх из клетки (i,j) в том случае, если он вошел в эту клетку слева (R[i,j-1]=1, луч вышел вправо в клетке слева [i,j-1]), и в этой клетке [i,j] установлено зеркало (Xij=1) ИЛИ в том случае, если он вошел в эту клетку снизу (U[i+1,j]=1, луч вышел вверх в клетке снизу [i+1,j]) и в этой клетке [i,j] нет зеркала (Xij=0) Аналогично для второго уравнения Луч будет выходить вправо из клетки (i,j) в том случае, если он вошел в эту клетку слева (R[i,j-1]=1, луч вышел вправо в клетке слева [i,j-1]), и в этой клетке [i,j] не установлено зеркало (Xij=0) ИЛИ в том случае, если он вошел в эту клетку снизу (U[i+1,j]=1, луч вышел вверх в клетке снизу [i+1,j]) и в этой клетке [i,j] есть зеркало (Xij=1) По условиям задачи нам заданы R[i,0] и U[N+1,i] для всех i. Требуется, решив эту систему уравнений, найти Xij. 2. Системы линейных уравнений над вещественными числами 2.1. Линейное уравнение с одним неизвестным. Слово линейный означает, что неизвестная присутствует в уравнении в первой степени: a*x=b Здесь a и b - произвольные числа, x - переменная, значение которой требуется найти. Понятно, что возможны следующие варианты: 1) a=0, b=0 Уравнение принимает вид 0*x=0 и оно является верным тождеством при любом значении x Например при x=2.7 0*2.7 = 0 В таком случае говорят, что УРАВНЕНИЕ ИМЕЕТ БЕСКОНЕЧНОЕ МНОЖЕСТВО РЕШЕНИЙ. 2) a=0, b<>0 Уравнение принимает вид: 0*x=b Поскольку умножение любого числа x на 0 дает 0, а b<>0, то НЕ СУЩЕСТВУЕТ такого значения x, при котором это уравнение обратилось бы в верное тождество. Поэтому в таком случае говорят уравнение НЕ ИМЕЕТ РЕШЕНИЯ. 3) a<>0 В этом случае решение ЕДИНСТВЕННОЕ и находится по формуле: x = b/a 2.2. Система двух линейных уравнений с двумя неизвестными. a11*x1+a12*x2 = b1 a21*x1+a22*x2 = b2 Здесь x1 и x2 - неизвестные, a11,a12,a21,a22,b1,b2 - некоторые заданные величины. Решить систему уравнений - означает найти такие x1 и x2, что каждое из уравнений обратиться в верное тождество. Например 5*x1 - 3*x2 = 1 4*x1 + 2*x2 = 14 Правильное решение этой системы - x1=2, x2=3, потому что 5*2 - 3*3 = 1 4*2 + 2*3 = 14 Решать такую систему можно несколькими способами: Первый называется метод Крамера: Вначале введем понятие МАТРИЦА: Для систем ДВУХ линейных уравнений с ДВУМЯ неизвестынми потребуется матрица с ДВУМЯ строками (число строк в матрице равно числу уравнений) и ДВУМЯ столбцами (число столбцов в матрице равно числу неизвестных): a11 a12 a21 a22 Например, для вышеприведеной системы уравнений матрица будет выглядеть так: 5 -3 4 2 Далее введем понятие ОПРЕДЕЛИТЕЛЬ матрицы. В некоторых книгах он еще называется ДЕТЕРМИНАНТ. Для матрицы 2*2 определитель вычисляется следующим образом: D = | a11 a12 | = a11*a22 - a21*a22 | a21 a22 | Например | 5 -3 | = 5*2 - 4*(-3)=10+12=22 | 4 2 | Как и в случае одного уравнения с одним неизвестным, при решении линейной системы с двумя уравнениями и двумя неизвестными, можно получить один из трех ответов (в зависимости от значений a11, a12, a21, a22, b1 и b2): - система имеет бесконечное множество решений - система имеет единственное решение - система не имеет решений Определитель | a11 a12 | | a21 a22 | потому так и называется, что он ОПРЕДЕЛЯЕТ ответ. А именно, если этот определитель НЕ РАВЕН 0, то данная система ИМЕЕТ ЕДИНСТВЕННОЕ РЕШЕНИЕ. В нашем примере, определитель равен 22 - значит система имеет единственное решение. Этот определитель еще называется ГЛАВНЫМ определителем. Поскольку для нахождения решения строятся еще ДВА ВСПОМОГАТЕЛЬНЫХ определителя (для каждой неизвестной величины - свой вспомогательный определитель): D1=| b1 a12 | = b1*a21 - b2*a12 | b2 a21 | D2=| a11 b1 | = a11*b2 - a21*b1 | a21 b2 | Составим и вычислим вспомогательные определители для нашей системы: 5*x1 - 3*x2 = 1 4*x1 + 2*x2 = 14 D1 = | 1 -3 | = 1*2 - 14*(-3)= 44 | 14 2 | D2 = | 5 1 | = 5*14 - 4*1 = 66 | 4 14 | Правило Крамера для решения систем двух линейных уравнений гласит: ЕСЛИ D <>0 , ТО СИСТЕМА ИМЕЕТ ЕДИНСТВЕННОЕ РЕШЕНИЕ: x1 = D1/D x2 = D2/D Если D=0, а хотя бы один из вспомогательных определителей (D1,D2) не равен 0, то система НЕ ИМЕЕТ РЕШЕНИЙ. Если D=D1=D2=0, то система имеет БЕСКОНЕЧНОЕ множество решений. Например в случае нашей системы x1 = 44/22 = 2 x2 = 66/22 = 3 Теперь рассмотрим другую систему уравнений 2*x1+3*x2=10 4*x1+6*x2=15 D = | 2 3 | = 2*6 - 4*3 = 0 | 4 6 | D1 = |10 3 | = 10*6 - 15*3 = 15 |15 6 | D2 = | 2 10 | = 2*15 - 4*10 = -10 | 4 15 | D=0, D1 и D2 не равны 0, следовательно, эта система уравнений не имеет решений. Теперь, рассмотрим систему уравнений 2*x1+3*x2=10 4*x1+6*x2=20 D = | 2 3 | = 2*6 - 4*3 = 0 | 4 6 | D1 = |10 3 | = 10*6 - 20*3 = 0 |20 6 | D2 = | 2 10 | = 2*20 - 4*10 = 0 | 4 20 | D, D1, D2 равны 0, следовательно, эта система уравнений имеет бесконечное множество решений. Теперь давайте внимательнее присмотримся к последним двум ситемам: 2*x1+3*x2=10 2*x1+3*x2=10 4*x1+6*x2=15 4*x1+6*x2=20 Можно заметить что коэффициенты при неизвестных ПРОПОРЦИОНАЛЬНЫ (4/2=6/3=2). Умножим на ДВА первое уравнение в обоих системах получим: 4*x1+6*x2=20 2*x1+6*x2=20 4*x1+6*x2=15 4*x1+6*x2=20 Становится очевидным, что первая система НЕ МОЖЕТ ИМЕТЬ РЕШЕНИЙ, поскольку ОДНО И ТО ЖЕ выражение 4*x1+6*x2 в соответствии с первым уравнением должно быть равно 20, а в соответствии со вторым уравнением - должно быть равно 15. Что касается второй системы, то теперь очевидно, что там есть только ОДНО УРАВНЕНИЕ с двумя неизвестными: 4*x1+6*x2=20 Задавая произвольные значения x2, будем получать линейное уравнение с одним неизвестным, которое можно вычислять, например при x2=2 получим 4*x1 + 6*2 = 20 откуда находим x1: 4*x1 = 20 - 12 = 8 а x1 = 2. Таким образом пара x1=4, x2=2 - одно из бесконечного множества решений системы 2*x1+3*x2=10 4*x1+6*x2=20 И действительно : 2*2 + 3*2 = 10 4*2 + 6*2 = 20 2.3. Система трех линейных уравнений с тремя неизвестными a11*x1 + a12*x2 + a13*x3 = b1 a21*x1 + a22*x2 + a23*x3 = b1 a31*x1 + a32*x2 + a33*x3 = b1 Для нее определители составляются следущим образом: | a11 a12 a13 | D = | a21 a22 a23 | | a31 a32 a33 | | b1 a12 a13 | D1= | b2 a22 a23 | | b3 a32 a33 | | a11 b1 a13 | D2= | a21 b2 a23 | | a31 b3 a33 | | a11 a12 b1 | D3= | a21 a22 b2 | | a31 a32 b3 | И опять по правилу Крамера: ЕСЛИ D<>0 ТО СИСТЕМА ИМЕЕТ ЕДИНСТВЕННОЕ РЕШЕНИЕ x1=D1/D, x2=D2/D, x3=D3/D Если D=0, и все Di=0 (D1=0, D2=0, D3=0) ТО СИСТЕМА ИМЕЕТ БЕСКОНЕЧНОЕ МНОЖЕСТВО РЕШЕНИЙ (задавая произвольно значение x3, можно вычислять соответствующие x1 и x2 решая систему двух уравнений с двумя неивзестынми) Если D=0 и хотя бы одно из Di<>0 (D1<>0 или D2<>0 или D3<>0) ТО СИСТЕМА НЕ ИМЕЕТ РЕШЕНИЙ Теперь рассмотрим как вычислять определитель третьего порядка через определители второго порядка. | a11 a12 a13 | D = | a21 a22 a23 | = a11*|a22 a23 | - a12 *|a21 a23 | + a13*| a21 a22 | | a31 a32 a33 | |a32 a33 | |a31 a33 | | a31 a32 | Заметим, что аналогичным способом можно решать системы и более старших порядков, хотя на практике этим пользуются редко. Если Вы хотите закрепить пройденный материал, предлагаю Вам выполнить следующие упражнения: - составьте системы уравнений из двух уравнений с двумя неизвестными, которые - не имеют решений - имеют единственное решение - имеют бесконечное множество решений - решите эти системы методом Крамера - напишите программу, которая решает систему двух уранвений с двумя неизвестными методом Крамера и проверьте ее на своих системах - составьте системы уравнений из трех уравнений с тремя неизвестными, которые - не имеют решений - имеют единственное решение - имеют бесконечное множество решений - напишите программу, которая решает систему трех уравнений с тремя неизвестными методом Крамера и проверьте ее на своих системах - составьте системы уравнений из четырех уравнений с четырьмя неизвестными, которые - не имеют решений - имеют единственное решение - имеют бесконечное множество решений - напишите программу, которая решает систему четырех уравнений с четырьмя неизвестными методом Крамера и проверьте ее на своих системах ЗАМЕЧАНИЕ: Рассмотрим систему уравнений x1 + x2 + x3 = 1 x1 + x2 + x3 = 2 x1 + x2 + x3 = 3 Для нее D = | 1 1 1 | = 0 | 1 1 1 | | 1 1 1 | D1= | 1 1 1 | = 0 D2= | 1 1 1 | = 0 D3= | 1 1 1 | = 0 | 2 1 1 | | 2 1 1 | | 2 1 1 | | 3 1 1 | | 3 1 1 | | 3 1 1 | По правилам Крамера, которые были описаны выше в таком случае система должна иметь множество решений, а она НЕ ИМЕЕТ РЕШЕНИЙ. Почему так случилось? Правило Крамера справедливо для НЕВЫРОЖДЕННОГО случая (когда все определители второй степени не равны 0). На самом деле здесь НЕСОВМЕСТНЫ (противоречивы) любые два уравнения. И потому нужно лбыло применить правило Крамера к системе из двух уравнений, а и тогда не применять правило Крамера к системе из трех уравнений. На практике это можно обходить так: Проверить, что равенство нулю определителей | a11 a12 | | b1 a12 | | a11 b1 | | a21 a22 | , | b2 a22 | , | a21 b2 | | a21 a22 | | b2 a22 | | a21 b2 | | a31 a32 | , | b3 a32 | , | a31 b3 | | a11 a12 | | b1 a12 | | a11 b1 | | a31 a32 | , | b3 a32 | , | a31 b3 | Если главный определитель равен нулю, а один из соответствующих вспомогатльных определителей не равен нулю, то система решений не имеет. На практике совместность/несовместность системы (то есть установление факта имеет она решения или вообще не имеет) удобнее делать с помощью понятия РАНГ матрицы. Этот способ будет описан ниже. 2.4. Метод Гаусса для решения систем линейных уравнений Для решения систем линейных уравнений с большим числом переменных и уравнений часто используют метод Гаусса. Для ручных вычислений он менее удобен чем метод Крамера, зато более удобен для программных вычислений. Рассмотрим систему N линейных уравнений c N неизвестными: a11*x1 + a12*x2 + ... + a1N*xN = b1 a21*x1 + a22*x2 + ... + a2N*xN = b2 ... aN1*x1 + aN2*x2 + ... + aNN*xN = bN Методом Гаусса эта система уравнений приводится к "диагональному" виду: c11*x1 + c12*x2 + ... + c1N*xN = d1 0*x1 + c22*x2 + ... + c2N*xN = d2 ... 0*x1 + 0*x2 + ... + cNN*xN = dN Таким образом в последней строке (строке N) есть только одно неизвестное xN, в предпоследней строке (строке N-1) - два неизвестных XN и X[N-1], в строке N-2 - три неизвестных (XN, X[N-1], X[N-2]) и т.д. Очевидно, что для диагональной системы легко сделать следующие выводы: Если CNN<>0, то система имеет единственное решение Если CNN=0, dN<>0 система не имеет решений Если CNN=0, dN=0 система имеет бесконечное множество решений В случае единственного решения xN=dN/CNN Для нахождения величин x[N-1], X[N-2]... достаточно подставлять найденные значения переменных в верхнее уравнение, превращая его в линейное и затем решать его так: x[N-1] = (d[N-1] - c[N-1,N]*xN)/c[N-1,N-1] x[N-2] = (d[N-2] - c[N-2,N]*xN - c[N-2,N-1]*x[N-1])/c[N-2,N-2] ... x[1] = (d[1] - c[1,N]*x[N] - ... - c[1,2]*x[2])/c[1,1] Например, "диагональная" система 3*x1 - 6*x2 + 4*x3 = 11 2*x2 + 5*x3 = 17 - 7*x3 = 13 Решается так: x3 = 13 / (-7) x2 = (17 - 5*x3)/2 x1 = (11 - 4*x3 + 6*x2)/3 Как же получить из обычной системы "диагональную"? Это предлагается делать следующим образом: Рассмотрим для примера первую и вторую строки a11*x1 + a12*x2 + ... + a1N*xN = b1 a21*x1 + a22*x2 + ... + a2N*xN = b2 Нам нужно получить с помощью эквивалентных преобразований строк 0 в позиции элемента a22. Для этого достаточно из второй строки вычесть первую, умноженную на k=a21/a11: то есть c21 = a21 - a11*(a21/a11) = 0 c22 = a22 - a12*(a21/a11) ... c2N = a2N - a1N*(a21/a11) d2 = b2 - b1 *(a21/a11) Например для строк 2*x1 + 3*x2 - 4*x3 = 11 4*x1 + 1*x2 + 2*x3 = 17 Получаем k= 4/2=2 c21 = 4 - 2*2 = 0 c22 = 1 - 3*2 = -5 c23 = 2 - (-4)*2 = 10 d2 = 17 - 11*2 = -5 То есть от системы 2*x1 + 3*x2 - 4*x3 = 11 4*x1 + 1*x2 + 2*x3 = 17 Мы переходим к системе 2*x1 + 3*x2 - 4*x3 = 11 0*x1 - 5*x2 +10*x3 = -5 Далее аналогичная операция проводится с третьей и первой строкой, чтобы получить 0 позиции 1,3. и т.д. - в результате получаем 0 во всем первом столбце. Затем вычитанием второй строки из 3, 4-ой и т.д. домноженной на соответствующий коэффициент второй строки получаем нули во втором столбце и т.д.. до предпоследнего столбца. Если в какой то момент на позиции элемента i,i возникает 0 на который, как известно, делить нельзя мы просто меняем этот столбец с любым столбцом справа, у которого элемент в данной строке не равен 0. И продолжаем описанный процесс. Для закрепления описанного метода решения систем линейных уравнений Вы можете написать программу реализующую его. Выше описан метод Гаусса для решения системы из N уравнений и N неизвестных. А что делать если число уравнений (M) НЕ РАВНО числу неизвестных N? Ответ на этот вопрос дает теорема Кронекера-Капелли: Представим две матрицы, отражающую нашу систему уравнений следующим образом: a11 a12 ... a1N a11 a12 ... a1N b1 A = a21 a22 ... a2N и AB = a21 a22 ... a2N b2 ... ... aM1 aM2 ... aMN aM1 aM2 ... aMN bM Применяя последовательно итерации метода Гаусса, мы можем преобразовать матрицы A и AB к диагональному виду: с11 с12 ... с1N s11 s12 ... s1N 0 c22 ... c2N 0 s22 ... s2N ... 0 ... 0 ckk ckN spp spN ... ... 0 cMk cMN 0 sMp sMN Числа k и p принято называть рангами соответствующих матриц. Если k=p=N - то система имеет единственное решение Если k=p<>N - система имеет бесконечное множество решений Если k0, a12<>0) Если b1 делится нацело на наибольший общий делитель чисел a11 и a12, то такое уравнение имеет бесконечное множество решений, иначе - оно не имеет решений. Рассмотрим пример: 2*x1 + 3*x2 = 13 Поскольку НОД(2,3)=1 то такое уравнение фактически имеет решение ПРИ ЛЮБОМ значении b1, в том числе и для b1=13. Например, при x2=1 x1= (13 - 3*1)/2 = 5 А вот уравнение 4*x1 + 6*x2 = 13 не имеет решения в целых числах, поскольку НОД(4,6)=2, а 13 не делится нацело на 2. И, действительно, при любых значениях x1 и x2 выражение 4*x1 + 6*x2 будет ЧЕТНО и следовательно ни при каких значениях x1 и x2 оно не может быть равно 13. 3.2. Решение в целых числах одного уравнения с множеством переменных a11*x1 + a12*x2 + ... + a1N = b1 При этом мы будем рассматривать случай, когда две или более переменных aij не равны 0. Иначе просто получаем одно уравнение с одним неизвестным. А этот случай мы уже рассматривали. Он может не иметь решения (если b1=0, a ai,j<>0) или иметь множество решений в остальных случаях. Итак уравнение имеет множество решений в целых числах, если b1 делится нацело на НОД всех aij, которые не равны 0 и не имеет решение в противном случае. Например рассмотрим уравнение из задачи Company (пункт 1.2): 6*job1 + 5*job2 + 8*job4 + 3*job10 = 100 НОД(6,5,8,3) = 1, следовательно это уравнение имеет множество решений в целых числах. Например, job1=job4=job10=0, job2=20. 3.3. Связь сравнений с диафантовыми уравнениями. Диафантовыми уравнениями как раз и называются уравнения, для которых нужно найти целые решения. Сравнениями называются уравнения вида a*x=b (mod m) Или a*x равно b по модулю m. Фактически это можно записать следующим образом: a*x-b = m*k, где k - некоторое целое число или a*x - m*k = b То есть из исходного сравнения мы получили уравнение в целых числах с двумя переменными x и k. Аналогичные преобразования можно выполнить для системы сравнений из задачи Sly Number (пункт 1.5) a0*x0 + a[n-1]*x1 + a[n-2]*x2 + ... + a1*x[n-1] = 1 (mod Q) a1*x0 + a0*x1 + a[n-1]*x2 + ... + a2*x[n-1] = 0 (mod Q) a2*x0 + a1*x1 + a0*x2 + ... + a3*x[n-1] = 0 (mod Q) ... a[n-1]*x0 + a[n-2]*x1 + a[n-3]*x2 + ... + a0*x[n-1] = 0 (mod Q) Тогда система примет вид (второй и третий столбцы опущены): a0*x0 + ... + a1*x[n-1] - Q*x[n] = 1 a1*x0 + ... + a2*x[n-1] - Q*x[n+1] = 0 ... a[n-1]*x0 + .. + a0*x[n-1] ... Q*x[2*n-1] = 0 Можно выполнять и обратное преобразование, например Пусть имеем уравнение a11*x1 + a12*x2 = b1 его можно переписать так: a11*x1 - b1 = -a12*x2 или (пусть для определенности a12>0) -a11*x1 = -b1 (mod a12) 3.4. Необходимое условие существования целочисленного решения системы двух уравнений с двумя неизвестными: a11*x1 + a12*x2 = b1 a21*x1 + a22*x2 = b2 "Если НОД всех определителей второго порядка матрицы AB делится нацело на НОД всех определителей второго порядка, система имеет множество целочисленных решений, иначе не имеет целочисленных решений" Матрица AB это матрица a11 a12 b1 a21 a22 b2 Все ее определители второго порядка это: D = | a11 a12 | = a11*a22 - a21*a22 | a21 a22 | D1= | b1 a12 | = b1*a22 - b2*a12 | b2 a22 | D2= | a11 b1 | = a11*b2 - a21*b1 | a21 b2 | Матрица A это матрица a11 a12 a21 a22 все ее определители второго порядка это D = | a11 a12 | = a11*a22 - a21*a22 | a21 a22 | Таким образом система a11*x1 + a12*x2 = b1 a21*x1 + a22*x2 = b2 имеет решения в целых чисах если и только если НОД (b1*a22 - b2*a12,a11*b2 - a21*b1) делится нацело на a11*a22 - a21*a22 3.5. Необходимое условие существования целочисленного решения системы двух уравнений с множеством неизвестныx: a11*x1 + a12*x2 + ... + a1N*xN = b1 a21*x1 + a22*x2 + ... + a2N*xN = b2 Аналогично предыдущему случаю "НОД всех определителей второго порядка матрицы AB должен делится нацело на НОД всех определителей второго порядка матрицы A" Рассмотрим это правило сразу на примере системы уравнений для задачи "Космолет марки ВАЗ" L1*p + L2*p - L3*p - L4*p + L5*q + L6*q - L7*q - L8*q = x1-x L1*q - L2*q + L3*q - L4*q + L5*p - L6*p + L7*p - L8*p = y1-y Для того, чтобы решение существовало, необходимо и достаточно, чтобы НОД (наибольший общий делитель) всех миноров СЛЕВА то есть получаемых из подматриц матрицы p p -p -p q q -q -q q -q q -q p -p p -p был делителем НОД всех миноров ПОЛНОЙ матрицы p p -p -p q q -q -q x1-x q -q q -q p -p p -p y1-y МИНОР - определитель матрицы вида a c b d который вычисляется как abs(a*d-b*c) Таким образом Для миноров СЛЕВА мы должны перебрать все пары столбцов Мне показалось, что с учетом модуля РАЗНЫХ пар там всего только 3 p p q -q минор = 2*p*q p q q p минор = abs(p^2 - q^2) p -q q p минор = p^2 + q^2 Миноров полной матрицы (вместе со свободными членами) на 8 больше - добавляются матрицы вида (каждая прежняя пара со столбцом свободных членов) p x1-x q x1-x q y1-y p y1-y p x1-x q x1-x -q y1-y -p y1-y -p x1-x -q x1-x q y1-y p y1-y -p x1-x -q x1-x -q y1-y -p y1-y Новых миноров здесь будет 4 abs(p*(y1-y)-q*(x1-x)) abs(q*(y1-y)-p*(x1-x)) abs(p*(y1-y)+q*(x1-x)) abs(q*(y1-y)+p*(x1-x)) Или обозначив Dx=x1-x, и Dy=y1-y, получим abs(p*Dy-q*Dx) abs(q*Dy-p*Dx) abs(p*Dy+q*Dx) abs(q*Dy+p*Dx) таким образом решение будет таково Если НОД (|p*Dy-q*Dx|, |p*Dy+q*Dx|, |q*Dy-p*Dx|, |q*Dy+p*Dx|) делится нацело на НОД (2*p*q,p^2+q^2,|p^2-q^2|) то система имеет решение иначе НЕТ Вернемся к исходной системе уравнений L1*p + L2*p - L3*p - L4*p + L5*q + L6*q - L7*q - L8*q = x1-x L1*q - L2*q + L3*q - L4*q + L5*p - L6*p + L7*p - L8*p = y1-y ее можно переписать следующим образом (L1+L2-L3-L4)*p + (L5+L6-L7-L8)*q = x1-x (L1-L2+L3-L4)*q + (L5-L6+L7-L8)*p = y1-y Введем новые обозначения переменных : x1 = L1+L2-L3-L4 x2 = L5+L6-L7-L8 x3 = L1-L2+L3-L4 x4 = L5-L6+L7-L8 Тогда систему уравнений можно переписать следующим образом: p*x1 + q*x2 = x1-x (обозначим Dx) q*x3 + p*x4 = y1-y ( -"- Dy) Это тоже система с двумя уравнениями, но в ней уже только 4 неизвестных (x1,x2,x3,x4). И соответственно меньше различных определителей, а именно для матрицы AB: |Dx p| = -Dy*p |Dy 0| |Dx q| = -Dy*q |Dy 0| |Dx 0| = Dx*p |Dy p| |Dx 0| = Dx*q |Dy q| А для матрицы A |p 0| = pq |0 q| |p 0| = p^2 |0 p| |q 0| = q^2 |0 q| И тогда решение будет таково Если НОД (|p*Dy|, |q*Dy|, |p*Dx|, |q*Dx|) делится нацело на НОД (p*q,p^2,q^2) то система имеет решение иначе НЕТ 3.6. Необходимое условие существования целочисленного решения системы множества уравнений с множеством неизвестныx Теоретически правило приведенное выше для системы с двумя уравнениями может быть распространено на системы более высоких порядков. Однако в связи с тем, что вычисление всех определителей довольно трудоемкая задача, на практике удобнее просто РЕШАТЬ систему уравнений - как это делать будет описано в следующем пункте 3.7. Решение системы уравнений в целых числах. Для решения системы уравнений в целых числах применим метод Гаусса. При этом наша задача упростится, поскольку мы ишем рещение в целых числах. Рассмотрим сразу одну из возможных реализаций: InputData; Solve; if No then writeln(NoSolution) else if Many then writeln(ManySolutions) else OutResult; Здесь InputData - процедура, которая вводит исходные данные (aij, bi) Solve - процедура, которая ищет решение и формирует значение двух логических переменных No = true, если система не имеет решений в целых числах Many = true, если система имеет множество решений в целых числах OutResult - процедура, которое выводит найденное решение, если он единственое Рассмотрим подробнее реализацию процедуры Solve procedure Solve; begin MN:=min(m,n); for c:=1 to MN do begin Set1(c); if Many or No then exit; for r:=c+1 to M do Zero(r,c); end; CountResult; end; Фактически циклом по количеству MN мы устанавливаем 1 в диагональную позицию (c,c). Если это сделать невозможно, автоматически определяется имеет ли система множество решений или не имеет их совсем (логические переменные Many, No). Если удалось поставить 1 на диагональную позицию, то с помощью процедуры Zero(r,c) обнуляем все элементы в столбце c ниже позиции (c,c). Одновременно эквивалентно модифицируются все элементы соответствующей строки r. Рассмотрим подробнее процедуру Zero(r,c): procedure Zero(r,c:longint); var p : longint; begin p:=a[r,c]; for j:=c to N+1 do a[r,j]:=a[r,j]-p*a[c,j]; end; Поскольку диагональный элемент равен 1, то формулы пересчета по сравнению с обычным методом Гаусса упрощены (отстутствует деление) и результат гарантированно будет целым числом. Рассмотрим также детальнее процедуру Set1(c), которая устанавливает 1 в позицию диагональную (c,c) строка c, столбец c матрицы a. procedure Set1(c:longint); var k1,k2,MinA,ri,cj : longint; begin if a[c,c]=1 then exit; for j:=c+1 to N do if a[c,j]=1 then begin SwapC(c,j); exit; end; for ri:=c+1 to M do for cj:=c to N do if a[ri,cj]=1 then begin SwapR(c,ri); SwapC(c,cj); exit; end; FindMin(c,k1,k2); SwapR(c,k1); SwapC(c,k2); if a[c,c]<>1 then begin Many:=true; No:=false; exit; end; end; Уточним назначение групп операторов: if a[c,c]=1 then exit; если в позиции (c,c) уже стоит 1, делать ничего не нужно for j:=c+1 to N do if a[c,j]=1 then begin SwapC(c,j); exit; end; Если 1 есть в строке c на позиции j,то меняем местами столбцы c и j и выходим из процедуры Set1 for ri:=c+1 to M do for cj:=c to N do if a[ri,cj]=1 then begin SwapR(c,ri); SwapC(c,cj); exit; end; Если есть 1 ниже и правее диагонального элемента (c,c) то меняем соответствующие строки и столбцы так, чтобы найденная 1 переместилась в позицию (c,c) FindMin(c,k1,k2); Эта процедура предпринимает последнюю попытку "водрузить" 1 на позицию (c,c) с помощью линейной комбинации каких-то двух строк ниже строки c. SwapR(c,k1); SwapC(c,k2); Сформированный элемент переносится в позицию (c,c) if a[c,c]<>1 then begin Many:=true; No:=false; exit; end; Если этот элемент не 1, то система имеет множество решений. Рассмотрим подробнее процедуру FindMin: procedure FindMin(c:longint; var k1,k2:longint); var min2,k3,k4,k5,t1,t2,MinA : longint; begin MinA:=maxlongint; for i:=c to M do for j:=c to N do if (abs(a[i,j])0) then begin MinA:=abs(a[i,j]); k1:=i; k2:=j end; if c=MN then begin Reduce(c,k1,MinA); if No then exit; end; if a[k1,k2]=1 then exit; min2:=maxLongint; for i:=c+1 to M do if (i<>k1) and (abs(a[i,k2])0) and (t2<>0) do begin inc(k4); t1:=(1-k4*a[k1,k2]) mod a[k3,k2]; t2:=(1+k4*a[k1,k2]) mod a[k3,k2]; end; if t1=0 then k5:=(1-k4*a[k1,k2]) div a[k3,k2] else k5:=(1+k4*a[k1,k2]) div a[k3,k2]; for j:=c to N+1 do a[k1,j]:=k4*a[k1,j]+k5*a[k3,j]; end; Рассмотрим детальнее блоки операторов: MinA:=maxlongint; for i:=c to M do for j:=c to N do if (abs(a[i,j])0) then begin MinA:=abs(a[i,j]); k1:=i; k2:=j end; Находим самый маленький элемент в части массива a[i,j], которая лежит правее и ниже элемента a[c,c]. k1 - номер строки, k2 - номер столбца найденного минимального элемента. if c=MN then begin Reduce(c,k1,MinA); if No then exit; end; Если эта последняя строка, в которой нужно устанавливать 1, то пытаемся сократить все элементы этой строки на MinA. если сокращение выполнить не удалось (с помощью процедуры Reduce) - то есть какой-то из элементов строки k1, которая содержит минимальный элемент, не делится на MinA, значит система решения не имеет. if a[k1,k2]=1 then exit; если элемент на позиции [k1,k2] оказался равным 1, то выходим min2:=maxLongint; for i:=c+1 to M do if (i<>k1) and (abs(a[i,k2])0) and (t2<>0) do begin inc(k4); t1:=(1-k4*a[k1,k2]) mod a[k3,k2]; t2:=(1+k4*a[k1,k2]) mod a[k3,k2]; end; if t1=0 then k5:=(1-k4*a[k1,k2]) div a[k3,k2] else k5:=(1+k4*a[k1,k2]) div a[k3,k2]; Подбираем такие множители k4 и k5, чтобы строка k1, умноженная на k4 в сумме со строкой k2 умноженной на k5 давали 1 в позиции [k1,k2] for j:=c to N+1 do a[k1,j]:=k4*a[k1,j]+k5*a[k3,j]; Пересчитываем все элементы строки k1. Фактически, то, что описано выше - это основа решения задачи Company: Southeastern European Regional Programming Contest Bucharest, Romania, October 21, 2000 Problem B. Company input.txt / output.txt / 10 sec A company pays different hourly wages for different job types. Each week the company keeps evidence of the total number of work hours for every job type and the total amount paid to all employees for that week. In different weeks different job types can be accomplished. The hourly wage for any job type in the same company remains unchanged. The hourly wage for any job type is a positive integer and the ratio between the maximum wage and the minimum wage is less than 6. You are asked to write a program that computes the hourly wage for every job type using the data collected a period of time (one or several weeks). The number of job types is limited to 200 and the number of weeks in one data set is limited to 50. The input file contains several data sets in text format. The format for the data set is: - The number of lines for the data set; - information_for__one_or_more_weeks The format of the information for a week is the following: job_type1 number_of _hours1 job_type2 number_of _hours2 job_type3 number_of _hours3 ::::: . total_paid ( the dot marks the ending of info for a week) The job type is represented as a string of characters (limited to 20). The number of hours is a positive integer (smaller than 1E5). The total paid is a positive integer (smaller than 2E10). The program should write to standard output (for every job type involved in the data set) a line containing the job type and the hourly wage. The output for a data set ends with a line containing a dot. If the program cannot compute a unique hourly wage for every job type it will print "Incomplete data" and if it cannot compute an integer hourly wage it will print "Inconsistent data" An example is given in the following table: input output 5 Incomplete data job1 6 . job2 5 job3 20 job8 4 job2 10 job10 3 job1 30 . 100 . 13 job3 1 job2 2 . 40 job1 3 job2 1 . 100 job1 1 job3 2 job2 3 . 100 job1 1 job2 5 . 80 Коротко условие задачи может быть переформулировано следующим образом. Задано M уравнений (соответствуют неделям в постановке задачи) и имеется N неизвестных (соответствуют работам в постановке задачи). Требуется выяснить, имеет ли данная система уравнений решение в целых числах (если имеет - то вывести это решение), либо существует множество решений (тогда вывести текст Incomplete data) либо решенией нет (тогда вывести текст Insonsistent Data). Решать систему уравнений будем приведением матрицы системы к треугольному виду методом Гаусса. Рассмотрим реализацию подробнее: С учетом возможности блока тестов в одном входном файле главная программа может выглядеть следующим образом: begin assign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output); while not eof(input) do begin InputDataS; Solve; if No then writeln(NoSolution) else if Many then writeln(ManySolutions) else OutResult; writeln('.'); end; close(input); close(output); end. Здесь InputDataS - процедура ввода исходных данных, заданных в специфическом строковом формате вместе с именами переменных (названиями работ) Solve - процедура решения системы из M уравнений с N неизвестными. В результате ее работы логические переменные No и Many обозначают соответственно отстутствие решений и множество решений OutResult - процедура вывод найденного решения Рассмотрим детальнее процедуру InputDataS: procedure InputDataS; var k,p,t,_ : integer; s,NameT : string; b : array [1..MaxM] of longint; begin for i:=1 to MaxM do for j:=1 to MaxN+1 do a[i,j]:=0; readln(k); M:=1; N:=0; for i:=1 to K do begin readln(s); if s[1]='.' then begin val(copy(s,2,length(s)-1),b[M],_); inc(M); end else begin p:=pos(' ',s); if p=0 then p:=pos(#9,s); NameT:=copy(s,1,p-1); t:=FindName(NameT); if t>N then inc(N); val(copy(s,p+1,length(s)-p),a[m,t],_); end; end; dec(M); for i:=1 to M do a[i,N+1]:=b[i]; for i:=1 to N do xn[i]:=i; No:=false; Many:=false; {Для самопроверки} {for i:=1 to N do read(x[i]);} OutMatrix; end; Обсудим текст процедуры покомпонентно: for i:=1 to MaxM do for j:=1 to MaxN+1 do a[i,j]:=0; Поскольку требуется обрабатывать множество тестов из одного файла, необходимо вначале работы "очистить" результаты предыдущей обработки. readln(k); M:=1; N:=0; for i:=1 to K do begin readln(s); if s[1]='.' then ... else ... end; k - количество строк, в которых задаются очередная система уравнений если s[1]='.' то строка описывает значение правой части уравнения иначе строка описывает левую часть уравнения Левая и правая части обрабатываются следующим образом: val(copy(s,2,length(s)-1),b[M],_); inc(M); При обработке левой части - формируется b[M] - значение правой части уравнения с номером M - увеличивается номер уравнения M p:=pos(' ',s); if p=0 then p:=pos(#9,s); NameT:=copy(s,1,p-1); t:=FindName(NameT); if t>N then inc(N); val(copy(s,p+1,length(s)-p),a[m,t],_); Оказалось, что в тестах имена переменных от коэффициентов могут разделяться как пробелом, так символом табуляции (#9). Для левой части в массив Name запоминаются новые имена переменных, в a[m,t] записываются их коэффициенты. t - номер переменной (в порядке их описания во вводе), находится с помощью функции FindName(NameT), реализацию которой рассмотрим несколько позже. dec(M); После заверешния ввода уточняем количество введенных уравнений. for i:=1 to M do a[i,N+1]:=b[i]; Для удобства последующей работы, заносим массив правых частей уравнений (b[i]) в N+1-ый столбец массива a. for i:=1 to N do xn[i]:=i; Поскольку при решении задачи столбцы (а следовательно и имена соответствующих переменных) будут меняться местами, то порядок переменных будет отслеживаться массивом xn. No:=false; Many:=false; Вначале считаем что система имеет решение. {Для самопроверки} {for i:=1 to N do read(x[i]);} OutMatrix; Очень удобное средство отладки кода по решению систем уравнений: вместе с исходными данными вводим и правильный ответ. А отладочная процедура OutMatrix не только форматированно выводит исходную матрицу, но и проверяет, является ли правильное решение решением ТЕКУЩЕГО состояния матрицы a. Процедура OutMatrix очевидна: procedure OutMatrix; begin { for i:=1 to M do begin for j:=1 to N do write(a[i,j]:4); writeln(' | ',a[i,N+1]); end; writeln; Control; writeln('--------------------------------------------'); writeln; } end; Заметим, что она всегда вызываает процедуру Control: procedure Control; var Left : longint; begin { for i:=1 to M do begin Left:=0; for j:=1 to N do inc(Left,a[i,j]*x[j]); if Left<>a[i,j+1] then begin writeln('Control: Ошибка в строке ',i); writeln(Left,'<>',a[i,N+1]); halt; end; end; writeln('Control: Ok') } end; Такой поход позволяет быстро находить и устранять описки при написании программы. Теперь вернемся к функции FindName: function FindName(NameT:string):longint; begin j:=1; while (j<=N) and (Name[j]<>NameT) do inc(j); if j>N then Name[j]:=NameT; FindName:=j; end; Очередное имя NameT ищется в списке имен Name из N элементов. если не находится - то добавляется туда. Процедура OutResult procedure OutResult; begin for i:=1 to N do for j:=1 to N do if i=xn[j] then writeln(Name[i],' ',x[j]); end; выводит результат в порядке задания имен переменных на вводе. Главная часть, решающая задачу - процедура Solve выглядит следующим образом: procedure Solve; begin MN:=min(m,n); for c:=1 to MN do begin Set1(c); if Many or No then exit; for r:=c+1 to M do Zero(r,c); end; CountResult; end; MN - минимум из количества уравнений и неизветсных Для количества столбцов от 1 до MN С помощью процедуры Set1 устанавливаем 1 в позиции (c,c) если это сделать невозможно - то единственного решения нет а устанавливаются в true переменные Many или No и работа процедуры Solve заканчивается Для всех строк к от с+1 до M с помощью процедуры Zero обнуляем элемент в позиции (r,c) синхронно корректируя все остальные элементы строки c После того как матрица приведена к диагональному виду, вычисляем результат с помощью процедуры CountResult. Теперь рассмотрим детальнее процедуру Set1: procedure Set1(c:longint); var k1,k2,MinA,ri,cj : longint; begin {writeln('Переносим 1 в позицию (',c,',',c,')');} if a[c,c]=1 then exit; for j:=c+1 to N do if a[c,j]=1 then begin SwapC(c,j); OutMatrix; exit; end; for ri:=c+1 to M do for cj:=c to N do if a[ri,cj]=1 then begin SwapR(c,ri); SwapC(c,cj); OutMatrix; exit; end; OutMatrix; FindMin(c,k1,k2,MinA); SwapR(c,k1); SwapC(c,k2); if a[c,c]<>1 then begin Many:=true; No:=false; exit; end; end; Обсудим текст покомпонентно: {writeln('Переносим 1 в позицию (',c,',',c,')');} Это строка отладочной печати. if a[c,c]=1 then exit; если a[c.c] уже равно 1 то и не нужно ничего делать for j:=c+1 to N do if a[c,j]=1 then begin SwapC(c,j); OutMatrix; exit; end; иначе находим в строке c элемент равный 1 (на позиции j) и меняем с помощью процедуры SwapC местами столбцы c и j for ri:=c+1 to M do for cj:=c to N do if a[ri,cj]=1 then begin SwapR(c,ri); SwapC(c,cj); OutMatrix; exit; end; Ищем 1 в оставшейся части матрицы, если находим ее (в строке ri, столбце rj), то меняем местами строки c и ri, а затем столбцы (c и cj). FindMin(c,k1,k2); SwapR(c,k1); SwapC(c,k2); if a[c,c]<>1 then begin Many:=true; No:=false; exit; end; Поскольку в матрице 1 уже нет, пытаемся сделать ее с помощью процедуры FindMin на позиции k1,k2. Затем переносим элемент с позиции k1,k2 на позицию (c,c), безусловно эквивалентно обменивая все элементы соответствующих строк и столбцов. Если построить элемент a[c,c]=1 не удалось, это означает, что возможно множество решений. Процедуры обмена строк и столбцов за заданными номераи очевидны: procedure SwapR(z,y:longint); begin for j:=1 to N+1 do begin i:=a[z,j]; a[z,j]:=a[y,j]; a[y,j]:=i; end; end; procedure SwapC(z,y:longint); begin for i:=1 to M do begin j:=a[i,z]; a[i,z]:=a[i,y]; a[i,y]:=j; end; i:=xn[z]; xn[z]:=xn[y]; xn[y]:=i; end; Заметим только, что при перемещении столбцов нужно запоминать их в массиве xn для того, чтобы в ответе вывести правильно названия переменных и их значения. Теперь рассмотрим детальнее процедуру FindMin: procedure FindMin(c:longint; var k1,k2,MinA:longint); var min2,k3,k4,k5,t1,t2 : longint; begin MinA:=maxlongint; for i:=c to M do for j:=c to N do if (abs(a[i,j])0) then begin MinA:=abs(a[i,j]); k1:=i; k2:=j end; if c=MN then begin Reduce(c,k1,MinA); if No then exit; end; if a[k1,k2]=1 then exit; min2:=maxLongint; for i:=c+1 to M do if (i<>k1) and (abs(a[i,k2])0) and (t2<>0) do begin inc(k4); t1:=(1-k4*a[k1,k2]) mod a[k3,k2]; t2:=(1+k4*a[k1,k2]) mod a[k3,k2]; end; if t1=0 then k5:=(1-k4*a[k1,k2]) div a[k3,k2] else k5:=(1+k4*a[k1,k2]) div a[k3,k2]; OutMatrix; for j:=c to N+1 do a[k1,j]:=k4*a[k1,j]+k5*a[k3,j]; OutMatrix; end; Рассмотрим текст покомпонентно: MinA:=maxlongint; for i:=c to M do for j:=c to N do if (abs(a[i,j])0) then begin MinA:=abs(a[i,j]); k1:=i; k2:=j end; Находим минимальный по абсолютной величине, но не равный нулю элемент MinA и его позицию k1,k2 в матрице A ниже и правее элемента A[c,c]. if c=MN then begin Reduce(c,k1,MinA); if No then exit; end; если c - последний номер, то пытаемся сократить на MinA строку k1, если не удается - значит решений нет. Процедуру Reduce рассмотрим чуть позже. if a[k1,k2]=1 then exit; если элемент на позиции [k1,k2] оказался равным 1, то выходим min2:=maxLongint; for i:=c+1 to M do if (i<>k1) and (abs(a[i,k2])0) and (t2<>0) do begin inc(k4); t1:=(1-k4*a[k1,k2]) mod a[k3,k2]; t2:=(1+k4*a[k1,k2]) mod a[k3,k2]; end; if t1=0 then k5:=(1-k4*a[k1,k2]) div a[k3,k2] else k5:=(1+k4*a[k1,k2]) div a[k3,k2]; Подбираем такие множители k4 и k5, чтобы строка k1, умноженная на k4 в сумме со строкой k2 умноженной на k5 давали 1 в позиции [k1,k2] for j:=c to N+1 do a[k1,j]:=k4*a[k1,j]+k5*a[k3,j]; Пересчитываем все элементы строки k1. Теперь вернемся к процедуре Reduce: procedure Reduce(c,k1,MinA:longint); begin for j:=c to N+1 do if (a[k1,j] mod MinA)=0 then a[k1,j]:=a[k1,j] div MinA else begin No:=true; exit; end; OutMatrix; end; Она пытается поделить на MinA все элементы строки k1 если это не удается, значит система решений не имеет. Процедура Zero procedure Zero(r,c:longint); var p : longint; begin p:=a[r,c]; for j:=c to N+1 do a[r,j]:=a[r,j]-p*a[c,j]; {writeln('Обнуляем в строке ',r,' столбце ',c);} OutMatrix; end; обрабатывает строку r следующим образом: из нее вычитается строка c, умноженная на a[r,c]. В результате элемент a[r,c] становится равным 0. И, наконец, процедура CountResult: procedure CountResult; var Left : longint; begin for i:=1 to Max(M,N) do x[i]:=0; x[MN]:=a[MN,N+1] div a[MN,MN]; for i:=MN-1 downto 1 do begin x[i]:=a[i,N+1]; for j:=i+1 to MN do dec(x[i],a[i,j]*x[j]) end; for i:=1 to M do begin Left:=0; for j:=1 to N do inc(Left,a[i,j]*x[j]); if Left<>a[i,N+1] then begin No:=true; {writeln(NoSolution); halt;} exit; end; end; {OutResult;} Control; end; Она по треугольной матрице из MN строк вычисляет результат x[i] for i:=1 to Max(M,N) do x[i]:=0; x[MN]:=a[MN,N+1] div a[MN,MN]; for i:=MN-1 downto 1 do begin x[i]:=a[i,N+1]; for j:=i+1 to MN do dec(x[i],a[i,j]*x[j]) end; А затем проверяет, что найденное решение удовлетворяет строкам с MN+1 до M: for i:=1 to M do begin Left:=0; for j:=1 to N do inc(Left,a[i,j]*x[j]); if Left<>a[i,N+1] then begin No:=true; exit; end; end; Control; Если не удовлетворяет - значит решений нет. Полный текст решения задачи Company приводится ниже: {$R+} program company; {SEE_00/B} const MaxN = 20 {200}; {неизвестных/столбцов} MaxM = 10 {50} ; {уравнений/строк} NoSolution = 'Inconsistent data'; ManySolutions = 'Incomplete data'; var a : array [1..MaxM,1..MaxN+1] of longint; x,xn : array [1..MaxN] of longint; Name : array [1..MaxN] of string[20]; M,N,MN,r,c,i,j : longint; No, Many : boolean; function min(a,b:longint):longint; begin if ab then max:=a else max:=b; end; procedure Control; var Left : longint; begin { for i:=1 to M do begin Left:=0; for j:=1 to N do inc(Left,a[i,j]*x[j]); if Left<>a[i,j+1] then begin writeln('Control: Ошибка в строке ',i); writeln(Left,'<>',a[i,j+1]); halt; end; end; writeln('Control: Ok') } end; procedure OutMatrix; begin { for i:=1 to M do begin for j:=1 to N do write(a[i,j]:4); writeln(' | ',a[i,N+1]); end; writeln; Control; writeln('--------------------------------------------'); writeln; } end; procedure SwapR(z,y:longint); begin for j:=1 to N+1 do begin i:=a[z,j]; a[z,j]:=a[y,j]; a[y,j]:=i; end; end; procedure SwapC(z,y:longint); begin for i:=1 to M do begin j:=a[i,z]; a[i,z]:=a[i,y]; a[i,y]:=j; end; {i:=x[z]; x[z]:=x[y]; x[y]:=i;} i:=xn[z]; xn[z]:=xn[y]; xn[y]:=i; end; procedure Reduce(c,k1,MinA:longint); begin for j:=c to N+1 do if (a[k1,j] mod MinA)=0 then a[k1,j]:=a[k1,j] div MinA else begin No:=true; exit; {writeln(NoSolutions); halt;} end; OutMatrix; end; procedure FindMin(c:longint; var k1,k2:longint); var min2,k3,k4,k5,t1,t2,MinA : longint; begin MinA:=maxlongint; for i:=c to M do for j:=c to N do if (abs(a[i,j])0) then begin MinA:=abs(a[i,j]); k1:=i; k2:=j end; if c=MN then begin Reduce(c,k1,MinA); if No then exit; end; if a[k1,k2]=1 then exit; min2:=maxLongint; for i:=c+1 to M do if (i<>k1) and (abs(a[i,k2])0) and (t2<>0) do begin inc(k4); t1:=(1-k4*a[k1,k2]) mod a[k3,k2]; t2:=(1+k4*a[k1,k2]) mod a[k3,k2]; end; if t1=0 then k5:=(1-k4*a[k1,k2]) div a[k3,k2] else k5:=(1+k4*a[k1,k2]) div a[k3,k2]; OutMatrix; for j:=c to N+1 do a[k1,j]:=k4*a[k1,j]+k5*a[k3,j]; OutMatrix; end; procedure Set1(c:longint); var k1,k2,MinA,ri,cj : longint; begin {writeln('Переносим 1 в позицию (',c,',',c,')');} if a[c,c]=1 then exit; for j:=c+1 to N do if a[c,j]=1 then begin SwapC(c,j); OutMatrix; exit; end; for ri:=c+1 to M do for cj:=c to N do if a[ri,cj]=1 then begin SwapR(c,ri); SwapC(c,cj); OutMatrix; exit; end; OutMatrix; FindMin(c,k1,k2); SwapR(c,k1); SwapC(c,k2); if a[c,c]<>1 then begin Many:=true; No:=false; exit; end; end; procedure Zero(r,c:longint); var p : longint; begin p:=a[r,c]; for j:=c to N+1 do a[r,j]:=a[r,j]-p*a[c,j]; {writeln('Обнуляем в строке ',r,' столбце ',c);} OutMatrix; end; procedure OutResult; begin for i:=1 to N do for j:=1 to N do if i=xn[j] then writeln(Name[i],' ',x[j]); end; procedure CountResult; var Left : longint; begin for i:=1 to Max(M,N) do x[i]:=0; x[MN]:=a[MN,N+1] div a[MN,MN]; for i:=MN-1 downto 1 do begin x[i]:=a[i,N+1]; for j:=i+1 to MN do dec(x[i],a[i,j]*x[j]) end; for i:=1 to M do begin Left:=0; for j:=1 to N do inc(Left,a[i,j]*x[j]); if Left<>a[i,j+1] then begin No:=true; {writeln(NoSolution); halt;} exit; end; end; {OutResult;} Control; end; procedure Solve; begin MN:=min(m,n); for c:=1 to MN do begin Set1(c); if Many or No then exit; for r:=c+1 to M do Zero(r,c); end; CountResult; end; function FindName(NameT:string):longint; begin j:=1; while (j<=N) and (Name[j]<>NameT) do inc(j); if j>N then Name[j]:=NameT; FindName:=j; end; procedure InputDataS; var k,p,t,_ : integer; s,NameT : string; b : array [1..MaxM] of longint; begin for i:=1 to MaxM do for j:=1 to MaxN+1 do a[i,j]:=0; readln(k); M:=1; N:=0; for i:=1 to K do begin readln(s); if s[1]='.' then begin val(copy(s,2,length(s)-1),b[M],_); inc(M); end else begin p:=pos(' ',s); if p=0 then p:=pos(#9,s); NameT:=copy(s,1,p-1); t:=FindName(NameT); if t>N then inc(N); val(copy(s,p+1,length(s)-p),a[m,t],_); end; end; dec(M); for i:=1 to M do a[i,N+1]:=b[i]; for i:=1 to N do xn[i]:=i; No:=false; Many:=false; {Для самопроверки} {for i:=1 to N do read(x[i]);} OutMatrix; end; begin assign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output); while not eof(input) do begin InputDataS; Solve; if No then writeln(NoSolution) else if Many then writeln(ManySolutions) else OutResult; writeln('.'); end; close(input); close(output); end. 3.8. Решение системы уравнений на подмножестве целых чисел. Одним из замечетальных свойств метода Гаусса для решения систем линейных уравнений является то, что он корректно работает не только для целых чисел, но и для подмножеств целых чисел, на которых "правильно" определены операции "сложения" и умножения. А именно: "... этот метод решения системы над кольцом целых чисел обобщается на любые кольца". Теперь настало время ознакомиться с определением кольца: Кольцом называется множество элементов с двумя бинарными (с двумя операндами) операциями, которые обычно принято называть сложение и умножение. При этом 1) кольцо должно быть абелевой группой относительно сложения: в частности - в кольце существует нулевой элемент, обозначаемый 0 и противоположный элемент -x для любого элемента x из кольца так, что x + (-x) =0 2) Операция умножения удовлетворяет правому и левому законам дистрибутивности относительно сложения, т.е : x*(y+z) = x*y + x*z и (y+z)*x=y*x+z*x для любых элементов x,y,z из кольца Перейдем от теории к практике :-) В задаче Shift Register переменные - числа 0 и 1. Определим операцию сложения как "сложение по модулю 2" А операцию умножения как обычное умножение. тогда обратным для 0 будет 0, а обратным для 1 будет 1. и 0+0 = 0, 1+1=0 очевидно также и выполнение дистрибутивных законов. Тогда получается, что заменив в методе Гаусса операцию обычного сложения на операцию сложения по модулю два. Мы можем применить метод Гаусса для этой задачи: 3.9. Решение задачи "Shift Register". CENTRAL EUROPEAN OLYMPIAD IN INFORMATICS Munster, Germany, July 5-12, 2003, Day 2: Задача 2. Shift Register register.in/register.out/1.5s/16 MB Регистр компьютера хранит биты. Сдвиговый регистр - это специальный вид регистра, в котором биты легко могут быть сдвинуты на одну позицию. Используя сдвиговый регистр и обратную связь легко сгенерировать двоичные псевдо-случайные числа, следующим образом: Изначально сдвиговый регистр размера N заполняется величинами a1, a2, :, aN. Затем на каждом такте регистр выдвигает самый правый бит, все другие биты сдвигаются на одну позицию вправо, на первую (самую левую) позицию заносится бит в соответствии с правилами: - каждый бит регистра присоединен к элементу XOR через переключатель (смотри картинку ниже). Для каждого бита i, переключатель si может иметь значение 1 или 0, который определяет, отправляется ли значение ai соответствующего бита на элемент XOR или нет. Пусть ki = si * ai. Новое значение a1 самого левого бита - это выходное значение вентиля XOR (k1,k2,:,kN). Заметим, что если в k1,k2,:,kN количество единиц нечетное, то величина выхода с XOR равна 1, иначе - равно 0. Ниже приведены формальные определения: a1 = XOR (k1, ..., kN) ai = a(i-1) для 2<=i<=N Выход = aN ---------- a1 a2 a3 a4 a5 a6 a7 output | | 0 1 0 1 1 0 0 1 - | ------------- 1 0 1 0 1 1 0 0 1 | | XOR | 2 1 0 1 0 1 1 0 0 | ------------- 3 1 1 0 1 0 1 1 0 | ^ ^ ^ ^ ^ ^ ^ 4 0 1 1 0 1 0 1 1 | o o o o o o o 5 0 0 1 1 0 1 0 1 | | | | | | 6 1 0 0 1 1 0 1 0 | o o o o o o o 7 1 1 0 0 1 1 0 1 -->1 0 1 1 0 0 1 8 0 1 1 0 0 1 1 0 9 1 0 1 1 0 0 1 1 10 0 1 0 1 1 0 0 1 11 1 0 1 0 1 1 0 0 12 1 1 0 1 0 1 1 0 13 0 1 1 0 1 0 1 1 14 0 0 1 1 0 1 0 1 В примере выше, величина a1 в момент времени 1 вычисляется следующим образом : XOR (1*1,0*0,1*1,1*1,0*0,1*0,1*1) = 0 Вам даются первые 2*N выходных величин сдвигового регистра. Зная эти значения, Вы должны определить значения переключателей si. Вход Первая строка входного файла register.in содержит размер N сдвигового регистра (1<=N<=750). Вторая строка содержит 2N чисел 0 или 1, которые задают первые 2N выходных битов сдвигового регистра. Выход Выходной файл register.out содержит ровно одну строку. Если существует установка переключателей, которая обеспечивает такой вывод из сдвигового регистра, то выведите эти значения переключателей si, начиная с s1. Если такой установки переключателей не существует, выедите -1. Примеры register.in 7 1 0 0 1 1 0 1 0 1 1 0 0 1 1 register.out 1 0 1 1 0 1 1 register.in 3 0 0 0 1 1 1 register.out -1 Коротко переформулировать условия задачи можно следующим образом: даны первые 2*N выходных величин сдвигового регистра. Определить переключатели (множители) Si. Понятно, что первые N выходных значений - это фактически состояние регистра перед началом работы - в обратном порядке: a[n], a[n-1], ..., a[1]. А следующие N выходных значений - это фактически величины, вдвигавшиеся в регистр, в прямом порядке. Обозначим их v[1],v[2],...,v[n] Тогда для нахождения S[i] требуется решить систему уравнений: v[1] = s[1]*a[1] + s[2]*a[2] + ... + s[N]*a[N] v[2] = s[1]*v[1] + s[2]*a[1] + ... + s[N]*a[N-1] v[3] = s[1]*v[2] + s[2]*v[1] + ... + s[N]*a[N-2] ... v[N] = s[1]*v[N-1] + s[2]*v[N-2] + ... + s[N]*a[1] Здесь все величины могут принимать значение либо 0, либо 1. Такая система может решаться обычным методом Гаусса, с заменой операции сложения на слоежение по модулю 2. Рассмотрим реализацию: Главная программа выглядит следующим образом: begin assign(input,'register.in'); reset(input); assign(output,'register.out'); rewrite(output); InputData; Solve; if No then writeln(NoSolution) else if Many then BuildX else OutResult; close(input); close(output); end. Здесь InputData - процедура ввода исходных данных и построения матрицы a[i,j] для данной системы уравнений Solve - процедура решения системы уравнений она может вернуть логические переменные No - если система не имеет решений Many - если система имеет множество решений BuildX - процедура построения одного из возможных решений, если решение не единственное Процедура InputData выглядит следующим образом: procedure InputData; begin readln(N); M:=N; if (M>MaxM) then begin writeln('OverFlow M', M,' ',MaxM); halt; end; for i:=N downto 1 do read(aa[i]); for i:=1 to N do read(v[i]); for i:=1 to M do for j:=1 to N+1 do a[i,j]:=0; for j:=1 to N do a[1,j]:=aa[j]; for i:=2 to N do begin a[i,1]:=v[i-1]; for j:=2 to N do a[i,j]:=a[i-1,j-1]; end; for i:=1 to N do a[i,N+1]:=v[i]; for i:=1 to N do xn[i]:=i; No:=false; Many:=false; {Для самопроверки} for i:=1 to N do read(x[i]); OutMatrix; end; Вектор исходных состояний регистра обозначен aa. Вектор xn хранит номера переменных. Поскольку при решении задачи будут меняться местами столбцы, будет меняться и порядок переменных, который и будет сохраняться в массиве xn. Заполнение матрицы a в соответствии с семантикой данной задачи производится операторами for j:=1 to N do a[1,j]:=aa[j]; for i:=2 to N do begin a[i,1]:=v[i-1]; for j:=2 to N do a[i,j]:=a[i-1,j-1]; end; for i:=1 to N do a[i,N+1]:=v[i]; Теперь рассмотрим подробнее процедуру Solve, решающую задачу procedure Solve; begin MN:=min(m,n); for c:=1 to MN do begin Set1(c); if Many or No then exit; for r:=c+1 to M do if a[r,c]<>0 then Zero(r,c); end; CountResult; end; Как обычно, она реализует преобразование матрицы к треугольному виду, при этом на диагонали стоят 1. Поскольку все значения a[i,j] и x[i] находятся в множестве {0,1}, это всегда возможно, если система имет единственное решение. Именно процедура Set1 формирует 1 в нужной позиции, или если этого сделать невозможно - устанавливает значение логических переменных Many (множество решений) и No (решение отсутствует). Процедура Zero обеспечивает обнуление всех элементов ниже установленной 1, операцией "сложение по модулю 2": procedure Zero(r,c:longint); var p : longint; begin for j:=c to N+1 do begin a[r,j]:=a[r,j]+a[c,j]; a[r,j]:= a[r,j] mod 2; end; {writeln('Обнуляем в строке ',r,' столбце ',c);} OutMatrix; end; Ппроцедура Set1 выглядит следующим образом: procedure Set1(c:longint); var k1,k2,MinA,ri,cj : longint; begin if a[c,c]=1 then exit; {writeln('Переносим 1 в позицию (',c,',',c,')');} for j:=c+1 to N do if a[c,j]=1 then begin SwapC(c,j); OutMatrix; exit; end; for ri:=c+1 to M do for cj:=c to N do if a[ri,cj]=1 then begin SwapR(c,ri); SwapC(c,cj); OutMatrix; exit; end; OutMatrix; if NoSol then No:=true else Many:=true; end; Рассмотрим ее покомпонентно: if a[c,c]=1 then exit; Если на позиции a[c,c] уже стоит 1 - ничего делать не нужно. for j:=c+1 to N do if a[c,j]=1 then begin SwapC(c,j); OutMatrix; exit; end; Если в строке c правее позиции [c,c] есть 1 (в столбце j), то меняем местами столбец j со столбцом c и выходим из процедуры. for ri:=c+1 to M do for cj:=c to N do if a[ri,cj]=1 then begin SwapR(c,ri); SwapC(c,cj); OutMatrix; exit; end; Если 1 есть в любой из строк ниже и правее позиции [c,c], то меняем местами соответствующие строки и столбцы, так чтобы в позиции [c,c] оказалась 1. OutMatrix; Процедура OutMatrix используется в отладочных целях - для вывода текущих значений матрицы a. if NoSol then No:=true else Many:=true; Функция NoSol вызывается чтобы ответить на вопрос - имеет ли система множество решений, или она их не имеет вовсе. function NoSol:boolean; begin NoSol:=true; if a[c,n+1]=1 then exit; for j:=c+1 to M do if a[j,n+1]=1 then exit; NoSol:=false; end; К текущему моменту известно, что ранг матрицы A уже меньше количества строк в этой матрице. Теперь осталось выяснить ранг матрицы AB, то есть ранг матрицы, в которой к a добавлен последним столбцом b. (a[i,N+1]). В случае с двоичными значениями элементов матрицы a и решений для этого достаточно осуществить следующие проверки: NoSol:=true; if a[c,n+1]=1 then exit; если в строке c есть 1, то решений нет. for j:=c+1 to M do if a[j,n+1]=1 then exit; если в любой из строк ниже строки с в столбце n+1 есть 1, то решений нет. Обратим внимание на процедуру SwapC: procedure SwapC(z,y:longint); begin for i:=1 to M do begin j:=a[i,z]; a[i,z]:=a[i,y]; a[i,y]:=j; end; i:=xn[z]; xn[z]:=xn[y]; xn[y]:=i; end; В ней во время обмена местами столбцов делаются синхронные обмены в массиве xn, который хранит номера переменных. И тогда процедура корректного вывода результатов OutResult выглядит следующим образом: procedure OutResult; var k,t : longint; begin for i:=1 to N-1 do for j:=1 to N do if i=xn[j] then write(x[j],' '); for j:=1 to N do if N=xn[j] then writeln(x[N]); end; Для построения результатов в случае единственного решения используется процедура CountResult: procedure CountResult; var Left : longint; begin for i:=1 to Max(M,N) do xx[i]:=x[i]; for i:=1 to Max(M,N) do x[i]:=0; x[MN]:=a[MN,N+1] div a[MN,MN]; for i:=MN-1 downto 1 do begin x[i]:=a[i,N+1]; for j:=i+1 to MN do begin dec(x[i],a[i,j]*x[j]); if x[i]=-1 then x[i]:=1; end; end; { OutResult;} Control; for i:=1 to M do begin Left:=0; for j:=1 to N do inc(Left,a[i,j]*x[j]); Left:=Left mod 2; if Left<>a[i,N+1] then begin No:=true; {writeln(NoSolution); halt;} exit; end; end; {OutResult;} {Control;} end; Заметим, что в нее же встроен и отладочный контроль корректности постренного результата Процедура BuildX используется для построения результатов в случае их множественности procedure BuildX; begin for i:=1 to Max(M,N) do x[i]:=0; if c>1 then for i:=c downto 1 do begin x[i]:=a[i,N+1]; for j:=i+1 to MN do begin dec(x[i],a[i,j]*x[j]); if x[i]=-1 then x[i]:=1; end; end; OutResult; Control; end; Ниже приведен полный текст решения задачи: {$R+} program register; {CEOI 2003, День 2, Задача 2} const MaxN = 750 ; {неизвестных/столбцов} MaxM = 750 ; {уравнений/строк} NoSolution = '-1'; ManySolutions = 'Incomplete data'; var a : array [1..MaxM+1,1..MaxN+1] of longint; x,xn,aa,v,xx : array [1..MaxN+1] of longint; M,N,MN,r,c,i,j,nt,kt : longint; No, Many : boolean; function min(a,b:longint):longint; begin if ab then max:=a else max:=b; end; procedure OutResult; var k,t : longint; begin for i:=1 to N-1 do for j:=1 to N do if i=xn[j] then write(x[j],' '); for j:=1 to N do if N=xn[j] then writeln(x[N]); { for j:=1 to N-1 do write(x[j],' '); writeln(x[N]);} { writeln('---- прав.ответ.'); for j:=1 to N do write(xx[j],' '); writeln;} end; procedure Control; var Left : longint; begin for i:=1 to M do begin Left:=0; for j:=1 to N do begin inc(Left,a[i,j]*x[j]); end; Left:=Left mod 2; if Left<>a[i,N+1] then begin writeln('Control: Ошибка в строке ',i); writeln(Left,'<>',a[i,N+1]); {OutResult;} halt; end; end; { writeln('Control: Ok')} end; procedure OutMatrix; begin (* for i:=1 to M do begin for j:=1 to N do write(a[i,j]:4); writeln(' | ',a[i,N+1]); end; Control; writeln; writeln('--------------------------------------------'); writeln; *) end; procedure SwapR(z,y:longint); begin for j:=1 to N+1 do begin i:=a[z,j]; a[z,j]:=a[y,j]; a[y,j]:=i; end; end; procedure SwapC(z,y:longint); begin for i:=1 to M do begin j:=a[i,z]; a[i,z]:=a[i,y]; a[i,y]:=j; end; i:=x[z]; x[z]:=x[y]; x[y]:=i; i:=xn[z]; xn[z]:=xn[y]; xn[y]:=i; end; function NoSol:boolean; begin NoSol:=true; if a[c,n+1]=1 then exit; for j:=c+1 to M do if a[j,n+1]=1 then exit; NoSol:=false; end; procedure Set1(c:longint); var k1,k2,MinA,ri,cj : longint; begin if a[c,c]=1 then exit; {writeln('Переносим 1 в позицию (',c,',',c,')');} for j:=c+1 to N do if a[c,j]=1 then begin SwapC(c,j); OutMatrix; exit; end; for ri:=c+1 to M do for cj:=c to N do if a[ri,cj]=1 then begin SwapR(c,ri); SwapC(c,cj); OutMatrix; exit; end; OutMatrix; if NoSol then No:=true else Many:=true; end; procedure Zero(r,c:longint); var p : longint; begin for j:=c to N+1 do begin a[r,j]:=a[r,j]+a[c,j]; a[r,j]:= a[r,j] mod 2; end; {writeln('Обнуляем в строке ',r,' столбце ',c);} OutMatrix; end; procedure CountResult; var Left : longint; begin for i:=1 to Max(M,N) do xx[i]:=x[i]; for i:=1 to Max(M,N) do x[i]:=0; x[MN]:=a[MN,N+1] div a[MN,MN]; for i:=MN-1 downto 1 do begin x[i]:=a[i,N+1]; for j:=i+1 to MN do begin dec(x[i],a[i,j]*x[j]); if x[i]=-1 then x[i]:=1; end; end; { OutResult;} Control; for i:=1 to M do begin Left:=0; for j:=1 to N do inc(Left,a[i,j]*x[j]); Left:=Left mod 2; if Left<>a[i,N+1] then begin No:=true; {writeln(NoSolution); halt;} exit; end; end; {OutResult;} {Control;} end; procedure Solve; begin MN:=min(m,n); for c:=1 to MN do begin Set1(c); if Many or No then exit; for r:=c+1 to M do if a[r,c]<>0 then Zero(r,c); end; CountResult; end; procedure InputData; begin readln(N); M:=N; if (M>MaxM) then begin writeln('OverFlow M', M,' ',MaxM); halt; end; for i:=N downto 1 do read(aa[i]); for i:=1 to N do read(v[i]); for i:=1 to M do for j:=1 to N+1 do a[i,j]:=0; for j:=1 to N do a[1,j]:=aa[j]; for i:=2 to N do begin a[i,1]:=v[i-1]; for j:=2 to N do a[i,j]:=a[i-1,j-1]; end; for i:=1 to N do a[i,N+1]:=v[i]; for i:=1 to N do xn[i]:=i; No:=false; Many:=false; {Для самопроверки} for i:=1 to N do read(x[i]); OutMatrix; end; procedure BuildX; begin for i:=1 to Max(M,N) do x[i]:=0; if c>1 then {x[c-1]:=a[c,N+1] div a[c-1,c-1];} for i:=c downto 1 do begin x[i]:=a[i,N+1]; for j:=i+1 to MN do begin dec(x[i],a[i,j]*x[j]); if x[i]=-1 then x[i]:=1; end; end; OutResult; Control; end; begin assign(input,'register.in'); reset(input); assign(output,'register.out'); rewrite(output); InputData; Solve; if No then writeln(NoSolution) else if Many then BuildX else OutResult; close(input); close(output); end. 3.10. Кольцо чисел {0,1,2} Для того, чтобы превратить множество чисел {0,1,2} в кольцо. Нужно правильно определить операции "сложение" и "умножение". Обычное сложение не подходит например потому, что в обычном сложении 2+2=4, а в нашем множестве нет такого элемента. По той же причине не подходит и обычное умножение. Зато подойдут сложение и умножение по модулю 3: А в качестве противоположного элемента -x нужно брать элемент (3-x) mod 3 то есть -0 = (3-0) mod 3 = 0 -1 = (3-1) mod 3 = 2 -2 = (3-2) mod 3 = 1 и соответственно a - b = a + b = (a + (3-b) mod 3) mod 3 Операция вычитания используется в методе Гаусса для целых чисел при пересчете элементов и вычислении результата. 4. Проблемные задачи. 4.1. Sly Number South Eastern 2002 Problem #8: Sly Number sly.in / sly.out / 25 sec Let's consider so called "sly number" which is given as an array A of N integers from set {0,1,2}. For example A[0]=1, A[1]=1, A[2]=0 and A[3]=2. A sly number is called ONE, if A[0]=1 and A[I]=0 for I=1,2,:,N-1. Consider following operation with two sly numbers A and B called 'Star Multiplication': k N - 1 -- -- C[k] = > A[i] * B[k-i] + > A[i] * B[N+k-i]. -- -- i = 0 i = k + 1 here C - the result of the operation, even also presented in an array - not necessarily sly number. This operation we will denote by <*> symbol. Moreover, there is also module operation over the results of 'Star Multiplication': (C mod Q) [i] = C[i] mod Q, where Q is a positive integer. We are given a sly number A and a module Q. We need to find such 'inverse sly number' B: (A * B) mod Q = ONE. Input The input file contains K data sets in text format. The first line of this file contains the number K of test cases. Each test consists of two lines. First line contains two integers separated by spaces: Q (2 <= Q <= 100) and N (5 <= N <= 50). Second lin e contains N integers from set {0,1,2} separated by spaces, which present sly number A. Output It should contain K lines - one line for each test case. If a solution exists, the line should contain the string "A solution can be found". In case there is no solution, the line should consist of string 'No solution'. Example input: 2 2 5 1 0 1 0 1 65 8 1 2 2 2 1 1 2 2 Example output: A solution can be found No solution Формализация постановки задачи может быть выполнена следующим образом: Пусть a0, a1, ..., a[N-1] - заданный вектор x0, x2, ..., x[N-1] - это значения, которые нам нужно найти Тогда, в соответствии с условиями задачи они являются решениями такой системы уравнений: a0*x0 + a[n-1]*x1 + a[n-2]*x2 + ... + a1*x[n-1] = 1 (mod Q) a1*x0 + a0*x1 + a[n-1]*x2 + ... + a2*x[n-1] = 0 (mod Q) a2*x0 + a1*x1 + a0*x2 + ... + a3*x[n-1] = 0 (mod Q) ... a[n-1]*x0 + a[n-2]*x1 + a[n-3]*x2 + ... + a0*x[n-1] = 0 (mod Q) И в соответствии с уловиями задачи нам требуется ответить на вопрос имеет ли решение эта система при заданных N, a[i] и Q. При этом известно, что N<=50, 2<=Q<=100, a[i] могут принимать значения только 0, 1 или 2. И все x[i] должны быть также из множества чисел {0,1,2}. К системе вида a0*x0 + a[n-1]*x1 + a[n-2]*x2 + ... + a1*x[n-1] = 1 a1*x0 + a0*x1 + a[n-1]*x2 + ... + a2*x[n-1] = 0 a2*x0 + a1*x1 + a0*x2 + ... + a3*x[n-1] = 0 ... a[n-1]*x0 + a[n-2]*x1 + a[n-3]*x2 + ... + a0*x[n-1] = 0 Можно применять метод Гаусса с введенными в предыдущем пункте операциями сложения и умножения. В результате чего можно найти решения этой системы. Однако к системе a0*x0 + ... + a1*x[n-1] - Q*x[n] = 1 a1*x0 + ... + a2*x[n-1] - Q*x[n+1] = 0 ... a[n-1]*x0 + .. + a0*x[n-1] ... Q*x[2*n-1] = 0 такой подход уже не применим, поскольку величина Q имеет значение не из множества {0,1,2} а из множества [2..100], а величины x[n], ..., x[2*n-1] - и вовсе произвольные целые числа. Если же мы будем решать последнюю систему над всем кольцом целых чисел, непонятно как нам "сузиться" в результате до решений, у которых x0 ... x[n-1] имеют целые значения в дипазоне [0..2] 4.2. Система уравнений Схожая проблема возникает и при попытке решать задачу "Система уравнений": Украинская олимпиада 2003 года, День 2, Задача 3 Задача 3. Система уравнений (100 баллов) Пусть k-ое уравнение системы из N уравнений имеет вид X+Y=bk, где X=x1k+x2k+...+xk-1 k; Y=xk k+1+...+xk N. Таким образом, левая часть каждого уравнения имеет (N-1)-но слагаемое и каждое неизвестное встречается ровно в двух уравнениях системы. Задание Напишите программу SYSTEM, которая по заданным b1,:,bN находит одно из решений системы, при условии что неизвестные xij могут принимать только значения 0 либо 1. Входные данные В первой строке входного файла SYSTEM.DAT находится натуральное число - количество тестовых блоков. Каждый тестовий блок начинается со строки, которая содержит число N (3<=N<=50) -количество уравнений в системе. Во второй строке блока находится N целых чисел bi (0<=bi<=50). Выходные данные Для каждого тестового блока в выходной файл SYSTEM.SOL должно быть записано одно из решений системи: (N-1)-на строка, каждая k-ая из которых содержит N-k чисел - найденных значений неизвестных: x12 ... x1N x23 ... x2N x34 ... x3N ... xN-1 N Если система не имеет решений для тестового блока, в выходной файл должна быть записана строка, которая содержит единственное число -1. Пример входных и выходных данных SYSTEM.DAT SYSTEM.SOL 2 -1 3 1 1 1 0 1 2 3 0 0 1 5 1 1 3 2 3 2 2 0 Формализация постановки задачи "Системы уравнений" может вглядеть следующми образом: требуется решать систему вида a11*x1 + a12*x2 + ... a1K*xK = b[1] a21*x1 + a22*x2 + ... a2K*xK = b[2] ... aN1*x1 + aN2*x2 + ... aNK*xK = b[N] Где Xi могут принимать значения только 0 и 1. K = (N-1) + (N-2) + ...+ 1 = (1+N-1)*(N-1)/2=N*(N-1)/2 Для удобства сопоставления с неизвестными в терминологии задачи они обозначаются с двумерными индексами x12, x13, ... , x[1,N-1] x23, ... , x[2,N-1] ... x[N-1,N] b[i] заданы - и могут быть произвольными целыми числами из интервала [0,50] Aij заданы, принимают значения только 0 и 1 При этом в построении Aij имеется определенная система которую можно проиллюстрировать значениями Aij для разных N: 121323 N=3 1 1 0 x12 + x13 = b1 1 0 1 x12 + + x23 = b2 0 1 1 x13 + x23 = b3 121314232434 N=4 1 1 1 0 0 0 x12 + x13 + x14 = b1 1 0 0 1 1 0 x12 + x23 + x24 = b2 0 1 0 1 0 1 x13 + x23 + x34 = b3 0 0 1 0 1 1 x14 + x24 + x34 = b4 12131415232425343545 N=5 1 1 1 1 0 0 0 0 0 0 x12 + x13 + x14 + x15 = b1 1 0 0 0 1 1 1 0 0 0 x12 + x23 + x24 + x25 = b2 0 1 0 0 1 0 0 1 1 0 x13 + x23 + x34 + x35 = b3 0 0 1 0 0 1 0 1 0 1 x14 + x24 + x34 + x45 = b4 0 0 0 1 0 0 1 0 1 1 x15 + x25 + x35 + x45 = b5 Можно заметить, что для получения новой матрицы (N+1) из N необходимо добавить к прежней сверху строку c N-1 единицами и остальными нулями (над каждым элементом прежней матрицы). А в левой части (под добавленными в первой строке единицами) разместить единичную матрицу (единицы по диагонали, остальные элементы - нули). Здесь переменные X и коэффициенты A имеют значения из кольца {0,1}. А величины B - произвольные целые от 0 до 50. 4.3. Box of Mirrors Baltic Olympiad in Informatics, 2001, День 1 Задача 1. Box of Mirrors Математик Андрис любит различные головоломки и одна из самых его любимых головоломок - "ящик с зеркалами". Если мы посмотрим на такой ящик сверху, мы увидим, что его основание содержит n*m квадратных ячеек (n строк, m столбцов). В каждой ячейке может быть установлено зеркало, расположенное по диагонали ячейки - от ее левого нижнего угла к правому верхнему углу. Обе стороны зеркала отражают свет. По краям ящика (и вертикальным и горизонтальным) есть щель, через которую луч света может попасть в ящик или выйти из ящика. Через каждую такую щель луч может подаваться только в одном направлении - перпендикулярно ребру, содержащему щель. поэтому луч, отражаясь от зеркала изменяет свое направление на 90 градусов. Если луч проходит сквозь пустую ячейку, то он не меняет свое направление. Щели пронумерованы последовательно от 1 до 2*(n+m), вокруг ящика, против часовой стрелки, начиная с левой стороны самой верхней левой ячейки и вниз. Поскольку расположение зеркал в ящике является невидимым, то единственный способ его узнать - светить лучи в некоторые щели и смотреть где выходит из ящика соответствующий луч. Напишите программу, которая: - прочитает из файла box.in размер ящика и описания мест входа и выхода лучей - определит, какие из ячеек ящика содержат зеркала, а какие - нет - выведет результат в файл box.out Если возможно несколько решений, выведите любое. Ввод Первая строка входного файла box.in содержит два положительных числа n (количество строк, 1<=n<=100) и m (количество столбцов, 1<=m<=100), разделенных одним пробелом. Каждая из последующих 2*(n+m) строк содержит одно положительное целое число. Число в строке номер i+1 указывает номер щели, через которую выйдет луч света, направленный на входе в щель с номером i. Вывод Ваша программа должна вывести в выходной файл box.out n строк, каждая из которых содержит m целых чисел, разделенных одиночными пробелами. J-тое число в i-той строке должно быть равно 1, если в ячейке с номером строки i и номером столбца j есть зеркало, и равно 0, если там зеркала нет. Пример Входной файл box.in: Правильный ответ в файле box.out 2 3 0 1 0 9 0 1 1 7 10 8 6 5 2 4 1 3 Данная задача может быть формализована следующим образом: Пусть Xij = 1, если в ячейке (i,j) стоит зеркало 0, в противном случае Здесь принято, что левая верхняя ячейка имеет номер 1,1 и номер ячеек растут вниз (первый индекс) и вправо (второй индекс). Введем величины Uij = 1, если из ячейки (i,j) луч выходит вверх 0, в противном случае Rij = 1, если из ячейки (i,j) луч выходит вправо 0, в противном случае Тогда можно заметить, что имеют место следующие равенства: ___ Uij = R[i,j-1]&Xij \/ U[i+1,j]&Xij ___ Rij = R[i,j-1]&Xij \/ U[i+1,j]&Xij То есть для первого уравнения Луч будет выходить вверх из клетки (i,j) в том случае, если он вошел в эту клетку слева (R[i,j-1]=1, луч вышел вправо в клетке слева [i,j-1]), и в этой клетке [i,j] установлено зеркало (Xij=1) ИЛИ в том случае, если он вошел в эту клетку снизу (U[i+1,j]=1, луч вышел вверх в клетке снизу [i+1,j]) и в этой клетке [i,j] нет зеркала (Xij=0) Аналогично для второго уравнения Луч будет выходить вправо из клетки (i,j) в том случае, если он вошел в эту клетку слева (R[i,j-1]=1, луч вышел вправо в клетке слева [i,j-1]), и в этой клетке [i,j] не установлено зеркало (Xij=0) ИЛИ в том случае, если он вошел в эту клетку снизу (U[i+1,j]=1, луч вышел вверх в клетке снизу [i+1,j]) и в этой клетке [i,j] есть зеркало (Xij=1) По условиям задачи нам заданы R[i,0] и U[N+1,i] для всех i. Требуется, решив эту систему уравнений, найти Xij. Похоже что имеем систему НЕЛИНЕЙНЫХ уравнений.