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 209. Защита от копирования

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

Условие

Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина Колец, на далекой-далекой планете жили-были полчища смешариков. Их технологии были настолько совершенны, что они создали машину времени и перенеслись на ней в будущее, на планету «Земля», где одному из них совершенно случайно попалась первая серия «Смешариков». Исследователей эта серия так потрясла, что они предприняли чрезвычайно опасный рейд, в ходе которого им удалось добыть полное собрание серий. Эти серии они увезли на родину, где они стали безумно популярными. К сожалению, мультфильмы были с системой защиты от копирования, а смешарики по своей законопослушной сущности не приспособлены к хакерской деятельности. Поэтому им пришлось обмениваться привезенными с Земли дисками.

Местная поп-звезда Билаш обиделся на такую популярность, к которой он не имел никакого отношения, и решил вернуть все в старое русло. Для этого Билаш хочет рассорить смешариков, чтобы они разделились на два не общающихся между собой лагеря. Для того, чтобы поссорить пару смешариков, Билашу требуется израсходовать 1 у.е. усилий. Но, так как Билаш жутко ленив, он хочет приложить минимум усилий для достижения своей цели. Помогите ему.

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

Hа первой строке два числа $N(N\leq 100)$ и $M$ — количество смешариков и количество пар смешариков, которые обмениваются мультфильмами. На последующих $M$ строках перечисляются пары чисел $U$ и $V$, означающих, что смешарик U и смешарик V знакомы друг с другом и обмениваются мультфильмами.

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

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

Тесты

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

Код решения

import java.util.*;

public class Main {

    static int maxn = 100;
    static int bestCost = Integer.MAX_VALUE;
    static int[][] relations = new int[Main.maxn][Main.maxn];

    public static void mincut(int N) {
        Vector<Vector<Integer>> compressed_vertices = new Vector<Vector<Integer>>();
        for (int i = 0; i < N; i++) {
            compressed_vertices.add(new Vector<Integer>());
            compressed_vertices.get(i).add(i);
        }

        int[] weights;
        weights = new int[N];
        boolean[] exist;
        exist = new boolean[N];
        boolean[] in_A;
        in_A = new boolean[N];
        for (int i = 0; i < N; i++) {
            exist[i] = true;
        }
        for (int ph = 0; ph < N - 1; ++ph) {
            for (int i = 0; i < N; i++) {
                in_A[i] = false;
            }
            for (int i = 0; i < N; i++) {
                weights[i] = 0;
            }
            int prev = 0;
            for (int it = 0; it < N - ph; ++it) {
                int sel = -1;
                for (int i = 0; i < N; ++i) {

                    if ((exist[i] == true) && (in_A[i] == false) && (sel == -1 || weights[i] > weights[sel])) {
                        sel = i;
                    }
                }
                if (it == N - ph - 1) {
                    if (weights[sel] < bestCost) {
                        bestCost = weights[sel];
                    }

                    compressed_vertices.get(prev).addAll(compressed_vertices.get(sel));

                    for (int i = 0; i < N; ++i) {
                        relations[prev][i] = relations[i][prev] += relations[sel][i];
                    }
                    exist[sel] = false;
                } else {

                    in_A[sel] = true;
                    for (int i = 0; i < N; ++i) {
                        weights[i] += relations[sel][i];
                    }
                    prev = sel;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        for (int i = 0; i < M; i++) {
            int U = in.nextInt() - 1;
            int V = in.nextInt() - 1;
            relations[U][V] = 1;
            relations[V][U] = 1;
        }
        mincut(N);
        System.out.print(bestCost);
    }

}

import java.util.*;

public class Main {

static int maxn = 100;

static int bestCost = Integer.MAX_VALUE;

static int[][] relations = new int[Main.maxn][Main.maxn];

public static void mincut(int N) {

Vector<Vector<Integer>> compressed_vertices = new Vector<Vector<Integer>>();

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

compressed_vertices.add(new Vector<Integer>());

compressed_vertices.get(i).add(i);

}

int[] weights;

weights = new int[N];

boolean[] exist;

exist = new boolean[N];

boolean[] in_A;

in_A = new boolean[N];

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

exist[i] = true;

}

for (int ph = 0; ph < N - 1; ++ph) {

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

in_A[i] = false;

}

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

weights[i] = 0;

}

int prev = 0;

for (int it = 0; it < N - ph; ++it) {

int sel = -1;

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

if ((exist[i] == true) && (in_A[i] == false) && (sel == -1 || weights[i] > weights[sel])) {

sel = i;

}

if (it == N - ph - 1) {

if (weights[sel] < bestCost) {

bestCost = weights[sel];

}

compressed_vertices.get(prev).addAll(compressed_vertices.get(sel));

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

relations[prev][i] = relations[i][prev] += relations[sel][i];

}

exist[sel] = false;

} else {

in_A[sel] = true;

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

weights[i] += relations[sel][i];

}

prev = sel;

}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int N = in.nextInt();

int M = in.nextInt();

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

int U = in.nextInt() - 1;

int V = in.nextInt() - 1;

relations[U][V] = 1;

relations[V][U] = 1;

}

mincut(N);

System.out.print(bestCost);

}

Решение

Зададим связи между смешариками в виде графов, где сами смешарики являются вершинами, смежными в том случае, если они дружат. Тогда задача сводится к нахождению минимального количества ребер, которые необходимо удалить в графе, чтобы разбить его на две не связанные между собою компоненты. Такую постановку задачи полностью решает алгоритм Штор-Вагнера в несколько упрощенном виде, так как нам не нужно знать, какие именно ребра графа надо разорвать, а достаточно подсчитать их количество.

Ссылки

Условие задачи на e-olymp
Код решения на 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-olimp 5079. Транзитивность ориентированного графа

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

Условие

Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин $u$, $v$ и $w$ из того, что из $u$ в вершину $v$ ведет ребро и из вершины $v$ в вершину $w$ ведет ребро, следует, что из вершины $u$ в вершину $w$ ведет ребро.
Проверьте, что заданный ориентированный граф является транизитивным.

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

Входной файл содержит число $n (1 \leq n \leq 100)$ — число вершин в графе, и затем $n$ строк по $n$ чисел, каждое из которых равно $0$ или $1$ — его матрицу смежности.

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

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

Тесты

Входные данные	Выходные данные
$3$ $0$ $1$ $1$ $0$ $0$ $1$ $0$ $0$ $0$	YES
$3$ $0$ $1$ $1$ $1$ $0$ $0$ $0$ $1$ $0$	NO

Код задачи

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String answer = "YES";
        short[][] graph = new short [n][n];
        for (int i = 0; i < n; i++) {
            for( int j = 0; j < n; j++) {
                graph[i][j] = sc.nextShort();
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if (graph[i][j] == 1){ 
                    for (int z = 0; z < n; z++){
                        if (graph[j][z] == 1 && graph[i][z] == 0) { 
                            answer = "NO";
                            break;
                        }   
                    }   
                }
            }
        }
    System.out.print(answer);
    }
}

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

String answer = "YES";

short[][] graph = new short [n][n];

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

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

graph[i][j] = sc.nextShort();

}

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

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

if (graph[i][j] == 1){

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

if (graph[j][z] == 1 && graph[i][z] == 0) {

answer = "NO";

break;

}

System.out.print(answer);

}

Решение

Представим матрицу смежности графа в виде двумерного массива. Тогда, если $graph[i][j]=1$, то из вершины $i$ в вершину $j$ ведёт ребро. Проверяем с помощью циклов транзитивность графа, то есть если из вершины $i$ в вершину $j$ ведёт ребро и из вершины $j$ в вершину $z$, то граф транзитивен, если есть ребро $graph[i][z]$.

Ссылки

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

e-olymp 2371. Черный квадрат

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

Условие

Вдохновленный шедевром Казимира Малевича «Черный квадрат», Петр Палевич решил создать собственную версию картины. Он приготовил полотно в виде прямоугольной сетки с $m \times n$ белыми квадратами — $m$ строк по $n$ ячеек каждая.

Петр покрасил некоторые клетки в черный цвет так, что черные ячейки сформировали квадрат размером $s \times s$ ячеек. Но на следующий день Петр разочаровался в своем творении и уничтожил его, разрезав полотно горизонтальными полосами размера $1 \times n$, после чего сжег их в камине.

На следующее утро Петр передумал и решил восстановить картину. Он попытался найти ее останки в камине, и, к счастью, одну из полос, а именно $k$-ую сверху, огонь не тронул.

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

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

Первая строка содержит четыре целых числа: $m$,$n$,$s$ и $k$.
$(1 \leq m,n \leq 5000, 1 \leq s \leq \min(m,n), 1 \leq k \leq m).$
Вторая строка содержит $n$ символов и описывает $k$-ую строку картины, ‘.’ означает белую клетку, ‘*’ означает черную клетку.

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

Если изображение может быть однозначно восстановлено, то следует вывести «Unique». Если существует несколько вариантов восстановления картины, то вывести «Ambiguous». Если ни одной соответствующей картины не существует, вывести «Impossible».

Тесты

Входные данные	Выходные данные
$3$ $4$ $2$ $3$ ..**	Unique
$4$ $4$ $2$ $3$ ..	Impossible
$3$ $5$ $2$ $2$ .**..	Ambiguous
$2$ $8$ $1$ $2$ ……*.	Unique

Код задачи

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int s = sc.nextInt();
        int k = sc.nextInt();
        String stripe = sc.next();
        int number_of_stars = 0;
        boolean end_of_stars = false;
        boolean sec_seq = false;
        String result = new String();
        for (int i = 0; !sec_seq && i < stripe.length(); i++){
            if ('*' == stripe.charAt(i)) {
                if (end_of_stars == true) sec_seq = true;
                else number_of_stars++;
            }
            else {
                if (end_of_stars == false && number_of_stars != 0){
                    end_of_stars = true;
                }
            }
        }
        if (sec_seq == true) result = "Impossible";
        else {
            if (number_of_stars == 0) {
                if (s > k-1 && s > m-k) result = "Impossible";
                else {
                    if (n > s) result = "Ambiguous";
                    else {
                        if ((s > m - k && k - 1 == s) || (s > k - 1 && m - k == s)){
                            result = "Unique";
                        }
                        else result = "Ambiguous";
                    }
                }
            }
            else {
                if (number_of_stars != s) result = "Impossible";
                else {
                    if (m == s || s == 1 || k == 1 || k == m) result = "Unique";
                    else result = "Ambiguous";
                }
            }
        }
        System.out.print(result);
    }
    
}

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int m = sc.nextInt();

int n = sc.nextInt();

int s = sc.nextInt();

int k = sc.nextInt();

String stripe = sc.next();

int number_of_stars = 0;

boolean end_of_stars = false;

boolean sec_seq = false;

String result = new String();

for (int i = 0; !sec_seq && i < stripe.length(); i++){

if ('*' == stripe.charAt(i)) {

if (end_of_stars == true) sec_seq = true;

else number_of_stars++;

}

else {

if (end_of_stars == false && number_of_stars != 0){

end_of_stars = true;

}

if (sec_seq == true) result = "Impossible";

else {

if (number_of_stars == 0) {

if (s > k-1 && s > m-k) result = "Impossible";

else {

if (n > s) result = "Ambiguous";

else {

if ((s > m - k && k - 1 == s) || (s > k - 1 && m - k == s)){

result = "Unique";

}

else result = "Ambiguous";

}

else {

if (number_of_stars != s) result = "Impossible";

else {

if (m == s || s == 1 || k == 1 || k == m) result = "Unique";

else result = "Ambiguous";

}

System.out.print(result);

}

Решение

Основная сложность задачи заключается в аккуратном рассмотрении всех возможных вариантов. После прочтения строки символов, которую представляет собой вытащенная из огня полоска, исследуем ее на количество подряд идущих символов $*$. Если последовательностей из звездочек в одной строке несколько, то никакие добавленные полоски не смогут сделать из нее квадрат, и тогда решений нет. Иначе дальнейшее решение делится на два случая:

Спасенная из огня полоска не содержит звездочек. Тогда мы проверяем, может ли поместиться квадрат из звездочек хотя бы в одну из двух частей, на которые эта полоска делит картину. Если да, проверяем, однозначно ли определяем этот квадрат, или же имеется несколько вариантов его возможного расположения в них.
Спасенная из огня полоска содержит звездочки. Тогда, если количество звездочек не совпадает с длиной стороны квадрата, то построить его невозможно, а иначе проверяем, однозначно ли определяем этот квадрат. Здесь необходимо аккуратно рассмотреть все «особенные» случаи, такие как квадрат, состоящий из одной звездочки, а также первая и последняя полоски картины. Очевидно, что в этих случаях расположение квадрата определяется единственным образом.

Ссылки

Текст задачи на e-olymp

e-olymp 13. Паук и муха

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

Задача

В пустой прямоугольной комнате размерами $A \times B \times C$ (длина, ширина, высота) на пол упала уснувшая муха. Паук, находившийся на одной из стен, или на полу комнаты, начал двигаться к ней по кратчайшему пути.

На какое расстояние он при этом переместится?

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

В первой строке заданы размеры комнаты $A$, $B$, $C$. Во второй строке — координаты мухи $X_1$,$Y_1$ и паука $X_2$, $Y_2$, $Z_2$.

Все входные данные — целые числа, не превышающие $500$.

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

Единственное число — расстояние, на которое переместится паук, вычисленное с точностью до 2-х знаков после запятой.

Тесты

Входные данные	Выходные данные
$3$ $4$ $8$ $0$ $0$ $3$ $4$ $0$	$5.00$
$2$ $2$ $8$ $1$ $1$ $2$ $1$ $4$	$5.00$
$6$ $4$ $3$ $5$ $1$ $0$ $2$ $1$	$6.08$
$30$ $60$ $27$ $13$ $21$ $8$ $0$ $17$	$38.33$
$40$ $40$ $40$ $10$ $5$ $8$ $40$ $37$	$72.03$

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

import java.io.PrintStream;
import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static double distance (double X1,double X2,double Y1,double Y2)
    {
        return (Math.sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)));
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double A = sc.nextDouble();
        double B = sc.nextDouble();
        double C = sc.nextDouble();
        double X1 = sc.nextDouble();
        double Y1 = sc.nextDouble();
        double X2 = sc.nextDouble();
        double Y2 = sc.nextDouble();
        double Z2 = sc.nextDouble();
        double result_distance = Double.MAX_VALUE;
        if (Z2==0) result_distance = distance(X1,X2,Y1,Y2);//"floor" case
        else
        {
            if (X2==0) {
                X2=-Z2;
                result_distance = distance (X1,X2,Y1,Y2);
            }//"left wall" case
            if (X2==A) {
                X2=A+Z2;
                result_distance = distance (X1,X2,Y1,Y2);
            }//"right wall" case
            if (Y2==0) {
                Y2=-Z2;
                result_distance = Math.min(result_distance, distance (X1,X2,Y1,Y2));
            }//"near wall" case
            if (Y2==B) {
                Y2=B+Z2;
                result_distance = Math.min(result_distance, distance (X1,X2,Y1,Y2));
            }//"distant wall" case
        }
        System.out.printf("%.2f", result_distance);
    }
}

import java.io.PrintStream;

import java.util.Scanner;

import java.lang.Math;

public class Main {

public static double distance (double X1,double X2,double Y1,double Y2)

{

return (Math.sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)));

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

double A = sc.nextDouble();

double B = sc.nextDouble();

double C = sc.nextDouble();

double X1 = sc.nextDouble();

double Y1 = sc.nextDouble();

double X2 = sc.nextDouble();

double Y2 = sc.nextDouble();

double Z2 = sc.nextDouble();

double result_distance = Double.MAX_VALUE;

if (Z2==0) result_distance = distance(X1,X2,Y1,Y2);//"floor" case

else

{

if (X2==0) {

X2=-Z2;

result_distance = distance (X1,X2,Y1,Y2);

}//"left wall" case

if (X2==A) {

X2=A+Z2;

result_distance = distance (X1,X2,Y1,Y2);

}//"right wall" case

if (Y2==0) {

Y2=-Z2;

result_distance = Math.min(result_distance, distance (X1,X2,Y1,Y2));

}//"near wall" case

if (Y2==B) {

Y2=B+Z2;

result_distance = Math.min(result_distance, distance (X1,X2,Y1,Y2));

}//"distant wall" case

}

System.out.printf("%.2f", result_distance);

}

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

Суть решения задачи заключается в переходе от трехмерного пространства комнаты к двумерному с помощью «развёртки» комнаты на координатную плоскость.

Переведя координаты паука в комнате в его новые координаты в двумерном пространстве, все, что нам остается сделать — вычислить кратчайшее расстояние между двумя точками на плоскости с помощью функции $distance$.
В простейшем случае, если паук находится на полу комнаты, т.е. его координата $Z2$ нулевая, координаты паука $X2$ и $Y2$ в точности описывают его положение в координатной плоскости развёртки, и преобразовывать их не требуется.
В противном случае отдельно рассматриваем варианты расположения паука на каждой из стен. В зависимости от того, на какой стене он находится, мы изменяем координаты в соответствии с развёрткой комнаты и находим расстояние от паука до мухи с помощью функции $distance$.
В случае местонахождения паука в каком-либо из углов комнаты, но не на полу, мы должны рассмотреть два варианта его положения в развёртке и найти минимальное из них.

Ссылки

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

e-olymp 7612. Алекс и квадраты оригами

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

Задача

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

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

В одной строке два целых числа $h$ и $w$ $(1 \leq h,w\leq 1000)$ — высота и ширина куска бумаги.

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

Выведите одно действительное число — наибольшую длину стороны квадратов. Всегда можно вырезать три одинаковых квадрата из листа бумаги размером $h \times w$ так, чтобы их стороны были параллельны сторонам листа.

Ответ следует вывести с точностью не меньше трех десятичных знаков.

Тесты

Входные данные	Выходные данные
$100$ $100$	$50.000$
$10$ $80$	$10.000$
$50$ $76$	$25.333$
$60$ $27$	$20.000$
$8$ $3$	$2.667$

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

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		double h = sc.nextDouble();
		double w = sc.nextDouble();
    	double b = Math.max(h, w);
    	double a = Math.min(w, h);
    	double c = Math.min(Math.min(w,h), Math.max(b/3, a/2));
    	System.out.printf("%.4f", c);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner sc = new Scanner(System.in);

double h = sc.nextDouble();

double w = sc.nextDouble();

double b = Math.max(h, w);

double a = Math.min(w, h);

double c = Math.min(Math.min(w,h), Math.max(b/3, a/2));

System.out.printf("%.4f", c);

}

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

Существует два варианта оптимального расположения трех квадратов — три в один ряд,

или же два, соприкасающихся одной стороной, и третий над ними

Обозначим за $a$ меньшую сторону листа бумаги, а за $b$ — большую. Если a не больше $\frac{b}{3}$, то оптимальным расположением квадратов в прямоугольнике будет первый вариант, а наибольшей возможной стороной квадратов является меньшая сторона листа бумаги $a$. В противном случае рассмотрим два варианта:

Если $\frac{a}{2} < \frac{b}{3}$, то квадраты будут располагаться в прямоугольнике первым способом, и ответом будет служить число $\frac{a}{2}$.
Иначе квадраты будут располагаться в прямоугольнике вторым способом, и ответом будет служить число $\frac{b}{3}$.

Таким образом, в случае $a > \frac{b}{3}$ ответом будет служить большее из двух чисел $\frac{a}{2}$ и $\frac{b}{3}$. Mинимальное из $\max \left(\frac{a}{2},\frac{b}{3} \right)$ и $a$ число и будет ответом.
Проверим нашу формулу:если $a < \frac{b}{3}$, то $\max \left(\frac{a}{2},\frac{b}{3} \right) = \frac{b}{3}$, и тогда $\min \left( a,\max \left(\frac{a}{2},\frac{b}{3} \right) \right) = a$. Иначе $\min \left( a,\max \left(\frac{a}{2},\frac{b}{3} \right) \right) = \max \left(\frac{a}{2},\frac{b}{3}\right)$, что нам и требуется.

Ссылки

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

e-olymp 1000. Задача a + b

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

Задача

Вычислите сумму $a+b$.

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

В каждой строке задано два целых числа $a$ и $b$ $(|a|,|b| \leq 30000)$.

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

Для каждого теста выведите сумму $a+b$ в отдельной строке.

Тесты

Входные данные	Выходные данные
$4$ $8$ $5$ $0$ $-6$ $8$	$12$ $5$ $2$
$-3$ $3$	$0$
$12$ $8$ $10$ $10$	$20$ $20$
$30000$ $30000$ $3000$ $3000$ $300$ $300$ $30$ $30$ $3$ $3$	$60000$ $6000$ $600$ $60$ $6$
$10$ $23$ $613$ $2$ $-200$ $300$	$33$ $615$ $100$

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

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

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);
		while (in.hasNextInt()){
        	int a = in.nextInt();
        	int b = in.nextInt();
        	System.out.println(a+b);
		}
	}
}

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

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);

while (in.hasNextInt()){

int a = in.nextInt();

int b = in.nextInt();

System.out.println(a+b);

}

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

Пока вводятся пары чисел, они считываются и на экран выводится их сумма.

Ссылки

Условие на e-olymp
Решение на языке C++ с описанием решения
Код на java

e-olymp 7457. Max-Min в двійковій системі счислення

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

Умова

Вивчаючи двійкову систему числення, Василько вирішив попрактикуватися і придумав таку вправу. Він із бітів числа створював найбільше і найменше число, переставляючи біти, після чого знаходив їх різницю. Проте хлопець не знає, чи правильно виконує вправу. Допоможіть йому. Напишіть програму, яка за даним числом $N$ знаходить різницю між найбільшим і найменшим числом, які утворюються із бітів заданого числа. У найбільшого числа найбільший біт співпадає з найбільшим бітом заданого числа.

Пояснення

$N=13_{10}$, в двійковій системі числення — $1101_2$, найбільше число $1110_2 = 14_{10}$, найменше число $0111_2 = 7_{10}$. $14−7=7$.

Вхідні дані

В єдиному рядку записане число $N (N<2^{31})$.

Вихідні дані

Єдине число — відповідь до вправи Василька.

Тести

Вхідні дані	Вихідні дані
2	1
15	0
86	105
1000	945
40	45

Код програми

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

class Main
{
	 public static double max_number(int n1, int n0){
	 	double number = 0;
    	for (int i = n0+n1-1; i >= n0; i = i-1)
    	{
        	number += Math.pow(2, i);  
    	}
    	return (number);
	}
	public static double min_number(int n1, int n0)
	{
	    double  number = 0;
	    for (int i = n1-1; i >= 0; i = i-1)
	    {
	        number = number + Math.pow(2, i);  
	    }
	    return(number);
	}
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner in = new Scanner(System.in);
        int n = in.nextInt();
	    int n1=0;
	    int n0=0;
	    while (n>0)
	    {
	        if (n%2==1){
	        	n1=n1+1;
	        	}
	        else{
	        	n0+=1;
	        }
	        n/=2;
	    }
	    int res = (int) max_number(n1, n0) - (int) min_number(n1, n0);
	    System.out.print(res);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static double max_number(int n1, int n0){

double number = 0;

for (int i = n0+n1-1; i >= n0; i = i-1)

{

number += Math.pow(2, i);

}

return (number);

}

public static double min_number(int n1, int n0)

{

double number = 0;

for (int i = n1-1; i >= 0; i = i-1)

{

number = number + Math.pow(2, i);

}

return(number);

}

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int n1=0;

int n0=0;

while (n>0)

{

if (n%2==1){

n1=n1+1;

}

else{

n0+=1;

}

n/=2;

}

int res = (int) max_number(n1, n0) - (int) min_number(n1, n0);

System.out.print(res);

}

Рішення

Процес вирішення даної задачі поділяється на 4 кроки:

За допомогою циклу рахуємо кількість одиниць та нулів у двійковому вигляді поданого числа $n$.
Створимо функцію $max_number$, яка за поданою кількістю нулів та одиниць буде повертати найбільше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Очевидно, що отримати найбільше число в двійковому вигляді можна, якщо записати спочатку всі одиниці, а потім — усі нулі.
Створимо функцію $min_number$, яка за поданою кількістю нулів та одиниць буде повертати найменше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Зрозуміло, що найменше число буде виглядати навпаки — спочатку будуть стояти всі нулі, а потім — усі одиниці.
Виведемо на екран різницю підрахованих функціями $max_number$ та $min_number$ значень.

Посилання

Умова на e-olymp
Вирішення мовою C++ з поясненнями
Код на java