e-olymp 971. Задача Иосифа Флавия

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

Задача

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

В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от $1$ до $N$, и будем исключать каждого $k$-ого до тех пор, пока не уцелеет только один человек. (Например, если $N=10$, $k=3$, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним — 5-й, и потом 10-й. Таким образом, уцелеет 4-й.)

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

Во входном файле даны натуральные числа $N$ и $k$. $1 ≤ N ≤ 500, 1 ≤ k ≤ 100$.

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

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

Тесты

Входные данные	Выходные данные
10 3	4
17 5	11
76 32	58

Код решения

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 n = in.nextInt(), k = in.nextInt();
		ArrayList<Integer> ns = new ArrayList<Integer>(n);
		for (int i = 1; i <= n; i++) 
			ns.add(i);
		
		int i = 0, j = 0;
		while(n > 1) {
			j = (++j) % k;
			if(j == 0) {
				n--;
				ns.remove(i);
			} else {
				i = (++i) % n;
			}
		}
		System.out.println(ns.get(0));
	}
}

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 n = in.nextInt(), k = in.nextInt();

ArrayList<Integer> ns = new ArrayList<Integer>(n);

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

ns.add(i);

int i = 0, j = 0;

while(n > 1) {

j = (++j) % k;

if(j == 0) {

n--;

ns.remove(i);

} else {

i = (++i) % n;

}

System.out.println(ns.get(0));

}

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

Все делается по алгоритму: убирается каждый $k$-тый человек до тех пор, пока не останется один.

Ссылки

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

e-olymp 1477. Наибольшее среднее

27/12/2018 by Андрей Лисовой

Задача

На доске выписаны $n$ целых чисел. Все они пронумерованы от $1$ до $n$. Разрешается выбрать два произвольных числа, вытереть оба с доски и написать новое число, равное их среднему арифметическому. Новое число получает номер $n + 1$. После этого снова выбираются два числа и вместо них записывается их среднее арифметическое, которому дается номер $n + 2$ и т.д. Так продолжается до тех пор, пока на доске не останется только одно число. Чем больше будет это число, тем более успешной считается последовательность действий.

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

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

В первой строке записано целое число $n$ $(1 \leq n \leq 10^5)$. Во второй строке задаются $n$ целых чисел, которые были первоначально записаны на доске. Все числа лежат в диапазоне от $-10000$ до $10000$.

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

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

Тесты

Входные данные	Выходные данные
$3$ $7$ $2$ $4$	$2$ $3$ $1$ $4$
$4$ $6$ $2$ $7$ $1$	$2$ $4$ $1$ $5$ $3$ $6$
$4$ $12$ $4$ $7$ $2$	$2$ $4$ $3$ $5$ $1$ $6$
$5$ $234$ $2$ $5$ $54$ $5$	$2$ $3$ $5$ $6$ $4$ $7$ $1$ $8$

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

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);
		TreeMap<Double, String> map = new TreeMap<>();
		int n = in.nextInt();
		for(int i = 1; i <= n; i++) {
			double item = in.nextDouble();
			if(map.get(item) == null) map.put(item, Integer.toString(i));
			else {
				String str = map.get(item);
				str += Integer.toString(i);
				map.put(item, str);
			}
		}
		while(map.size() != 1) {
			double x = map.firstKey();
			String strX = map.get(x);
			char numx = '0';
			if(strX.length() == 1) {
				map.remove(x);
				numx = strX.charAt(0);
			}
			else {
				numx = strX.charAt(0);
				map.put(x, strX.substring(1));
			}
			double y = map.firstKey();
			String strY = map.get(y);
			char numy = '0';
			if(strY.length() == 1) {
				map.remove(y);
				numy = strY.charAt(0);
			}
			else {
				numy = strY.charAt(0);
				map.put(y, strY.substring(1));
			}
			int numXInt = Character.getNumericValue(numx);
			int numYInt = Character.getNumericValue(numy);
			System.out.println(Math.min(numXInt, numYInt) + " " + Math.max(numXInt, numYInt));
			double newKey = (x + y) / 2;
			if(map.get(newKey) == null) map.put(newKey, Integer.toString(++n));
			else {
				String str = map.get(newKey);
				str += Integer.toString(++n);
				map.put(newKey, str);
			}
		}
	}
}

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

TreeMap<Double, String> map = new TreeMap<>();

int n = in.nextInt();

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

double item = in.nextDouble();

if(map.get(item) == null) map.put(item, Integer.toString(i));

else {

String str = map.get(item);

str += Integer.toString(i);

map.put(item, str);

}

while(map.size() != 1) {

double x = map.firstKey();

String strX = map.get(x);

char numx = '0';

if(strX.length() == 1) {

map.remove(x);

numx = strX.charAt(0);

}

else {

numx = strX.charAt(0);

map.put(x, strX.substring(1));

}

double y = map.firstKey();

String strY = map.get(y);

char numy = '0';

if(strY.length() == 1) {

map.remove(y);

numy = strY.charAt(0);

}

else {

numy = strY.charAt(0);

map.put(y, strY.substring(1));

}

int numXInt = Character.getNumericValue(numx);

int numYInt = Character.getNumericValue(numy);

System.out.println(Math.min(numXInt, numYInt) + " " + Math.max(numXInt, numYInt));

double newKey = (x + y) / 2;

if(map.get(newKey) == null) map.put(newKey, Integer.toString(++n));

else {

String str = map.get(newKey);

str += Integer.toString(++n);

map.put(newKey, str);

}

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

Для решения задачи необходимо использовать multimap, которого не в языке программирования Java. Для решения данной задачи числа на доске будут ключами, а их номера будем записывать в строку. Для задания такого «multimap» будем считывать с входного потока числа и смотреть есть ли в нашей карте такой ключ, если есть, то к строке добавляем ещё символ справа, если нет, то за в строку вставляем номер числа. Затем в цикле, пока не один элемент в «multimap» будем выбирать первые два элемента. Для выбираем первый ключ с помощью функции map.firstKey(), находим значение по ключу, проверяем длину полученной строки, если она равна $1$, то запоминаем символ строки и удаляем элемент с «multimap», иначе запоминаем первый символ строки и удаляем его из строки, записывая в «multimap» элемент с измененной строкой. Аналогично получаем следующее значение. Переводим символы в числа и выводим их номера элементов, которые были изъяты из «multimap» и находим среднее число. Добавляем в «multimap» пару, где первое значение — это найденное средние двух чисел, а второе — номер(добавление данного элемента осуществляется аналогично заполнению, т.е. если ключ уже есть в «multimap», то добавляем к значению справа номер). В конце концов мы получим, что в «multimap» будет всего одна пара и цикл остановит свою работу. Задача решена. Однако она не проходит по времени.

Ссылки

Условие задачи на e-olymp
Код решения на 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

Сумма делителей

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

Данная задача является упрощенным вариантом задания олимпиады KPI-OPEN 2018.

Задача

Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу:
Найти сумму делителей данного числа $n.$
Костя обратился к Вам как к опытному программисту, который знает алгебру, с просьбой о помощи решить данную задачу.

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

Одно целое число $n \left(1 \leqslant n < 10^{10}\right).$

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

Выведите сумму делителей числа $n.$

Тесты

Входные данные	Выходные данные
$12$	$28$
$239$	$240$
$1234$	$1854$
$6$	$12$
$1000000007$	$1000000008$
$44100$	$160797$
$223092870$	$836075520$
$2147483648$	$4294967295$
$678906$	$1471002$
$1111111$	$1116000$
$9876543210$	$27278469036$
$99460729$	$99470703$
$5988$	$14000$
$1$	$1$
$1348781387$	$1617960960$
$135792$	$406224$
$5402250$	$17041284$
$375844500$	$1259767236$
$1000000000$	$2497558338$
$2357947691$	$2593742460$

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long sumOfDivisors = 1;
		Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        HashMap<Long, Long> primeDivInPow = new HashMap<>();
        for(long i = 2; i * i <= n; i++){
	        while(n % i == 0){
	            if(primeDivInPow.containsKey(i) == false){
	                primeDivInPow.put(i, (long) 1);
	            }
	            primeDivInPow.put(i, primeDivInPow.get(i) * i);
	            n /= i;
	        }
        }
        if(n != 1){
        	primeDivInPow.put(n, n);
		}
		for (Map.Entry<Long, Long> entry : primeDivInPow.entrySet()) {
			 sumOfDivisors *= (entry.getValue() * entry.getKey() - 1) / (entry.getKey() - 1);
		}
		System.out.println(sumOfDivisors);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

long sumOfDivisors = 1;

Scanner in = new Scanner(System.in);

long n = in.nextLong();

HashMap<Long, Long> primeDivInPow = new HashMap<>();

for(long i = 2; i * i <= n; i++){

while(n % i == 0){

if(primeDivInPow.containsKey(i) == false){

primeDivInPow.put(i, (long) 1);

}

primeDivInPow.put(i, primeDivInPow.get(i) * i);

n /= i;

}

if(n != 1){

primeDivInPow.put(n, n);

}

for (Map.Entry<Long, Long> entry : primeDivInPow.entrySet()) {

sumOfDivisors *= (entry.getValue() * entry.getKey() - 1) / (entry.getKey() - 1);

}

System.out.println(sumOfDivisors);

}

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

Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$

Ссылки

Код решения

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

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

Задача

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

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

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

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

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

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

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

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

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

Тесты

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

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

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

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

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Map;

import java.util.Scanner;

import java.util.TreeMap;

public class Main {

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

Scanner sc = new Scanner(System.in);

int m = sc.nextInt();

int n = sc.nextInt();

int[] nums = new int[m];

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

nums[i] = sc.nextInt();

}

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

blackBox.put(Integer.MAX_VALUE, 1);

int size = 1;

int curKey = Integer.MAX_VALUE;

int curValue = 1;

int curPosition = 0;

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

int req = sc.nextInt();

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

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

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

if (curKey == nums[j]) {

curValue++;

}

else {

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

}

if(nums[j] < curKey) {

if (curPosition == 0) {

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

curKey = curEnrty.getKey();

curValue = curEnrty.getValue();

curPosition = curValue - 1;

}

else {

curPosition--;

}

size = req + 1;

System.out.println(curKey);

if (curPosition == curValue - 1) {

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

curKey = curEnrty.getKey();

curValue = curEnrty.getValue();

curPosition = 0;

}

else {

curPosition++;

}

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

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

Ссылки

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

e-olymp 161. Роботы

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

Задача

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

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

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

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

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

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

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

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

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

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

Тесты

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

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

import java.util.*;

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

import java.util.*;

public class Main {

private static class Pair{

int a, b;

public Pair(int a, int b) {

this.a=a;

this.b=b;

}

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int na = scanner.nextInt();

int[] A = new int[na];

int[] times = new int[n];

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

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

A[i] = scanner.nextInt();

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

}

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

Pair pair=q.poll();

times[i]=pair.a;

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

}

q.clear();

int nb = scanner.nextInt();

int[] B = new int[nb];

int max_time=0;

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

B[i] = scanner.nextInt();

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

}

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

Pair pair=q.poll();

times[i]+=pair.a;

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

if(times[i]>max_time)

max_time=times[i];

}

System.out.println(max_time);

}

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

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

Ссылки

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

Шифровка

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

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

Взята с сайта.
Мюллер много раз пытался поймать Штирлица с поличным, но тот всё время выкручивался. Как-то раз Штирлиц просматривал электронную почту. В это время незаметно вошел Мюллер и увидел, как у него на экране появился бессмысленный набор символов. «Шифровка», — подумал Мюллер. «UTF-8», — подумал Штирлиц.
Известно, что Штирлиц шифрует текст следующим образом:

1)Убирает все пробелы и знаки препинания.
2)Заменяет все подряд идущие одинаковые буквы на одну такую букву.
3)Многократно вставляет в произвольное место текста две одинаковых буквы.

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

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

aaxxHuuuuelllnnloxxvvoo!

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

Hello!

Решение с использованием функционала класса String

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		ArrayList arr = new ArrayList();
		String str,str2;
		String empty = "";
		Scanner input = new Scanner(System.in);
		str = input.nextLine();
		for(int i = 0;i < str.length(); i++)
		{
			str2 = empty;
			str2 += str.charAt(i);
			if(i == str.length()-1)
				arr.add(str2);
			else
			{
				if(str.charAt(i) == str.charAt(i+1))
					i++;
				else arr.add(str2);
			}
		}
		for(int i = 0;i < arr.size();i++)
		{
			System.out.print(arr.get(i));
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

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

class Ideone

{

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

{

ArrayList arr = new ArrayList();

String str,str2;

String empty = "";

Scanner input = new Scanner(System.in);

str = input.nextLine();

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

{

str2 = empty;

str2 += str.charAt(i);

if(i == str.length()-1)

arr.add(str2);

else

{

if(str.charAt(i) == str.charAt(i+1))

i++;

else arr.add(str2);

}

for(int i = 0;i < arr.size();i++)

{

System.out.print(arr.get(i));

}

Решение с использованием функционала структуры данных ArrayList

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		ArrayList arr = new ArrayList();
		Scanner input = new Scanner(System.in);
		String str,str2;
		String empty = "";
		str = input.nextLine();
		for(int i = 0;i<str.length();i++)
		{
			str2 = empty;
			str2 += str.charAt(i);
			arr.add(str2);
		}
		for(int i = 0;i < arr.size(); i++)
		{
			if(i != arr.size()-1)
			{
				if(arr.get(i).equals(arr.get(i+1)))
				{
					arr.remove(i);
					arr.remove(i);
					i--;
				}
			}
		}
		for(int i = 0;i < arr.size();i++)
		{
			System.out.print(arr.get(i));
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

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

class Ideone

{

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

{

ArrayList arr = new ArrayList();

Scanner input = new Scanner(System.in);

String str,str2;

String empty = "";

str = input.nextLine();

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

{

str2 = empty;

str2 += str.charAt(i);

arr.add(str2);

}

for(int i = 0;i < arr.size(); i++)

{

if(i != arr.size()-1)

{

if(arr.get(i).equals(arr.get(i+1)))

{

arr.remove(i);

i--;

}

for(int i = 0;i < arr.size();i++)

{

System.out.print(arr.get(i));

}

Решение

Записываем строку в переменную типа $latex String$. Записываем ее в $latex ArrayList$ посимвольно. В следующем цикле добавляем проверку на индекс текущего элемента чтобы не выйти за пределы списка и проверяем совпадают ли ближайшие 2 символа, если да то удаляем их, если нет то переходим к следующему шагу цикла. По его окончанию выводим элементы списка.
Пример решения со строками на ideone.
Пример решения с списком на ideone.

A301. Количество точек в полукругах

13/11/2017 by Вадим Гордийчук

Задача

Даны действительные числа [latex]x_1, y_1[/latex], [latex]x_2, y_2[/latex], [latex]\ldots[/latex], [latex]x_{20}, y_{20}[/latex], [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex], [latex]\left( 0 < r_1 < r_2 < \ldots < r_{11} \right)[/latex]. Пары [latex]\left( x_1, y_1 \right)[/latex], [latex]\left( x_2, y_2 \right)[/latex], [latex]\ldots[/latex] [latex]\left( x_{20}, y_{20} \right)[/latex] рассматриваются как координаты точек плоскости. Числа [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex] рассматриваются как радиусы одиннадцати полукругов в полуплоскости [latex]y > 0[/latex] с центром в начале координат. Найти количество точек, попадающих внутрь каждого полукруга (границы-полуокружности не принадлежат полукругам).

Примечание: будем рассматривать задачу с произвольным количеством точек [latex]n[/latex] и полуокружностей [latex]m[/latex].

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

[latex]n[/latex], [latex]m[/latex], [latex]x_i, y_i[/latex], [latex]i = \overline{1, n}[/latex], [latex]r_j[/latex], [latex]j = \overline{1, m}[/latex]

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

[latex]a_j[/latex] — количество точек в [latex]j[/latex]-том полукруге, [latex]j = \overline{1, m}[/latex].

Тест

Входные данные	Выходные данные
20 11 14 4 5 -4 4 90 2 4.91 8 9.0 8.3 4.111 20 49.0 0 301.419 8.01 34.5 2.1 -49.1 0.01 0.03 56 1.91 4.04918 34.49294 -1.85892 5.01674 51 214 14.94 44.09 41.4 -154 -581.49 495 14.39 -81.682 77 194.4 0.3 20.82 50.9 51 65.845 90.37 109.58 170.83 217 301.58901 314	1 6 9 9 11 12 12 12 13 15 15

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

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

20 11

14 4
5 -4
4 90
2 4.91
8 9.0
8.3 4.111
20 49.0
0 301.419
8.01 34.5
2.1 -49.1
0.01 0.03
56 1.91
4.04918 34.49294
-1.85892 5.01674
51 214
14.94 44.09
41.4 -154
-581.49 495
14.39 -81.682
77 194.4
0.3
20.82
50.9
51
65.845
90.37
109.58
170.83
217
301.58901
314

1
6
9
9
11
12
12
12
13
15
15

Иллюстрация к тесту:

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

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

class Dot
{
	public double x, y;

	public Dot() {}

	public Dot(double x, double y)
	{
		this.x = x;
		this.y = y;
	}
}

public class Main
{
	public static double euclidianDistanceToZero(Dot a)
	{
		return Math.sqrt(a.x*a.x+a.y*a.y);
	}

	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n_dot = in.nextInt();
		int n_circ = in.nextInt();

		Vector <Dot> dots = new Vector<Dot>();

		for(int i = 0; i < n_dot; ++i)
		{
			Dot a = new Dot(in.nextDouble(), in.nextDouble());
			if (a.y > 0)
				dots.addElement(a);
		}

		double rads[] = new double[n_circ];
		int amounts[] = new int[n_circ];

		for(int i = 0; i < n_circ; ++i)
		{
			rads[i] = in.nextDouble();
			amounts[i] = 0;
		}

		if (n_circ == 1)
		{
			for(int i = 0; i < dots.size(); ++i)
				if (euclidianDistanceToZero(dots.elementAt(i)) < rads[0])
					++amounts[0];
		}
		else
			for(int i = 0; i < dots.size(); ++i)
			{
				int j = n_circ;
				double r = euclidianDistanceToZero(dots.elementAt(i));
	
				if (r < rads[n_circ-1]) // if dot belongs to one of the semicircles
				{
					if (r < rads[0]) // if dot belongs to the first semicircle
						j = 0;
					else if (rads[n_circ-2] <= r) // if dot belongs to the last semicircle
						j = n_circ-1;
					else // binary search of the smallest semicircle, which includes dot
					{
						int prev_l = 0, prev_r = n_circ, k;

						while(j == n_circ)
						{
							k = (prev_l+prev_r)/2;

							if (rads[k-1] <= r && r < rads[k])
								j = k;
							else if (r >= rads[k])
								prev_l = (prev_l+k)/2;
							else //if (r < rads[k-1])
								prev_r = (prev_r+k)/2;
						}
					}

					++amounts[j]; //increasing amount of dots, which belong to [j, n_circ-1] circles.
				}
			}

		for(int accumulated_amount = 0, i = 0; i < n_circ; ++i)
		{
			accumulated_amount += amounts[i];
			amounts[i] = accumulated_amount;
		}

		for(int i = 0; i < n_circ; ++i)
			out.println(String.valueOf(amounts[i]));
		out.flush();
	}
}

100

import java.util.*;

import java.lang.*;

import java.io.*;

class Dot

{

public double x, y;

public Dot() {}

public Dot(double x, double y)

{

this.x = x;

this.y = y;

}

public class Main

{

public static double euclidianDistanceToZero(Dot a)

{

return Math.sqrt(a.x*a.x+a.y*a.y);

}

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

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n_dot = in.nextInt();

int n_circ = in.nextInt();

Vector <Dot> dots = new Vector<Dot>();

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

{

Dot a = new Dot(in.nextDouble(), in.nextDouble());

if (a.y > 0)

dots.addElement(a);

}

double rads[] = new double[n_circ];

int amounts[] = new int[n_circ];

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

{

rads[i] = in.nextDouble();

amounts[i] = 0;

}

if (n_circ == 1)

{

for(int i = 0; i < dots.size(); ++i)

if (euclidianDistanceToZero(dots.elementAt(i)) < rads[0])

++amounts[0];

}

else

for(int i = 0; i < dots.size(); ++i)

{

int j = n_circ;

double r = euclidianDistanceToZero(dots.elementAt(i));

if (r < rads[n_circ-1]) // if dot belongs to one of the semicircles

{

if (r < rads[0]) // if dot belongs to the first semicircle

j = 0;

else if (rads[n_circ-2] <= r) // if dot belongs to the last semicircle

j = n_circ-1;

else // binary search of the smallest semicircle, which includes dot

{

int prev_l = 0, prev_r = n_circ, k;

while(j == n_circ)

{

k = (prev_l+prev_r)/2;

if (rads[k-1] <= r && r < rads[k])

j = k;

else if (r >= rads[k])

prev_l = (prev_l+k)/2;

else //if (r < rads[k-1])

prev_r = (prev_r+k)/2;

}

++amounts[j]; //increasing amount of dots, which belong to [j, n_circ-1] circles.

}

for(int accumulated_amount = 0, i = 0; i < n_circ; ++i)

{

accumulated_amount += amounts[i];

amounts[i] = accumulated_amount;

}

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

out.println(String.valueOf(amounts[i]));

out.flush();

}

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

Из входного потока считываем координаты всех точек, и отсеиваем из них те, у которых координата [latex]y \le 0[/latex], так как они по условию не могут принадлежать данным полуокружностям, остальные же добавляем в вектор точек dots. После этого, создаём два массива: первый rads — массив радиусов — считываем из входного потока, второй amounts — обнуляем. В i-ой ячейке массива amounts будем хранить количество точек, которые принадлежат [latex]i[/latex]-тому, и большим чем он полукругам. После этого, используя алгоритм бинарного поиска, находим наименьший полукруг, который содержит точку, и запоминаем его номер. Затем количество точек, содержащихся в данном и больших, чем данный полукругах, увеличиваем на единицу.

После обработки вектора точек, массив amounts преобразуем в массив количеств точек, содержащихся в конкретных полукругах, так как до этой обработки он содержит количество точек, которые «аккумулированы» i-тым, и большими чем i-тый полукруги.

Таким образом, общая асимптотика программы составит [latex]O \left(m+n \cdot \log_{2}{m}\right)[/latex], где [latex]n[/latex] — количество точек, а [latex]m[/latex] — полукругов.

Ссылки

Код на ideone.com;
Условие задачи, страница 126.

e-olymp 6127. The queue of unlimited size

31/08/2016 by Владислав Козачков

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

Условие

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

push n

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

pop

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

front

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

size

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

clear

Программа должна очистить очередь и вывести ok.

exit

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

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

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

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

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

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

Тесты:

№	Входные данные	Выходные данные:
1	push 1 front exit	ok 1 bye
2	size push 1 size push 2 size push 3 size exit	0 ok 1 ok 2 ok 3 bye

Код на Java:

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

class Main {
	public static class Node {
		public int value;
		public Node next;
		
		public Node() {
			value = 0;
			next = null;
		}
		public Node(int newValue, Node newNext) {
			value = newValue;
			next = newNext;
		}
	}
	
	public static class Queue {
		private int size;
		private Node first;
		private Node last;
		
		public Queue() {
			size = 0;
			first = null;
			last = null;
		}
		
		public void push(int v) {
			Node newNode = new Node(v, null);
			if (size == 0) {
				first = last = newNode;
			} else {
				last.next = newNode;
				last = newNode;
			}
			size++;
		}
		public boolean pop() {
			boolean ret = false;
			if (size > 0) {
				int val = first.value;
				first = first.next;
				size--;
				System.out.println(val);
				ret = true;
			}
			return ret;
		}
		public boolean front() {
			boolean ret = false;
			if (size > 0) {
				System.out.println(first.value);
				ret = true;
			}
			return ret;
		}
		public int getSize() {
			return size;
		}
		public void clear() {
			first = null;
			last = null;
			size = 0;
		}
	}
	public static void main(String[] args) {
		Queue q = new Queue();
		String s;
		int n;
		Scanner scan = new Scanner(System.in);
		while ((s = scan.next()) != null) {
			switch(s) {
				case "size": System.out.println(q.getSize()); break;
				case "push":
					n = scan.nextInt();
					q.push(n);
					System.out.println("ok");
					break;
				case "pop":
					if (q.pop() == false) {
						System.out.println("error");
					}
					break;
				case "front":
					if (q.front() == false) {
						System.out.println("error");
					}
					break;
				case "clear":
					q.clear();
					System.out.println("ok");
					break;
				case "exit":
					System.out.println("bye");
					return;
				default: break;
			}
		}
	}
}

100

101

102

103

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static class Node {

public int value;

public Node next;

public Node() {

value = 0;

next = null;

}

public Node(int newValue, Node newNext) {

value = newValue;

next = newNext;

}

public static class Queue {

private int size;

private Node first;

private Node last;

public Queue() {

size = 0;

first = null;

last = null;

}

public void push(int v) {

Node newNode = new Node(v, null);

if (size == 0) {

first = last = newNode;

} else {

last.next = newNode;

last = newNode;

}

size++;

}

public boolean pop() {

boolean ret = false;

if (size > 0) {

int val = first.value;

first = first.next;

size--;

System.out.println(val);

ret = true;

}

return ret;

}

public boolean front() {

boolean ret = false;

if (size > 0) {

System.out.println(first.value);

ret = true;

}

return ret;

}

public int getSize() {

return size;

}

public void clear() {

first = null;

last = null;

size = 0;

}

public static void main(String[] args) {

Queue q = new Queue();

String s;

int n;

Scanner scan = new Scanner(System.in);

while ((s = scan.next()) != null) {

switch(s) {

case "size": System.out.println(q.getSize()); break;

case "push":

n = scan.nextInt();

q.push(n);

System.out.println("ok");

break;

case "pop":

if (q.pop() == false) {

System.out.println("error");

}

break;

case "front":

if (q.front() == false) {

System.out.println("error");

}

break;

case "clear":

q.clear();

System.out.println("ok");

break;

case "exit":

System.out.println("bye");

return;

default: break;

}

Алгоритм:

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

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

e-olimp 6129. Дек неограниченного размера

28/08/2016 by Ирина Литвиненко

Задача:

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

push_front

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

push_back

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

pop_front

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

pop_back

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

front

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

back

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

size

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

clear

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

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

Тесты:

Последовательность

Результат

push_front
4
push_back
5
front
push_front
3
back
size
pop_front
pop_back
clear
pop_back
size
exit

4
ok

5
3
3
5
ok
error
0
bye

import java.util.Scanner;

public class Deque {

    private class Node {
        Node prev;
        Node next;
        int x;

        Node() {
            prev = null;
            next = null;
            x = 0;
        }
        Node(Node a, Node b, int c) {
            prev = a;
            next = b;
            x = c;
        }
    };

    Node Front = null;
    Node Back = null;
    int Size = 0;

    int size() {
        return Size;
    }

    void push_back(int p) {
        if (Size == 0) {
            Node NewNode = new Node(Back, Front, p);
            Front = NewNode;
            Back = NewNode;
        } else {
            Node NewNode = new Node(null, Back, p);
            Back.prev = NewNode;
            Back = NewNode;
        }
        Size++;
    }

    void push_front(int p) {
        if (Size == 0) {
            Node NewNode = new Node(Back, Front, p);
            Front = NewNode;
            Back = NewNode;
        } else {
            Node NewNode = new Node(Front, null, p);
            Front.next = NewNode;
            Front = NewNode;
        }
        Size++;
    }

    int back() {
        if (Size != 0) {
            return Back.x;
        } else {
            return 0;
        }
    }

    int front() {
        if (Size != 0) {
            return Front.x;
        } else {
            return 0;
        }
    }

    int pop_front() {
        if (Size != 0) {
            int x = Front.x;
            Node NewNode = Front.prev;
            Front = NewNode;
            Size--;
            return x;
        } else {
            return 0;
        }
    }

    int pop_back() {
        if (Size != 0) {
            int x = Back.x;
            Node NewNode = Back.next;
            Back = NewNode;
            Size--;
            return x;
        } else {
            return 0;
        }
    }

    void clear() {
        while (Size > 0) {
            Node NewNode = Front.prev;
            Front = NewNode;
            Size--;
        }
        Front = null;
        Back = null;
    }


    public static void main(String[] args) {
        Deque deque = new Deque();
        Scanner scanner = new Scanner(System.in);
        System.out.println("enter your command");
        String command = scanner.nextLine();

        while (!command.equals("exit")) {
            if (command.equals("push_back")) {
                int v = scanner.nextInt();
                deque.push_back(v);
                System.out.println("ok\n");
            } else if (command.equals("push_front")) {
                int v = scanner.nextInt();
                deque.push_front(v);
                System.out.println("ok\n");
            } else if (command.equals("front")) {
                if (deque.size() > 0) {
                    System.out.println(deque.front());
                } else {
                    System.out.println("error\n");
                }
            } else if (command.equals("back")) {
                if (deque.size() > 0) {
                    System.out.println(deque.back());
                } else {
                    System.out.println("error\n");
                }
            } else if (command.equals("size")) {
                System.out.println(deque.size());
            } else if (command.equals("pop_front")) {
                if (deque.size() > 0) {
                    System.out.println(deque.pop_front());
                } else {
                    System.out.println("error\n");
                }
            } else if (command.equals("pop_back")) {
                if (deque.size() > 0) {
                    System.out.println(deque.pop_back());
                } else {
                    System.out.println("error\n");
                }
            } else if (command.equals("clear")) {
                System.out.println("ok\n");
                deque.clear();
            }
            command = scanner.nextLine();
        }
        System.out.println("bye");
    }
};

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

import java.util.Scanner;

public class Deque {

private class Node {

Node prev;

Node next;

int x;

Node() {

prev = null;

next = null;

x = 0;

}

Node(Node a, Node b, int c) {

prev = a;

next = b;

x = c;

}

};

Node Front = null;

Node Back = null;

int Size = 0;

int size() {

return Size;

}

void push_back(int p) {

if (Size == 0) {

Node NewNode = new Node(Back, Front, p);

Front = NewNode;

Back = NewNode;

} else {

Node NewNode = new Node(null, Back, p);

Back.prev = NewNode;

Back = NewNode;

}

Size++;

}

void push_front(int p) {

if (Size == 0) {

Node NewNode = new Node(Back, Front, p);

Front = NewNode;

Back = NewNode;

} else {

Node NewNode = new Node(Front, null, p);

Front.next = NewNode;

Front = NewNode;

}

Size++;

}

int back() {

if (Size != 0) {

return Back.x;

} else {

return 0;

}

int front() {

if (Size != 0) {

return Front.x;

} else {

return 0;

}

int pop_front() {

if (Size != 0) {

int x = Front.x;

Node NewNode = Front.prev;

Front = NewNode;

Size--;

return x;

} else {

return 0;

}

int pop_back() {

if (Size != 0) {

int x = Back.x;

Node NewNode = Back.next;

Back = NewNode;

Size--;

return x;

} else {

return 0;

}

void clear() {

while (Size > 0) {

Node NewNode = Front.prev;

Front = NewNode;

Size--;

}

Front = null;

Back = null;

}

public static void main(String[] args) {

Deque deque = new Deque();

Scanner scanner = new Scanner(System.in);

System.out.println("enter your command");

String command = scanner.nextLine();

while (!command.equals("exit")) {

if (command.equals("push_back")) {

int v = scanner.nextInt();

deque.push_back(v);

System.out.println("ok\n");

} else if (command.equals("push_front")) {

int v = scanner.nextInt();

deque.push_front(v);

System.out.println("ok\n");

} else if (command.equals("front")) {

if (deque.size() > 0) {

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

} else {

System.out.println("error\n");

}

} else if (command.equals("back")) {

if (deque.size() > 0) {

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

} else {

System.out.println("error\n");

}

} else if (command.equals("size")) {

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

} else if (command.equals("pop_front")) {

if (deque.size() > 0) {

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

} else {

System.out.println("error\n");

}

} else if (command.equals("pop_back")) {

if (deque.size() > 0) {

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

} else {

System.out.println("error\n");

}

} else if (command.equals("clear")) {

System.out.println("ok\n");

deque.clear();

}

command = scanner.nextLine();

}

System.out.println("bye");

}

};

Решение

Решение на Ideone
Дек — (двухсторонняя очередь) — структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец, то есть дисциплинами обслуживания являются одновременно FIFO и LIFO. Для реализации дека неограниченного размера удобно использовать двусвязный список.