e-olymp 2270. Поиск цикла

02/12/2020 by Наташа Писаревская

Задача

Дан ориентированный невзвешенный граф. Необходимо определить есть ли в нём циклы, и если есть, то вывести любой из них.

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

В первой строке находятся два натуральных числа $n$ и $m$ $($$1$ $\leqslant$ $n$ $\leqslant$ $10$^$5$$, $$1$ $\leqslant$ $m$ $\leqslant$ $10$^$5$$)$ — количество вершин и ребер в графе соответственно. Далее в $m$ строках перечислены рёбра графа. Каждое задаётся парой чисел — номерами начальной и конечной вершин соответственно.

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

Если в графе нет цикла, то вывести «NO», иначе вывести «YES» и затем перечислить вершины в порядке обхода цикла.

Тесты

№	Входные данные	Выходные данные
1	2 2 1 2 1 2	NO
2	2 2 1 2 2 1	YES 1 2
3	6 7 1 2 1 5 2 3 2 4 4 6 6 5 5 2	YES 2 4 6 5
4	6 6 1 3 2 4 3 4 1 2 3 5 3 6	NO
5	4 4 1 3 4 2 2 3 3 4	YES 3 4 2

import java.util.*;
public class Main {
    public static int n, m, flag = 0;
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    public static ArrayList<Integer> used = new ArrayList<Integer>();
    public static ArrayList<Integer> path = new ArrayList<Integer>();
    // поиск в глубину для каждой вершины
    static void dfs(int v) {
        if (flag == 1) return; // если уже нашли цикл, то останавливаемся
        else {
            used.set(v, 1); // посещаем вершину
            path.add(v); // добавляем ее в порядок обхода графа
            for (int i = 0; i < graph.get(v).size(); i++) {
                int to = graph.get(v).get(i); // следующая вершина графа
                if (used.get(to) == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл
                    path.add(to); // добавляем следующую вершину в порядок обхода графа
                    flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся
                    return;
                }
                else dfs(to); // если не посетили, то посещаем
                if (flag == 1) return; // если нашли цикл, то останавливаемся
            }
            used.set(v, 2); // если не нашли цикл, то выходим из вершины
            path.remove(path.size() - 1);
        }
    }
    // проверяем вершины на наличие цикла
    static void checkNodes() {
        for (int i = 0; i <= n; i++) {
            if (used.get(i) == 0) { // если не посещали вершину, то посещаем ее
                dfs(i);
                if (flag == 1) return; // если нашли цикл, то останавливаемся
            }
        }
    }
    public static void main (String[] args) {
        Scanner s = new Scanner(System.in);
        // считываем количество вершин и ребер
        n = s.nextInt();
        m = s.nextInt();
        for (int i = 0; i <= n; i++) {
            used.add(0);
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            // считываем ребра и заполняем граф
            int v1 = s.nextInt();
            int v2 = s.nextInt();
            graph.get(v1).add(v2);
        }
        checkNodes(); // проверяем вершины на наличие цикла
        if (flag == 1) { // если цикл найден
            int i = path.size() - 2; // последняя вершина цикла
            int to = path.get(path.size() - 1); // вершина в которой зациклились
            while (path.get(i) != to) { // получаем индекс вершины в которой зациклились
                i--;
            }
            System.out.println("YES");
            while (i < path.size() - 1) {  // выводим сам цикл
                System.out.print(path.get(i) + " ");
                i++;
            }
            System.out.println();
        }
        else
            System.out.print("NO");
    }
}

import java.util.*;

public class Main {

public static int n, m, flag = 0;

public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

public static ArrayList<Integer> used = new ArrayList<Integer>();

public static ArrayList<Integer> path = new ArrayList<Integer>();

// поиск в глубину для каждой вершины

static void dfs(int v) {

if (flag == 1) return; // если уже нашли цикл, то останавливаемся

else {

used.set(v, 1); // посещаем вершину

path.add(v); // добавляем ее в порядок обхода графа

for (int i = 0; i < graph.get(v).size(); i++) {

int to = graph.get(v).get(i); // следующая вершина графа

if (used.get(to) == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл

path.add(to); // добавляем следующую вершину в порядок обхода графа

flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся

return;

}

else dfs(to); // если не посетили, то посещаем

if (flag == 1) return; // если нашли цикл, то останавливаемся

}

used.set(v, 2); // если не нашли цикл, то выходим из вершины

path.remove(path.size() - 1);

}

// проверяем вершины на наличие цикла

static void checkNodes() {

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

if (used.get(i) == 0) { // если не посещали вершину, то посещаем ее

dfs(i);

if (flag == 1) return; // если нашли цикл, то останавливаемся

}

public static void main (String[] args) {

Scanner s = new Scanner(System.in);

// считываем количество вершин и ребер

n = s.nextInt();

m = s.nextInt();

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

used.add(0);

graph.add(new ArrayList<>());

}

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

// считываем ребра и заполняем граф

int v1 = s.nextInt();

int v2 = s.nextInt();

graph.get(v1).add(v2);

}

checkNodes(); // проверяем вершины на наличие цикла

if (flag == 1) { // если цикл найден

int i = path.size() - 2; // последняя вершина цикла

int to = path.get(path.size() - 1); // вершина в которой зациклились

while (path.get(i) != to) { // получаем индекс вершины в которой зациклились

i--;

}

System.out.println("YES");

while (i < path.size() - 1) { // выводим сам цикл

System.out.print(path.get(i) + " ");

i++;

}

System.out.println();

}

else

System.out.print("NO");

}

Решение

Для решения данной задачи воспользуемся поиском в глубину. Также будем отмечать вершины в различными цветами ($0$ (белый) — мы еще не посещали вершину, $1$ (серый) — посетили вершину и не вышли из нее (зациклились), $2$ (черный) — посетили вершину и вышли из неё).

В векторе $graph$ будем хранить сам граф, для проверки на цикличность воспользуемся вектором $visited$, так же будем хранить порядок обхода графа в векторе $path$. Так как по условию, в случае нескольких циклов, необходимо вывести любой, то мы будем находить первый и на этом останавливаться, для этого заведем переменную $flag$, которая равна 1, если цикл уже найден, и равна 0, если цикл еще не найден. В векторе $visited$ будем окрашивать вершину в один из цветов. Если мы захотим посетить $1$ (серую) вершину, то это будет означать, что мы отыскали цикл в этой вершине, тогда устанавливаем $flag = 1$.

Осталось лишь вывести его на экран. Для этого воспользуемся вектором $path$, в котором последний элемент — вершина, в которой цикл. Ищем предпоследнее вхождение этой вершины в векторе $path$ и выводим сам цикл.

Ссылки

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

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

e-olymp 1868. Функция

27/12/2018 by Иван Василевский

Условие задачи
Вычислите функцию:
$$f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если } n \mod \; 2 = 1 \\ f(n-1)+f(n-3), \text{ если } n \mod \; 2 = 0 \end{cases}$$
Входные данные
Одно натуральное число $n$ $(1 \leq n \leq 10^{12})$
Выходные данные
Значение $f(n)$ , взятое по модулю $2^{32}$.
Тесты

Входные данные	Выходные данные
10	7
123	229966
1	1
100	136345
51	5092

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.HashMap;
import java.lang.Math;

class Main
{

    private static long mod = 1L << 32;
    public static Map<Long, Long> mp = new HashMap<Long, Long>();

    public static long f(long n) {
        if (n <= 2) {
            return 1;
        }
        if (mp.containsKey(n)) {
            return mp.get(n);
        }
        if (n % 2 == 1) {
            long d = (f(6 * n / 7) % mod + f(2 * n / 3) % mod) % mod;
            mp.put(n, d);
            return mp.get(n);
        }
        long o = (f(n - 1) % mod + f(n - 3) % mod) % mod;
        mp.put(n, o);
        return mp.get(n);
    }


    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] params1 = bufferedReader.readLine().split(" ");
        long n;
        n = Long.parseLong(params1[0]);
        System.out.print(f(n));
    }
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Map;

import java.util.HashMap;

import java.lang.Math;

class Main

{

private static long mod = 1L << 32;

public static Map<Long, Long> mp = new HashMap<Long, Long>();

public static long f(long n) {

if (n <= 2) {

return 1;

}

if (mp.containsKey(n)) {

return mp.get(n);

}

if (n % 2 == 1) {

long d = (f(6 * n / 7) % mod + f(2 * n / 3) % mod) % mod;

mp.put(n, d);

return mp.get(n);

}

long o = (f(n - 1) % mod + f(n - 3) % mod) % mod;

mp.put(n, o);

return mp.get(n);

}

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

{

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

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

long n;

n = Long.parseLong(params1[0]);

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

}

Решение задачи
Решение данной задачи стоит начать с написания рекурсивной функции для вычисления функций по условию задачи. Так как рекурсия будет довольно таки сложной и много раз повторяются одни и те же результаты при вызове функции, следовательно, программа будет долгое время обрабатывать нашу задачу. То есть, к примеру, на 5 и 20 итерации, возвращаемые значения функции могут совпасть, что без оптимизации будет просчитываться еще раз, а с оптимизацией функция уже знает, чему равно значение с данными аргументами.Далее, по условию, мы пишем наконец нашу функцию:

Если число, которое ввел пользователь, меньше либо равно двум, то наша функция возвращает значение один.
Если есть значение с таким же ключом, то оно возвращает значение.
Если число, которое ввел пользователь, дает остаток от деления один, то наша функция возвращает значение $f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor)$.
Во всех остальных случаях наша функция возвращает значение $f(n-1)+f(n-3)$.

Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 1872. Снеговики

27/12/2018 by Дима Мороз

Задача

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

В местечке Местячково учитель Андрей Сергеевич Учитель купил через интернет-магазин «Интернет-магазин аппаратов клонирования» аппарат для клонирования снеговиков. Теперь дети могут играть и даже играют во дворе в следующую игру. Время от времени один из них выбирает понравившегося снеговика, клонирует его и:

либо добавляет ему сверху один шар;
либо удаляет из него верхний шар (если снеговик не пустой).

Учитель Андрей Сергеевич Учитель записал последовательность действий и теперь хочет узнать суммарную массу всех построенных снеговиков.

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

Первая строка содержит количество действий $n (1 ≤ n ≤ 200000)$. В строке номер $i + 1$ содержится описание действия:

$t m$ — клонировать снеговика номер $t (0 ≤ t < i)$ и добавить сверху шар массой $m (0 < m ≤ 1000)$;
$t 0$ — клонировать снеговика номер $t (0 ≤ t < i)$ и удалить верхний шар. Гарантируется, что снеговик не пустой.

В результате действия $i$, описанного в строке $i + 1$ создается снеговик номер $i$. Изначально имеется пустой снеговик с номером ноль.

Все входные числа целые.

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

Выведите суммарную массу построенных снеговиков.

Тесты

Входные данные	Выходные данные
8 0 1 1 5 2 4 3 2 4 3 5 0 6 6 1 0	74
4 0 3 1 2 2 1 1 1	18
2 0 1 1 5	7
5 1 2 3 4 5 5 1 7 5 6	26

Код задачи

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), count = 0, t, m;
		int a[][] = new int[n + 1][2];
		a[count][1] = 0;
		a[count][0] = -1;
		count++;
		long sumr = 0;
		for(int i = 0; i < n; i++){
			t = in.nextInt();
			m = in.nextInt();
			if(m == 0){
				a[count][1] = a[a[t][0]][1];
				a[count][0] = a[a[t][0]][0];
			}else{
				a[count][1] = a[t][1] + m;
				a[count][0] = t;
			}
			sumr += a[count][1];
			count++;
		}
		System.out.println(sumr);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), count = 0, t, m;

int a[][] = new int[n + 1][2];

a[count][1] = 0;

a[count][0] = -1;

count++;

long sumr = 0;

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

t = in.nextInt();

m = in.nextInt();

if(m == 0){

a[count][1] = a[a[t][0]][1];

a[count][0] = a[a[t][0]][0];

}else{

a[count][1] = a[t][1] + m;

a[count][0] = t;

}

sumr += a[count][1];

count++;

}

System.out.println(sumr);

}

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

Считываем n — количество действий. Задаем двухмерный массив размером [n+1][2] . Указываем значение первого элемента равное $0$ и нулевого элемента равного $-1$, чтобы он ни на что не ссылался в начале. В цикле считываем номер снеговика, которого нужно клонировать и массу шара, которую нужно добавить. Если масса шара равна $0$, то мы клонируем снеговика и убираем последний его шар, ссылаясь на снеговика в котором этого шара еще не было. Если же масса шара не равно $0$, то мы клонируем снеговика и добавляем ему шар массой $m$. Во второй ячейке указываем предка с которого строится новый снеговик. Выводим общую массу снеговиков.

Ссылки

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

e-olymp 7340. Поле-чудес

27/12/2018 by Даниель Савчак

Задача

Петрик і Марічка захопились грою поле-чудес: Марічка записує слово, що складається з великих англійських букв, а Петрик старається розпізнати його, причому відгадана буква відкривається на всіх позиціях, де вона міститься. За яку найменшу кількість ходів Петрик зможе відгадати задане слово.

Вхідні дані

Слово записане великими англійськими буквами (не більше [latex]100[/latex] символів).

Вихідні дані

Відповідь до задачі.

Тести

Вхідні дані	Вихідні дані
[latex]GOOGLE[/latex]	[latex]4[/latex]
[latex]ALBUS[/latex]	[latex]5[/latex]
[latex]OOO[/latex]	[latex]1[/latex]

Код програми

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
        String s;
        s = in.next();

        for (int j = 0; j < s.length(); j++) {
            int i = j + 1;
            while(i< s.length())
            {
                if (s.charAt(j) == s.charAt(i) && i!= j)
                {
                    String s1=s.substring(0, i);
                    String s2 = s.substring(i+1,s.length());
                    s=s1.concat(s2);
                }
                else i++;
            }
        }
        System.out.println(s.length());
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Main

{

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

{

Scanner in = new Scanner(System.in);

String s;

s = in.next();

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

int i = j + 1;

while(i< s.length())

{

if (s.charAt(j) == s.charAt(i) && i!= j)

{

String s1=s.substring(0, i);

String s2 = s.substring(i+1,s.length());

s=s1.concat(s2);

}

else i++;

}

System.out.println(s.length());

}

Рішення завдання

Створимо місце для слова і прочитаємо його,далі для того, щоб однакові букви йшли поряд і заведемо змінну, спочатку рівну [latex]1[/latex], так як слово складається мінімум з однієї букви, і будемо збільшувати її на [latex]1[/latex], якщо зустрінеться нова буква..

Код програми з множиною

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		SortedSet <Character> set = new TreeSet<>();
		Scanner in = new Scanner(System.in);
		String s = in.next();
		for(int i = 0; i < s.length(); i++){
        	set.add(s.charAt(i));
		}
		System.out.print(set.size());
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Main

{

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

{

SortedSet <Character> set = new TreeSet<>();

Scanner in = new Scanner(System.in);

String s = in.next();

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

set.add(s.charAt(i));

}

System.out.print(set.size());

}

Рішення завдання

Створимо місце і прочитаємо слово. Подалі кожну букву слова запишемо, як елемент множини [latex]і.[/latex] Так як множина автоматично видаляє всі однакові елементи, то відповіддю до завдання буде кількість елементів множини.

Посилання

Умова завдання на e-olymp.com.

Код рішення на ideone.com.

Код рішення з множиною на ideone.com.

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 93. Truck driving

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

Task

Umidsh Izadish is a truck driver and wants to drive from a city to another city while there exists a dedicated straight road between each pair of cities in that country. Amount of consumed fuel is the distance between two cities which is computed from their coordinates. There is a gas station in each city, so Umidsh can refuel the gas container of his truck. Your job is to compute the minimum necessary volume of gas container of Umidsh’s Truck.

Input data

The first line of input contains an integer, the number of test cases. Following, there are data for test cases. Each test case begins with a line containing one integer $C$, $2 /leq C /leq 200$, which is the number of cities. The next $C$ lines each contain two integers $x$,$y$ representing the coordinate of one city. First city is the source city and second is the destination city of Umidsh.

Output data

There should be one line for each test case in output. Each line should contain one floating point number which is the minimum necessary volume of truck’s gas container, printed to three decimals.

Tests

Input	Output
$2$ $2$ $0$ $0$ $3$ $4$ $3$ $17$ $4$ $19$ $4$ $18$ $5$	$5.000$ $1.414$
$1$ $3$ $4$ $5$ $4$ $6$ $4$ $7$	$1.000$
$2$ $4$ $0$ $1$ $0$ $-1$ $1$ $0$ $-1$ $0$ $3$ $8$ $9$ $0$ $1$ $14$ $14$	$1.414$ $11.314$

Code

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

public class TruckDriving {

    public class Node implements Comparable<Node> {

        Integer first;
        Integer second;

        @Override
        public int compareTo(Node other) {
            if (this.first != other.first) {
                return this.first.compareTo(other.first);
            } else {
                return this.second.compareTo(other.second);
            }
        }
    }

    int distance[] = new int[200];

    public TruckDriving() {

        Scanner sc = new Scanner(System.in);
        int testCaseCount = sc.nextInt();
        for (int i = 0; i < testCaseCount; i++) {
            int cityCount = sc.nextInt();
            ArrayList<Node> coordCity = new ArrayList<Node>(cityCount);
            for (int j = 0; j < cityCount; j++) {
                int coordX = sc.nextInt();
                int coordY = sc.nextInt();
                Node city = new Node();
                city.first = coordX;
                city.second = coordY;
                coordCity.add(city);
            }

            findMinimum(coordCity, cityCount);
            // System.out.println(distance.get(1));
            double res = Math.sqrt(distance[1]);
            System.out.format("%.3f", res);
            System.out.println();
        }

    }

    public void findMinimum(ArrayList<Node> coordCity, int cityCount) {
        //  System.out.println(distance);
        distance[0] = 0;
        for (int i = 1; i < cityCount; i++) {
            distance[i] = Integer.MAX_VALUE;
        }

        PriorityQueue<Node> q = new PriorityQueue<Node>();
        Node zeroPair = new Node();
        zeroPair.first = 0;
        zeroPair.second = 0;

        q.add(zeroPair);
        while (!q.isEmpty()) {
            int num_v = q.peek().second;
            Node cur = coordCity.get(num_v);
            int distv = -q.peek().first;
            q.poll();
            for (int j = 0; j < cityCount; j++) {
                int distan = Math.max(distv, (cur.first - coordCity.get(j).first) * (cur.first - coordCity.get(j).first) + (cur.second - coordCity.get(j).second) * (cur.second - coordCity.get(j).second));
                if (distance[j] > distan) {
                    distance[j] = distan;
                    Node tempPair = new Node();
                    tempPair.first=-distan;
                    tempPair.second=j;
                    q.add(tempPair);
                }
            }

        }
    }

    public static void main(String[] args) {
        TruckDriving tr = new TruckDriving();

    }
}

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.PriorityQueue;

import java.util.Scanner;

public class TruckDriving {

public class Node implements Comparable<Node> {

Integer first;

Integer second;

@Override

public int compareTo(Node other) {

if (this.first != other.first) {

return this.first.compareTo(other.first);

} else {

return this.second.compareTo(other.second);

}

int distance[] = new int[200];

public TruckDriving() {

Scanner sc = new Scanner(System.in);

int testCaseCount = sc.nextInt();

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

int cityCount = sc.nextInt();

ArrayList<Node> coordCity = new ArrayList<Node>(cityCount);

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

int coordX = sc.nextInt();

int coordY = sc.nextInt();

Node city = new Node();

city.first = coordX;

city.second = coordY;

coordCity.add(city);

}

findMinimum(coordCity, cityCount);

// System.out.println(distance.get(1));

double res = Math.sqrt(distance[1]);

System.out.format("%.3f", res);

System.out.println();

}

public void findMinimum(ArrayList<Node> coordCity, int cityCount) {

// System.out.println(distance);

distance[0] = 0;

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

distance[i] = Integer.MAX_VALUE;

}

PriorityQueue<Node> q = new PriorityQueue<Node>();

Node zeroPair = new Node();

zeroPair.first = 0;

zeroPair.second = 0;

q.add(zeroPair);

while (!q.isEmpty()) {

int num_v = q.peek().second;

Node cur = coordCity.get(num_v);

int distv = -q.peek().first;

q.poll();

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

int distan = Math.max(distv, (cur.first - coordCity.get(j).first) * (cur.first - coordCity.get(j).first) + (cur.second - coordCity.get(j).second) * (cur.second - coordCity.get(j).second));

if (distance[j] > distan) {

distance[j] = distan;

Node tempPair = new Node();

tempPair.first=-distan;

tempPair.second=j;

q.add(tempPair);

}

public static void main(String[] args) {

TruckDriving tr = new TruckDriving();

}

Solution

We can interpretate the set of the cities as weighted graph, which vertices represent cities and weight of each edge between two vertices is the gas volume required for passing the distance between corresponding cities.
The volume of truck’s gas container depends on the gas volume required for arrival to the each next station of the Umidsh’s way. The maximum between gas volume required to get to the city $A$ and gas volume required to pass the way from the city $a$ to the city $B$ represents the minimum necessary gas volume required to get to the city $B$ through the city $A$. So the volume of truck’s gas container would turn to minimum, when the maximum gas volume required for passing the distance between each two stations of his way would turn to minimum. Thus we could use modified Dijkstra’s algorithm to find the biggest value among the weights of an edges between each two stations of the way between vertice 0 and vertice 1.

Note: To use Node objects in the PriorityQueue, there should be a way to compare this objects. Thus, it was required to overwrite a method CompareTo so that we could implement interface Comparable

References

The task at e-olymp.com

e-olymp 977. Дерево?

26/12/2018 by Костя Григорян

Задача

Неориентированный граф без петель и кратных ребер задан матрицей смежности. Определить, является ли этот граф деревом.

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

Первая строка содержит количество вершин графа $n \left (1 \leq n \leq 100 \right).$ Далее записана матрица смежности размером $n × n$, в которой $1$ обозначает наличие ребра, $0$ — его отсутствие. Матрица симметрична относительно главной диагонали.

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

Выведите сообщение YES, если граф является деревом, и NO в противном случае.

Тесты

Входные данные	Выходные данные
[latex]3 \\ 0 \ 1 \ 0 \\ 1 \ 0 \ 1 \\ 0 \ 1 \ 0[/latex]	[latex]YES[/latex]
[latex]2 \\ 0 \ 1 \\ 1 \ 0[/latex]	[latex]YES[/latex]
[latex]4 \\ 0 \ 0 \ 0 \ 1 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 1 \ 0 \ 0 \ 0[/latex]	[latex]NO[/latex]
[latex]1 \\ 0[/latex]	[latex]YES[/latex]

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

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

class Main
{
	private static void dfs(int v, int p, ArrayList<ArrayList<Integer>> g , int[] A) {
		A[v]++;
		if (A[v]>1)
			return;
		for (int i=0; i<g.get(v).size(); i++)
		{
			if (g.get(v).get(i)!=p)
				dfs(g.get(v).get(i), v, g, A);
		}
	}
	
	public static void main (String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] A = new int[n];
		ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
		for (int i=0; i<n; i++) {
			ArrayList<Integer> r = new ArrayList<Integer>();
			for (int j=0; j<n; j++) {
				int a = scanner.nextInt();
				if (a==1) {
					r.add(j);
				}
			}
			g.add(r);
		}
		int t=0;
		dfs(0, -1, g, A);
		for (int i=0; i<n; i++)
		{
			if (A[i]!=1)
			{
				t++;
				break;
			}
		}
		if (t!=0)
			System.out.print("NO");
		else
			System.out.print("YES");
	}
}

import java.util.Scanner;

import java.util.ArrayList;

class Main

{

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

A[v]++;

if (A[v]>1)

return;

for (int i=0; i<g.get(v).size(); i++)

{

if (g.get(v).get(i)!=p)

dfs(g.get(v).get(i), v, g, A);

}

public static void main (String[] args)

{

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int[] A = new int[n];

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

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

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

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

int a = scanner.nextInt();

if (a==1) {

r.add(j);

}

g.add(r);

}

int t=0;

dfs(0, -1, g, A);

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

{

if (A[i]!=1)

{

t++;

break;

}

if (t!=0)

System.out.print("NO");

else

System.out.print("YES");

}

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

Считываем граф в ArrayList<ArrayList>. Далее выбираем любую вершину и запускаем из нее своего рода dfs. Заключается он в том, что мы идем к потомкам текущей вершины, попутно смотря были ли мы здесь. Если были, завершаем процесс, так как мы нашли цикл (граф, содержащий цикл, не является деревом). При этом мы не идем от потомка к предку. В конце проверяем обошли ли мы все вершины и не встречались ли нам циклы.

Ссылки

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

e-olymp 4475. Часы

09/12/2018 by Алиса Ворохта

Задача

Жители планеты Олимпия любят летать в гости на другие планеты. Ученые планеты разработали часы, которые могут налаживаться для отсчета времени на любой планете. Эти часы состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.

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

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

Входной файл содержит в единственной строке натуральные числа $S, M, H, K$ (количество секунд в минуте, минут в часе, часов в сутках и общее количество шариков соответственно), причем:

$S, M, H ≤ 60$;
$S+M+H-2≤K≤1000$

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

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

Тесты

Входные данные	Выходные данные
$5$ $12$ $12$ $30$	$380$
$7$ $10$ $40$ $70$	$5610$
$60$ $60$ $60$ $500$	$4560840$
$60$ $30$ $5$ $1000$	$4970$

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

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static double gcd(double a, double b){
		double temp;
    	while(b > 0){
        	a = a - b*Math.floor(a/b);
        	temp = a;
			a = b;
	    	b = temp;
    	}
    	return a;
    }
    public static double lcm(double a, double b){
    	return a*(b/gcd(a,b));
    }
	public static void main (String[] args) throws java.lang.Exception
	{
    	int S, M, H, K;
		Scanner in = new Scanner(System.in);
		S = in.nextInt();
		M = in.nextInt();
		H = in.nextInt();
		K = in.nextInt();
		Deque clock = new ArrayDeque(); 
		for(int i = 1; i <= K; i++)
    		clock.addLast(i);
    	Stack s = new Stack();
    	Stack m = new Stack();
    	Stack h = new Stack();
    	while(h.size() != H){
    		s.push(clock.getFirst());  //первый шарик очереди падает
    		clock.removeFirst();       //на секундную чашу
    		if(s.size() == S){         //при переполнении чаши  
				m.push(s.peek());      //последний упавший шарик
    			s.pop();               //переходит на минутную чашу
    			while(!s.empty()){     //остальные шарики  
					clock.addLast((Integer)s.peek());   //переходят в конец очереди
					s.pop();           //в обратном порядке     
				}
				if(m.size() == M){     //аналогично при переполнении          
					h.push(m.peek());  //минутной чаши      
					m.pop();
					while(!m.empty()){
						clock.addLast((Integer)m.peek());
						m.pop();
					}
				}
			}
		}
		while(!h.empty()){
			clock.addLast((Integer)h.peek());
			h.pop();
		}
		/*суточная перестановка
		1  2  3  4  5  6  ... K
		a1 a2 a3 a4 a5 a6 ... ak*/
		int[] permutation = new int[K + 1];
		for(int i = 1; i <= K; i++){
			permutation[i] = clock.getFirst();
			clock.removeFirst();
		}
		//разложение перестановки в композицию непересекающихся циклов
		boolean[] used = new boolean[K+1]; 
		double permutationOrder = 1;    //метки на посещенных элементах
		for(int i = 1; i <= K; i++){    //порядок перестановки
		if(!used[i]){    //если элемент не принадлежит ни одному из обследованных циклов
				double cycleLength = 1;  //найти длину его цикла
				for(int x = i; permutation[x] != i; x = permutation[x]){
					used[x] = true;
					cycleLength++;
				}
				/*и воспользоваться тем, что порядок перестановки -
				произведение длин циклов из его разложения*/
				permutationOrder = lcm(permutationOrder, cycleLength);
			}
    	}
    	System.out.print(Math.round(permutationOrder));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static double gcd(double a, double b){

double temp;

while(b > 0){

a = a - b*Math.floor(a/b);

temp = a;

a = b;

b = temp;

}

return a;

}

public static double lcm(double a, double b){

return a*(b/gcd(a,b));

}

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

{

int S, M, H, K;

Scanner in = new Scanner(System.in);

S = in.nextInt();

M = in.nextInt();

H = in.nextInt();

K = in.nextInt();

Deque clock = new ArrayDeque();

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

clock.addLast(i);

Stack s = new Stack();

Stack m = new Stack();

Stack h = new Stack();

while(h.size() != H){

s.push(clock.getFirst()); //первый шарик очереди падает

clock.removeFirst(); //на секундную чашу

if(s.size() == S){ //при переполнении чаши

m.push(s.peek()); //последний упавший шарик

s.pop(); //переходит на минутную чашу

while(!s.empty()){ //остальные шарики

clock.addLast((Integer)s.peek()); //переходят в конец очереди

s.pop(); //в обратном порядке

}

if(m.size() == M){ //аналогично при переполнении

h.push(m.peek()); //минутной чаши

m.pop();

while(!m.empty()){

clock.addLast((Integer)m.peek());

m.pop();

}

while(!h.empty()){

clock.addLast((Integer)h.peek());

h.pop();

}

/*суточная перестановка

1 2 3 4 5 6 ... K

a1 a2 a3 a4 a5 a6 ... ak*/

int[] permutation = new int[K + 1];

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

permutation[i] = clock.getFirst();

clock.removeFirst();

}

//разложение перестановки в композицию непересекающихся циклов

boolean[] used = new boolean[K+1];

double permutationOrder = 1; //метки на посещенных элементах

for(int i = 1; i <= K; i++){ //порядок перестановки

if(!used[i]){ //если элемент не принадлежит ни одному из обследованных циклов

double cycleLength = 1; //найти длину его цикла

for(int x = i; permutation[x] != i; x = permutation[x]){

used[x] = true;

cycleLength++;

}

/*и воспользоваться тем, что порядок перестановки -

произведение длин циклов из его разложения*/

permutationOrder = lcm(permutationOrder, cycleLength);

}

System.out.print(Math.round(permutationOrder));

}

Алгоритм решения

Интуитивно понятно, что положение шариков в очереди ежесуточно изменяется по одному и тому же закону, в силу однообразия процесса. Отыскать конкретный вид перестановки можно прямым моделированием часов, используя дек для описания лотка и стеки — каждой из чаш (у очереди задействованы оба конца, у чаш — только один).
Определить порядок суточной перестановки можно и возведением её в степень, но это нерациональный способ. Используя теорему о разложении перестановки в композицию циклов (к слову, непересекающихся), можно заметить, что порядок каждого из циклов равен его длине. Если мысленно представить перестановку в виде ориентированного графа, то процесс поиска циклов сведётся к поиску в глубину: обойти каждую компоненту связности, зафиксировать число входящих в неё вершин (на илл.)
$\begin{pmatrix}
1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\
1& 5& 8& 2& 4& 3& 7& 7& 6& 10
\end{pmatrix}$
Зная длины всех циклов, нетрудно заметить, что задача сводится к поиску НОК полученной последовательности длин. Обосновать такой переход можно индуктивно: порядок перестановки, представимой в виде композиции двух циклов, равен НОК их длин, а случай большего количества циклов в разложении сводится к рассмотренному последовательным рассмотрением пар циклов (результат не зависит от порядка рассмотрения в силу ассоциативности композиции).

Примечание

Операция взятия остатка для чисел с плавающей точкой не определена аппаратно, так что алгоритм Евклида вычисления НОД реализован в соответствии с его математическим описанием.

Ссылки

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

e-olymp 2892. Сумма значений

03/12/2018 by Костя Григорян

Задача

Найдите сумму значений функции
$$f \left(x \right ) = x + \frac{1}{x}$$
в нескольких целых точках.

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

В первой строке задано количество точек $n$ $\left (1 \leqslant n \leqslant 50 \right ).$ В следующей строке заданы $n$ целых чисел $x_1, x_2, …, x_n$ — точки, значения функции в которых нужно просуммировать $\left (0 \leqslant \left |x_i \right | \leqslant 10^9 \right ).$

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

Выведите одно число — сумму значений функции $f \left(x \right )$ в заданных точках. Ответ считается правильным, если абсолютная или относительная погрешность не превышает $10^{-9}.$

Тесты

Входные данные	Выходные данные
$3$	$7.833333333333333$
$1 \ 2 \ 3$
$2$	$0$
$1 \ -1$
$5$	$4.265140415140415$
$10 \ -13 \ 21 \ -18 \ 4$
$1$	$10.1$
$10$

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

import java.util.Scanner;
import java.util.ArrayList;
import java.math.BigDecimal; 
 
public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		BigDecimal ans = new BigDecimal(0);
		ArrayList<BigDecimal> a = new ArrayList<BigDecimal>();
		for(int i=0; i<n; i++) {
			BigDecimal x = scanner.nextBigDecimal();
			a.add(x);
		}
		for(int i=0; i<n; i++) {
			BigDecimal w = a.get(i);		
			BigDecimal v = new BigDecimal(1); 
			ans = ans.add(w.add(v.divide(w, 15, BigDecimal.ROUND_HALF_UP)));
		}
		System.out.println(ans);
	}
}

import java.util.Scanner;

import java.util.ArrayList;

import java.math.BigDecimal;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

BigDecimal ans = new BigDecimal(0);

ArrayList<BigDecimal> a = new ArrayList<BigDecimal>();

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

BigDecimal x = scanner.nextBigDecimal();

a.add(x);

}

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

BigDecimal w = a.get(i);

BigDecimal v = new BigDecimal(1);

ans = ans.add(w.add(v.divide(w, 15, BigDecimal.ROUND_HALF_UP)));

}

System.out.println(ans);

}

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

Мы просто суммируем значения функции в каждой точке. Тут использовали класс BigDecimal для точек и значений функции для более высокой точности.

Ссылки

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

e-olymp 161. Роботы

06/11/2018 by Костя Григорян

Задача

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $A$, а вторую – роботы типа $B$. Чтобы сэкономить на покупке роботов, было решено купить не новых роботов последней модели, а уже бывших в употреблении. В результате, время, которое разные роботы тратили на выполнение одной и той же операции, существенно различалось, что привело к трудностям в планировании работ.

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

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

В первой строке натуральное число $N$, $1 ≤ N ≤ 100000$ – количество деталей, которое необходимо обработать.

Во второй строке натуральное число $N_a$, $1 ≤ N_a ≤ 1000$ – количество роботов, выполняющих первую операцию.

В третьей строке через пробел $N_a$ натуральных чисел $A_{i}$, $1 ≤ A_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $A$ на выполнение операции.

В четвертой строке натуральное число $N_b$, $1 ≤ N_b ≤ 1000$ – количество роботов, выполняющих вторую операцию.

В пятой строке через пробел $N_b$ натуральных чисел $B_{i}$, $1 ≤ B_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $B$ на выполнение операции.

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

В первой строке одно целое число – минимальное время, за которое все $N$ деталей будут обработаны сначала роботом типа $A$, а потом роботом типа $B$. Временем передачи детали от робота типа $A$ роботу типа $B$ пренебречь.

Тесты

Входные данные	Выходные данные
[latex]6[/latex]	[latex]9[/latex]
[latex]3[/latex]
[latex]1\, 3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]2[/latex]	[latex]5[/latex]
[latex]2[/latex]
[latex]3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]5[/latex]	[latex]41[/latex]
[latex]4[/latex]
[latex]84\, 50\, 50\ 8[/latex]
[latex]2[/latex]
[latex]1\, 21[/latex]
[latex]100[/latex]	[latex]100[/latex]
[latex]2[/latex]
[latex]1\, 50[/latex]
[latex]4[/latex]
[latex]1\, 2\, 3\, 4[/latex]

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

import java.util.*;

public class Main {
	
	private static class Pair{
		int a, b;
		
		public Pair(int a, int b) {
			this.a=a;
			this.b=b;
		}
		
	}
	
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int na = scanner.nextInt();
		int[] A = new int[na];
		int[] times = new int[n];
		PriorityQueue<Pair> q = new PriorityQueue<>((a, b)->a.a-b.a);
		for(int i=0; i<na; i++) {
			A[i] = scanner.nextInt();
			q.add(new Pair(A[i], A[i]));
		}
		for(int i=0; i<n; i++) {
			Pair pair=q.poll();
			times[i]=pair.a;
			q.add(new Pair(pair.a+pair.b, pair.b));
		}
		q.clear();
		int nb = scanner.nextInt();
		int[] B = new int[nb];
		int max_time=0;
		for(int i=0; i<nb; i++) {
			B[i] = scanner.nextInt();
			q.add(new Pair(B[i], B[i]));
		}
		for(int i=n-1; i>=0; i--) {
			Pair pair=q.poll();
		    times[i]+=pair.a;
			q.add(new Pair(pair.a+pair.b, pair.b));
			if(times[i]>max_time)
				max_time=times[i];
		}
		System.out.println(max_time);
	}
}

import java.util.*;

public class Main {

private static class Pair{

int a, b;

public Pair(int a, int b) {

this.a=a;

this.b=b;

}

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int na = scanner.nextInt();

int[] A = new int[na];

int[] times = new int[n];

PriorityQueue<Pair> q = new PriorityQueue<>((a, b)->a.a-b.a);

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

A[i] = scanner.nextInt();

q.add(new Pair(A[i], A[i]));

}

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

Pair pair=q.poll();

times[i]=pair.a;

q.add(new Pair(pair.a+pair.b, pair.b));

}

q.clear();

int nb = scanner.nextInt();

int[] B = new int[nb];

int max_time=0;

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

B[i] = scanner.nextInt();

q.add(new Pair(B[i], B[i]));

}

for(int i=n-1; i>=0; i--) {

Pair pair=q.poll();

times[i]+=pair.a;

q.add(new Pair(pair.a+pair.b, pair.b));

if(times[i]>max_time)

max_time=times[i];

}

System.out.println(max_time);

}

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

Решение состоит из двух этапов.
Найдем минимальное время, которое понадобится роботам первого типа, чтобы завершить обработку всех деталей. Для каждой детали, мы берем робота с минимальным временем завершения обработки этой детали и обновляем его время на время обработки им одной детали.
На втором этапе фактически делаем тоже, что и на первом с учетом следующей стратегии комбинации. Для детали, которая пройдет первый этап последней, на втором этапе резервируем самый быстрый из роботов второго типа.
Теперь оценим сложность работы алгоритма. Для каждой из $n$ деталей работает логарифмическая вставка в очередь с приоритетом. Получаем, что асимптотическая вычислительная сложность алгоритма $O(n\, \log n)$.

Ссылки

Условие задачи на e-olymp
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова:

Задача

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

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

Тесты

№

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

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

Решение

Ссылки

10

7

123

229966

1

1

100

136345

51

5092

Задача

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

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

Тесты

Код задачи

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

Ссылки

Задача

Вхідні дані

Вихідні дані

Тести

Код програми

Рішення завдання

Код програми з множиною

Рішення завдання

Посилання

Условие

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

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

Тесты

Код решения

Решение

Ссылки

Task

Input data

Output data

Tests

Code

Solution

References

Задача

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

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

Тесты

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

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

Ссылки

Задача

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

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

Тесты

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

Алгоритм решения

Примечание

Ссылки

Задача

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

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

Тесты

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

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

Ссылки

Задача

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

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

Тесты

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

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

Ссылки