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 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 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 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
Код решения

A281 Последовательные вычисления значений нового массива

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

Условие задачи:
Даны действительные числа [latex]a_{1}, \ldots, a_{n}, b_{1}, \ldots, b_{n}[/latex]. Члены последовательности [latex]c_{1}, \ldots, c_{n+1}[/latex] связаны с членами данных последовательностей соотношениями [latex]c_{n+1}=0, c_{\left (n+1\right )-i}=\frac{a_{\left (n+1\right )-i}}{b_{\left (n+1\right )-i}-c_{\left (n+1\right )-i+1}} \left (i=1, \ldots, n \right ).[/latex] Получить [latex]c_{1}, \ldots, c_{n+1}[/latex].

Входные данные:
В первой строке задано число [latex]n[/latex]. В последующих строках записано две числовые последовательности из n чисел.

Выходные данные:
Вывести результирующую последовательность [latex]c[/latex], найденную согласно условию задачи.

Тесты:

Входные данные		Выходные данные
28	100 23 45 62 17 873 46 927 64 5 8 9 3 0 89 73 12 53 62 7 12 35 64 50 227 23 100 80 12 34 23 6 7 8 9 25 10 9 73 24 27 8 4 3 2 0 9 1 45 62 100 104 5 6 14 21	8.89145197864941 0.7532429753739995 3.46536409638595 10.014351523139867 -0.19111480725820545 95.9517680178081 -1.0983211464949347 50.88210356032888 6.781413598577088 0.5624396639914702 0.11015755091584475 0.3767441860465116 0.1111111111111111 0.0 4.803215151847447 -14.529255339679752 8.024345590557227 0.5045509487875016 -105.04390117066583 9.590229411789153 0.2700904535823736 0.5704400476332376 0.6438589905891021 0.5993533748082496 20.57676071984004 -6.031862745098037 9.813084112149534 3.8095238095238093 0.0
10	2 -4 1 2 45.2 34 -23 34 56 7.09 -3.4 4 4 -5 2.4 34.04 23 567 -3 4	-0.8567913942992066 -1.0657095142326265 0.24663198875517678 -0.05462407795229777 31.61389033873605 0.9702487256173882 -1.0025608427005548 0.05874893533055214 -11.733892090099529 1.7725 0.0

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

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n=in.nextInt();
		double[] A = new double[n];
		double[] B = new double[n];
		double[] C = new double[n+1];
		String ans = new String("");
		double inf = 1.0 / 0;
		C[n] = 0.0;
		int k=0;
		while(k<n){
			A[k] = in.nextDouble();
			k++;
		}
		String c=in.nextLine();
		int t=0;
		while(t<n){
			B[t]=in.nextDouble();
			t++;
		}
		for (int i=1; i<=n; i++){
			if(B[n-i]-C[n-i+1]!=0) C[n-i]=A[n-i]/(B[n-i]-C[n-i+1]);
			else C[n-i]=inf;
		}
		for (int i=0; i<=n; i++){
			ans+=Double.toString(C[i])+" ";	
		}
		System.out.println(ans);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int n=in.nextInt();

double[] A = new double[n];

double[] B = new double[n];

double[] C = new double[n+1];

String ans = new String("");

double inf = 1.0 / 0;

C[n] = 0.0;

int k=0;

while(k<n){

A[k] = in.nextDouble();

k++;

}

String c=in.nextLine();

int t=0;

while(t<n){

B[t]=in.nextDouble();

t++;

}

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

if(B[n-i]-C[n-i+1]!=0) C[n-i]=A[n-i]/(B[n-i]-C[n-i+1]);

else C[n-i]=inf;

}

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

ans+=Double.toString(C[i])+" ";

}

System.out.println(ans);

}

Алгоритм решения:
Узнаем количество необходимых элементов: считаем число [latex]n[/latex]. С помощью двух циклов также считаем все элементы массивов [latex]a[/latex] и [latex]b[/latex]. Заведем еще один счетчик для нахождения значений ячеек нового массива, воспользовавшись нашей заданной формулой [latex]c_{\left (n+1\right )-i}=\frac{a_{\left (n+1\right )-i}}{b_{\left (n+1\right )-i}-c_{\left (n+1\right )-i+1}} \left (i=1, \ldots, n \right )[/latex] при условии, что [latex]c_{n+1}=0.[/latex] Выведем все элементы единой строкой.

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

e-olymp 5741. Стек шаров

16/12/2017 by Антон Куперман

Задание

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

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

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

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

Каждый тест задается в нескольких строках. Первая строка содержит количество рядов [latex]N (1 ≤ N ≤ 1000)[/latex] в стеке. [latex]i[/latex]-ая из следующих [latex]N [/latex] строксодержит [latex]i[/latex] целых чисел [latex]B_{ij} (-10^{5}≤ B_{ij}≤ 10^{5}[/latex] для [latex]1 ≤ j ≤ i ≤ N)[/latex]; значение [latex]B_{ij}[/latex] равно числу, записанному на [latex]j[/latex]-ом шаре в [latex]i[/latex]-ом ряду стека (первый ряд — самый верхний, в каждом ряду первым шаром является самый левый).

За последним тестом следует строка, содержащая один ноль.

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

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

Тесты

Ввод	Вывод
4 3 -5 3 -8 2 -8 3 9 -2 7 2 -2 1 -10 3 1 -5 3 6 -4 1 0	7 0 6
3 7 2 1 3 4 6 2 5 9 2 1 2 0	23 16 2

Код

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

public class Main
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		int[][] s = new int[1001][1001];
		while (in.hasNextInt()) 
		{
			int n = in.nextInt();
			int ans = 0;
			if(n==0)
			{
				break;
			} else {
				for (int i = 1; i <= n; i++) 
				{
					for (int j = 1; j <= i; j++) 
					{
						s[i][j] = in.nextInt();
						s[i][j] += s[i - 1][j];
					}
				}
				for (int j = 1; j <= n; j++)
				{
					for (int i = j; i <= n; i++) 
					{
						s[i][j] += s[i - 1][j - 1];
					}
					for (int i = n - 1; i >= j; i--) {
						s[i][j] = Math.max(s[i][j], s[i + 1][j]);
					}
				}
				for (int i = 1; i <= n; i++) {
					ans = Math.max(ans, s[i][i]);
				}
				System.out.println(ans);
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int[][] s = new int[1001][1001];

while (in.hasNextInt())

{

int n = in.nextInt();

int ans = 0;

if(n==0)

{

break;

} else {

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

{

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

{

s[i][j] = in.nextInt();

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

}

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

{

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

{

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

}

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

s[i][j] = Math.max(s[i][j], s[i + 1][j]);

}

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

ans = Math.max(ans, s[i][i]);

}

System.out.println(ans);

}

Решение

Иницианилизируем двумерный массив [latex]s[/latex], который будет играть роль нашего стека. При считывании массива будем сразу суммировать предыдущие шары. Далее будем хранить в нижних шарах стека сумму всех верхних и при обходе с помощью максимума находить оптимальный путь. Остаётся только найти максимум среди получившихся сумм. Это и будет нашим ответом.

Ссылки

e-olymp 6129. Дек с защитой от ошибок

10/12/2017 by Эммануил Прокопов

Задача с сайта e-olymp.com.

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

Реализуйте структуру данных «дек». Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

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

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Перед исполнением операций pop_front, pop_back, front, back программа должна проверять, содержится ли в деке хотя бы один элемент. Если во входных данных встречается операция pop_front, pop_back, front, back, и при этом дек пуст, то программа должна вместо числового значения вывести строку error.

Входные данные
Каждая строка содержит одну команду.

Выходные данные
Для каждой команды вывести в отдельной строке соответствующий результат.

Тесты

№	Входные данные	Выходные данные
1	front back pop_back pop_front exit	error error error error bye
2	push_back 1 back exit	ok 1 bye
3	push_back 1 push_front 2 back front size clear size pop_back exit	ok ok 1 2 2 ok 0 error bye

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

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

class DequeException extends Exception {}

class Node <T>
{
	T val;
	Node prev, next;
	
	Node(T v, Node p, Node n) {val = v; prev = p; next = n;}
}

class MyDeque <T>
{
	int size;
	Node<T> first, last;
	
	MyDeque() {
		size = 0;
		first = null;
		last = null;
	}
	
	String pushBack(T val) {
		if (size > 0) {
			Node currentNode = new Node<T> (val, last, null);
			last.next = currentNode;
			last = currentNode;
			size++;
		}
		else {
			Node currentNode = new Node<T> (val, null, null);
			last = currentNode;
			first = currentNode;
			size++;
		}
		return "ok";
	}
	
	String pushFront(T val) {
		if (size > 0) {
			Node currentNode = new Node<T> (val, null, first);
			first.prev = currentNode;
			first = currentNode;
			size++;
		}
		else {
			Node currentNode = new Node<T> (val, null, null);
			last = currentNode;
			first = currentNode;
			size++;
		}
		return "ok";
	}
	
	T popFront() throws DequeException {
		if(size == 0) throw new DequeException();
		T v = first.val;
		first = first.next;
		size--;
		return v;
	}
	
	T popBack() throws DequeException {
		if(size == 0) throw new DequeException();
		T v = last.val;
		last = last.prev;
		size--;
		return v;
	}
	
	T front() throws DequeException {
		if(size == 0) throw new DequeException();
		return first.val;
	}
	
	T back() throws DequeException {
		if(size == 0) throw new DequeException();
		return last.val;
	}
	
	int getSize() {
		return size;
	}
	
	String clear() {
		size = 0;
		return "ok";
	}
	
	String ex() {
		return "bye";
	}
}

class Main
{
	public static void main (String[] args) {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		MyDeque<String> deque = new MyDeque<String>();
		String s, val;
		
		while(in.hasNext()) {
			s = in.next();
			if (s.equals("exit")) out.println(deque.ex());
			else if (s.equals("clear")) out.println(deque.clear());
			else if (s.equals("size")) out.println(deque.getSize());
			else if (s.equals("back")) {
				try {
					out.println(deque.back());
				} catch(DequeException e) {
					out.println("error");
				}
			}
			else if(s.equals("front")) {
				try {
					out.println(deque.front());
				} catch(DequeException e) {
					out.println("error");
				}
			}
			else if (s.equals("pop_back")) {
				try {
					out.println(deque.popBack());
				} catch(DequeException e) {
					out.println("error");
				}
			}
			else if (s.equals("pop_front")) {
				try {
					out.println(deque.popFront());
				} catch(DequeException e) {
					out.println("error");
				}
			}
			else if(s.equals("push_back")) {
				val = in.next();
				out.println(deque.pushBack(val));
			}
			else if(s.equals("push_front")) {
				val = in.next();
				out.println(deque.pushFront(val));
			}
			out.flush();	
		}
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

import java.util.*;

import java.io.*;

class DequeException extends Exception {}

class Node <T>

{

T val;

Node prev, next;

Node(T v, Node p, Node n) {val = v; prev = p; next = n;}

}

class MyDeque <T>

{

int size;

Node<T> first, last;

MyDeque() {

size = 0;

first = null;

last = null;

}

String pushBack(T val) {

if (size > 0) {

Node currentNode = new Node<T> (val, last, null);

last.next = currentNode;

last = currentNode;

size++;

}

else {

Node currentNode = new Node<T> (val, null, null);

last = currentNode;

first = currentNode;

size++;

}

return "ok";

}

String pushFront(T val) {

if (size > 0) {

Node currentNode = new Node<T> (val, null, first);

first.prev = currentNode;

first = currentNode;

size++;

}

else {

Node currentNode = new Node<T> (val, null, null);

last = currentNode;

first = currentNode;

size++;

}

return "ok";

}

T popFront() throws DequeException {

if(size == 0) throw new DequeException();

T v = first.val;

first = first.next;

size--;

return v;

}

T popBack() throws DequeException {

if(size == 0) throw new DequeException();

T v = last.val;

last = last.prev;

size--;

return v;

}

T front() throws DequeException {

if(size == 0) throw new DequeException();

return first.val;

}

T back() throws DequeException {

if(size == 0) throw new DequeException();

return last.val;

}

int getSize() {

return size;

}

String clear() {

size = 0;

return "ok";

}

String ex() {

return "bye";

}

class Main

{

public static void main (String[] args) {

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

MyDeque<String> deque = new MyDeque<String>();

String s, val;

while(in.hasNext()) {

s = in.next();

if (s.equals("exit")) out.println(deque.ex());

else if (s.equals("clear")) out.println(deque.clear());

else if (s.equals("size")) out.println(deque.getSize());

else if (s.equals("back")) {

try {

out.println(deque.back());

} catch(DequeException e) {

out.println("error");

}

else if(s.equals("front")) {

try {

out.println(deque.front());

} catch(DequeException e) {

out.println("error");

}

else if (s.equals("pop_back")) {

try {

out.println(deque.popBack());

} catch(DequeException e) {

out.println("error");

}

else if (s.equals("pop_front")) {

try {

out.println(deque.popFront());

} catch(DequeException e) {

out.println("error");

}

else if(s.equals("push_back")) {

val = in.next();

out.println(deque.pushBack(val));

}

else if(s.equals("push_front")) {

val = in.next();

out.println(deque.pushFront(val));

}

out.flush();

}

Описание

Структура данных «дек» реализована в виде двусвязного списка. В классе MyDeque реализованы все требуемые методы. Те из них, после вызова которых, по условию, программа должна вывести некоторую строку, возвращают эту строку («ok» или «bye»). При попытке удалить или просмотреть элемент пустого дека создаётся и передаётся новый объект класса DequeException, наследующего класс Exception. В ходе работы функции main создаётся объект класса MyDeque, после чего читаются строки из входного потока и выполняются требуемые команды. В случае, если перехватывается исключение, выводится строка «error».

Код на ideone.com.

Засчитанное решение на e-olymp.com.

AL6

28/11/2017 by Валентин Лавриненко

Условие

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

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

$latex ({([])})$

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

Yes.

Код

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

class Ideone
{
	public static class stack
	{
		char arr[] = new char[10];
		int current;
		stack(){current = 0;};
		void push(char x)
		{
			arr[current] = x;
			current++;
		}
		void pop()
		{
			current--;
		}
		char back()
		{
			return arr[current-1];
		}
		int size()
		{
			return current;
		}
	};
	public static void main (String[] args) throws java.lang.Exception
	{
		String brace;
		Scanner input = new Scanner(System.in);
		brace = input.nextLine();
		stack x = new stack();
		char a = brace.charAt(0);
		if(a == '(' || a == '{' || a== '[') 
		{
			for(int i=0;i<brace.length();i++)
			{
				a = brace.charAt(i);
				if(a == '(' || a == '{' || a== '[')
					x.push(a);
				else if(Math.abs(a - x.back()) < 3 && x.size() != 0)
				{
            				x.pop();
				} else
				{
					System.out.println("No");
					System.exit(0);
				}
			}
			if(x.size() == 0)
			{
				System.out.println("Yes");
			} else System.out.println("No");
		}
		else 
		{
			System.out.println("No");
			System.exit(0);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static class stack

{

char arr[] = new char[10];

int current;

stack(){current = 0;};

void push(char x)

{

arr[current] = x;

current++;

}

void pop()

{

current--;

}

char back()

{

return arr[current-1];

}

int size()

{

return current;

}

};

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

{

String brace;

Scanner input = new Scanner(System.in);

brace = input.nextLine();

stack x = new stack();

char a = brace.charAt(0);

if(a == '(' || a == '{' || a== '[')

{

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

{

a = brace.charAt(i);

if(a == '(' || a == '{' || a== '[')

x.push(a);

else if(Math.abs(a - x.back()) < 3 && x.size() != 0)

{

x.pop();

} else

{

System.out.println("No");

System.exit(0);

}

if(x.size() == 0)

{

System.out.println("Yes");

} else System.out.println("No");

}

else

{

System.out.println("No");

System.exit(0);

}

Решение

Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать класс $latex stack$, в который поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.

Пример работы программы можно увидеть на сайте ideone.
Условие задачи.

e-olymp 2820. Перемещение коня

06/07/2017 by Присяжный Михаил

Постановка задачи

Ссылка на задачу с сайта e-olymp

Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из [latex]n[/latex] клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче.

Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.

Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток [latex]n[/latex] и [latex]b[/latex] в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из [latex]a[/latex] в [latex]b[/latex].

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

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква ([latex]a[/latex]—[latex]h[/latex]), задающая столбец и второй – цифра ([latex]1[/latex]—[latex]8[/latex]), задающая строку на шахматной доске.

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

Для каждого теста вывести одну строку следующего содержания: «Путь от xx к yy занимает n шагов»

Тест

Пример входных данных	Пример выходных данных
[latex]e2[/latex] [latex]e4[/latex]	Путь от [latex]e2[/latex] к [latex]e4[/latex] занимает [latex]2[/latex] шагов.
[latex]a1[/latex] [latex]b2[/latex]	Путь от [latex]a1[/latex] к [latex]b2[/latex] занимает [latex]4[/latex] шагов.
[latex]b2[/latex] [latex]c3[/latex]	Путь от [latex]b2[/latex] к [latex]c3[/latex] занимает [latex]2[/latex] шагов.
[latex]a1[/latex] [latex]h8[/latex]	Путь от [latex]a1[/latex] к [latex]h8[/latex] занимает [latex]6[/latex] шагов.
[latex]a1[/latex] [latex]h7[/latex]	Путь от [latex]a1[/latex] к [latex]h7[/latex] занимает [latex]5[/latex] шагов.
[latex]h8[/latex] [latex]a1[/latex]	Путь от [latex]h8[/latex] к [latex]a1[/latex] занимает [latex]6[/latex] шагов.
[latex]b1[/latex] [latex]c3[/latex]	Путь от [latex]b1[/latex] к [latex]c3[/latex] занимает [latex]1[/latex] шагов.
[latex]f6[/latex] f[latex]6[/latex]	Путь от [latex]f6[/latex] к [latex]f6[/latex] занимает [latex]0[/latex] шагов.

Решение

import java.util.*;
import java.lang.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Main {

    public static class Pair <T1, T2> {
        public T1 fst;
        public T2 snd;

        public Pair(T1 t1, T2 t2) {

            this.fst = t1;
            this.snd = t2;
        }
    }

    public static void main(String[] args) 
 {
        char a, b;
        int nx, ny, tx, ty;
        int mx[] = {-1, -1, 1, 1, -2, -2, 2, 2};
        int my[] = {2, -2, 2, -2, 1, -1, 1, -1};
        int A[][] = new int[8][8];
        Scanner s = new Scanner(System.in);
        String str;
        while (s.hasNextLine()) {
            String line = s.nextLine();
            Pattern p = Pattern.compile("^(.)(\\d) (.)(\\d)$");
            Matcher m = p.matcher(line);
            m.find();
            a = m.group(1).toCharArray()[0];
            ny = Integer.parseInt(m.group(2));
            b = m.group(3).toCharArray()[0];
            ty = Integer.parseInt(m.group(4));
            nx = a - 'a';
            ny--;
            tx = b - 'a';
            ty--;
            A[nx][ny] = 0;
            Queue<Pair<Integer, Integer>> q = new LinkedList<Pair<Integer, Integer>>();
            q.add(new Pair<Integer, Integer>(nx, ny));
            while (!q.isEmpty()) {
                Pair<Integer, Integer> c = q.peek();
                int x = c.fst, y = c.snd;
                if (x == tx && y == ty) break;
                q.remove();
                for (int i = 0; i < 8; i++) {
                    if (x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) {
                        q.add(new Pair<Integer, Integer>(x + mx[i], y + my[i]));
                        A[x + mx[i]][y + my[i]] = A[x][y] + 1;
                    }
                }
            }
            System.out.printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]);
        }
    }
}

import java.util.*;

import java.lang.*;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

class Main {

public static class Pair <T1, T2> {

public T1 fst;

public T2 snd;

public Pair(T1 t1, T2 t2) {

this.fst = t1;

this.snd = t2;

}

public static void main(String[] args)

{

char a, b;

int nx, ny, tx, ty;

int mx[] = {-1, -1, 1, 1, -2, -2, 2, 2};

int my[] = {2, -2, 2, -2, 1, -1, 1, -1};

int A[][] = new int[8][8];

Scanner s = new Scanner(System.in);

String str;

while (s.hasNextLine()) {

String line = s.nextLine();

Pattern p = Pattern.compile("^(.)(\\d) (.)(\\d)$");

Matcher m = p.matcher(line);

m.find();

a = m.group(1).toCharArray()[0];

ny = Integer.parseInt(m.group(2));

b = m.group(3).toCharArray()[0];

ty = Integer.parseInt(m.group(4));

nx = a - 'a';

ny--;

tx = b - 'a';

ty--;

A[nx][ny] = 0;

Queue<Pair<Integer, Integer>> q = new LinkedList<Pair<Integer, Integer>>();

q.add(new Pair<Integer, Integer>(nx, ny));

while (!q.isEmpty()) {

Pair<Integer, Integer> c = q.peek();

int x = c.fst, y = c.snd;

if (x == tx && y == ty) break;

q.remove();

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

if (x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) {

q.add(new Pair<Integer, Integer>(x + mx[i], y + my[i]));

A[x + mx[i]][y + my[i]] = A[x][y] + 1;

}

System.out.printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]);

}

Ссылка на решение задания с сайта e-olymp

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Для начала объявим переменные aи b типа char, где a и b — это координаты двух клеток. В цикле при помощи форматированного ввода по шаблону вводим 4 переменных, в которых a, ny — координата одной клетки и b, ty — координата другой клетки. nx — цифровая координата, которую мы получаем из буквы, отнимая от a. Создаем очередь, добавляем начальную клетку и ищем все возможные ходы пока не попадем в нужную клетку. Чтобы получить длину пути, нужно хранить длины путей до данной клетки в матрице и обновлять ее, по ходу продвижения. Длина в начальной клетке — 0, а длина в каждой последующей — 1. На экран выводим количество шагов, которые необходимо сделать конем, чтобы попасть из одной клетки в другую.

e-olymp 6128. Простой дек

05/07/2017 by Хоба Юрий

Постановка задачи

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

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

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит [latex]100[/latex]. Все операции:

pop_front,

pop_back,

front,

back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает [latex]10000[/latex], если это не указано особо.

Также условие задачи можно посмотреть здесь.

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример выходных данных.

Тесты

№	Входные данные	Выходные данные
1	push_back 3 push_front 14 size clear push_front 1 back push_back 2 front pop_back size pop_front size exit	ok ok 2 ok ok 1 ok 1 2 1 1 0 bye
2	push_front 7 push_front 8 push_front 9 pop_back back push_front 11 size pop_back pop_back pop_back push_back 90 front exit	ok ok ok 7 8 ok 3 8 9 11 ok 90 bye
3	push_back -5 push_back -20 push_back 2 pop_front push_front 7 size clear pop_back push_front 11 size exit	ok ok ok -5 ok 3 ok -1 ok 1 bye

Посмотреть работу программы на примере первого теста можно на сайте ideone.

Решение

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

class Deque
{
	final int maxSize = 10000;
	int size; 
	public int head, end;
	int[] data;
	
	public Deque() 
	{
		data = new int[maxSize];
		head = 0;
		end = 0;
		size = 0;
	}
	
	public void push_front(int e)
	{
		if (size == maxSize)
		{
			System.out.println("Deque is full.");
			return;
		}
		else if (size==0)
		{
			end = head;
			data[head] = e;
			size++;
		}
		else
		{
			head++;
			if (head>=maxSize)
				head = 0;
			data[head] = e;
			size++;
		}
		System.out.println("ok");
	}
	
	public void push_back(int e)
	{
		if (size == maxSize)
		{
			System.out.println("Deque is full.");
			return;
		}
		else if (size==0)
		{
			head = end;
			data[end] = e;
			size++;
		}
		else
		{
			end--;
			if (end<0)
				end = maxSize-1;
			data[end] = e;
			size++;
		}
		System.out.println("ok");
	}
	
	public void clear()
	{
		head = 0;
		end = 0;
		size = 0;
		System.out.println("ok");
	}
	
	public int size()
	{
		return size;
	}
	
	public int back()
	{
		if (size!=0)
			return data[end];
		else 
			return -1;
	}
	
	public int front()
	{
		if (size!=0)
			return data[head];
		else 
			return -1;
	}
	
	public int pop_back()
	{
		if (size!=0)
		{	
			int tmp = data[end];
			end++;
			if (end>=maxSize)
				end = 0;
			size --;
			return tmp;
		}
		else 
			return -1;
	}
	
	public int pop_front()
	{
		if (size!=0)
		{	
			int tmp = data[head];
			head--;
			if (head<0)
				head = maxSize - 1;
			size --;
			return tmp;
		}
		else 
			return -1;
	}
}

public class task
{
	static public void main (String[] args) throws IOException
	{
		Deque dq = new Deque();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;
		
		while((str = br.readLine()) != null)
		{
			String[] inp = str.split(" ");
			if (inp[0].equals("push_front"))
			{
				dq.push_front(Integer.parseInt(inp[1]));
			}
			else if (inp[0].equals("push_back"))
			{
				dq.push_back(Integer.parseInt(inp[1]));
			}
			else if (inp[0].equals("pop_back"))
			{
				System.out.println(dq.pop_back());
			}
			else if (inp[0].equals("pop_front"))
			{
				System.out.println(dq.pop_front());
			}
			else if (inp[0].equals("front"))
			{
				System.out.println(dq.front());
			}
			else if (inp[0].equals("back"))
			{
				System.out.println(dq.back());
			}
			else if (inp[0].equals("size"))
			{
				System.out.println(dq.size());
			}
			else if (inp[0].equals("clear"))
			{
				dq.clear();
			}
			else if (inp[0].equals("exit"))
			{
				System.out.println("bye");
				br.close();
				return;
			}
		}
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

class Deque

{

final int maxSize = 10000;

int size;

public int head, end;

int[] data;

public Deque()

{

data = new int[maxSize];

head = 0;

end = 0;

size = 0;

}

public void push_front(int e)

{

if (size == maxSize)

{

System.out.println("Deque is full.");

return;

}

else if (size==0)

{

end = head;

data[head] = e;

size++;

}

else

{

head++;

if (head>=maxSize)

head = 0;

data[head] = e;

size++;

}

System.out.println("ok");

}

public void push_back(int e)

{

if (size == maxSize)

{

System.out.println("Deque is full.");

return;

}

else if (size==0)

{

head = end;

data[end] = e;

size++;

}

else

{

end--;

if (end<0)

end = maxSize-1;

data[end] = e;

size++;

}

System.out.println("ok");

}

public void clear()

{

head = 0;

end = 0;

size = 0;

System.out.println("ok");

}

public int size()

{

return size;

}

public int back()

{

if (size!=0)

return data[end];

else

return -1;

}

public int front()

{

if (size!=0)

return data[head];

else

return -1;

}

public int pop_back()

{

if (size!=0)

{

int tmp = data[end];

end++;

if (end>=maxSize)

end = 0;

size --;

return tmp;

}

else

return -1;

}

public int pop_front()

{

if (size!=0)

{

int tmp = data[head];

head--;

if (head<0)

head = maxSize - 1;

size --;

return tmp;

}

else

return -1;

}

public class task

{

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

{

Deque dq = new Deque();

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

String str;

while((str = br.readLine()) != null)

{

String[] inp = str.split(" ");

if (inp[0].equals("push_front"))

{

dq.push_front(Integer.parseInt(inp[1]));

}

else if (inp[0].equals("push_back"))

{

dq.push_back(Integer.parseInt(inp[1]));

}

else if (inp[0].equals("pop_back"))

{

System.out.println(dq.pop_back());

}

else if (inp[0].equals("pop_front"))

{

System.out.println(dq.pop_front());

}

else if (inp[0].equals("front"))

{

System.out.println(dq.front());

}

else if (inp[0].equals("back"))

{

System.out.println(dq.back());

}

else if (inp[0].equals("size"))

{

System.out.println(dq.size());

}

else if (inp[0].equals("clear"))

{

dq.clear();

}

else if (inp[0].equals("exit"))

{

System.out.println("bye");

br.close();

return;

}

Описание решения

Чтобы смоделировать работу дека, напишем соответствующий класс class Deque, который будет содержать следующие поля:

int[] data — массив для хранения данных внутри дека;
static final int maxSize = 10000 — статическое неизменное поле, содержащее максимальное количество элементов в деке (по условию задачи 10000);
int size — текущее количество элементов в деке;
int head, end — индексы первого (верхнего) и последнего (нижнего) элементов дека в массиве int[] data.

Так как дек — это структура, в которой элементы можно добавлять и удалять как в начало, так и в конец, то индексы первого и последнего элементов в массиве будут постоянно изменяться при добавлении/удалении в дек объектов. Поэтому крайне важно организовать модель так, чтобы при произвольном добавлении в начало и конец дека новых элементов, массив содержал эти элементы в правильном порядке, а в программе не возникало ошибки выхода за границы массива.

Это сделано следующим образом: изначально индексы первого и последнего элементов массива data равны 0, как и размер массива (это описывается в конструкторе класса Deque). При добавлении в начало дека нового элемента, индекс первого элемента int head будет смещаться на 1 вперед, пока не достигнет верхней границы массива (9999), затем начнет свой отсчет опять с нуля. При добавлении нового элемента в конец дека, смещаться будет индекс последнего элемента, причем вниз, пока не достигнет 0, затем продолжит с верхней границы массива. Такой подход дает возможность непрерывно добавлять и удалять в дек элементы, однако если количество элементов в деке станет максимальным ( if (size == maxSize)), добавить новый элемент уже не получится, для него нужно освободить место.

При запуске программы, сперва создается объект класса Deque dq = new Deque(), затем программа принимает входные данные while((str = br.readLine()) != null) и вызывает соответствующий метод класса Deque.

Описание методов класса:

push_front и push_back — добавление в дек нового элемента. Если текущее количество элементов в деке равен максимально допустимому количеству элементов, добавления происходить не будет, а программа выдаст предупреждающее сообщение. Если дек не пустой, количество элементов увеличится на 1, а сам элемент будет размещен в массиве с соответствующим индексом head или end (в зависимости от того, куда добавляется элемент, в верх или в низ). Этот индекс, соответственно, увеличится или уменьшится на 1. Если количество элементов в деке равно 0, вставка произойдет точно так же, однако индексы head и end останутся прежними, указывая таким образом на один и тот же элемент. После успешной вставки на экран будет выведено сообщение «ok».
pop_front и pop_back — если в деке есть хотя бы 1 элемент, функция возвратит из массива data элемент с индексом head или end (соответственно для каждого метода), при этом этот индекс «двигается» в обратную для себя сторону (индекс верхнего элемента уменьшается, индекс нижнего — увеличивается), а количество элементов в деке уменьшается на 1. Если же дек пуст, функция вернет значение -1.
back и front — методы, аналогичные pop_front и pop_back, с тем отличием, что не будут изменять индексы head и end или количество элементов в деке, а просто возвратят нужные элементы.
size — возвращает количество элементов в деке ( return size;).
clear — приравнивает поля size, head и end к 0, имитируя удаление из дека всех элементов. Выводит на экран сообщение «ok».
exit — выводит на экран сообщение «bye», после чего программа завершит работу.

Посмотреть решение задания можно на сайте e-olymp.

Задача

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

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

Тесты

№

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

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

Решение

Ссылки

Задача

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

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

Тесты

Код задачи

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

Ссылки

Условие

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

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

Тесты

Код решения

Решение

Ссылки

Задача

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

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

Тесты

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

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

Примечание

Ссылки

Задание

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

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

Тесты

Код

Решение

Ссылки

Условие

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

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

Код

Решение

Постановка задачи

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

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

Тесты

Решение

Описание решения