e-olimp 8536. Заповнення смуги $3 \times n$

02/12/2020 by Анна Цивинская

Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.

Задача

Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

Вхідні дані

Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.

Вихідні дані

Вивести кількість способів, якими можна заповнити смугу.

Тести

Вхідні дані	Вихідні дані
1	1
5	4
12	60
50	122106097

Код № 1

import java.util.Scanner;

class Main {
	public static void main (String[] args) {
	    Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
	    int[] F = new int[51];
	    F[0] = 0;
	    F[1] = 1;
	    F[2] = 1;
	    F[3] = 2;
	    F[4] = 3;
	    for(int i = 5; i <= n; i++) {
	       F[i] = F[i-2] + F[i-3] + F[i-4];
	    }
	    System.out.println(F[n]);
	}
}

import java.util.Scanner;

class Main {

public static void main (String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int[] F = new int[51];

F[0] = 0;

F[1] = 1;

F[2] = 1;

F[3] = 2;

F[4] = 3;

for(int i = 5; i <= n; i++) {

F[i] = F[i-2] + F[i-3] + F[i-4];

}

System.out.println(F[n]);

}

Рішення 1

Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

Код № 2

import java.util.Scanner;

public class Main {
	public static int[] F = new int[51];
	public static int numberOfWays(int n){
		F[0] = 0;
		F[1] = 1;
		F[2] = 1;
		F[3] = 2;
		F[4] = 3;
	    if(F[n] > 0) {
    		return F[n];
		} else {
    		F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);
		}
		return F[n];
	}
	public static void main (String[] args){
	    Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
	    System.out.println(numberOfWays(n));
	}
}

import java.util.Scanner;

public class Main {

public static int[] F = new int[51];

public static int numberOfWays(int n){

F[0] = 0;

F[1] = 1;

F[2] = 1;

F[3] = 2;

F[4] = 3;

if(F[n] > 0) {

return F[n];

} else {

F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);

}

return F[n];

}

public static void main (String[] args){

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

System.out.println(numberOfWays(n));

}

Рішення 2

Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

Посилання

Код задачі № 1 на Ideone
Код задачі № 2 на Ideone

e-olymp 9414. Убить всех термитов

03/10/2020 by Андрей Метасов

Условие задачи

На дереве живут термиты. Ваша задача убить их всех. Дерево является неориентированным связным графом с $n$ вершинами и $n — 1$ ребрами. Чтобы убить термитов, Вам следует отравить некоторые вершины. Если термит попадает на вершину с ядом, то он немедленно умирает. Вы не знаете, где изначально находятся термиты. Но Вы знаете, что термиты каждый раз попадают в случайную соседнюю вершину. Однако если термит прошел ребро $(u, v)$, то следующее ребро должно отличаться от $(v, u)$ за исключением случая, когда термит попадает в лист (в этом случае термит поворачивается и возвращается назад). Вам следует отравить минимальное количество вершин так, чтобы термиты попали в отравленные вершины после конечного числа шагов.

Входные данные

Первая строка содержит одно целое число $n$ $(1 \leqslant n \leqslant 100000)$. Следующая строка содержит $n — 1$ целое число $p_{i} (2 \leqslant i \leqslant n)$, означающее что ребро соединяет $p_{i}$ и $i$.

Выходные данные

Выведите минимальное количество отравленных вершин.

Тесты

№	Входные данные	Выходные данные
1	1	1
2	2 1	1
3	8 1 1 2 1 2 3 2	2
4	5 1 2 1 4	1
5	16 1 2 3 4 5 3 7 1 9 9 11 11 13 13 15	3
6	10 1 2 3 3 1 2 3 7 9	2
7	8 1 1 3 3 1 6 6	2

Код

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static final int NMAX = 100001;
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>> (NMAX);
    static ArrayList<Integer> killed = new ArrayList<Integer> (NMAX);
    static ArrayList<Boolean> used = new ArrayList<Boolean> (NMAX);
    static ArrayList<Integer> dist = new ArrayList<Integer> (NMAX);
    static int ans = 0;

    public static void kills(int v, int p)
    {
        if (v == p) kills(tree.get(v).get(0), v);
        if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) kills(to, v);
        if (tree.get(v).size() >= 3) killed.set(v, killed.get(v) + 1);
        return;
    }

    public static void goup(int v, int p)
    {
        if (v == p)
        {
            for (Integer to : tree.get(v)) if (dist.get(to) < dist.get(v)) goup(to, v);
            killed.set(v, 0);
            return;
        }
        if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) goup(to, v);
        if (tree.get(v).size() >= 3)
        {
            killed.set(v, killed.get(v) + 1);
            return;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int i=0;i<NMAX; i++)
        {
            tree.add(new ArrayList<Integer>());
            dist.add(0);
            used.add(false);
            killed.add(0);
        }
        int n,v;
        n = in.nextInt();
        if (n <= 5) {System.out.print(1); return;} // Частный случай
        tree.get(1).add(0); // Корень тоже должен быть "развилкой"
        ArrayList<Integer> leaves = new ArrayList<Integer> ();
        for (int i = 1; i < n; i++)
        {
            v = in.nextInt();
            tree.get(v).add(i+1);
            tree.get(i+1).add(v); //Заполнение графа в том виде, в котором его дают
        }

        for (int i = 1; i <= n; i++)
        {
            if (tree.get(i).size() == 1 || (i == 1 && tree.get(i).size() == 2)) leaves.add(i); //Запоминаем все листья
        }

        LinkedList<Integer> q = new LinkedList<>(); dist.set(1, 0);
        q.offer(1); used.set(1, true);
        while (!q.isEmpty())
        {
            int qv = q.poll();
            used.set(qv, true);
            for (Integer to : tree.get(qv))                //BFS заполняющий вектор dist
            {
                if (!used.get(to))
                {
                    q.offer(to);
                    dist.set(to, dist.get(qv)+1);
                }
            }
        }

        for (Integer l : leaves)
        {
            kills(l, l);        // Первый этап - запросы от каждого листа
        }

        int maxdist = -1; for (int i = 1; i <= n; i++) maxdist = Math.max(maxdist, dist.get(i)); // Определение максимального "уровня" дерева
        int wentup = 1;
        while (wentup != 0)
        {
            wentup = 0;
            for (int l = maxdist; l > 0; l--)
            {
                for (int i = 2; i <= n; i++)
                {
                    if (killed.get(i) == 1 && dist.get(i) == l)
                    {
                        goup(i, i);                    //Этап 2 - поднятие "недошедших" запросов
                        wentup++;
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) if (killed.get(i) >= 2) ans++; //Финальный подсчет "отравленных" развилок
        System.out.print(ans);
    }
}

100

101

102

103

104

105

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class Main {

static final int NMAX = 100001;

static ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>> (NMAX);

static ArrayList<Integer> killed = new ArrayList<Integer> (NMAX);

static ArrayList<Boolean> used = new ArrayList<Boolean> (NMAX);

static ArrayList<Integer> dist = new ArrayList<Integer> (NMAX);

static int ans = 0;

public static void kills(int v, int p)

{

if (v == p) kills(tree.get(v).get(0), v);

if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) kills(to, v);

if (tree.get(v).size() >= 3) killed.set(v, killed.get(v) + 1);

return;

}

public static void goup(int v, int p)

{

if (v == p)

{

for (Integer to : tree.get(v)) if (dist.get(to) < dist.get(v)) goup(to, v);

killed.set(v, 0);

return;

}

if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) goup(to, v);

if (tree.get(v).size() >= 3)

{

killed.set(v, killed.get(v) + 1);

return;

}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

for (int i=0;i<NMAX; i++)

{

tree.add(new ArrayList<Integer>());

dist.add(0);

used.add(false);

killed.add(0);

}

int n,v;

n = in.nextInt();

if (n <= 5) {System.out.print(1); return;} // Частный случай

tree.get(1).add(0); // Корень тоже должен быть "развилкой"

ArrayList<Integer> leaves = new ArrayList<Integer> ();

for (int i = 1; i < n; i++)

{

v = in.nextInt();

tree.get(v).add(i+1);

tree.get(i+1).add(v); //Заполнение графа в том виде, в котором его дают

}

for (int i = 1; i <= n; i++)

{

if (tree.get(i).size() == 1 || (i == 1 && tree.get(i).size() == 2)) leaves.add(i); //Запоминаем все листья

}

LinkedList<Integer> q = new LinkedList<>(); dist.set(1, 0);

q.offer(1); used.set(1, true);

while (!q.isEmpty())

{

int qv = q.poll();

used.set(qv, true);

for (Integer to : tree.get(qv)) //BFS заполняющий вектор dist

{

if (!used.get(to))

{

q.offer(to);

dist.set(to, dist.get(qv)+1);

}

for (Integer l : leaves)

{

kills(l, l); // Первый этап - запросы от каждого листа

}

int maxdist = -1; for (int i = 1; i <= n; i++) maxdist = Math.max(maxdist, dist.get(i)); // Определение максимального "уровня" дерева

int wentup = 1;

while (wentup != 0)

{

wentup = 0;

for (int l = maxdist; l > 0; l--)

{

for (int i = 2; i <= n; i++)

{

if (killed.get(i) == 1 && dist.get(i) == l)

{

goup(i, i); //Этап 2 - поднятие "недошедших" запросов

wentup++;

}

for (int i = 1; i <= n; i++) if (killed.get(i) >= 2) ans++; //Финальный подсчет "отравленных" развилок

System.out.print(ans);

}

Решение задачи

Поскольку в задаче речь идет о дереве, циклов в нем нет по определению. Значит, единственным способом для термита ходить «вечно» будет путь между двумя листами, в которых он сможет разворачиваться. Фактически, задача сводится к вопросу «Какое минимальное количество вершин в дереве нужно отравить, чтобы нельзя было добраться из любого листа в другой лист не пройдя через отравленные?».

Определим для этого $3$ типа вершин: лист, развилка и обычная вершина. Листом назовем вершину, у которой нет детей (всего $1$ связь с другой вершиной). Обычные вершины — те, у которых ровно $2$ связи (для нашего термита это пути вниз или вверх). Развилкой назовем вершину, у которой $3$ или больше связей с другими. Будем считать корень тоже развилкой, даже если у него всего $2$ связи, или листом, если одна. Через развилки можно ходить из одного листа в другой, либо «вверх» — в сторону корня.

$1$ — корень; $5,6,3$ — листья; $4$ — развилка; $2$ — обычная;

Первый этап

Очевидно, выгоднее всего «закрывать» развилки. А среди них — те, которые соединяют несколько листов напрямую. Пусть каждый лист отправляет «запрос» вверх по дереву на закрытие ближайшей к нему развилки. Когда «запрос» доходит до развилки, он тут же записывается на её счёт. Таким образом, в дереве выше вершина $4$ будет иметь $2$ запроса — от листов $5$ и $6$, а корень — $1$ запрос от листа $3$.

Теперь, просто считаем количество вершин с количеством запросов $\geqslant2$ и «закрываем» их.

Второй этап

Увы, первый этап не идеален и может «не донести» запросы в нужное место, т.к. некоторые развилки (а именно — соединяющие лист и другую развилку) могут остаться с одним запросом и не быть закрытыми. Если таких много, термит все еще может ходить между листами. Например, в таком дереве:

Дерево, в котором необходим второй этап

Вершина $2$ и корень получают по $1$ запросу и остаются открытыми, а у термита остается путь между листами $10$ и $6$.

Для предотвращения таких случаев, пробежимся по дереву «снизу вверх» — от самого нижнего уровня до верхнего и для каждой развилки, у которой ровно $1$ запрос, сместим его вверх аналогично первому этапу — до ближайшей развилки. Будем выполнять этот шаг, пока есть такие вершины (с $1$ запросом).

В итоге, все запросы «соединятся» в нужных развилках, значение в них станет $\geqslant2$ и эти развилки нужно будет тоже закрыть. Для дерева выше, будет закрыт корень.

Осталось посчитать кол-во закрытых.

Описание алгоритма

Дерево будем хранить в ArrayList<ArrayList<Integer>> tree . Количество запросов для вершины $i$ хранится в killed.get(i). Стандартный ArrayList used для поиска в ширину и dist- ArrayList расстояний от корня до вершин, которые и будут определяться с помощью BFS.

Функция kills предназначена для того, чтобы донести запрос от листа до развилки. Она рассматривает $3$ случая:

v == p — текущая вершина совпадает с той, из которой пришли. Это крайний случай, говорящий о том, что мы только начали и находимся в листе. Тогда, идем в единственно возможном направлении — tree.get(v).get(0).
tree.get(v).size() == 2 — вершина обычного типа, просто идем «вверх», выбирая из двух путей тот, что не совпадает с предыдущей вершиной.
tree.get(v).size() >= 3 — попали в развилку. Увеличиваем ее значение killed.get(v) и выходим из рекурсии.

Функция goup отличается от kills лишь тем, что при v == p выбирает из всех направлений то, которое ближе к корню, используя dist.

Подготовка

Можно заметить, что для всех деревьев из $5$ или менее вершин ответ будет $1$. Проверим это сразу при вводе n. Далее, осторожно считываем дерево в tree (см. Входные данные). В следующем цикле, определяем листья и запоминаем их в ArrayList leaves. Нужно учесть то, что корень может быть листом, если у него всего $2$ связи — одна с деревом, а другая — искусственно созданная нами в $0$ вершину. Последний шаг — запустить поиск в ширину из корня, который заполнит ArrayList dist расстояниями от корня до вершин.

Первый этап

Просто запускаем kills (l, l) из каждого листа l для «отправки» запросов в ближайшие развилки.

Второй этап

Определяем максимальную «глубину» дерева — максимальное расстояние вершины от корня. Далее, для каждого уровня от самого нижнего до корня, при определении вершины со значением killed.get(i) == 1 запускаем goup (i, i), а в переменной wentup считаем количество таких случаев. Как только их не останется — while выйдет из цикла.

Наконец, осталось просто посчитать количество вершин, у которых значение killed.get(i) >= 2.
Задача на e-olymp
Код решения на ideone
Засчитанное решение на e-olymp

e-olimp 1658. Факториал

19/09/2020 by Елизавета Савицкая

Задача

Вычислите факториал числа.

Входные данные

Одно целое число [latex]n[/latex] ([latex] 0 \leqslant n \leqslant 20[/latex]).

Выходные данные

Выведите значение [latex]n! = 1 · 2 · 3 · … · n.[/latex]

Тесты

Входные данные	Выходные данные
3	6
0	1
20	2432902008176640000

Решение №1

class Main {
	public static void main (String[] args) throws java.lang.Exception {
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		long factorial = 1;
    	for(int k = 1; k <= n; k++) {
        	factorial *= k;
    	}
    	System.out.print(factorial);
	}
}

class Main {

public static void main (String[] args) throws java.lang.Exception {

java.util.Scanner i = new java.util.Scanner(System.in);

int n = i.nextInt();

long factorial = 1;

for(int k = 1; k <= n; k++) {

factorial *= k;

}

System.out.print(factorial);

}

Факториал натурального числа [latex]n[/latex] определяется как произведение всех натуральных чисел от [latex]1[/latex] до [latex]n[/latex] включительно.

Решение №2

public class Main{
	public static long factorial(int a){
		if (a == 0)
        	return 1;
        else
        	return a*factorial(a - 1);
    }
    public static void main (String[] args) throws java.lang.Exception 	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int a;
		int n = i.nextInt();
        System.out.print(factorial(n));
	}
}

public class Main{

public static long factorial(int a){

if (a == 0)

return 1;

else

return a*factorial(a - 1);

}

public static void main (String[] args) throws java.lang.Exception {

java.util.Scanner i = new java.util.Scanner(System.in);

int a;

int n = i.nextInt();

System.out.print(factorial(n));

}

Также факториал числа можно найти при помощи рекурсивной функции (функции, которая вызывает сама себя).

Ссылки

Условие задачи на E-Olymp
Код задачи № 1 на Ideone
Код задачи № 2 на Ideone

e-olymp 2214. Функция 9

25/12/2018 by Андрей Лисовой

Задача

Дана функция, аргументы которой — произвольные натуральные числа
$$f(M, N)=\begin{cases}
f(M-N, N), & \text{ npu } M>N \\
N, & \text{ npu } M=N \\
f(N-M, M), & \text{ npu } N>M
\end{cases}$$
Составить алгоритм (написать программу), вычисляющий значение функции.

Вводные данные

Два натуральных числа $n$ и $m$ $(1\leq n, m \leq 10^{18}).$

Выходные данные

Искомое значение функции.

Тесты

Входные данные	Выходные данные
$6$ $3$	$3$
$12$ $12$	$12$
$126$ $98$	$98$
$10329$ $1501$	$1501$
$1008359$ $15113$	$15113$

Код программы

import java.util.*;

class Main
{
	public static void main (String[] args) {
		Scanner in = new Scanner(System.in);
    	        long n, m;
    	        n = in.nextLong();
    	        m = in.nextLong();
    	        System.out.print(f(n, m));
	}
	static long f(long n, long m) {
		if (n % m == 0) return m;
	        if (m % n == 0) return n;
	        if (m > n) return f(m % n, n);
	        else return f(n % m , m);
	}
}

import java.util.*;

class Main

{

public static void main (String[] args) {

Scanner in = new Scanner(System.in);

long n, m;

n = in.nextLong();

m = in.nextLong();

System.out.print(f(n, m));

}

static long f(long n, long m) {

if (n % m == 0) return m;

if (m % n == 0) return n;

if (m > n) return f(m % n, n);

else return f(n % m , m);

}

Решение задачи

Для решения задачи напишем функцию f. Именно эта функция и будет считать искомое значение. Из условия задачи видим, что для решения потребуется рекурсия. Для этого, если остаток от деления одного натурального числа на другое не равен нулю, то мы снова возращаемся в функцию (в зависимости от того, что больше $n$ или $m$). Это будет продолжаться до тех пор, пока остаток от деления одного натурального числа на другое не будет равен нулю (как только $n \mod m = 0$ или $m \mod n = 0,$ то функция возращает в переменную искомое значение). Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 1521. Оптимальное умножение матриц

18/12/2018 by Кирилл Волков

Задача

Имея два двумерных массива $A$ и $B$, мы можем вычислить $C = AB$ используя стандартные правила умножения матриц:

$$C_{ij} = \sum_{k}A_{ik}{Bkj}$$

Число колонок в массиве $A$ должно совпадать с числом строк массива $B$. Обозначим через $rows(A)$ и $columns(A)$ соответственно количество строк и колонок в массиве $A.$ Количество умножений, необходимых для вычисления матрицы $C$ (ее количество строк совпадает с $A$, а количество столбцов с $B$) равно $rows(A)$ $columns(B)$ $columns(A).$ Например, если A имеет размер 10 × 20, B имеет размер 20 × 15, то для их умножения необходимо совершить 10 × 15 × 20, или 3000 умножений для вычисления матрицы $C.$

Перемножать несколько матриц можно несколькими способами. Например, если у нас имеются матрицы $X$, $Y$ и $Z$, то вычислить $XYZ$ можно либо как $(XY)Z$, либо как $X(YZ)$. Пусть $X$ имеет размер 5 × 10, $Y$ имеет размер 10 × 20, $Z$ имеет размер 20 × 35. Подсчитаем количество умножений, необходимых для перемножения трех матриц в каждом из этих двух случаях:

$(XY)Z$

$5 × 20 × 10 = 1000$ умножений для определения матрицы (XY), имеющей размер $5 × 20.$
Потом $5 × 35 × 20 = 3500$ умножений для нахождения конечного результата.
Общее количество умножений: $4500.$
$X(YZ)$

$10 × 35 × 20 = 7000$ умножений для определения матрицы (YZ), имеющей размер $10 × 35.$
Потом $5 × 35 × 10$ умножений для нахождения конечного результата.
Общее количество умножений: $8750.$
Очевидно, что при вычислении $(XY)Z$ требуется меньшее количество умножений.

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

Входные данные
Для каждой последовательности перемножаемых матриц Вам будут даны лишь размеры матриц. Каждый тест состоит из количества $n (n \leq 10)$ перемножаемых матриц, за которым следуют $n$ пар целых чисел, описывающих размеры матриц (количество строк и столбцов); размеры матриц задаются в порядке их перемножения. Последний тест содержит $n = 0$ и не обрабатывается.

Выходные данные
Пусть матрицы пронумерованы $A1, A2,\ldots, An.$ Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются начиная с 1. Вывод должен строго соответствовать формату, приведенному в примере. Если существует несколько оптимальных порядков перемножения матриц, выведите любой из них.

Тесты

Входные данные	Выходные данные
3 1 5 5 20 20 1 3 5 10 10 20 20 35 6 30 35 35 15 15 5 5 10 10 20 20 25 0	Case 1: (A1 x (A2 x A3)) Case 2: ((A1 x A2) x A3) Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
10 653 273 273 692 692 851 851 691 691 532 532 770 770 690 690 582 582 519 519 633 0	Case 1: (A1 x ((((((((A2 x A3) x A4) x A5) x A6) x A7) x A8) x A9) x A10))
2 11 12 12 33 7 1 5 5 28 28 19 19 2 2 10 10 1 1 12 4 10 29 29 133 133 8 8 15 0	Case 1: (A1 x A2) Case 2: (((((A1 x A2) x A3) x A4) x (A5 x A6)) x A7) Case 3: ((A1 x (A2 x A3)) x A4)

Код программы

import java.util.Scanner;

public class Main {
    private static class Matrix {
        private int width;
        private int height;

        public Matrix(int width, int height) {
            this.width = width;
            this.height = height;
        }
    }

    private static long multiple(long[][] dp, Matrix[] sizes, int[][] bestCut, int l, int r ) {
        if (dp[l][r] == Long.MAX_VALUE) {
            for (int i = l; i < r; i++) {
            long cur = multiple(dp, sizes, bestCut, l, i) + multiple(dp, sizes, bestCut, i + 1, r) + sizes[l].width * sizes[i].height * sizes[r].height;
                if (cur < dp[l][r]) {
                    dp[l][r] = cur;
                    bestCut[l][r] = i;
                }
            }
        }
        return dp[l][r];
    }

    private static void print(int l, int r, int[][] bestCut) {
        if (l == r) {
            System.out.print("A" + (l + 1));
        }
        else {
            System.out.print("(");
            print(l, bestCut[l][r], bestCut);
            System.out.print(" x ");
            print(bestCut[l][r] + 1, r, bestCut);
            System.out.print(")");
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int c = 1, n = sc.nextInt(); n != 0; n = sc.nextInt(), c++) {
            long[][] dp = new long[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j] = Long.MAX_VALUE;
                }
            }
            Matrix[] sizes = new Matrix[n];
            int[][] bestCut = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    bestCut[i][j] = Integer.MAX_VALUE;
                }
            }
            for (int i = 0; i < n; i++) {
                int width = sc.nextInt();
                int height = sc.nextInt();
                sizes[i] = new Matrix(width, height);
            }
            for (int i = 0; i < n; i++) {
                dp[i][i] = 0;
            }
            multiple(dp, sizes, bestCut, 0, n-1);
            System.out.print("Case " + c + ": ");
            print(0, n - 1, bestCut);
            System.out.println();
        }
    }
}

import java.util.Scanner;

public class Main {

private static class Matrix {

private int width;

private int height;

public Matrix(int width, int height) {

this.width = width;

this.height = height;

}

private static long multiple(long[][] dp, Matrix[] sizes, int[][] bestCut, int l, int r ) {

if (dp[l][r] == Long.MAX_VALUE) {

for (int i = l; i < r; i++) {

long cur = multiple(dp, sizes, bestCut, l, i) + multiple(dp, sizes, bestCut, i + 1, r) + sizes[l].width * sizes[i].height * sizes[r].height;

if (cur < dp[l][r]) {

dp[l][r] = cur;

bestCut[l][r] = i;

}

return dp[l][r];

}

private static void print(int l, int r, int[][] bestCut) {

if (l == r) {

System.out.print("A" + (l + 1));

}

else {

System.out.print("(");

print(l, bestCut[l][r], bestCut);

System.out.print(" x ");

print(bestCut[l][r] + 1, r, bestCut);

System.out.print(")");

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

for (int c = 1, n = sc.nextInt(); n != 0; n = sc.nextInt(), c++) {

long[][] dp = new long[n][n];

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

dp[i][j] = Long.MAX_VALUE;

}

Matrix[] sizes = new Matrix[n];

int[][] bestCut = new int[n][n];

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

bestCut[i][j] = Integer.MAX_VALUE;

}

for (int i = 0; i < n; i++) {

int width = sc.nextInt();

int height = sc.nextInt();

sizes[i] = new Matrix(width, height);

}

for (int i = 0; i < n; i++) {

dp[i][i] = 0;

}

multiple(dp, sizes, bestCut, 0, n-1);

System.out.print("Case " + c + ": ");

print(0, n - 1, bestCut);

System.out.println();

}

Решение задачи

Обозначим результат перемножения матриц ${\displaystyle A_{i}A_{(i+1)}…A_{j}}$ ${\displaystyle A_{i}A_{(i+1)}…A_{j}}$ через ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$, где i\leq j. Если i<j, то существует такое k, которое разбивает ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$ между матрицами ${\displaystyle A_{k}}$ A_k и ${\displaystyle A_{k+1}}$ A_${{k+1}}$, i\leq k<j. То есть для вычисления ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$ надо сначала вычислить ${\displaystyle A_{i..k}}$ ${\displaystyle A_{i..k}}$, потом ${\displaystyle A_{k+1..j}}$ ${\displaystyle A_{k+1..j}}$ и затем их перемножить. Выбор $k$ является аналогом расстановки скобок между матрицами. Выбрав некоторое $k$ мы свели задачу к двум аналогичным подзадачам для матриц ${\displaystyle A_{i..k}}$ ${\displaystyle A_{i..k}}$ и ${\displaystyle A_{k+1..j}}$ ${\displaystyle A_{k+1..j}}.$ Объясняется оно просто: для того, чтобы найти произведение матриц ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$ при i=j не нужно ничего делать — это и есть сама матрица ${\displaystyle A_{i}}$ A_${i}.$ При нетривиальном случае мы перебираем все точки разбиения матрицы ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$ на матрицы ${\displaystyle A_{i..k}}$ ${\displaystyle A_{i..k}}$ и ${\displaystyle A_{k+1..j}}$ ${\displaystyle A_{k+1..j}}$, ищем кол-во операций, необходимое чтобы их получить и затем перемножаем для получения матрицы ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}.$ (Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц ${\displaystyle A_{i..k}A_{k+1..j}}$ ${\displaystyle A_{i..k}A_{k+1..j}}$). Считаем, что размеры матриц заданы в массиве ${\displaystyle p}$ p и размер матрицы ${\displaystyle A_{i}}$ A_${i}$ равен ${\displaystyle p_{i-1}\times p_{i}}$ ${\displaystyle p_{i-1}\times p_{i}}.$ Будем запоминать в двумерном массиве m результаты вычислений для подзадач, чтобы избежать пересчета для уже вычислявшихся подзадач.

Ссылки

Описание алгоритма решения
Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone