e-olymp 1228. Добавить все

27/12/2018 by Саша Рябова

Условие

Условие задачи отражает Вашу задачу: необходимо просто сложить числа. Но это будет унизительно если Вас попросят просто написать такую программу на языке C/C++ для заданного множества чисел. Давайте внесем в задачу оттенок изобретательности.

Введем понятие стоимости для операции сложения. Стоимость сложения двух чисел положим равным их сумме. Например, сложить числа $1$ и $10$ стоит $11$. Стоимость сложения $1,2$ равна $3$. Складывать числа можно разными способами:

$1 + 2 = 3$ (стоимость = 3), $3 + 3 = 6$ (стоимость = 6), Всего = 9
$1 + 3 = 4$ (стоимость = 4), $2 + 4 = 6$ (стоимость = 6), Всего = 10
$2 + 3 = 5$ (стоимость = 5), $1 + 5 = 6$ (стоимость = 6), Всего = 11

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

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

Начинаются целым числом $n (2 \leq n \leq 100000)$, за которым следуют $n$ целых неотрицательных чисел (все числа меньше $100000$).

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

Вывести наименьшую стоимость сложения всех чисел.

Тесты

Входные данные	Выходные данные
$4$ $10$ $12$ $13$ $11$	$92$
$5$ $100$ $11$ $8$ $30$ $12$	$272$
$4$ $2$ $2$ $2$ $2$	$16$
$6$ $1$ $2$ $3$ $4$ $5$ $6$	$51$

Код решения

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        PriorityQueue<Long> nums = new PriorityQueue<Long>();
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        for (int i = 0; i < n; i++) {
            long number = sc.nextLong();
            nums.add(number);
        }

        long minSum = 0;
        long a;
        long b;
        while (!nums.isEmpty()) {
            
            a = nums.poll();
                     
            if (nums.isEmpty()) {
                break;
            }
            b = nums.poll();
            minSum += a + b;            
            nums.add(a + b);

        }
        System.out.println(minSum);

    }
}

import java.util.PriorityQueue;

import java.util.Scanner;

public class Main{

public static void main(String[] args) {

PriorityQueue<Long> nums = new PriorityQueue<Long>();

Scanner sc = new Scanner(System.in);

long n = sc.nextLong();

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

long number = sc.nextLong();

nums.add(number);

}

long minSum = 0;

long a;

long b;

while (!nums.isEmpty()) {

a = nums.poll();

if (nums.isEmpty()) {

break;

}

b = nums.poll();

minSum += a + b;

nums.add(a + b);

}

System.out.println(minSum);

}

Решение

Стоимость сложения всех чисел будет минимальной, если на каждом следующем шаге мы будем складывать два наименьшие числа из множества $A$, состоящего из данного ряда чисел и уже вычисленных «частичных сумм». Таким образом, каждый шаг цикла поиска минимальной стоимости сложения будет состоять из нахождения двух минимальных чисел из множества, удаления этих чисел из множества $A$ и добавления в него результата их суммирования. В специальную переменную $minSum$ будем также каждый раз добавлять результат этого суммирования. Таким образом, количество элементов во множестве будет с каждым шагом уменьшаться на одно, и в конце, когда в нем останется единственный элемент, переменная $minSum$ будет содержать искомую стоимость сложения всех чисел.
Реализовать такой код достаточно просто, если реализовать множество $A$ в виде очереди с приоритетом.

Ссылки

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

e-olymp 1308. Наибольшая грань подстроки

25/12/2018 by Саша Рябова

Условие

Гранью (border, verge, brink) $br$ строки $S$ называется любой собственный префикс этой строки, равный суффиксу $S$.
Строка $S=abaababaabaab$ имеет две грани (не пустые): $ab$ и $abaab$. Строка $S=abaabaab$ также имеет две грани: $ab$ и $abaab$, но вторая грань — перекрывающаяся. Строка длины $n$ из повторяющегося символа, например $aaaaaaaa$ (или $a^8$), имеет $n-1$ грань. Для $S=a^8$ это грани: $a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa$.
Понятие «собственный префикс» исключает грань, совпадающую с самой строкой.
Длина грани — это количество символов в ней.
Сделаем обобщение задачи. Пусть необходимо вычислить значения наибольших граней для всех подстрок $S[1..i] (i = 1..n)$ и сохранить их в массиве $br[1..n]$.
Найдите наибольшее значение грани в массиве наибольших граней $br$ для всех подстрок $S$.

Тесты

Входные данные	Выходные данные	Комментарий
$abaabaab$	5	$abaab$ в исходной строке
$abaababaabaab$	6	$abaaba$ в подстроке abaababaabaab
$aaaaaaaa$	7	$aaaaaaa$ в исходной строке
$YM$	0	Грань отсутствует, т.к. префикс и суффикс не могут совпадать с самой строкой, а кроме $Y$ в качестве префикса и $M$ в качестве суффикса вариантов выбора нет
$&#%*%#&$	1	$&$ в исходной строке
$15015105$	2	$15$ в подстроке 15015105

Код задачи

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.nextLine();
        int answer = 0;    // Длина наибольшей грани
        for(int i = 1; i < S.length() && S.length() - i > answer; i++) { 
            int j = 0;
            /*
            Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
            i - первый символ очередного суффикса
            j - длина текущей грани и первый символ очередного префикса
            */
            while(j < S.length() - i && S.charAt(j) == S.charAt(i + j)){  // Накапливаем длину, пока символы префикса и суффикса совпадают
                j++;
            }
            if (j > answer) answer = j;
        }
        System.out.print(answer);
    }
    
}

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String S = sc.nextLine();

int answer = 0; // Длина наибольшей грани

for(int i = 1; i < S.length() && S.length() - i > answer; i++) {

int j = 0;

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

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

while(j < S.length() - i && S.charAt(j) == S.charAt(i + j)){ // Накапливаем длину, пока символы префикса и суффикса совпадают

j++;

}

if (j > answer) answer = j;

}

System.out.print(answer);

}

Решение

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

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

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

for(int i = 1; i < S.length() && S.length() - i > answer; i++) { 
            int j = 0;
            /*
            Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
            i - первый символ очередного суффикса
            j - длина текущей грани и первый символ очередного префикса
            */

for(int i = 1; i < S.length() && S.length() - i > answer; i++) {

int j = 0;

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

Начнем параллельно «двигаться» вправо по строке, проверяя на совпадение соответствующие символы префикса и суффикса и продолжая до тех пор, пока не наткнемся на различные символы или пока не дойдем до конца строки. При этом будем попутно накапливать значение длины текущей грани, пока пары символов совпадают.К примеру, если в очередной итерации первые символы префикса и суффикса — это первый и третий символы строки соответственно, то сначала проверим на совпадение символы на позициях 1 и 3, затем 2 и 4, 3 и 5 и т. д.

while(j < S.length() - i && S.charAt(j) == S.charAt(i + j)){  // Накапливаем длину, пока символы префикса и суффикса совпадают
                j++;
            }

while(j < S.length() - i && S.charAt(j) == S.charAt(i + j)){ // Накапливаем длину, пока символы префикса и суффикса совпадают

j++;

}

В виду того, что нумерация символов в строке начинается с нуля, переменная $j$ выполняет здесь одновременно роль первого символа префикса и длины текущей грани.

Сравним длину текущей грани с длиной максимальной грани и, если необходимо, обновим значение максимальной.

Отметим, что значение переменной $j$, получаемое в каждой итерации, представляет собой максимально возможную длину грани либо исходной строки (если проверки на совпадение пар символов закончились из-за достижения конца строки), либо подстроки, получаемой путем отбрасывания правой части исходной до того символа, на котором обнаружилось несовпадение.

Ссылки

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

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-olymp4491 Трое из Простоквашино

26/12/2017 by Валентина Андриеш

Условие задачи:
— Дядя Федор, Дядя Федор, я научился строить дерево отрезков.
— Подожди, Шарик, я занят.
— Ну Дядя Федор, ну смотри какой я код написал:

int build(int v, int left, int right) {
	if (left == right) {
		t[v] = a[left];
		return 0;

	}
	int mid = (left+right) / 2;
	build(v*2, left, mid);
	build(v*2+1, mid+1, right);
	t[v] = max(t[v*2], t[v*2+1]);
	return 0;
}

int get_max(int v, int left, int right, int lpos, int rpos) {
	if (left == lpos && right == rpos)
		return t[v];
	if (lpos > rpos)
		return -1;
	int mid = (left+right) / 2;
	return max(get_max(v*2, left, mid, lpos, min(rpos, mid)),
	get_max(v*2+1,mid+1,right,max(lpos,mid+1),rpos));
}

int build(int v, int left, int right) {

if (left == right) {

t[v] = a[left];

return 0;

}

int mid = (left+right) / 2;

build(v*2, left, mid);

build(v*2+1, mid+1, right);

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

return 0;

}

int get_max(int v, int left, int right, int lpos, int rpos) {

if (left == lpos && right == rpos)

return t[v];

if (lpos > rpos)

return -1;

int mid = (left+right) / 2;

return max(get_max(v*2, left, mid, lpos, min(rpos, mid)),

get_max(v*2+1,mid+1,right,max(lpos,mid+1),rpos));

}

— Ну хорошо, Шарик, раз ты так хорошо разобрался с этой темой, давай я тебе дам массив из [latex]n[/latex] неотрицательных чисел и число [latex]k[/latex], а ты мне скажешь сколько существует таких пар [latex]l;r \left ( 1\leq l\leq r\leq n \right ),[/latex] что функция, вызванная следующим образом:

[latex]get[/latex]_[latex]max(1, 1, n, l, r)[/latex]
вернет значение равное [latex]k[/latex]. Можно считать, что перед этим была вызвана функция

[latex]build(1, 1, n)[/latex]

— Хорошо, Дядя Федор!

Входные данные:
В первой строке находятся число [latex]n \left ( 1\leq n\leq 10^{6} \right )[/latex] — количество элементов в массиве и [latex]k \left ( 1\leq k\leq 10^{9} \right )[/latex] — значение, которое должна вернуть функция. В следующей строке находится [latex]n[/latex] неотрицательных чисел, не превышающих [latex]10^{9}[/latex] — элементы массива.

Выходные данные:
Выведите единственное число – ответ на задачу.

Тесты:

Входные данные			Выходные данные
[latex]n[/latex]	[latex]k[/latex]	[latex]elem[/latex]_[latex]tree[][/latex]	[latex]ans[/latex]
5	3	1 2 3 2 3	11
10	6	1 4 7 6 2 4 1 9 6 6	7
20	15	5 2 4 7 15 3 15 20 31 15 15 1 23 4 8 15 1 2 15 6	43

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

import java.util.*;

public class Main
{
  public static void main(String[] args) 
  {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    int[] elem_tree = new int[n];
    int ans=0, left=0, right=0;
    for(int i=0; i<n; i++){
    	elem_tree[i]=in.nextInt();
    	if (elem_tree[i]==k){
    		ans+=i-left+1;
    		right=i;
    	}
    	else{
    		if(elem_tree[i]>k){
        			right=0;
        			left=i+1;
    		}
    		else if(elem_tree[i]<k && right!=0) ans+=right-left+1;
    	}
    }
    System.out.println(ans);
  }
}

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k = in.nextInt();

int[] elem_tree = new int[n];

int ans=0, left=0, right=0;

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

elem_tree[i]=in.nextInt();

if (elem_tree[i]==k){

ans+=i-left+1;

right=i;

}

else{

if(elem_tree[i]>k){

right=0;

left=i+1;

}

else if(elem_tree[i]<k && right!=0) ans+=right-left+1;

}

System.out.println(ans);

}

Алгоритм решения:
Зададим отрезок массива, на котором обозначим границы [latex]\left [ left, right \right ][/latex]. Инициализируем изначально оба конца нулем. Рассмотрим некоторое [latex]elem\_tree\left [ i \right ][/latex] на нашем сегменте. Тогда если [latex]elem\_tree\left [ i \right ]=k[/latex], то на всем отрезке от [latex]left[/latex] до [latex]i[/latex] максимумом будет [latex]k[/latex]. Увеличим в таком случае [latex]left[/latex] и сделаем его равным [latex]i[/latex], причем [latex]right=0.[/latex] Если [latex]elem\_tree\left [ i \right ]\lt k[/latex], максимум будет также равен [latex]k[/latex]. В таком случае увеличиваем только [latex]right.[/latex] Если же [latex]elem\_tree\left [ i \right ]\gt k[/latex] , то [latex]left[/latex] устанавливаем равным [latex]i+1[/latex], а [latex]right[/latex] обнуляем.
Пройдя по всему массиву, мы должны получить значения [latex]left[/latex] равное количеству пар в которых максимум равен [latex]k[/latex], а [latex]right[/latex] должно стать равным нулю.

Код программы на Java
Условие задачи

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Category Archives: C. Дерево отрезков

e-olymp 1228. Добавить все

Условие

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

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

Тесты

Код решения

Решение

Ссылки

e-olymp 1308. Наибольшая грань подстроки

Условие

Тесты

Код задачи

Решение

Ссылки

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

Задача

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

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

Тесты

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

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

Ссылки

e-olymp4491 Трое из Простоквашино