e-olymp 51. К-домино

25/12/2018 by Александра Филистович

Задача

Работник отдела технического контроля любил выбраковывать «доминошки», которые содержали одинаковые значения. Так как на предприятии, выпускающем [latex]K[/latex]-домино, этого не знали, к нему постоянно поступали претензии на сумму, равную стоимости [latex]K[/latex]-домино. Стоимость [latex]K[/latex]-домино составляла ровно столько гривен, сколько было в купленном покупателем наборе доминошек.Для того, чтобы его не уволили с работы, работник ОТК выбраковывал иногда не только все не любимые «доминошки», а несколько больше, но не более половины гарантированно выбраковыванных.Зная сумму претензии, пришедшей на предприятие, установите, какой из наборов [latex]K[/latex]-домино был куплен покупателем.

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

Единственное число [latex]S[/latex] – сумма претензии, пришедшей на предприятие, [latex]S ≤ 2000000000[/latex].

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

Единственное число – индекс [latex]K[/latex] купленного покупателем [latex]K[/latex]-домино.

№	Входные данные	Выходные данные
1	5	3
2	10	4
3	1000000	1414
4	555666777888	1054198
5	13	5

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scan = new Scanner(System.in);
		long s = scan.nextLong();
                //применяем формулу и округляем число вниз
		double k = Math.floor(Math.sqrt(2 * s + 1));
                //переводим double в int
		int ans = (int) k;
		System.out.println (ans);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner scan = new Scanner(System.in);

long s = scan.nextLong();

//применяем формулу и округляем число вниз

double k = Math.floor(Math.sqrt(2 * s + 1));

//переводим double в int

int ans = (int) k;

System.out.println (ans);

}

Решение

[latex]K[/latex]-домино — набор домино с минимальным количеством точек на одной из половин доминошки.
Количество дублей, то есть количество точно выбракованных доминошек — [latex]k[/latex]+1. Общее количество доминошек [latex]k[/latex]-домино:$$(k+1){{k+2}\over{2}}$$
Пусть работник дополнительно выбраковывал [latex]e[/latex] доминошек. [latex]s[/latex] — сумма претензии, тогда имеем:

[latex]k+1+e+s= (k+1){{k+2}\over{2}}[/latex]
[latex]k^2<=2s+1[/latex]
[latex]k=[\sqrt{2s+1}][/latex]

Ссылки

Ссылка на e-olymp.
Ссылка на Ideone

e-olymp4491 Трое из Простоквашино

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

Условие задачи:
— Дядя Федор, Дядя Федор, я научился строить дерево отрезков.
— Подожди, Шарик, я занят.
— Ну Дядя Федор, ну смотри какой я код написал:

int build(int v, int left, int right) {
	if (left == right) {
		t[v] = a[left];
		return 0;

	}
	int mid = (left+right) / 2;
	build(v*2, left, mid);
	build(v*2+1, mid+1, right);
	t[v] = max(t[v*2], t[v*2+1]);
	return 0;
}

int get_max(int v, int left, int right, int lpos, int rpos) {
	if (left == lpos && right == rpos)
		return t[v];
	if (lpos > rpos)
		return -1;
	int mid = (left+right) / 2;
	return max(get_max(v*2, left, mid, lpos, min(rpos, mid)),
	get_max(v*2+1,mid+1,right,max(lpos,mid+1),rpos));
}

int build(int v, int left, int right) {

if (left == right) {

t[v] = a[left];

return 0;

}

int mid = (left+right) / 2;

build(v*2, left, mid);

build(v*2+1, mid+1, right);

t[v] = max(t[v*2], t[v*2+1]);

return 0;

}

int get_max(int v, int left, int right, int lpos, int rpos) {

if (left == lpos && right == rpos)

return t[v];

if (lpos > rpos)

return -1;

int mid = (left+right) / 2;

return max(get_max(v*2, left, mid, lpos, min(rpos, mid)),

get_max(v*2+1,mid+1,right,max(lpos,mid+1),rpos));

}

— Ну хорошо, Шарик, раз ты так хорошо разобрался с этой темой, давай я тебе дам массив из [latex]n[/latex] неотрицательных чисел и число [latex]k[/latex], а ты мне скажешь сколько существует таких пар [latex]l;r \left ( 1\leq l\leq r\leq n \right ),[/latex] что функция, вызванная следующим образом:

[latex]get[/latex]_[latex]max(1, 1, n, l, r)[/latex]
вернет значение равное [latex]k[/latex]. Можно считать, что перед этим была вызвана функция

[latex]build(1, 1, n)[/latex]

— Хорошо, Дядя Федор!

Входные данные:
В первой строке находятся число [latex]n \left ( 1\leq n\leq 10^{6} \right )[/latex] — количество элементов в массиве и [latex]k \left ( 1\leq k\leq 10^{9} \right )[/latex] — значение, которое должна вернуть функция. В следующей строке находится [latex]n[/latex] неотрицательных чисел, не превышающих [latex]10^{9}[/latex] — элементы массива.

Выходные данные:
Выведите единственное число – ответ на задачу.

Тесты:

Входные данные			Выходные данные
[latex]n[/latex]	[latex]k[/latex]	[latex]elem[/latex]_[latex]tree[][/latex]	[latex]ans[/latex]
5	3	1 2 3 2 3	11
10	6	1 4 7 6 2 4 1 9 6 6	7
20	15	5 2 4 7 15 3 15 20 31 15 15 1 23 4 8 15 1 2 15 6	43

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

import java.util.*;

public class Main
{
  public static void main(String[] args) 
  {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    int[] elem_tree = new int[n];
    int ans=0, left=0, right=0;
    for(int i=0; i<n; i++){
    	elem_tree[i]=in.nextInt();
    	if (elem_tree[i]==k){
    		ans+=i-left+1;
    		right=i;
    	}
    	else{
    		if(elem_tree[i]>k){
        			right=0;
        			left=i+1;
    		}
    		else if(elem_tree[i]<k && right!=0) ans+=right-left+1;
    	}
    }
    System.out.println(ans);
  }
}

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k = in.nextInt();

int[] elem_tree = new int[n];

int ans=0, left=0, right=0;

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

elem_tree[i]=in.nextInt();

if (elem_tree[i]==k){

ans+=i-left+1;

right=i;

}

else{

if(elem_tree[i]>k){

right=0;

left=i+1;

}

else if(elem_tree[i]<k && right!=0) ans+=right-left+1;

}

System.out.println(ans);

}

Алгоритм решения:
Зададим отрезок массива, на котором обозначим границы [latex]\left [ left, right \right ][/latex]. Инициализируем изначально оба конца нулем. Рассмотрим некоторое [latex]elem\_tree\left [ i \right ][/latex] на нашем сегменте. Тогда если [latex]elem\_tree\left [ i \right ]=k[/latex], то на всем отрезке от [latex]left[/latex] до [latex]i[/latex] максимумом будет [latex]k[/latex]. Увеличим в таком случае [latex]left[/latex] и сделаем его равным [latex]i[/latex], причем [latex]right=0.[/latex] Если [latex]elem\_tree\left [ i \right ]\lt k[/latex], максимум будет также равен [latex]k[/latex]. В таком случае увеличиваем только [latex]right.[/latex] Если же [latex]elem\_tree\left [ i \right ]\gt k[/latex] , то [latex]left[/latex] устанавливаем равным [latex]i+1[/latex], а [latex]right[/latex] обнуляем.
Пройдя по всему массиву, мы должны получить значения [latex]left[/latex] равное количеству пар в которых максимум равен [latex]k[/latex], а [latex]right[/latex] должно стать равным нулю.

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

e-olymp 1388. Заправки

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

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

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

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

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

Сначала идет количество городов n (1 ≤ n ≤ 100), затем идет n чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Затем идет количество дорог m в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами — номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.

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

Выведите одно число — суммарную стоимость маршрута или -1, если добраться невозможно.

Тесты

№	Входные данные	Выходные данные
1	4 1 10 2 15 4 1 2 1 3 4 2 4 3	3
2	4 1 10 2 15 0	-1
3	5 1 2 3 4 5 4 1 2 2 3 3 4 4 5	10

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

import java.util.*;

class Main
{
	//Условная бесконечность
	public static final int INF = 1000000;
	
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n, m, curFrom, curTo;
		n = input.nextInt();
		
		int price[] = new int[n+1];     //Цены на бензин в i-ом городе
		int distance[] = new int[n+1];  //Минимальные затраты на то, чтобы обраться до i-го города
		boolean used[] = new boolean[n+1]; //Был ли рассмотрен этот город?
		Vector <Integer> graph[] = new Vector[n+1];
		for (int i = 1; i <= n; ++i) {
			price[i] = input.nextInt();
			distance[i] = INF;
			used[i] = false;
			graph[i] = new Vector();
		}
		//Заполнение списка смежности
		m = input.nextInt();
		for (int i = 0; i < m; ++i) {
			curFrom = input.nextInt();
			curTo = input.nextInt();
			graph[curFrom].add(curTo);
			graph[curTo].add(curFrom);
		}
		//Нахождение оптимальной стоимости маршрута. На каждой итерации цикла находим город,
		//стоимость маршрута из начального города к которому минимальна. Если оказывается,
		//что эта стоимость бесконечна, значит, искомого пути не существует.
		distance[1] = 0;
		for(int i = 0; i < n; ++i) {
			int curCity = -1; //Город, рассматривыемый в данной итерации
			for (int j = 1; j <= n; ++j)
				if (!used[j] && (curCity == -1 || distance[j] < distance[curCity])) curCity = j;
			if (distance[curCity] == INF) break;
			used[curCity] = true;
			//Релаксация стоимости маршрута для всех городов, в которые можно попасти из данного
			for(int j = 0; j < graph[curCity].size(); ++j) {
				int to = graph[curCity].elementAt(j); 
				distance[to] = Math.min(distance[to], distance[curCity] + price[curCity]);
			}
		}
		//Вывод ответа
		System.out.print(distance[n] == INF ? -1 : distance[n]);
	}
}

import java.util.*;

class Main

{

//Условная бесконечность

public static final int INF = 1000000;

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n, m, curFrom, curTo;

n = input.nextInt();

int price[] = new int[n+1]; //Цены на бензин в i-ом городе

int distance[] = new int[n+1]; //Минимальные затраты на то, чтобы обраться до i-го города

boolean used[] = new boolean[n+1]; //Был ли рассмотрен этот город?

Vector <Integer> graph[] = new Vector[n+1];

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

price[i] = input.nextInt();

distance[i] = INF;

used[i] = false;

graph[i] = new Vector();

}

//Заполнение списка смежности

m = input.nextInt();

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

curFrom = input.nextInt();

curTo = input.nextInt();

graph[curFrom].add(curTo);

graph[curTo].add(curFrom);

}

//Нахождение оптимальной стоимости маршрута. На каждой итерации цикла находим город,

//стоимость маршрута из начального города к которому минимальна. Если оказывается,

//что эта стоимость бесконечна, значит, искомого пути не существует.

distance[1] = 0;

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

int curCity = -1; //Город, рассматривыемый в данной итерации

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

if (!used[j] && (curCity == -1 || distance[j] < distance[curCity])) curCity = j;

if (distance[curCity] == INF) break;

used[curCity] = true;

//Релаксация стоимости маршрута для всех городов, в которые можно попасти из данного

for(int j = 0; j < graph[curCity].size(); ++j) {

int to = graph[curCity].elementAt(j);

distance[to] = Math.min(distance[to], distance[curCity] + price[curCity]);

}

//Вывод ответа

System.out.print(distance[n] == INF ? -1 : distance[n]);

}

Описание

Оптимальную стоимость маршрута будем находить по алгоритму Дейкстры. Цены на бензин в i-ом городе хранятся в массиве price. Минимальные стоимости маршрутов к каждому из городов хранятся в массиве distance, изначально все маршруты принимаем бесконечно дорогими. Кроме того, для хранения информации о том, был ли рассмотрен i-й город, используется массив used. Сам граф представляется в виде списка смежности. Для этого используется массив векторов <strong>graph</strong>. Если в итоге стоимость маршрута до целевого города осталась бесконечной, значит, пути к нему не существует, и выводится -1. Иначе выводится эта стоимость.

Код на ideone.com.

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

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

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

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

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

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

push_front

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

push_back

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

pop_front

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

pop_back

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

front

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

back

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

size

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

clear

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

exit

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

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

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

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

Тесты

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

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

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

class DequeException extends Exception {}

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

import java.util.*;

import java.io.*;

class DequeException extends Exception {}

class Node <T>

{

T val;

Node prev, next;

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

}

class MyDeque <T>

{

int size;

Node<T> first, last;

MyDeque() {

size = 0;

first = null;

last = null;

}

String pushBack(T val) {

if (size > 0) {

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

last.next = currentNode;

last = currentNode;

size++;

}

else {

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

last = currentNode;

first = currentNode;

size++;

}

return "ok";

}

String pushFront(T val) {

if (size > 0) {

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

first.prev = currentNode;

first = currentNode;

size++;

}

else {

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

last = currentNode;

first = currentNode;

size++;

}

return "ok";

}

T popFront() throws DequeException {

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

T v = first.val;

first = first.next;

size--;

return v;

}

T popBack() throws DequeException {

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

T v = last.val;

last = last.prev;

size--;

return v;

}

T front() throws DequeException {

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

return first.val;

}

T back() throws DequeException {

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

return last.val;

}

int getSize() {

return size;

}

String clear() {

size = 0;

return "ok";

}

String ex() {

return "bye";

}

class Main

{

public static void main (String[] args) {

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

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

String s, val;

while(in.hasNext()) {

s = in.next();

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

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

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

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

try {

out.println(deque.back());

} catch(DequeException e) {

out.println("error");

}

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

try {

out.println(deque.front());

} catch(DequeException e) {

out.println("error");

}

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

try {

out.println(deque.popBack());

} catch(DequeException e) {

out.println("error");

}

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

try {

out.println(deque.popFront());

} catch(DequeException e) {

out.println("error");

}

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

val = in.next();

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

}

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

val = in.next();

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

}

out.flush();

}

Описание

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

Код на ideone.com.

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

e-olimp 7365

05/12/2017 by Мазурин Эдвард

Ссылка на оригинал задачи

Задача «Молоко и пирожок»

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее 30 кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость 200 мл, а упаковки молока – 0.9 л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

Тесты:

Количество детей	Вес	Количество упаковок молока	Количество пирожков
3	30 29 30	1	1
5	25 41 56 20 20	1	3
4	30 30 30 30	0	0
7	25 26 27 28 29 23 24	2	7

Код:

import java.util.*;

public class MilkAndPatty {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("Введите n: ");
        int n = in.nextInt();    // количество учеников
        int k;                   // пакеты молока
        int p = 0;               // пирожки
        double m = 0.2, u = 0.9; // объем стакана/пачки молока
        for(int i=0; i<n; i++) {
            System.out.print("Введите w: ");
            int w = in.nextInt(); // вес учеников
            if (w<30) p++;
            if(w>=30) p=p+0;
        }
        k = (int)Math.ceil(p*m/u);
        System.out.print(k + " " + p);
    }
}

import java.util.*;

public class MilkAndPatty {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

System.out.print("Введите n: ");

int n = in.nextInt(); // количество учеников

int k; // пакеты молока

int p = 0; // пирожки

double m = 0.2, u = 0.9; // объем стакана/пачки молока

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

System.out.print("Введите w: ");

int w = in.nextInt(); // вес учеников

if (w<30) p++;

if(w>=30) p=p+0;

}

k = (int)Math.ceil(p*m/u);

System.out.print(k + " " + p);

}

Алгоритм:

Объявление и ввод значений переменных.
Используем цикл for для подсчета необходимого количества пирожков.
На основе предыдущих данных и округления в большую сторону (метод Math.ceil ), подсчитываем необходимое количество пакетов молока.
Окончание работы программы.

Работающая версия программы на Ideone.com

Ссылка на источник

A393a

28/11/2017 by Мазурин Эдвард

Задача:

Даны натуральное число [latex]n[/latex], целочисленная квадратная матрица порядка [latex]n[/latex]. Получить [latex]{b}_{1}[/latex],…,[latex]{b}_{n},[/latex] где [latex]{b}_{i}[/latex] — это наименьшее из значений, элементов находящихся в начале [latex]i[/latex]-й строки матрицы до элемента, принадлежащего главной диагонали, включительно.

Тесты:


Вводимые данные		Предполагаемый вывод	Комментарий
4	4 3 2 1	4 3 2 1	Тест пройден
	4 3 2 1
	4 3 2 1
	4 3 2 1
	1 2 3 4	1 1 1 1	Тест пройден
	1 2 3 4
	1 2 3 4
	1 2 3 4

Решение:

Считываем матрицу и проходим в цикле по каждой строке ведя поиск минимального элемента (но есть одно «Но», поиск ведется под главной диагональю матрицы).
У всех элементов находящихся под главной диагональю матрицы, включительно, индекс строк больше или равен индексу столбцов заданной матрицы. Учтем это при составлении программы.
Осталось только написать код с учетом вышеперечисленных особенностей задачи.

Код:

import java.util.*;

public class multi_arrays {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        System.out.print("Введите n: ");
        int n = in.nextInt();                //Объявление переменной, обозначающей размерность массива
            int[][] a = new int [n][n];      //Создание двумерного массива
        for (int i = 0; i < n; i++) {        
            for (int j = 0; j < n; j++) {
                System.out.print("Заполните массивы элементами: ");
                a[i][j] = in.nextInt();
            }
        }
        for (int i = 0; i < n; i++) {
            int min = a[i][0];
            for (int j = 0; i - j >= 0; j++)  // критерий отбора элементов под главной диагональю
            {
                if (a[i][j] < min) {
                    min = a[i][j];
                }
            }
            System.out.println(min);
        }
    }
}

import java.util.*;

public class multi_arrays {

public static void main(String[] args){

Scanner in = new Scanner(System.in);

System.out.print("Введите n: ");

int n = in.nextInt(); //Объявление переменной, обозначающей размерность массива

int[][] a = new int [n][n]; //Создание двумерного массива

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

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

System.out.print("Заполните массивы элементами: ");

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

}

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

int min = a[i][0];

for (int j = 0; i - j >= 0; j++) // критерий отбора элементов под главной диагональю

{

if (a[i][j] < min) {

min = a[i][j];

}

System.out.println(min);

}

Версия программы на Ideone.com

Ссылка на источник

Шифровка

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.

Ю 4.24

28/11/2017 by Мазурин Эдвард

Задача:

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


Вводимые данные	Предполагаемый вывод	Комментарий
1 1 1 1 1 1	1 1 2 3 4 5	Тест пройден
1 2 3 4 5 6 7 8 9	1 1 3 6 10 15 21 28 36	Тест пройден
3 5 2 9 0 4 65 156 1	3 3 8 10 19 19 23 88 244	Тест пройден
2 -7 3 8 -4 5 -2 4 2	2 2 -5 -2 6 2 7 5 9	Тест пройден

Код:

import java.util.*;


public class cu_total {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        System.out.print("Введите n: ");
        int n = in.nextInt(); //Объявление переменной, обозначающей размерность массива
        int[] a = new int[n]; //Создание массива
        for(int i=0;i<n;i++){ //Ввод значений элементов массива с помощью цикла
            System.out.print("Заполните массив элементами: ");
            a[i] = in.nextInt();
        }
        int b[] = new int[n]; //Создание дополнительного массива, в котором и будет храниться результат.
        int S=0;              //Создание вспомогательной переменной
        b[0]=a[0];            //Инициализация первого элемента второго массива
        for(int i=1;i<n;i++)  //Преобразование элементов первого массива в элементы второго массива и ввод результата во второй массив
        {
            S+=a[i-1];
            b[i]=S;
        }
        for(int i=0;i<n;i++){
            System.out.println(b[i]);
        }
        System.out.print("\n" + "Тест пройден");
    }
}

import java.util.*;

public class cu_total {

public static void main(String[] args){

Scanner in = new Scanner(System.in);

System.out.print("Введите n: ");

int n = in.nextInt(); //Объявление переменной, обозначающей размерность массива

int[] a = new int[n]; //Создание массива

for(int i=0;i<n;i++){ //Ввод значений элементов массива с помощью цикла

System.out.print("Заполните массив элементами: ");

a[i] = in.nextInt();

}

int b[] = new int[n]; //Создание дополнительного массива, в котором и будет храниться результат.

int S=0; //Создание вспомогательной переменной

b[0]=a[0]; //Инициализация первого элемента второго массива

for(int i=1;i<n;i++) //Преобразование элементов первого массива в элементы второго массива и ввод результата во второй массив

{

S+=a[i-1];

b[i]=S;

}

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

System.out.println(b[i]);

}

System.out.print("\n" + "Тест пройден");

}

Описание:

Простейшие операции с массивом. С помощью цикла записываем данные в массив, после чего, снова с помощью цикла, записываем новые данные во второй массив. Далее выводим результат.

Алгоритм:

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

Работающая версия программы на Ideone.com

Ссылка на источник

AL6

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

Условие

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

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

$latex ({([])})$

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

Yes.

Код

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

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

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static class stack

{

char arr[] = new char[10];

int current;

stack(){current = 0;};

void push(char x)

{

arr[current] = x;

current++;

}

void pop()

{

current--;

}

char back()

{

return arr[current-1];

}

int size()

{

return current;

}

};

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

{

String brace;

Scanner input = new Scanner(System.in);

brace = input.nextLine();

stack x = new stack();

char a = brace.charAt(0);

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

{

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

{

a = brace.charAt(i);

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

x.push(a);

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

{

x.pop();

} else

{

System.out.println("No");

System.exit(0);

}

if(x.size() == 0)

{

System.out.println("Yes");

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

}

else

{

System.out.println("No");

System.exit(0);

}

Решение

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

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

Монстр

26/11/2017 by Мазурин Эдвард

Ссылка на оригинал задачи

Задача:

Монстр гонится за Риком и Морти на другой планете. Они настолько напуганы, что иногда кричат. Точнее, Рик кричит в моменты времени [latex]b,[/latex] [latex]b + a,[/latex] [latex]b + 2a,[/latex] [latex]b + 3a,[/latex]…, а Морти кричит в моменты времени [latex]d,[/latex] [latex]d + c,[/latex] [latex]d + 2c,[/latex] [latex]d + 3c,[/latex]….

Монстр поймает их, если в какой-то момент времени они закричат одновременно. Так что он хочет знать, когда он поймает их (первый момент времени, когда они закричат одновременно) или они никогда не закричат одновременно.

Ввод:

Первая строка входных данных содержит два целых числа [latex]a[/latex] и [latex]b[/latex] [latex](1\leq a,[/latex] [latex]b\leq 100).[/latex]

Вторая строка входных данных содержит два целых числа [latex]c[/latex] и [latex]d[/latex] [latex](1\leq c,[/latex] [latex]d\leq 100).[/latex]

Вывод:

Выведите первый момент времени, когда Рик и Морти закричат одновременно, или - 1, если они никогда не закричат одновременно.

Тесты:

Ввод	Вывод
20 2 9 19	82
2 1 16 12	-1

Код:

import java.util.*;

public class RickAndMorty {

    public static void main(String[] args) {
        int n, m;
        Vector s = new Vector();
        Scanner in = new Scanner(System.in);
        System.out.print("Введите a: ");
        int a = in.nextInt();
        System.out.print("Введите b: ");
        int b = in.nextInt();
        System.out.print("Введите c: ");
        int c = in.nextInt();
        System.out.print("Введите d: ");
        int d = in.nextInt();
       
        for(int i=0;i<=100;i++)
        {
            for(int j=0;j<=100;j++)
            {
                n=b+i*a;
                m=d+j*c;
                if(m==n)
                {
                    s.add(n);
                }
            }
        }
        if(s.isEmpty())
        {
            System.out.print(-1);
        } else
            System.out.print(s.firstElement());
    }
}

import java.util.*;

public class RickAndMorty {

public static void main(String[] args) {

int n, m;

Vector s = new Vector();

Scanner in = new Scanner(System.in);

System.out.print("Введите a: ");

int a = in.nextInt();

System.out.print("Введите b: ");

int b = in.nextInt();

System.out.print("Введите c: ");

int c = in.nextInt();

System.out.print("Введите d: ");

int d = in.nextInt();

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

{

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

{

n=b+i*a;

m=d+j*c;

if(m==n)

{

s.add(n);

}

if(s.isEmpty())

{

System.out.print(-1);

} else

System.out.print(s.firstElement());

}

Решение:

В этих моментах времени, заданных прогрессиями, изменяется только коэффициент при [latex]a[/latex] и [latex]c.[/latex] Создадим для них 2 цикла. Так как равных моментов времени может быть много, а нам нужен только первый, создаем вектор и ,когда моменты равны, добавляем в него этот момент. Затем, уже вне цикла, проверяем пустой ли вектор, и в таком случаем выводим -1, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.

Версия программы на Ideone.com

Ссылка на источник