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 1704. Умная черепашка

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

Задача

Имеется клетчатое поле размером $m \times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?

Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.

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

Два натуральных числа $m$ и $n$, не превышающие $30$.

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

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

Тесты

Входные данные	Выходные данные
$4$ $3$	$10$
$5$ $5$	$70$
$4$ $8$	$120$
$10$ $10$	$48620$

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        long[][] a = new long[m][n];
        a[m-1][0] = 1;
        for(int i = m-1; i >= 0; i--) {
            for(int j = 0; j < n; j++) {
                if(i == m-1 && j == 0) continue;
                a[i][j] = (i < m-1 ? a[i+1][j] : 0) + (j > 0 ? a[i][j-1] : 0);
            }
        }
        System.out.print(a[0][n-1]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int m = in.nextInt();

int n = in.nextInt();

long[][] a = new long[m][n];

a[m-1][0] = 1;

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

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

if(i == m-1 && j == 0) continue;

a[i][j] = (i < m-1 ? a[i+1][j] : 0) + (j > 0 ? a[i][j-1] : 0);

}

System.out.print(a[0][n-1]);

}

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

Для решения задачи представим, что черепашка уже находится в правом верхнем углу поля. Начинаем движение сверху-вниз справа-налево, т.е возможные ходы черепашки только наоборот(черепашка может ходит вверх и направо). Если черепашка сместилась вниз по карте, т.e. j > 0, то прибавляем ячейке значение верхней, если черепашка сместилась налево, т.e. i < m-1, то прибавляем ячейке значение правой. Эта сумма будет накапливаться и будет равна количеству всех возможных ходов черепашки. Проходя через всю карту, попадем в левую нижнюю ячейку(старт черепашки), эта ячейка и будет содержать число возможных путей к правой верхней точки. Задача решена.

Ссылки

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

e-olymp 992. Города и дороги

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

Задача

В галактике «Milky Way» на планете «Neptune» есть n городов, некоторые из которых соединены дорогами. Император «Maximus» галактики «Milky Way» решил провести инвентаризацию дорог на планете «Neptune». Но, как оказалось, он не силен в математике, поэтому он просит Вас сосчитать количество дорог.

Вводные данные

В первой строке записано число $n$ $(0 \leq n \leq 100)$. В следующих $n$ строках записано по $n$ чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции $(i, j)$ квадратной матрицы стоит единичка, то $i$-ый и $j$-ый города соединены дорогами, а если нолик, то не соединены.

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

Вывести одно число — количество дорог на планете «Neptune».

Тесты

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

Код программы(использование матрицы смежности)

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[][] x = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				x[i][j] = in.nextInt();
			}
		}
		int roads = 0;
		for(int i = 0; i < n; i++) {
			for(int j = i; j < n; j++) {
				if(x[i][j] == 1) roads++;
			}
		}
		System.out.print(roads);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[][] x = new int[n][n];

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

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

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

}

int roads = 0;

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

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

if(x[i][j] == 1) roads++;

}

System.out.print(roads);

}

Решение задачи(использование матрицы смежности)

Для решения задачи вводим матрицу смежности. Далее в цикле проходим верхнюю треугольную часть матрицы смежности и если попадается $1$, то увеличиваем число дорог на $1$. Выводим количество дорог. Задача решена.

Код программы(потоковая обработка)

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n=0;
		int i;
		while(in.hasNextInt()) {
			i = in.nextInt();
			if(i == 1) n++;
		}
		System.out.print(n/2);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n=0;

int i;

while(in.hasNextInt()) {

i = in.nextInt();

if(i == 1) n++;

}

System.out.print(n/2);

}

Решение задачи(потоковая обработка)

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

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com(матрица смежности)
Код решения на ideone.com(потоковая обработка)

e-olymp 2471. От матрицы смежности к списку рёбер

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

Задача

Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка рeбер.

Вводные данные

Первая строка содержит количество вершин $n$ $(1 \leq n \leq 100)$ в графе. Затем идут $n$ строк по $n$ элементов в каждой — описание матрицы смежности.

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

Вывести список ребер, упорядоченный по первой вершине в паре вершин, которая описывает ребро.

Тесты

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

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[][] x = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				x[i][j] = in.nextInt();
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = i; j < n; j++) {
				if(x[i][j] == 1) System.out.println((i+1) + " " + (j+1));
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[][] x = new int[n][n];

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

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

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

}

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

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

if(x[i][j] == 1) System.out.println((i+1) + " " + (j+1));

}

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

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

Ссылки

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

A302. Количество различных цифр числа в его десятичной записи

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

Задача

Дано натуральное число $N$. Сколько различных цифр встречается в его десятичной записи?

Вводные данные

Натуральное число $N$.

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

Количество различных цифр.

Тесты

Входные данные	Выходные данные
$1234$	$4$
$100$	$2$
$1234567890$	$10$
$3333$	$1$
$11112222$	$2$

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int[] folder = new int[10];
    	long N = in.nextLong();
    	while(N != 0) {
        	folder[(int)N % 10]++;
        	N /= 10;
    	}
    	int sum = 0;
    	for (int i = 0; i < 10; i++)
        	if(folder[i] != 0) sum++;
        System.out.print(sum);	
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int[] folder = new int[10];

long N = in.nextLong();

while(N != 0) {

folder[(int)N % 10]++;

N /= 10;

}

int sum = 0;

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

if(folder[i] != 0) sum++;

System.out.print(sum);

}

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

Для решения задачи создадим массив folder в котором будем хранить количество встреч для различных цифр десятичной записи в соответствующих позициях массива. Находим цифры числа $N$($N \mod 10$ последняя цифра числа, затем $N / 10$). Увеличиваем на $1$ значения соответствующей позиции массива(цифра числа равна индексу массива). Для определения количества различных цифр делаем цикл и проверяем ненулевые значения массива folder. Задача решена.

Ссылки

Условие задачи(стр. 126).
Код решения на ideone.com

А329. Квадрат суммы цифр числа

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

Задача

Задача из сборника задач по программированию Абрамова С.А. 2000 г.
Даны натуральные числа $n$, $m$. Получить все меньшие $n$ натуральные числа, квадрат суммы цифр которых равен $m$.

Вводные данные

Два положительных числа $n$ и $m$.

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

Все целые числа из $(0,n)$, удовлетворяющие условию.

Тесты

Входные данные	Выходные данные
$1234$ $9$	$3$ $12$ $21$ $30$ $102$ $111$ $120$ $201$ $210$ $300$ $1002$ $1011$ $1020$ $1101$ $1110$ $1200$
$100$ $4$	$2$ $11$ $20$
$49$ $49$	$7$ $16$ $25$ $34$ $43$
$1000$ $1$	$1$ $10$ $100$

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

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);
    	long n, m, t, sum;
    	n = in.nextLong(); 
    	m = in.nextLong();
    	for(long i = 1; i < n; i++) {
        	t = i;
        	sum = 0;
	        while(t != 0)
	            sum += t%10;
	            t /= 10;
	        }
        if(sum*sum == m) System.out.print(i + " ");
    	}
    }
}

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

long n, m, t, sum;

n = in.nextLong();

m = in.nextLong();

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

t = i;

sum = 0;

while(t != 0)

sum += t%10;

t /= 10;

}

if(sum*sum == m) System.out.print(i + " ");

}

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

Для того, чтоб найти каждую цифру числа будем искать остаток от деления на $10$, которым является последняя цифра числа, а затем делить число нацело на $10$, чтоб предпоследняя цифра стала последней. Будем повторять эту операцию пока число не равно $0$. Все полученные цифры числа складываем. Таким способом будем искать сумму цифр каждого целого числа от $1$ до $n-1$, параллельно возводя полученную сумму в квадрат, а результат сравнивая с $m$.

Ссылки

Условие задачи(страница 135)
Код решения на ideone.com

e-olymp 4557. Одинокий король

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

Задача

Позиция короля на шахматной доске

Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из $n$ его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) — возможные ходы короля показаны на рисунке снизу.

Определите, побывал ли король дважды на одном и том же поле за свои $n$ ходов.

Возможные ходы короля

Вводные данные

В первой строке задано общее число ходов короля $n$ $(0 \leq n \leq 1000)$. В последующих $n$ строках заданы направления перемещения короля: строка под номером $i+1$ задаёт направление перемещения короля на $i$-ом ходу.

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

Выведите единственное число — номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение «Ok» (без кавычек), а во второй — манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.

Напоминаем, что манхэттенское расстояние между точками с координатами $(x_1, y_1)$ и $(x_2, y_2)$ определяется по формуле: $d=|x_2 — x_1| + |y_2 — y_1|$.

Тесты

Входные данные	Выходные данные
$5\;1\;2\;4\;7\;4$	$4$
$5\;1\;2\;4\;6\;4$	$Ok$ $2$
$8\;3\;3\;7\;7\;5\;5\;3\;3$	$3$
$12\;2\;3\;4\;1\;3\;2\;5\;6\;8\;2\;1\;7$	$10$
$9\;2\;2\;3\;3\;4\;4\;7\;7\;7$	$Ok$ 2

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int[][] x = new int[2001][2001];
		int n = in.nextInt();
		int move;
		int xPos=1001, yPos=1001;
		for(int i = 0; i < n; i++) {
			move = in.nextInt();
			if(x[xPos][yPos] == 1) { 
            	System.out.print(i);
            	return;
        	}
        	else x[xPos][yPos]=1;
	        if(move == 1) {
	            xPos--;
	            yPos++;
	        }
	        if(move == 2) {
	            yPos++;
	        }
	        if(move == 3) {
	            xPos++;
	            yPos++;
	        }
	        if(move == 4) {
	            xPos++;
	        }
	        if(move == 5) {
	            xPos++;
	            yPos--;
	        }
	        if(move == 6) {
	            yPos--;
	        }
	        if(move == 7) {
	            xPos--;
	            yPos--;
	        }
	        if(move == 8) {
	            xPos--;
	        }
		}
		System.out.print("Ok" + "\n" + (Math.abs(xPos-1001)+Math.abs(yPos-1001)));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int[][] x = new int[2001][2001];

int n = in.nextInt();

int move;

int xPos=1001, yPos=1001;

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

move = in.nextInt();

if(x[xPos][yPos] == 1) {

System.out.print(i);

return;

}

else x[xPos][yPos]=1;

if(move == 1) {

xPos--;

yPos++;

}

if(move == 2) {

yPos++;

}

if(move == 3) {

xPos++;

yPos++;

}

if(move == 4) {

xPos++;

}

if(move == 5) {

xPos++;

yPos--;

}

if(move == 6) {

yPos--;

}

if(move == 7) {

xPos--;

yPos--;

}

if(move == 8) {

xPos--;

}

System.out.print("Ok" + "\n" + (Math.abs(xPos-1001)+Math.abs(yPos-1001)));

}

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

Создаем массив(изначально заполненный нулями). Задаем координаты короля по центру int xPos=1001, yPos=1001;. Затем в цикле вводим все ходы короля и проверяем был ли он уже в этой ячейке, если нет — ставим $1$, и вводим ход короля и задаем ему новые координаты, если да — выводим номер хода и завершаем программу. Если король ни разу не попал на ячейку, в которой уже был, то программа находим манхэттенское расстояние между начальными координатами и конечными. Задача решена.

Ссылки

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

e-olymp 1607. Число в обратном порядке

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

Задача

Запишите целое неотрицательное число $n$ в обратном порядке.

Вводные данные

Одно целое неотрицательное $64$-х разрядное число.

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

Выведите число в обратном порядке.

Тесты

Входные данные	Выходные данные
$1234$	$4321$
$100$	$001$
$34567$	$76543$
$10983743$	$34738901$
$98352374234$	$43247325389$

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

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);
		String c = in.nextLine();
        for (int i = c.length()-1; i >= 0; i--) {
            System.out.print(c.charAt(i));
        }
	}
}

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

String c = in.nextLine();

for (int i = c.length()-1; i >= 0; i--) {

System.out.print(c.charAt(i));

}

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

Для решения задачи вводим строку. Узнаем ее длину с помощью функции с.length(), затем циклом выводим строку в обратном порядке. Задача решена.

Ссылки

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

e-olymp 4281. Невнимательность

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

Задача

Степан успешно прошёл собеседование и вот уже как четыре месяца работает в одной из самых престижных ИТ компаний. Пришло время сдавать проект менеджеру и Степан, как настоящий студент, всё делает в последнюю ночь перед сдачей. Набирает текст Степан необычно очень быстро, но невнимательно. Вот и в этот раз последнюю часть текста он набрал не обратив внимания, что случайно нажал клавишу $caps\;lock.$ Таким образом большие буквы были набраны маленькими, а маленькие — большими. Другие символы он набрал верно. Степан настолько устал, что нет сил исправить ошибки, и он решил несколько часов поспать.

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

Вводные данные

В одной строке содержится невнимательно набранный Степаном текст. В строке не более $500$ символов.

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

Вывести исправленный текст.

Тесты

Входные данные	Выходные данные
$sCHOOL$	$School$
$hOME$	$Home$
$hAPPY nEW yEAR$	$Happy New Year$
$uNIVERSITY$	$University$
$mERRY cHRISTMAS$	$Merry Christmas$

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

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

class Main
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		String c = in.nextLine();
		String str = "";
        for (int i = 0; i < c.length(); i++) {
            if (c.charAt(i) >= 'a' && c.charAt(i) <= 'z')
                str += Character.toUpperCase(c.charAt(i));
            else
                str += Character.toLowerCase(c.charAt(i));
        }
        System.out.print(str);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

String c = in.nextLine();

String str = "";

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

if (c.charAt(i) >= 'a' && c.charAt(i) <= 'z')

str += Character.toUpperCase(c.charAt(i));

else

str += Character.toLowerCase(c.charAt(i));

}

System.out.print(str);

}

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

Для решения задачи считываем всю строку. Затем в цикле проверяем каждый символ строки на то, является ли символ маленькой буквой английского алфавита, если да, то увеличиваем букву (функция Character.toUpperCase(c.charAt(i)), если нет, то уменьшаем букву (функция Character.toLowerCase(c.charAt(i))). Складываем получаемые буквы в строку str. Выводи строку. Задача решена.

Ссылки

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

e-olymp 2214. Функция 9

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

Задача

Дана функция, аргументы которой — произвольные натуральные числа
$$f(M, N)=\begin{cases}
f(M-N, N), & \text{ npu } M>N \\
N, & \text{ npu } M=N \\
f(N-M, M), & \text{ npu } N>M
\end{cases}$$
Составить алгоритм (написать программу), вычисляющий значение функции.

Вводные данные

Два натуральных числа $n$ и $m$ $(1\leq n, m \leq 10^{18}).$

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

Искомое значение функции.

Тесты

Входные данные	Выходные данные
$6$ $3$	$3$
$12$ $12$	$12$
$126$ $98$	$98$
$10329$ $1501$	$1501$
$1008359$ $15113$	$15113$

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

import java.util.*;

class Main
{
	public static void main (String[] args) {
		Scanner in = new Scanner(System.in);
    	        long n, m;
    	        n = in.nextLong();
    	        m = in.nextLong();
    	        System.out.print(f(n, m));
	}
	static long f(long n, long m) {
		if (n % m == 0) return m;
	        if (m % n == 0) return n;
	        if (m > n) return f(m % n, n);
	        else return f(n % m , m);
	}
}

import java.util.*;

class Main

{

public static void main (String[] args) {

Scanner in = new Scanner(System.in);

long n, m;

n = in.nextLong();

m = in.nextLong();

System.out.print(f(n, m));

}

static long f(long n, long m) {

if (n % m == 0) return m;

if (m % n == 0) return n;

if (m > n) return f(m % n, n);

else return f(n % m , m);

}

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

Для решения задачи напишем функцию f. Именно эта функция и будет считать искомое значение. Из условия задачи видим, что для решения потребуется рекурсия. Для этого, если остаток от деления одного натурального числа на другое не равен нулю, то мы снова возращаемся в функцию (в зависимости от того, что больше $n$ или $m$). Это будет продолжаться до тех пор, пока остаток от деления одного натурального числа на другое не будет равен нулю (как только $n \mod m = 0$ или $m \mod n = 0,$ то функция возращает в переменную искомое значение). Задача решена.

Ссылки

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