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

e-olymp 1225. Черный Ящик

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

Задача

Черный Ящик представляет собой примитивную базу даных. Он может хранить массив целых чисел, а также имеет специальную переменную $i$. В начальный момент Черный Ящик пустой, переменная $i$ равна $0$. Черный Ящик обрабатывает последовательность команд (транзакций). Существует два типа транзакций:
ADD(x): добавить элемент x в Черный Ящик;
GET: увеличить $i$ на $1$ и вывести $i$-ый минимальный элемент среди всех чисел, находящихся в Черном Ящике.
Помните, что $i$-ый минимальный элемент находится на $i$-ом месте после того как все элементы Черного Ящика будут отсортированы в неубывающем порядке.
Рассмотрим работу черного ящика на примере:

№	Транзакция	$i$	Содержимое Черного Ящика после транзакции	Ответ
1	ADD(3)	0	3
2	GET	1	3	3
3	ADD(1)	1	1, 3
4	GET	2	1, 3	3
5	ADD(-4)	2	-4, 1, 3
6	ADD(2)	2	-4, 1, 2, 3
7	ADD(8)	2	-4, 1, 2, 3, 8
8	ADD(-1000)	2	-1000, -4, 1, 2, 3, 8
9	GET	3	-1000, -4, 1, 2, 3, 8	1
10	GET	4	-1000, -4, 1, 2, 3, 8	2
11	ADD(2)	4	-1000, -4, 1, 2, 2, 3, 8

Необходимо разработать эффективный алгоритм выполнения заданной последовательности транзакций. Максимальное количество транзакций ADD и GET равно $30000$ (каждого типа).
Опишем последовательность транзакций двумя целочисленными массивами:

$A_1, \ A_2, \ldots , \ A_m:$ последовательность элементов, которая будет добавляться в Черный Ящик. Элементами являются целые числа, по модулю не большие $2 000 000 000$, $m \leq 30000$. Для выше описанного примера $A = \left (3, 1, -4, 2, 8, -1000, 2 \right).$
$u_1, \ u_2, \ldots, \ u_n:$ последовательность указывает на количество элементов в Черном Ящике в момент выполнения первой, второй, … $n$-ой транзакции GET. Для выше описанного примера $u = \left (1, 2, 6, 6 \right ).$

Работа Черного Ящика предполагает, что числа в последовательности $u_1, \ u_2, \ldots , \ u_n$ отсортированы в неубывающем порядке, $n \leq m$, а для каждого $p \left (1 \leq p \leq n \right )$ имеет место неравенство $p \leq u(p) \leq m$. Это следует из того, что для $p$-го элемента последовательности $u$ мы выполняем GET транзакцию, которая выводит $p$-ый минимальный элемент из набора чисел $A_1, \ A_2, \ldots , \ A_{u_p}$.

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

Состоит из следующего набора чисел: $m, \ n, \ A_1, \ A_2, \ldots , \ A_m, \ u_1, \ u_2, \ldots , \ u_n.$ Все числа разделены пробелами и (или) символом перевода на новую строку.

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

Вывести ответы Черного Ящика на последовательность выполненных транзакций. Каждое число должно выводиться в отдельной строке.

Тесты

Входные данные	Выходные данные
7 4 3 1 -4 2 8 -1000 2 1 2 6 6	3 3 1 2
8 3 5 8 3 7 3 5 7 0 2 3 3	5 5 8
10 4 6 3 7 3 8 4 7 4 6 15 4 6 8 9	3 3 4 4
5 5 1 2 3 4 5 1 2 3 4 5	1 2 3 4 5
11 5 4 6 8 9 5 3 6 8 10 12 13 6 7 8 9 10	3 4 5 6 6

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] nums = new int[m];
        for(int i = 0; i < m; i++){
            nums[i] = sc.nextInt();
        }
        TreeMap<Integer, Integer> blackBox = new TreeMap<>();
        blackBox.put(Integer.MAX_VALUE, 1);
        int size = 1;
        int curKey = Integer.MAX_VALUE;
        int curValue = 1;
        int curPosition = 0;
        for(int i = 0; i < n; i++){
            int req = sc.nextInt();
            for(int j = size - 1; j < req; j++){
                if (blackBox.containsKey(nums[j])) {
                    blackBox.put(nums[j], blackBox.get(nums[j]) + 1);
                    if (curKey == nums[j]) {
                        curValue++;
                    }
                }
                else {
                    blackBox.put(nums[j], 1);
                }
                if(nums[j] < curKey) {
                    if (curPosition == 0) {
                        Map.Entry<Integer, Integer> curEnrty= blackBox.lowerEntry(curKey);
                        curKey = curEnrty.getKey();
                        curValue = curEnrty.getValue();
                        curPosition = curValue - 1;
                    }
                    else {
                        curPosition--;
                    }
                }
            }
            size = req + 1;
            System.out.println(curKey);
            if (curPosition == curValue - 1) {
                Map.Entry<Integer, Integer> curEnrty = blackBox.higherEntry(curKey);
                curKey = curEnrty.getKey();
                curValue = curEnrty.getValue();
                curPosition = 0;
            }
            else {
                curPosition++;
            }
        }
    }
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Map;

import java.util.Scanner;

import java.util.TreeMap;

public class Main {

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

Scanner sc = new Scanner(System.in);

int m = sc.nextInt();

int n = sc.nextInt();

int[] nums = new int[m];

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

nums[i] = sc.nextInt();

}

TreeMap<Integer, Integer> blackBox = new TreeMap<>();

blackBox.put(Integer.MAX_VALUE, 1);

int size = 1;

int curKey = Integer.MAX_VALUE;

int curValue = 1;

int curPosition = 0;

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

int req = sc.nextInt();

for(int j = size - 1; j < req; j++){

if (blackBox.containsKey(nums[j])) {

blackBox.put(nums[j], blackBox.get(nums[j]) + 1);

if (curKey == nums[j]) {

curValue++;

}

else {

blackBox.put(nums[j], 1);

}

if(nums[j] < curKey) {

if (curPosition == 0) {

Map.Entry<Integer, Integer> curEnrty= blackBox.lowerEntry(curKey);

curKey = curEnrty.getKey();

curValue = curEnrty.getValue();

curPosition = curValue - 1;

}

else {

curPosition--;

}

size = req + 1;

System.out.println(curKey);

if (curPosition == curValue - 1) {

Map.Entry<Integer, Integer> curEnrty = blackBox.higherEntry(curKey);

curKey = curEnrty.getKey();

curValue = curEnrty.getValue();

curPosition = 0;

}

else {

curPosition++;

}

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

В следствие того, что в JCF нет мультисета, реализуем необходимые нам его функции (а именно итерирование) на базе TreeSet, ключами которого будут уникальные значения, хранящиеся в черном ящике, а значениями — количество раз, которое это значение содержится в черном ящике. При чтении очередного запроса добавляем соответствующие элементы в черный ящик, итерируясь вниз в случае добавления меньшего элемента чем текущий, и итерируемся вверх после каждого запроса.

Ссылки

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

e-olymp 7107. Без лифта

27/11/2018 by Кирилл Волков

Задача

Три друга – Андрей, Борис и Владимир живут соответственно на $a$, $b$ и $v$ этажах многоэтажного дома. Они занимаются спортом, поэтому никогда не пользуются лифтом. Однажды им потребовалось срочно встретиться у кого-то из них дома.

Составьте программу, которая определяла бы номер этажа, на котором они встретятся, при чем время до встречи было бы минимальным. Учтите, что скорость спуска по лестнице в $\frac{47}{31}$ раза больше, чем скорость подъема.

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

Программа получает на вход три натуральных числа – номера этажей, на которых живут друзья ($1 \leq a, b, v \leq 28$).

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

Программа выводит номер этажа, на котором они встречаются.

Тесты

Входные данные	Выходные данные
$1$ $5$ $8$	$5$
$1$ $1$ $2$	$1$
$4$ $11$ $14$	$4$
$6$ $3$ $2$	$3$
$2$ $9$ $1$	$2$

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

import java.util.Scanner;
import static java.lang.Integer.max;
import static java.lang.Math.min;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();
        int minFloor = min(min(a, b), c);
        int maxFloor = max(max(a, b), c);
        int middleFloor = a + b + c - minFloor - maxFloor;
        int resultFloor;
        if (31 * (maxFloor - minFloor) < 47 * (middleFloor - minFloor)) {
            resultFloor = minFloor;
        }
        else {
            resultFloor = middleFloor;
        }
        System.out.println(resultFloor);
    }
}

import java.util.Scanner;

import static java.lang.Integer.max;

import static java.lang.Math.min;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int a = scanner.nextInt();

int b = scanner.nextInt();

int c = scanner.nextInt();

int minFloor = min(min(a, b), c);

int maxFloor = max(max(a, b), c);

int middleFloor = a + b + c - minFloor - maxFloor;

int resultFloor;

if (31 * (maxFloor - minFloor) < 47 * (middleFloor - minFloor)) {

resultFloor = minFloor;

}

else {

resultFloor = middleFloor;

}

System.out.println(resultFloor);

}

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

По условию скорость спуска по лестнице в $\frac{47}{31}$ раза больше, чем скорость подъема. Назовем эту величину коэффициентом подъема.
Примем, что человек спускается на один этаж за единицу времени. Тогда он поднимается на один этаж за единицу времени, умноженную на коэффициент подъема.
Вначале необходимо установить, какой из этажей является максимальным, какой — минимальным, какой — промежуточным.
Очевидно, что друг, живущий на промежуточном этаже доберется до максимального этажа быстрее, чем тот, кто живет на минимальном, а также доберется до минимального этажа быстрее, чем тот, кто живет на максимальном. Кроме того, друг, живущий на максимальном этаже, быстрее спустится на минимальный этаж, чем живущий на минимальном поднимется на максимальный. Отсюда получаем, что если друзья будут подниматься на максимальный этаж, то потраченное время не будет наименьшим возможным. То есть друзья могут встретиться либо на минимальном, либо на промежуточном этаже. Время, потраченное на спуск на минимальный этаж, численно равно разнице между максимальным и минимальным этажом. Время, потраченное на путь к промежуточному этажу, численно равно максимуму между разницей между минимальным и промежуточным этажами, умноженной на коэффициент подъема и разницей между максимальным и промежуточным этажами. Так как разница между максимальным и промежуточным этажами всегда не превышает разницы между максимальным и минимальным этажами, то для определения искомого этажа нам достаточно сравнивать разницу между максимальным и минимальным этажами и разницу между минимальным и промежуточным этажами, умноженной на коэффициент подъема.
В случае, если первая величина будет меньше второй, то друзья должны встретиться на минимальном этаже, в противном случае — на промежуточном.

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

Ссылки

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

e-olymp 5274. Фенечка

21/11/2018 by Кирилл Волков

Задача

Саша находится в процессе творческого поиска. Она хочет сплести ещё одну фенечку, но испытывает сложности при выборе цветов. Сейчас все $n$ ниток, которые она планирует использовать для плетения, выложены в ряд. В процессе размышления Саша время от времени заменяет нитку одного цвета ниткой другого, а также для проверки того, что узор получается тем, который подразумевается, проверяет, что некоторые последовательности цветов ниток равны.

Напишите программу, которая автоматизирует эти проверки.

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

В первой строке записаны два целых числа $n$ и $k$ — количество ниток в фенечке и запросов к программе, соответственно $(1 \leq n, k \leq 100000).$ Во второй строке записана строка из $n$ символов — цвета ниток в начальном состоянии. Каждый цвет обозначается строчной или прописной буквой латинского алфавита или цифрой. В следующих $k$ строках заданы запросы двух видов:

«* i c» — заменить нитку с номером $i$ на нитку цвета $c$,
«? i j len» — проверить, равны ли последовательности цветов ниток, начинающиеся в позициях $i$ и $j$ и имеющие длину $len$.

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

Для каждого запроса второго вида выведите «+», если последовательности равны, или «-« в противном случае.

Тесты

Входные данные	Выходные данные
6 3 abccba ? 2 4 2 * 4 a ? 1 4 2	-+
7 4 abacaba ? 1 5 3 * 6 c ? 2 6 2 ? 3 5 3	+-+
8 3 atgthcta ? 2 4 3 * 8 h ? 4 7 2	-+
9 3 abbababba ? 1 6 4 * 2 c ? 1 6 4	+-

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

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static long[] t;
    private static long[]codes;
    private static final long prime = 61;
    private static long[] pows;
    private static void build (int v, int tl, int tr) {
        if (tl == tr){
            t[v] = (codes[tl] * pows[tl - 1]);
        }
        else {
            int tm = (tl + tr) / 2;
            build (2 * v, tl, tm);
            build (2 * v + 1, tm + 1, tr);
            t[v] = (t[2 * v] + t[2 * v + 1]);
        }
    }

    private static long sum (int v, int tl, int tr, int l, int r) {
        if (l > r){
            return 0;
        }
        if (l == tl && r == tr)
            return t[v];
        int tm = (tl + tr) / 2;
        return sum (2 * v, tl, tm, l, Math.min(r, tm))
                + sum (2 * v + 1, tm + 1, tr, Math.max(l, tm + 1), r);
    }

    private static void update (int v, int tl, int tr, int pos, long newVal) {
        if (tl == tr)
            t[v] = (newVal * pows[pos - 1]);
        else {
            int tm = (tl + tr) / 2;
            if (pos <= tm)
                update (v*2, tl, tm, pos, newVal);
            else
                update (2 * v + 1, tm + 1, tr, pos, newVal);
            t[v] = (t[2 * v] + t[2 * v + 1]);
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] params = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        codes = new long[n + 1];
        pows = new long[n + 1];
        t = new long[4 * n];
        int k = Integer.parseInt(params[1]);
        String a = bufferedReader.readLine();
        for (int i = 1; i <= n; i++) {
            codes[i] = a.charAt(i - 1) - 'A' + 1;
        }
        pows[0] = 1;
        for (int i = 1; i <= n; i++) {
            pows[i] = pows[i - 1] * prime;
        }
        build(1, 1, n);
        for (int t = 0; t <k; t++) {
            char q = (char) bufferedReader.read();
            bufferedReader.skip(1);
            if (q == '?') {
                String[] query = bufferedReader.readLine().split(" ");
                int i = Integer.parseInt(query[0]);
                int j = Integer.parseInt(query[1]);
                int len = Integer.parseInt(query[2]);
                if (i > j) {
                    int temp = i;
                    i = j;
                    j = temp;
                }
                if(sum(1, 1, n, i, i + len - 1) * pows[j - i] == sum(1, 1, n, j, j + len - 1)){
                    System.out.print("+");
                }
                else{
                    System.out.print("-");
                }
            }
            else if(q == '*') {
                String[] query = bufferedReader.readLine().split(" ");
                int temp = Integer.parseInt(query[0]);
                char c = query[1].charAt(0);
                update(1, 1, n, temp, c - 'A' + 1);
            }
        }
    }
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class Main {

private static long[] t;

private static long[]codes;

private static final long prime = 61;

private static long[] pows;

private static void build (int v, int tl, int tr) {

if (tl == tr){

t[v] = (codes[tl] * pows[tl - 1]);

}

else {

int tm = (tl + tr) / 2;

build (2 * v, tl, tm);

build (2 * v + 1, tm + 1, tr);

t[v] = (t[2 * v] + t[2 * v + 1]);

}

private static long sum (int v, int tl, int tr, int l, int r) {

if (l > r){

return 0;

}

if (l == tl && r == tr)

return t[v];

int tm = (tl + tr) / 2;

return sum (2 * v, tl, tm, l, Math.min(r, tm))

+ sum (2 * v + 1, tm + 1, tr, Math.max(l, tm + 1), r);

}

private static void update (int v, int tl, int tr, int pos, long newVal) {

if (tl == tr)

t[v] = (newVal * pows[pos - 1]);

else {

int tm = (tl + tr) / 2;

if (pos <= tm)

update (v*2, tl, tm, pos, newVal);

else

update (2 * v + 1, tm + 1, tr, pos, newVal);

t[v] = (t[2 * v] + t[2 * v + 1]);

}

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

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params = bufferedReader.readLine().split(" ");

int n = Integer.parseInt(params[0]);

codes = new long[n + 1];

pows = new long[n + 1];

t = new long[4 * n];

int k = Integer.parseInt(params[1]);

String a = bufferedReader.readLine();

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

codes[i] = a.charAt(i - 1) - 'A' + 1;

}

pows[0] = 1;

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

pows[i] = pows[i - 1] * prime;

}

build(1, 1, n);

for (int t = 0; t <k; t++) {

char q = (char) bufferedReader.read();

bufferedReader.skip(1);

if (q == '?') {

String[] query = bufferedReader.readLine().split(" ");

int i = Integer.parseInt(query[0]);

int j = Integer.parseInt(query[1]);

int len = Integer.parseInt(query[2]);

if (i > j) {

int temp = i;

i = j;

j = temp;

}

if(sum(1, 1, n, i, i + len - 1) * pows[j - i] == sum(1, 1, n, j, j + len - 1)){

System.out.print("+");

}

else{

System.out.print("-");

}

else if(q == '*') {

String[] query = bufferedReader.readLine().split(" ");

int temp = Integer.parseInt(query[0]);

char c = query[1].charAt(0);

update(1, 1, n, temp, c - 'A' + 1);

}

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

Наивный алгоритм тратит на выполнение первого запроса $O\left(1\right)$ единиц времени, а на выполнение запросов второго типа — $O\left(n\right)$ единиц времени. Таким образом получаем ассиптотическую временную сложность $O\left(kn\right),$ из-за чего задача не проходит по времени.
Для сравнения строк будем использовать полиномиальный хеш, зависящий от $p$ (в нашем случае $p = 61$), при этом будем отождествлять равенство хешей по модулю $m$ (в нашем случае $m = 2^{64}$) и самих строк (при этом может случиться так, что хеши будут совпадать, а сами строки — нет, но вероятность достаточно мала и мы будем ею пренебрегать). Таким образом мы получаем возможность сравнивать строки за $O\left(1\right)$ единиц времени. Будем использовать для хранения текущего состояния строки (а точнее ее хеша) дерево отрезков, при этом на нижнем ярусе будем хранить хеши каждого отдельного символа строки с учетом его месторасположения в строке. Таким образом получим возможность выполнять запросы и первого, и второго типов за $O\left(\log{n}\right)$ единиц времени, при этом следует учесть, что хеши двух одинаковых подстрок будут отличаться в $p^{j-i} \mod m$ раз, где $i$ — меньший из индексов начала сравниваемых подстрок, $j$ — больший. Таким образом, получаем итоговую асимптотическую сложность алгоритма $O\left(k\log{n}\right)$

Ссылки

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

e-olymp 4000. Обход в глубину

09/11/2018 by Кирилл Волков

Задача

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

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

В первой строке содержится количество вершин графа $n$ и выделенная вершина $s$ $\left (1 \leq s \leq n \leq 100 \right).$ В следующих n строках записано по n чисел — матрица смежности графа, в котрой цифра «$0$» означает отсутствие ребра между вершинами, а цифра «$1$» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

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

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

Тесты

Входные данные	Выходные данные
3 1 0 0 1 0 0 0 1 0 0	2
4 2 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0	4
6 2 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0	3
4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	1
5 3 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0	5

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

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    private static int count = 0;

    private static void dfs(ArrayList<Integer>[] adj, boolean[] was, int v) {
        count++;
        for (int e: adj[v]) {
            if (!was[e]) {
                was[e] = true;
                dfs(adj, was, e);
            }
        }
    }

    private static void dfs(ArrayList<Integer>[] adj, int v) {
        boolean[] was = new boolean[adj.length];
        was[v] = true;
        dfs(adj, was, v);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v = scanner.nextInt() - 1;
        ArrayList<Integer>[] adj = (ArrayList<Integer>[]) new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                int d = scanner.nextInt();
                if (d == 1) {
                    adj[i].add(j);
                }
            }
        }
        dfs(adj, v);
        System.out.println(count);
    }
}

import java.util.ArrayList;

import java.util.Scanner;

public class Main {

private static int count = 0;

private static void dfs(ArrayList<Integer>[] adj, boolean[] was, int v) {

count++;

for (int e: adj[v]) {

if (!was[e]) {

was[e] = true;

dfs(adj, was, e);

}

private static void dfs(ArrayList<Integer>[] adj, int v) {

boolean[] was = new boolean[adj.length];

was[v] = true;

dfs(adj, was, v);

}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int v = scanner.nextInt() - 1;

ArrayList<Integer>[] adj = (ArrayList<Integer>[]) new ArrayList[n];

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

adj[i] = new ArrayList<>();

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

int d = scanner.nextInt();

if (d == 1) {

adj[i].add(j);

}

dfs(adj, v);

System.out.println(count);

}

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

Для хранения графа воспользуемся списками смежности. Реализуем стандартный поиск в глубину. Пусть $c$ количество вершин в компоненте графа. Изначально $c = 0.$ При посещении очередной, не посещенной ранее вершины, значение $c$ увеличивается на один. Таким образом, при полном обходе компоненты графа, $c$ будет искомым числом.

Ссылки

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

e-olymp 440. Подделка чека

24/10/2018 by Кирилл Волков

Задача

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

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

Во входном файле в первой строке содержится одно целое положительное число не более чем из $100$ цифр.

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

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

Тесты

Входные данные	Выходные данные
$123321$	$332121$
$7888778888878888788878878777887$	$8888878888788878887778878777887$
$1091$	$9100$
$26364$	$64263$
$98765$	$98765$

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String s = bufferedReader.readLine();
        String maxS = s;
        int start = s.length() - 1;
        boolean found = false;
        for (int i = 0; i < s.length() && !found; i++) {
            for (int j = i; j < s.length() && !found; j++) {
                if (s.charAt(j) > s.charAt(i)) {
                    start = i;
                    found = true;
                }
            }
        }
        for (int j = start + 1; j < s.length(); j++) {
            StringBuilder curMax = new StringBuilder(s);
            if (s.charAt(j) >= s.charAt(start)) {
                for (int k = j; k < s.length(); k++) {
                    curMax.insert(start + k - j, s.charAt(k));
                    curMax.delete(k + 1, k + 2);
                    String curMaxString = curMax.toString();
                    if (curMaxString.compareTo(maxS) > 0) {
                        maxS = curMaxString;
                    }
                }
            }
        }
        System.out.println(maxS);
    }
}

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String s = bufferedReader.readLine();

String maxS = s;

int start = s.length() - 1;

boolean found = false;

for (int i = 0; i < s.length() && !found; i++) {

for (int j = i; j < s.length() && !found; j++) {

if (s.charAt(j) > s.charAt(i)) {

start = i;

found = true;

}

for (int j = start + 1; j < s.length(); j++) {

StringBuilder curMax = new StringBuilder(s);

if (s.charAt(j) >= s.charAt(start)) {

for (int k = j; k < s.length(); k++) {

curMax.insert(start + k - j, s.charAt(k));

curMax.delete(k + 1, k + 2);

String curMaxString = curMax.toString();

if (curMaxString.compareTo(maxS) > 0) {

maxS = curMaxString;

}

System.out.println(maxS);

}

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

Пусть заданы два числа: $a = \overline{a_1a_2 \ldots a_k},\ b = \overline{b_1b_2 \ldots b_k}$. Тогда $a > b \Leftrightarrow \exists i: \ \forall j < i \ a_j = b_j \ \wedge \ a_i > b_i$. Отсюда получаем необходимое условие получения максимального числа при перестановке в записи числа $a$ групп цифр $\overline{a_ia_{i+1} \ldots a_l}$ и $\overline{a_ja_{j+1} \ldots a_m} \ l<j$ местами: $i = \min_{1 < s < k} s: \ \exists t>s: \ a_t \gt a_s$. Если такое $i$ существует, то делаем перебор по всем возможным перестановкам, таким что первая группа чисел начинается с индекса $i$ и таким образом находим максимально возможное число. В противном случае данное число уже является максимальным.

Ссылки

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

e-olymp 88. Месть Ли Чака

15/10/2018 by Кирилл Волков

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

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

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

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

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main{

    private static class Node {
        private int i;
        private int j;

        private Node(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    private static void fill(int[][] a, int value) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                a[i][j] = value;
            }
        }
    }

    private static void bfsSecondPlayer(char[][] map, int[][] moves, Node start) {
        Queue<Node> queue = new LinkedList<>();
        moves[start.i][start.j] = 0;
        queue.add(start);
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            int i = curNode.i;
            int j = curNode.j;
            if (i > 0 && map[i - 1][j] != 'R' && map[i - 1][j] != 'e' && moves[i][j] + 1 < moves[i - 1][j]) {
                moves[i - 1][j] = moves[i][j] + 1;
                queue.add(new Node(i - 1, j));
            }
            if (i < moves.length - 1 && map[i + 1][j] != 'R' && map[i + 1][j] != 'e' && moves[i][j] + 1 < moves[i + 1][j]) {
                moves[i + 1][j] = moves[i][j] + 1;
                queue.add(new Node(i + 1, j));
            }
            if (j > 0 && map[i][j - 1] != 'R' && map[i][j - 1] != 'e' && moves[i][j] + 1 < moves[i][j - 1]) {
                moves[i][j - 1] = moves[i][j] + 1;
                queue.add(new Node(i, j - 1));
            }
            if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && map[i][j + 1] != 'e' && moves[i][j] + 1 < moves[i][j + 1]) {
                moves[i][j + 1] = moves[i][j] + 1;
                queue.add(new Node(i, j + 1));
            }
        }
    }

    private static boolean bfsFirstPlayer(char[][] map, int[][] moves, int[][] secondPlayerMoves, Node start) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(start);
        moves[start.i][start.j] = 0;
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            int i = curNode.i;
            int j = curNode.j;
            if (map[i][j] == 'e') {
                return true;
            }
            if (i > 0 && map[i - 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i - 1][j], secondPlayerMoves[i - 1][j])) {
                moves[i - 1][j] = moves[i][j] + 1;
                queue.add(new Node(i - 1, j));
            }
            if (i < moves.length - 1 && map[i + 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i + 1][j], secondPlayerMoves[i + 1][j])) {
                moves[i + 1][j] = moves[i][j] + 1;
                queue.add(new Node(i + 1, j));
            }
            if (j > 0 && map[i][j - 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j - 1], secondPlayerMoves[i][j - 1])) {
                moves[i][j - 1] = moves[i][j] + 1;
                queue.add(new Node(i, j - 1));
            }
            if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j + 1], secondPlayerMoves[i][j + 1])) {
                moves[i][j + 1] = moves[i][j] + 1;
                queue.add(new Node(i, j + 1));
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int tests = Integer.parseInt(bufferedReader.readLine());
        for (int r = 0; r < tests; r++) {
            String[] sizes = bufferedReader.readLine().split(" ");
            int n = Integer.parseInt(sizes[0]);
            int m = Integer.parseInt(sizes[1]);
            char[][] map = new char[n][m];
            Node g = null;
            Node l = null;
            Node e = null;
            for (int i = 0; i < n; i++) {
                map[i] = bufferedReader.readLine().toCharArray();
                for (int j = 0; j < m; j++) {
                    if (map[i][j] == 'g') {
                        g = new Node(i, j);
                    }
                    else if (map[i][j] == 'l') {
                        l = new Node(i, j);
                    }
                    else if (map[i][j] == 'e') {
                        e = new Node(i, j);
                    }
                }
            }
            int[][] secondPlayerDistances = new int[n][m];
            fill(secondPlayerDistances, Integer.MAX_VALUE);
            bfsSecondPlayer(map, secondPlayerDistances, l);
            int[][] firstPlayerDistances = new int[n][m];
            fill(firstPlayerDistances, Integer.MAX_VALUE);
            boolean ok = bfsFirstPlayer(map, firstPlayerDistances, secondPlayerDistances, g);
            System.out.println(ok ? "YES" : "NO");
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.Queue;

public class Main{

private static class Node {

private int i;

private int j;

private Node(int i, int j) {

this.i = i;

this.j = j;

}

private static void fill(int[][] a, int value) {

for (int i = 0; i < a.length; i++) {

for (int j = 0; j < a[i].length; j++) {

a[i][j] = value;

}

private static void bfsSecondPlayer(char[][] map, int[][] moves, Node start) {

Queue<Node> queue = new LinkedList<>();

moves[start.i][start.j] = 0;

queue.add(start);

while (!queue.isEmpty()) {

Node curNode = queue.poll();

int i = curNode.i;

int j = curNode.j;

if (i > 0 && map[i - 1][j] != 'R' && map[i - 1][j] != 'e' && moves[i][j] + 1 < moves[i - 1][j]) {

moves[i - 1][j] = moves[i][j] + 1;

queue.add(new Node(i - 1, j));

}

if (i < moves.length - 1 && map[i + 1][j] != 'R' && map[i + 1][j] != 'e' && moves[i][j] + 1 < moves[i + 1][j]) {

moves[i + 1][j] = moves[i][j] + 1;

queue.add(new Node(i + 1, j));

}

if (j > 0 && map[i][j - 1] != 'R' && map[i][j - 1] != 'e' && moves[i][j] + 1 < moves[i][j - 1]) {

moves[i][j - 1] = moves[i][j] + 1;

queue.add(new Node(i, j - 1));

}

if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && map[i][j + 1] != 'e' && moves[i][j] + 1 < moves[i][j + 1]) {

moves[i][j + 1] = moves[i][j] + 1;

queue.add(new Node(i, j + 1));

}

private static boolean bfsFirstPlayer(char[][] map, int[][] moves, int[][] secondPlayerMoves, Node start) {

Queue<Node> queue = new LinkedList<>();

queue.add(start);

moves[start.i][start.j] = 0;

while (!queue.isEmpty()) {

Node curNode = queue.poll();

int i = curNode.i;

int j = curNode.j;

if (map[i][j] == 'e') {

return true;

}

if (i > 0 && map[i - 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i - 1][j], secondPlayerMoves[i - 1][j])) {

moves[i - 1][j] = moves[i][j] + 1;

queue.add(new Node(i - 1, j));

}

if (i < moves.length - 1 && map[i + 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i + 1][j], secondPlayerMoves[i + 1][j])) {

moves[i + 1][j] = moves[i][j] + 1;

queue.add(new Node(i + 1, j));

}

if (j > 0 && map[i][j - 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j - 1], secondPlayerMoves[i][j - 1])) {

moves[i][j - 1] = moves[i][j] + 1;

queue.add(new Node(i, j - 1));

}

if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j + 1], secondPlayerMoves[i][j + 1])) {

moves[i][j + 1] = moves[i][j] + 1;

queue.add(new Node(i, j + 1));

}

return false;

}

public static void main(String[] args) throws IOException{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

int tests = Integer.parseInt(bufferedReader.readLine());

for (int r = 0; r < tests; r++) {

String[] sizes = bufferedReader.readLine().split(" ");

int n = Integer.parseInt(sizes[0]);

int m = Integer.parseInt(sizes[1]);

char[][] map = new char[n][m];

Node g = null;

Node l = null;

Node e = null;

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

map[i] = bufferedReader.readLine().toCharArray();

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

if (map[i][j] == 'g') {

g = new Node(i, j);

}

else if (map[i][j] == 'l') {

l = new Node(i, j);

}

else if (map[i][j] == 'e') {

e = new Node(i, j);

}

int[][] secondPlayerDistances = new int[n][m];

fill(secondPlayerDistances, Integer.MAX_VALUE);

bfsSecondPlayer(map, secondPlayerDistances, l);

int[][] firstPlayerDistances = new int[n][m];

fill(firstPlayerDistances, Integer.MAX_VALUE);

boolean ok = bfsFirstPlayer(map, firstPlayerDistances, secondPlayerDistances, g);

System.out.println(ok ? "YES" : "NO");

}

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

Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. Обозначим начальное местоположение Гайбраша — $g,$ Ли Чака — $l.$, выход $e.$
Безопасный для Гайбраша маршрут существует тогда и только тогда, когда существует путь $\omega,$ такой, что для $\forall v \in \omega \ \rho \left(g, v \right ) + 1 < \rho(l, v).$ С помощью поиска в ширину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в ширину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае — нет.

Ссылки

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

e-olymp 480. Возведение в степень — 2

29/09/2018 by Кирилл Волков

Задача

Для заданных $A$, $B$ и $M$ вычислить $A^B \mod M$.

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

Во входном файле даны три натуральных числа $A$, $B$, $M$ $(1 ≤ A, \, B ≤ 10^{18}, \, 2 ≤ M ≤ 2 \cdot 10^9)$, записанные в одной строке через пробел.

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

В выходной файл выведите одно число, равное $A^B \mod M$.

Тесты

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

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

import java.util.Scanner;

public class Main {
    public static long binPow(long a, long b, int m) {
        a %= m;
        if (b == 0) return 1;
        else if (b % 2 == 0) {
            return binPow((a * a) % m, b / 2, m);
        }
        else return (a * binPow(a, b - 1, m)) % m;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        int m = scanner.nextInt();
        System.out.println(binPow(a, b, m));
    }
}

import java.util.Scanner;

public class Main {

public static long binPow(long a, long b, int m) {

a %= m;

if (b == 0) return 1;

else if (b % 2 == 0) {

return binPow((a * a) % m, b / 2, m);

}

else return (a * binPow(a, b - 1, m)) % m;

}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

long a = scanner.nextLong();

long b = scanner.nextLong();

int m = scanner.nextInt();

System.out.println(binPow(a, b, m));

}

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

По свойствам операций со сравнениями по модулю:
$$C \equiv C \mod K \pmod K$$
$$CD \equiv (C \mod K) \cdot (D \mod K) \pmod K$$
$$C \equiv D \pmod K \Rightarrow C^n \equiv D^n \pmod K$$
Отсюда выводим рекуррентную формулу бинарного возведения в степень по модулю:
$$
A^B \mod M =
\begin{cases}
1 \text{ при } B = 0\\\
\left ( \left (A \mod M \right ) \left ( (A \mod M)^{B-1} \mod M \right )\right )\mod M \\\\ \text{ при } B \equiv 1 \pmod 2\\\
\left ( \left (A \mod M \right)^2 \right)^{\frac{B}{2}} \mod M \text{ при } B \equiv 0 \pmod 2 \wedge B \neq 0
\end{cases}
$$

Ссылки

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

e-olymp 61. Уборка снега

22/09/2018 by Кирилл Волков

Задача

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

При этом известно, что:

Снегоход может очищать только одну проезжую полосу дороги за один проход.
Все дороги прямые с одной полосой движения в каждом направлении.
Снегоход может поворачивать на любом перекрестке в любую сторону, а также может развернуться в тупике.
Во время очистки снега снегоход двигается со скоростью 20 км/час, и со скоростью 50 км/час по уже очищенной дороге.
Возможность проехать все дороги всегда существует.

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

Первая строка содержит два числа $x$ и $y$ ($-30000 \leq x, y \leq 30000$) — координаты ангара (в метрах), откуда начинает свое движение снегоход. Далее в каждой отдельной строке заданы координаты (в метрах) начала и конца улиц (по $4$ числа в строке). В городе может быть до $100$ улиц.

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

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

Тесты

Входные данные	Выходные данные
$0$ $0$ $0$ $0$ $-1000$ $2000$ $0$ $0$ $1000$ $2000$	$0:27$
$0$ $1000$ $0$ $0$ $0$ $3000$ $0$ $0$ $1000$ $1000$ $0$ $0$ $3000$ $0$ $3000$ $0$ $3000$ $3000$ $3000$ $3000$ $0$ $3000$ $0$ $3000$ $1000$ $2000$ $3000$ $0$ $2000$ $1000$ $3000$ $3000$ $2000$ $2000$	$1:46$
$-500$ $0$ $-1000$ $0$ $0$ $0$ $0$ $0$ $1000$ $0$ $-1000$ $1000$ $0$ $0$ $-1000$ $1000$ $0$ $2000$ $0$ $2000$ $1000$ $1000$ $1000$ $1000$ $0$ $1000$ $0$ $1000$ $0$ $0$	$0:49$
$1000$ $500$ $-1000$ $0$ $1000$ $0$ $-1000$ $1000$ $1000$ $1000$ $-1000$ $0$ $-1000$ $1000$ $1000$ $0$ $1000$ $1000$ $-1000$ $0$ $1000$ $1000$ $1000$ $0$ $-1000$ $1000$ $-1000$ $1000$ $0$ $2000$ $0$ $2000$ $1000$ $1000$	$1:20$
$500$ $-500$ $0$ $0$ $1000$ $-1000$ $1000$ $-1000$ $2000$ $0$ $2000$ $0$ $3000$ $-1000$ $3000$ $-1000$ $4000$ $0$ $4000$ $0$ $5000$ $-1000$ $5000$ $-1000$ $6000$ $0$ $0$ $0$ $8000$ $0$	$1:39$

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        scanner.nextDouble();
        scanner.nextDouble();
        double length = 0;
        while(scanner.hasNextDouble()) {
            double startX = scanner.nextDouble();
            double startY = scanner.nextDouble();
            double finishX = scanner.nextDouble();
            double finishY = scanner.nextDouble();
            length += Math.sqrt((finishX - startX) * (finishX - startX) + (finishY - startY) * (finishY - startY));
        }
        long minutes = Math.round(3 * length / 500);
        System.out.print(minutes / 60 + ":" + minutes % 60);
    }
}

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

scanner.nextDouble();

double length = 0;

while(scanner.hasNextDouble()) {

double startX = scanner.nextDouble();

double startY = scanner.nextDouble();

double finishX = scanner.nextDouble();

double finishY = scanner.nextDouble();

length += Math.sqrt((finishX - startX) * (finishX - startX) + (finishY - startY) * (finishY - startY));

}

long minutes = Math.round(3 * length / 500);

System.out.print(minutes / 60 + ":" + minutes % 60);

}

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

Пусть граф $G = \left \langle V, U \right \rangle$ — граф, ребра которого — указанные в задаче дороги, а вершины — перекрестки. Граф $G$ — ориентированный, при чем, в силу того, что все дороги имеют двустороннее движение, из того, что $\left ( v_i, v_j \right ) \in U$ следует, что $\left ( v_j, v_i \right ) \in U.$ Из этого следует, что полустепень захода каждой вершины равна ее полустепени исхода, из чего, по критерию существования Эйлерова цикла, граф $G$ содержит Эйлеров цикл, т.е. существует путь, такой, что снегоход сможет очистить все дороги, пройдя по каждой ровно один раз в каждую сторону, следовательно длина такого пути будет равна удвоенной длине дорог. Снегоход всегда двигается со скоростью $V = 20 \text{км/час} = \frac{1000}{3} \text{м/мин}.$ По каждой из дорог снегоход проезжает два раза, таким образом общее искомое время минутах: $t = \frac{2L}{V} = \frac{3L}{500},$ где $L$ — длина всех дорог.
Замечание. Как видно из алгоритма решения, не имеет значения, где конкретно расположена точка начала движения, главное, чтобы она располагалась на одной из улиц.

Ссылки

Условие задачи на e-olymp

Решение задачи на e-olymp

Код решения

e-olymp 7369. Километровые столбы (Mileposts)

09/09/2018 by Кирилл Волков

Задача

Андрей очень любит ездить по железной дороге. Он садится у окна и внимательно следит за местностью, которую он проезжает. Особенно он обращает внимание на километровые столбы. Каждый столб с километражем, который при делении на $7$ дает в остатке $3$, он считает «счастливым». Составьте программу, которая бы определяла количество «счастливых» столбов, если во время езды он проезжает столбы с отметками от $a$ до $b.$

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

Два натуральных числа $a$ и $b$ ($0 \leq a \lt b \leq 10^9$).

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

Вывести количество «счастливых» столбов.

Тесты

Входные данные	Выходные данные
$0$ $5$	$1$
$26$ $49$	$3$
$73$ $80$	$2$
$5$ $8$	$0$
$17$ $37$	$3$

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

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] params = bufferedReader.readLine().split(" ");
        int a = Integer.parseInt(params[0]);
        int b = Integer.parseInt(params[1]);
        System.out.println((b + 4) / 7 - (a + 3) / 7);
    }
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class Main {

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

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params = bufferedReader.readLine().split(" ");

int a = Integer.parseInt(params[0]);

int b = Integer.parseInt(params[1]);

System.out.println((b + 4) / 7 - (a + 3) / 7);

}

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

Количество «счастливых» столбцов $l$ от $0$ до $n$, то есть количество натуральных чисел $k$ от $0$ до $n$, таких, что $k \mod7 = 3$, равно количеству чисел от $0$ до $n-3$, делящихся нацело на $7$, увеличенному на $1.$ То есть $l = \lfloor \frac{n-3}{7} \rfloor +1 = \lfloor \frac{n+4}{7} \rfloor$. Тогда количество «счастливых» столбов на промежутке от $a$ до $b$ равно разности количества «счастливых» столбов на промежутке от $0$ до $b$ и количества «счастливых столбов» на промежутке от $0$ до $a$ не включительно. Отсюда получаем итоговую формулу решения, указанную в коде программы.
Поясним теперь использование класса java.io.BufferedReader вместо java.util.Scanner. Класс Scanner предоставляет удобный высокоуровневый инструментарий для парсинга целых чисел из входного потока, за что приходится расплачиваться производительностью. В силу достаточно малого ограничения по времени на работу программы мы вынуждены использовать более низкоуровневый инструментарий для чтения строки с параметрами из входного потока и самостоятельно парсить ее.

Ссылки

Условие задачи на e-olymp

Решение задачи на e-olymp

Код решения