Реальные задачи на C

Недавно попали ко мне тексты задач по программированию, которые даются реальным студентам одного московского университета в качестве заданий на лабораторные работы. Язык — С, программы консольные.

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

Задача: Сочи-2014

В рамках строительства олимпийских объектов местным чиновникам было поручено предложить план дороги на участке недалеко от Сочи. Участок можно схематично представить как матрицу из NxM подучастков, для каждого из которых выделяется некая сумма на его освоение. Дорогой называется такой набор из M подучастков, что в каждом столбце содержится ровно по одному подучастку и для подучастков с координатами (i1, j) и (i2, j+1) верно, что |i1-i2| ≤ 1. Соответственно, сумма денег, выделяемых на освоение дороги, равна сумме денег выделяемых на каждый из её подучастков. Так как большая сумма несомненно приведёт к лучшему качеству исполнения дороги в целом, чиновники заинтересованы в максимизации осваиваемых средств. Ваша задача в том, чтобы помочь России не упасть в грязь лицом на предстоящих играх.

Задача: Решение системы линейных уравнений

Грустная панда сидит и смотрит на систему линейных алгебраических уравнений Ax = b с целочисленными коэффициентами. С первого взгляда бросается в глаза, что все эти коэффициенты невелики. Для того, чтобы развеселить панду, требуется реализовать программу, которая смогла бы найти точное решение этой системы.

На вход программе подается натуральное число N (N ≤ 500) и последовательность целых чисел a11, a12, ..., a1N, b1, a21, ...., aNN, bN. Требуется вывести последовательность целых чисел x1, ..., xN, являющихся решением данной системы уравнений.
Панда уверена в том, что такое решение существует и единственно.

Задача: Апельсин

К Вам на улице подходит незнакомец и говорит, что всем известно эффективное решение задачи вычисления i-ого члена последовательности Фибоначчи по модулю числа p*. Однако, теперь его интересует более общая задача для произвольной линейной рекуррентной последовательности, заданной формулой
Fn = A1 * Fn-1 + ... + AkFn-k.
Не в силах противостоять ему, Вы решаете помочь. Ваша задача посчитать FN mod p.

Задача: Экстерминатус

Мир наш исполнен войны — целая вечность сражений во имя Императора. Он никогда не прекращает и не отступается от бесконечной вражды, а значит - не должны и мы.

Второй год Похода Мучений. В отдалённой системе войска Императора столкнулись с планетой полной ужасающих человекоподобных зверей, представляющих собой серьёзную угрозу. После ожесточённых боёв связь с ударным отрядом чёрных тамплиеров во главе с братом Герхартом была потеряна, в связи с чем было приятно единственно верное решение в таких ситуациях — ЭКСТЕРМИНАТУС, то есть полное уничтожение всего живого на поверхности. Для запуска орбитальной бомбардировки требуются специальные коды. Обычно они приходят на отдельный канал и с ними не возникает никаких проблем, но в этот раз в связи с оплошностью подчинённого несколько передач принимались по одному каналу и результаты перемешались. Ваша задача состоит в том, чтобы извлечь из полученной информации коды запуска орудий.

Передача состоит из заглавных и строчных латинских букв, цифр, а также 4 основных арифметических действий '+', '-', '*', '/'. Её длина не превосходит 2000 символов. Известно, что кодом является некоторая команда вида A op B, где A и B — целые неотрицательные числа, а op - одно из арифметических действий, результат которой является корректно вычислимым выражением модуль которого не превосходит 120000. При этом выражение "A op B" является подстрокой исходного сообщения. Гарантируется, что числа A,B и результат операции над ними не переполняют 32-х битные целые знаковые числа. Необходимо найти все такие команды и вывести их каждую с новой строки в виде A op B = res, где res — результат вычисления. Всё остальное считается мусором из других передач. Заметим, что для выражения A op1 B op2 C нужно вывести

A op1 B = res1
B op2 C = res2

Examples

Input
rDU+9519+28006-
+45350-80003-7034/14870/50385i-25266-39120*8557

Output
9519 + 28006 = 37525
45350 - 80003 = -34653
80003 - 7034 = 72969
7034 / 14870 = 0
14870 / 50385 = 0
25266 - 39120 = -13854

Задача: Генерал танковых войск

Генерал танковых войск Петя из 8Б класса проснулся в это субботнее утро в приподнятом настроении. Сегодня он и его верные братья по оружию нанесут решительный удар по Берлину, отомстят своим жалким недругам из 9В класса, добудут много золота и покроют себя славой. И в этот раз никакие ничего не понимающие в тактике главнокомандующие-родители не прервут героическую операцию под предлогом того, что ночные наступления совершенно недопустимы. К сожалению, Петя обнаружил, что один из родителей, недовольный тем, что успехи Пети вне поля сражения не дотягивают даже до звания рядового, сменил пароль от компьютера. Рядом Петей была найдена бумажка с длинной строкой. Вспомнив все предыдущие пароли, он понял, что каждый новый является подстрокой данной строки. Прикинув время, необходимое для проверки одного пароля, Петя теперь хочет подсчитать сколько вообще паролей возможно, чтобы понять, успеет ли он к ночному наступлению. Разделите горе Пети и помогите ему.

Задача: Пожалуйста, прочтите: личное обращение родителей Олега

У мальчика Олега редкая болезнь: боязнь условных переходов и команд условной передачи данных. Мальчик очень хочет стать программистом, но для этого необходимо дорогостоящее лечение в Германии. Однако есть и паллиативное решение. Помогите мальчику Олегу написать программу, вычисляющую модуль введённого числа, но не применяя инструкций условных переходов и условной передачи данных. Используя это решение как пример, он сможет писать и другие программы, несмотря на свой недуг.
Update от автора задач: эта  — на ассемблере.