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.

e-olymp 1078. Степень строки

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

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

Обозначим через [latex]a\cdot b[/latex] конкатенацию строк [latex]a[/latex] и [latex]b[/latex].

Например, если [latex]a=[/latex] «abc» и [latex]b=[/latex] «def», то [latex]a\cdot b=[/latex] «abcdef».
Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:

[latex]a^{0}=[/latex] «» (пустая строка)
[latex]a^{n+1}=a\cdot a^{n}[/latex]

По заданной строке [latex]s[/latex] необходимо найти наибольшее значение [latex]n[/latex], для которого [latex]s=a^{n}[/latex] для некоторой строки [latex]a[/latex].

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

Каждый тест состоит из одной строки [latex]s[/latex], содержащей печатные (отображаемые) символы. Строка [latex]s[/latex] содержит не менее одного и не более миллиона символов.

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

Для каждой входной строки [latex]s[/latex] вывести в отдельной строке наибольшее значение [latex]n[/latex], для которого [latex]s=a^{n}[/latex] для некоторой строки [latex]a[/latex].

Тесты

№	Входные данные	Выходные данные
1	abcabcabc	3
2	aaaaaaaaaa	10
3	ollollo	1
4	pjpjpjpj	4

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

Решение

import java.util.*;

class task6 
{
	static public int StringPow(final String str)
	{
		int size = str.length();
		int pow = 1;
		for (int i=1; i<=size/2; i++)
		{
			if (size % i != 0)
				continue;
			String sub1 = new String(str.substring(0, i));
			boolean found = true;
			for (int j = i; j < size; j+=i)
			{
				String sub2 = new String(str.substring(j, j+i));
				if (!sub1.equals(sub2))
				{
					found = false;
					break;
				}
			}
			if (found)
			{
				pow = (size/i);
				break;
			}
		}
		return pow;
	}
	
	static public void main (String[] argv)
	{
		String str;
		Scanner in = new Scanner(System.in);
		while (in.hasNext())
		{
			str = in.nextLine();
			System.out.println(StringPow(str));
		}
		in.close();
	}
}

import java.util.*;

class task6

{

static public int StringPow(final String str)

{

int size = str.length();

int pow = 1;

for (int i=1; i<=size/2; i++)

{

if (size % i != 0)

continue;

String sub1 = new String(str.substring(0, i));

boolean found = true;

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

{

String sub2 = new String(str.substring(j, j+i));

if (!sub1.equals(sub2))

{

found = false;

break;

}

if (found)

{

pow = (size/i);

break;

}

return pow;

}

static public void main (String[] argv)

{

String str;

Scanner in = new Scanner(System.in);

while (in.hasNext())

{

str = in.nextLine();

System.out.println(StringPow(str));

}

in.close();

}

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

Получая строку str из потока ввода, вызываем функцию static public int StringPow(final String str) и передаем полученную строку в качестве входного параметра. Функция StringPow возвращает значение типа int — наибольшую степень строки, которую программа и передаст в поток вывода в качестве выходных данных.

Минимальной степенью строки может быть число [latex]1[/latex] — в том случае, если в заданной строке [latex]s[/latex] нет повторяющихся подстрок. Максимальной же степенью строки может быть количество символов, из которых строка состоит — в том случае, если строка состоит из одного повторяющегося символа. В этом случае этот символ и будет считаться повторяющейся подстрокой.

Получив в качестве входного аргумента строку str, предположим внутри тела функции StringPow, что степень данной строки равна [latex]1[/latex] ( int pow = 1;) на тот случай, если бо́льшую степень найти не удастся.

Так как нужно найти число повторений подстроки минимального размера в строке str, будем проверять все подстроки размером от [latex]1[/latex] символа до size/2, где size — длина строки. Строка не может состоять из повторяющейся подстроки размером меньше [latex]1[/latex] или больше половины строки. Отсюда цикл for (int i=1; i<=size/2; i++).

Сразу будем отсеивать подстроки, из повторений которых строка не может состоять из-за несоответствия количества символов строки и подстроки ( if (size % i != 0) continue;). К примеру, строка длиной [latex]8[/latex] символов не может состоять из повторений подстроки длиной [latex]3[/latex] символа.

Запоминаем эту подстроку String sub1 = new String(str.substring(0, i));, а затем будем сравнивать с каждой следующей подстрокой такого же размера String sub2 = new String(str.substring(j, j+i)); во внутреннем цикле, предполагая перед этим, что мы нашли нужную нам подстроку ( boolean found = true;); если сверяемые подстроки различаются ( if (!sub1.equals(sub2))) — значит рассматриваемая подстрока sub1 искомой подстрокой не является. Прерываем действие внутреннего цикла и переходим к следующей подстроке, длиной на 1 символ больше. Если же строка полностью состоит из подстроки sub1 находим степень строки — число повторений подстроки в строке, иначе говоря, делим размер строки на размер подстроки ( pow = (size/i);).

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

Ю4.32

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

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

Суммы по косой. Просуммировать элементы матрицы [latex]A(n,n)[/latex] по каждой из линий, параллельных главной диагонали. Напечатать полученные суммы.

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

[latex]n[/latex] — размерность матрицы [latex](n\geq 1)[/latex].
[latex]A[/latex] — квадратная матрица.

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

Суммы элементов матрицы [latex]A[/latex] по каждой из линий, параллельной главной диагонали.

Тесты

№	Входные данные		Выходные данные
№	Размерность матрицы [latex](n)[/latex]	Матрица [latex]A[/latex]	Суммы
1	2	[latex]\begin{pmatrix} 3 & 6\\ -7 & -5 \end{pmatrix} [/latex]	-7 -2 6
2	3	[latex]\begin{pmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{pmatrix} [/latex]	7 12 15 8 3
3	4	[latex]\begin{pmatrix} 4 & 1 & -6 & 3\\ 2 & 8 & 19 & 7\\ -8 & -11 & 3 & -13\\ 0 & 2 & 16 & -9 \end{pmatrix} [/latex]	0 -6 7 6 7 1 3

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

Решение

import java.util.*;

class task5
{	
	public static void main (String[] args)
	{
		int n;
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		if (n<1)
		{
			System.out.println("Размерность матрицы не может быть меньше 1.");
			return;
		}

		double[][] matrix = new double[n][n];
		double[] sum = new double [2*n - 1];
		
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				matrix[i][j] = in.nextDouble();
		
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				 sum[(j-i + n-1] += matrix[i][j];
		
		for (int i=0; i<(2*n-1); i++)
			System.out.print(sum[i]+" ");
		
	}
}

import java.util.*;

class task5

{

public static void main (String[] args)

{

int n;

Scanner in = new Scanner(System.in);

n = in.nextInt();

if (n<1)

{

System.out.println("Размерность матрицы не может быть меньше 1.");

return;

}

double[][] matrix = new double[n][n];

double[] sum = new double [2*n - 1];

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

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

matrix[i][j] = in.nextDouble();

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

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

sum[(j-i + n-1] += matrix[i][j];

for (int i=0; i<(2*n-1); i++)

System.out.print(sum[i]+" ");

}

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

Сначала объявляем переменную n — размерность матрицы [latex]A[/latex] — и присваиваем ей значение, которое вводит пользователь. Если [latex](n\geq 1)[/latex] — продолжаем работу, иначе выводим сообщение об ошибке и завершаем работу программы.

Теперь, зная размерность матрицы, можем инициализировать 2 массива:

Двумерный массив double[][] matrix = new double[n][n]; размерностью [latex](n\times n)[/latex], который будет содержать в себе значения элементов матрицы [latex]A[/latex];
Массив double[] sum = new double [2*n - 1]; размерностью [latex](2*n-1)[/latex] для хранения сумм диагоналей. Такая размерность обусловлена следующей логикой: главная диагональ матрицы размерностью [latex](n\times n)[/latex] содержит [latex]n[/latex] элементов. Побочная диагональ, находящаяся выше, содержит в себе уже [latex](n-1)[/latex] элементов и т.д., пока элементов в диагонали больше нуля. Становится ясно, что выше главной диагонали находится [latex](n-1)[/latex] побочных диагоналей, еще столько же ниже. Прибавляем еще главную диагональ к этому числу и выводим формулу количества диагоналей у матрицы, параллельных главной: [latex]2(n-1)+1=2n-1[/latex].

Заполняем с помощью двух циклов for массив matrix из потока ввода, а затем в таких же циклах находим суммы элементов требуемых диагоналей ( sum[(j-i) + (n-1)] += matrix[i][j];).

Известно, что индексы [latex]i,j[/latex] элементов главной диагонали матрицы всегда одинаковы. Аналогично можно заметить, что на побочных диагоналях индекс [latex]j[/latex] отличается от индекса [latex]i[/latex] на число — «расстояние» между главной диагональю и рассматриваемой побочной. К примеру, если рассматривать побочную диагональ, находящуюся выше через одну от главной («расстояние» между ними равно 2), то в таком случае [latex]j-i=2[/latex].

И если на главной диагонали разность индексов будет равна 0, на диагоналях выше эта разность будет числом положительным, а на диагоналях ниже — отрицательным, то при попытке обращения к элементу массива sum[j-i] мы неизбежно столкнемся с ошибкой, так как индекс массива не может быть числом отрицательным. Значит, чтобы избежать этого, нам надо прибавить к этому индексу некую константу, чтобы самая нижняя диагональ [latex]n-1[/latex] обладала индексом 0 в массиве sum. Отсюда и формула [latex](j-i+n-1)[/latex].

А170

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

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

Даны натуральные числа [latex]n, a_{1}, a_{2},\ldots, a_{n} (n\geq 4)[/latex]. Числа [latex]a_{1}, a_{2},\ldots , a_{n}[/latex] — это измеренные в сотых долях секунды результаты [latex]n[/latex] спортсменов в беге на [latex]100[/latex] м. Составить команду из четырех лучших бегунов для участия в эстафете [latex]4\times100[/latex], т.е. указать одну из четверок натуральных чисел [latex]i, j, k, l[/latex], для которой [latex]1\leq i\leq j\leq k\leq l\leq n[/latex] и [latex]a_{i}+a_{j}+a_{k}+a_{l}[/latex] имеет наименьшее значение.

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

[latex]n[/latex] — количество бегунов [latex](n\geq 4)[/latex].
[latex]a_{1}, a_{2},\ldots, a_{n}[/latex] — результаты спортсменов в беге на [latex]100[/latex] м.

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

[latex]i, j, k, l[/latex] — номера спортсменов, избранных для команды [latex](1\leq i\leq j\leq k\leq l\leq n)[/latex]

Тесты

№	Входные данные		Выходные данные
№	Количество спортсменов [latex](n)[/latex]	Результаты бега спортсменов	Номера спортсменов, избранных для команды
1	3	2.1 3.7 1.1	[latex]n[/latex] не должно быть меньше 4
2	4	1.4 2.1 0 0.2	Результаты должны быть больше 0
3	6	6.5 4.1 1.2 8 9.1 4.9	1 2 3 6
4	12	2.5 9 14 7.1 1.3 4.9 6.7 1.9 10.01 2.45 0.01 13	5 8 10 11

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

Решение

import java.util.*;

class task4
{	
	public static int FindMax(double[] resRun, int[] nRun)
	{
		double max = resRun[0];
		int maxN = 0;
		for (int i=1; i<resRun.length; i++)
		{
			if (resRun[i] > max)
			{
				max = resRun[i];
				maxN = i;
			}
		}
		return maxN;
	}
	
	public static void main (String[] args)
	{
		final int teamSize = 4;	//размер отбираемой команды
		int n;		//количество бегунов
		int[] nRun = new int[teamSize];	//номера бегунов
		double[] resRun = new double[teamSize];	//результаты этих бегунов
		
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		if (n < teamSize)
		{
			System.out.println("n не должно быть меньше 4");
			return;
		}
		
		double max = 0;	//результат худшего бегуна в отобранной команде для сравнения с очередным результатом
		int maxN = 0;	//номер (индекс) худшего бегуна в массиве
		for (int i = 0; i < n; i++)
		{
			double a = in.nextDouble();
			if (a <= 0)
			{
				System.out.printf("Результаты должны быть больше 0");
				return;
			}
			
			if (i<teamSize)	//заполяем команду первыми попавшимися бегунами
			{
				nRun[i] = i;
				resRun[i] = a;
				if (i==teamSize-1)
				{
					maxN = FindMax(resRun, nRun);
					max = resRun[maxN];
				}
			}
			
			else if (a < max)	//заменяем бегуна с наихудшим результатом бегуном, с лучшим результатом
			{
				resRun[maxN] = a;
				nRun[maxN] = i;
				maxN = FindMax(resRun, nRun);
				max = resRun[maxN];
			}
		}
		
		Arrays.sort(nRun);
		
		for (int i = 0; i<teamSize; i++)
		{
			System.out.println(nRun[i]+1);
		}
	}
}

import java.util.*;

class task4

{

public static int FindMax(double[] resRun, int[] nRun)

{

double max = resRun[0];

int maxN = 0;

for (int i=1; i<resRun.length; i++)

{

if (resRun[i] > max)

{

max = resRun[i];

maxN = i;

}

return maxN;

}

public static void main (String[] args)

{

final int teamSize = 4; //размер отбираемой команды

int n; //количество бегунов

int[] nRun = new int[teamSize]; //номера бегунов

double[] resRun = new double[teamSize]; //результаты этих бегунов

Scanner in = new Scanner(System.in);

n = in.nextInt();

if (n < teamSize)

{

System.out.println("n не должно быть меньше 4");

return;

}

double max = 0; //результат худшего бегуна в отобранной команде для сравнения с очередным результатом

int maxN = 0; //номер (индекс) худшего бегуна в массиве

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

{

double a = in.nextDouble();

if (a <= 0)

{

System.out.printf("Результаты должны быть больше 0");

return;

}

if (i<teamSize) //заполяем команду первыми попавшимися бегунами

{

nRun[i] = i;

resRun[i] = a;

if (i==teamSize-1)

{

maxN = FindMax(resRun, nRun);

max = resRun[maxN];

}

else if (a < max) //заменяем бегуна с наихудшим результатом бегуном, с лучшим результатом

{

resRun[maxN] = a;

nRun[maxN] = i;

maxN = FindMax(resRun, nRun);

max = resRun[maxN];

}

Arrays.sort(nRun);

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

{

System.out.println(nRun[i]+1);

}

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

Отличительной особенностью задач из категории «потоковая обработка» является то, что обработка большого объема данных происходит циклически, без их запоминания. То есть, когда пользователь вводит в программу массив значений, программа запоминает очередное значение, обрабатывает его соответствующим образом, а потом заменяет новым поступившим значением. Это дает преимущество в использовании памяти перед программами, которые запоминают весь массив целиком.

Так как по условию размер отбираемой команды — [latex]4[/latex] бегуна ( final int teamSize = 4;), введем ограничение на количество бегунов в целом — их должно быть [latex]4[/latex] или больше, иначе программа выдаст сообщение об ошибке и завершит работу.

Введя количество бегунов n, пользователь после этого будет вводить результат каждого. Программа запоминает этот результат ровно на один шаг цикла ( double a = in.nextDouble();), за который разберется, что с ним делать, а затем заменит следующим результатом.

Так как программа не запоминает весь массив целиком, найти [latex]4[/latex] наименьших значения перебором не получится. Поэтому инициализируем [latex]2[/latex] массива, один из которых ( double[] resRun = new double[teamSize];) будет хранить результаты бегунов, отобранных в команду, а другой ( int[] nRun = new int[teamSize];) — их номера.

Результаты бегунов, отобранных в команду изначально равны нулю; это говорит о том, что еще ни один бегун в команду отобран не был. Результаты и номера первых [latex]4[/latex] бегунов мы запомним в этих массивах, так как иначе мы просто потеряем эти данные и больше не сможем сравнить их со следующими. Теперь, когда 4 бегуна отобраны, следует найти номер бегуна с наихудшим результатом (с помощью функции public static int FindMax(double[] resRun, int[] nRun)). Этот бегун — первый в очереди на замену, если очередной полученный результат вдруг окажется лучшим (меньшим). Следует отметить, что программа будет искать номер наихудшего бегуна лишь в тех случаях, когда этот бегун будет заменен; в ином случае, когда результат очередного бегуна хуже, мы замены в команде не производим, соответственно, худший бегун в команде остается тем же.

Таким образом, с каждым шагом цикла результаты отобранных в команду бегунов становятся либо меньше, либо остаются прежними. После обработки последнего введенного результата, мы получим массив resRun лучших результатов и массив nRun номеров этих бегунов. Остается лишь отсортировать номера бегунов ( Arrays.sort(nRun);), как того требует условие, и вывести их значения.

A334(а). Вложенная сумма

30/06/2017 by Хоба Юрий

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

Вычислить: [latex]\sum \limits_{i=1}^{m}\sum \limits_{j=1}^{n}\frac{1}{i+j^2}[/latex], где [latex]m[/latex] и [latex]n[/latex] — вводимые числа.

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

[latex]m[/latex] и [latex]n[/latex] — верхние границы сумм.

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

Результат вычисления выражения.

Тесты

№	Входные данные	Выходные данные
1	1 5	0.8972
2	19 3	5.3469
3	164 395	34.7509
4	0 102	0

Результаты тестов на wolframalpha.com:

Решение

import java.util.*;

class Task3
{
	public static void main (String[] args)
	{
		int m, n;
		double S = 0;
		Scanner in = new Scanner(System.in);
		m = in.nextInt();
		n = in.nextInt();
		for (int i = 1; i <= m; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				S += 1.0/(i + j*j);
			}
		}
		
		System.out.println(S);
	}
}

import java.util.*;

class Task3

{

public static void main (String[] args)

{

int m, n;

double S = 0;

Scanner in = new Scanner(System.in);

m = in.nextInt();

n = in.nextInt();

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

{

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

{

S += 1.0/(i + j*j);

}

System.out.println(S);

}

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

Так как необходимо найти вложенную сумму, будем использовать вложенный цикл (цикл внутри цикла). На каждом шаге внутреннего цикла прибавляем к сумме (которая изначально равна 0) результат выражения [latex]1/(i + j^2)[/latex]. В числителе вместо 1 пишем 1.0, что преобразует результат выражения в тип double, так как результат выражения — число вещественное.

Посмотреть, как работает программа со входными данными 164 395 можно на сайте ideone.

e-olymp 111. Часы

30/06/2017 by Хоба Юрий

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

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

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

Начальное и конечное время одних календарных суток в часах [latex](H)[/latex] и минутах [latex](M)[/latex] через пробел [latex](0 \leq H \leq 23, 0 \leq M \leq 59)[/latex].

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

Ответ на задачу — общее количество ударов.

Тесты

№	Входные данные		Выходные данные
№	Начальное время	Конечное время	Выходные данные
1	00 00	02 35	18
2	17 23	22 29	45
3	16 57	16 57	0
4	00 00	23 59	180

Решение

import java.util.*;

class Main
{
	public static void main (String[] args)
	{
		int m1,m2,h1,h2, rings = 0;
		Scanner in = new Scanner(System.in);
		h1 = in.nextInt();
		m1 = in.nextInt();
		h2 = in.nextInt();
		m2 = in.nextInt();
		in.close();
		
		while (true)
		{
			if (m1 == 0)
				rings += (h1==0 || h1==12)?12:h1%12;
			
			if (m1 == 30)
				rings += 1;
			
			if (m1 == m2 && h1 == h2)
				break;
			
			m1 ++ ;
			if (m1 > 60)
			{
				m1 = 0;
				h1 ++ ;
			}
		}
		System.out.println(rings);
	}
}

import java.util.*;

class Main

{

public static void main (String[] args)

{

int m1,m2,h1,h2, rings = 0;

Scanner in = new Scanner(System.in);

h1 = in.nextInt();

m1 = in.nextInt();

h2 = in.nextInt();

m2 = in.nextInt();

in.close();

while (true)

{

if (m1 == 0)

rings += (h1==0 || h1==12)?12:h1%12;

if (m1 == 30)

rings += 1;

if (m1 == m2 && h1 == h2)

break;

m1 ++ ;

if (m1 > 60)

{

m1 = 0;

h1 ++ ;

}

System.out.println(rings);

}

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

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

Действия внутри цикла следует выполнять в следующем порядке:

Увеличение количества ударов на 1 или на ту цифру (число), на которую указывает часовая стрелка
Проверка равенства текущего времени и конечного.
Увеличение времени на 1 минуту (переход на следующий час если текущая минута прошла отметку 59)

Такой порядок не позволит пропустить условие прерывания цикла или удара часов в различных случаях (например, начальное и конечное время равны, начальная минута равна 0 или 30).

В итоге к переменной rings будет прибавляться 1 каждый раз, когда минутная стрелка достигает 30 и число, на которое указывает часовая стрелка, каждый раз, когда минутная стрелка достигает 0 (находим остаток от деления количества часов на 12 за исключением тех случаев, когда часы показывают 12 или 0 часов rings += (h1==0 || h1==12)?12:h1%12;).

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

Посмотреть, как работает программа со входными данными 00 00 23 59 можно на сайте ideone.

e-olymp 107. Компакт-диски

30/06/2017 by Хоба Юрий

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

Чистые компакт-диски продают в трёх видах упаковок. Упаковка из 100 дисков стоит 100 грн., из 20 дисков — 30 грн., а один диск стоит 2 грн. Какую минимальную сумму нужно истратить для покупки [latex]N[/latex] таких дисков?

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

Единственное число [latex]N[/latex] — количество дисков. Значение [latex]N[/latex] натуральное, не больше 1000.

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

Искомая минимальная сумма в гривнах.

Тесты

№	Входные данные	Выходные данные
1	0	0
2	163	196
3	238	260
4	298	300

Решение

import java.util.*;
 
class Task2
{
	public static void main (String[] args)
	{
		int N;
		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		if (N % 100 >= 65)
			N = 100 * (N / 100 + 1);
		if (N % 20 > 15)
			N = 20 * (N / 20 + 1);
		System.out.println((N / 100) * 100 + (N % 100 / 20) * 30 + 2 * (N % 20));
	}
}

import java.util.*;

class Task2

{

public static void main (String[] args)

{

int N;

Scanner in = new Scanner(System.in);

N = in.nextInt();

if (N % 100 >= 65)

N = 100 * (N / 100 + 1);

if (N % 20 > 15)

N = 20 * (N / 20 + 1);

System.out.println((N / 100) * 100 + (N % 100 / 20) * 30 + 2 * (N % 20));

}

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

Задача может быть решена по алгоритму «купить максимальное количество упаковок из 100, потом из 20 дисков, а потом докупать по одному диску, чтобы получить требуемые для покупки [latex]N[/latex] дисков». Такой алгоритм можно записать формулой: [latex](N / 100) * 100 + (N \% 100 / 20) * 30 + 2 * (N \% 20)[/latex].

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

К примеру, если необходимо купить 96 дисков, куда дешевле купить за 100 гривен упаковку, содержащую 100 дисков, чем 4 упаковки по 20 дисков и отдельно еще 16 дисков, что в общей стоимости даст 152 гривны.

Поэтому сперва следует проверить, не будет ли покупка большего количества дисков дешевле. Для этого используются условия if (N % 100 >= 65) и if (N % 20 > 15), где 65 и 15 — лимит количества дисков, при превышении которого покупка упаковок из 100 и 20 дисков соответственно — дешевле.

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

Посмотреть, как работает программа со входными данными 238 можно на сайте ideone.

e-olymp 7336. Пирожки

29/06/2017 by Хоба Юрий

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

Пирожок в столовой стоит [latex]a[/latex] гривен и [latex]b[/latex] копеек. Найдите, сколько гривен и копеек заплатил Петя за [latex]n[/latex] пирожков.

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

Три натуральных числа [latex] a, b, n[/latex] [latex](0\leq a, b, n \leq100)[/latex]

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

Через пропуск два числа: стоимость покупки в гривнах и копейках.

Тесты

№	Входные данные	Выходные данные
1	5 9 2	10 18
2	0 15 18	2 70
3	5 25 0	0 0

Решение

import java.util.*;

class Task1
{
	public static void main (String[] args)
	{
		int a, b, n;
		Scanner in = new Scanner(System.in);
		a = in.nextInt();
		b = in.nextInt();
		n = in.nextInt();
		int total = (a*100+b)*n;
		System.out.printf("%d %d", total/100, total%100);
	}
}

import java.util.*;

class Task1

{

public static void main (String[] args)

{

int a, b, n;

Scanner in = new Scanner(System.in);

a = in.nextInt();

b = in.nextInt();

n = in.nextInt();

int total = (a*100+b)*n;

System.out.printf("%d %d", total/100, total%100);

}

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

Для объявления переменных a,b,n и total используем тип int, так как эти числа являются натуральными. Для простоты подсчета переводим сумму в копейки; так как в одной гривне 100 копеек, количество гривен мы умножаем на 100, прибавляем количество копеек, а затем умножаем получившуюся сумму в копейках на количество пирожков. Отсюда формула: total = (a*100 + b)*n.

В результате получаем число, в котором две последние цифры — это количество копеек, а остальные — количество гривен. Выводим их на экран с помощью соответствующих операций деления total/100 для гривен и деления по модулю total%100 для копеек.

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

Посмотреть, как работает программа со входными данными 5, 9, 2 можно на сайте ideone.