e-olymp 2165. Лишние пробелы

14/07/2017 by Гуменюк Марина

Задача

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

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

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

Дана строка s. Строка содержит только латинские буквы и пробелы.

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

Строка без лишних пробелов.

Тесты

№	Входные данные	Выходные данные
1	«Alexandr Sergeevich Pushkin»	«Alexandr Sergeevich Pushkin»
2	«JohnSnow»	«JohnSnow»
3	» Mr Charlie Chaplin »	«Mr Charlie Chaplin»
4	«Mechnikov University»	«Mechnikov University»
5	«Daenerys Targaryen»	«Daenerys Targaryen»

Код

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

public class Main
{
	public static void main(String[] args)
	{
		Scanner in = new Scanner(System.in);
		String s = in.nextLine();
		s = s.replaceAll(" +", " ");
        if(s.charAt(0) == ' ') 
	    {
	        s = s.substring(1, s.length());
	    }
		if(s.charAt(s.length()-1) == ' ')
		{
	        s = s.substring(0, s.length()-1);
		}
		System.out.print(s);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

public class Main

{

public static void main(String[] args)

{

Scanner in = new Scanner(System.in);

String s = in.nextLine();

s = s.replaceAll(" +", " ");

if(s.charAt(0) == ' ')

{

s = s.substring(1, s.length());

}

if(s.charAt(s.length()-1) == ' ')

{

s = s.substring(0, s.length()-1);

}

System.out.print(s);

}

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

Решение

Вводим строку s, которая содержит латинские буквы и пробелы. Используем метод replaceAll() для удаления лишних пробелов. Чтоб не удалить последний оставшийся пробел используем regex " +", " " . «Прочитать» его по-русски можно так: " +" — выделить 1 или больше пробелов до символа, не являющимся пробелом и " " — заменить выделенную последовательность на 1 пробел. Проверяем символы на концах строки на наличие пробела. Перезаписываем подстроку без пробелов в строку s.

Затем выводим полученную строку.

Ю4.3

13/07/2017 by Гуменюк Марина

Задача

Центрирование массива. От каждого из заданных чисел [latex]{x}_{1}, {x}_{2}, \ldots, {x}_{m}[/latex] отнять их среднее арифметическое [latex]\overline{x}_{i} = {x}_{i}[/latex] — [latex]{x}_{cp}[/latex], [latex]i = 1, 2[/latex], … , [latex]m[/latex].

[latex]\overline{x}[/latex] = [latex]1/m[/latex];
[latex]E[/latex] от [latex]m[/latex] при [latex]i = 1 (x_1)[/latex];
[latex]{x}_{i}[/latex] = [latex]{x}_{i}[/latex] — [latex]\overline{x}[/latex]; [latex]i = 1, 2[/latex], … , [latex]m[/latex]

Результаты разместить на месте исходных данных.

Тесты

Количество элементов в массиве — m	Массив	Результат
2	2 5	-1,5 1,5
2	2 6	-2 2
7	2 6 -3 5 1 0 0	0.43 4.43 -4.57 3.43 -0.57 -1.57 -1.57

Код

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int m = in.nextInt();//количество элементов в массиве
		double sum = 0; // сумма чисел массива
		
		double[] arr = new double[m];
		for(int i = 0; i < m; i++)
		{
			arr[i] = in.nextDouble();
		}
		
		for (int i = 0; i < m; i++)
		{
			sum += arr[i];//вводим следующее число
		}

		for (int i = 0; i < m; i++)
		{
			arr[i] = arr[i] - (sum / m);//результат
			System.out.println(arr[i]);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int m = in.nextInt();//количество элементов в массиве

double sum = 0; // сумма чисел массива

double[] arr = new double[m];

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

{

arr[i] = in.nextDouble();

}

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

{

sum += arr[i];//вводим следующее число

}

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

{

arr[i] = arr[i] - (sum / m);//результат

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

}

Протестированный код можно увидеть тут.

Решение

Объявляем массив типа double размерностью m. Считываем размерность из первой строки ввода, конвертируем из типа string в тип int; затем считываем элементы массива из второй строки ввода (их конвертируем в double — для точности вычислений). В циклах: находим сумму введенных чисел, затем их среднее арифметическое, затем высчитываем новые значения элементов массива, вычитая от каждого из них среднее арифметическое всего массива. Записываем новые значения поэлементно в исходный массив arr[ ]. Выводим arr[ ].

MS 7. Средняя зарплата

13/07/2017 by Гуменюк Марина

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

Входные данные
Фамилия работника name и величина его зарплаты salary.

Выходные данные
Средняя зарплата по компании.

Тесты

Входные данные			Выходные данные
	name	salary	totalSalary/employeesNum
1.	Ivanov	100	100
1.	Ivanov	300	200
2.	Smirnov	150	150
3.	Popov	200	200

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

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		String name;
		double salary, totalSalary=0, employeesNum=0;
		Scanner in = new Scanner(System.in);
		
		while (in.hasNext())
		{
			name = in.next();
			salary = in.nextDouble();
			totalSalary+=salary;
			employeesNum++;
		}
		System.out.println(totalSalary/employeesNum);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Ideone

{

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

{

String name;

double salary, totalSalary=0, employeesNum=0;

Scanner in = new Scanner(System.in);

while (in.hasNext())

{

name = in.next();

salary = in.nextDouble();

totalSalary+=salary;

employeesNum++;

}

System.out.println(totalSalary/employeesNum);

}

Пояснение

С потока данных считывается первое значение и записывается в переменную name. Затем считывается заработная плата и записывается в переменную sal. В переменную total записывается общая полученная сумма работниками, увеличивается счетчик количества выплат sum. Средняя зарплата считается по формуле среднего арифметического: [latex]x = \frac{total}{sum}[/latex] и выводится потоком вывода.

Ссылка на код по тесту 1.

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

e-olymp 128. Счастливые билеты

10/07/2017 by Гуменюк Марина

Задача. Подсчитайте количество счастливых билетов, у которых сумма первых трёх цифр равна N(N≤27). Счастливым билетом называется билет с шестизначным номером, у которого сумма первых трёх цифр равна сумме трёх последних.

Тесты

Число N	3	27	26	1	10
Количество билетов	100	1	9	9	3969

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

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, c = 0;
		Scanner in = new Scanner(System.in);
		String reader = in.nextLine();
		n = Integer.parseInt(reader);
  		
  		for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа
  		{
     		for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры
     		{
        		if ( n - i - j >= 0 && n - i - j < 10 ) //условие для третьей цифры
        		{
					c++;//подсчет подходящих номеров
				} 
    		}
  		}
  		System.out.println(c*c); //увеличение количества в c раз для шестизначного числа
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Ideone

{

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

{

int n, c = 0;

Scanner in = new Scanner(System.in);

String reader = in.nextLine();

n = Integer.parseInt(reader);

for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа

{

for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры

{

if ( n - i - j >= 0 && n - i - j < 10 ) //условие для третьей цифры

{

c++;//подсчет подходящих номеров

}

System.out.println(c*c); //увеличение количества в c раз для шестизначного числа

}

Код можно увидеть тут.

Алгоритм

Любой шестизначный номер мы можем представить как 2 трехзначных номера.

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

Когда в цикле встречается подходящая комбинация, мы увеличиваем счетчик [latex]c[/latex] на 1. Поскольку на самом деле номер шестизначный, то каждой удачной комбинации в первой его половине будет соответствовать [latex]c[/latex] комбинаций во второй. Следовательно, искомое число счастливых билетов будет равно [latex]c^2[/latex].

Ссылка на авторское решение задачи.

e-olymp 63. Анфиса и цветы

06/07/2017 by Гуменюк Марина

Задача. Анфиса и цветы

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

Мурзик одну из цветочных клумб сделал в виде шахматной доски размерами [latex]m[/latex] на [latex]n,[/latex] в каждой клеточке которой растет какой-то цветок. Иногда на эту клумбу он выводит на прогулку Анфису (да, не удивляйтесь, они действительно друзья). Анфиса, начиная всегда с верхнего левого угла передвигается по клумбе к правому нижнему и собирает цветы, причем таким образом, чтобы каждый раз проходить новым маршрутом, а Мурзик на выходе вручает ей кусочек сыра.
Посчитать, какое наибольшее количество кусочков сыра получит Анфиса, если она все время старается сохранить как можно больше цветов. При каждом очередном своем проходе Анфиса обязательно должна собрать как минимум один цветок.

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

В одной строке через пробел заданы два числа [latex]m[/latex] на [latex]n.[/latex]

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

Вывести наибольшее количество кусочков сыра, которые может получить Анфиса.
Также условие задачи можно посмотреть здесь.

<р2>Реализация

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		String reader = in.nextLine();
		String[] s = reader.split(" ");

		long m = Long.parseLong(s[0]);		
		long n = Long.parseLong(s[1]);	
		long p = (m * n - (m + n - 1)) + 1;
	
		System.out.println(p);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

String reader = in.nextLine();

String[] s = reader.split(" ");

long m = Long.parseLong(s[0]);

long n = Long.parseLong(s[1]);

long p = (m * n - (m + n - 1)) + 1;

System.out.println(p);

}

Проверить код можно тут.

Тестирование

№	Входные данные (m, n)	Выходные данные
1	2, 3	3
2	3, 3	5
3	3, 4	7
4	4, 3	7
6	5, 7	25

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

Задана цветочная клумба в виде шахматной доски размерами [latex]m[/latex] на [latex]n[/latex]. Очевидно, что количество цветов на данной клумбе равно [latex]m\cdot n[/latex]. Пусть Анфиса, совершая свое очередное передвижение, начиная с левого верхнего угла клумбы и направляясь к правому нижнему, съедает [latex](m-1)\cdot (n-1)[/latex] цветов, так как, согласно условию задачи, Анфиса обязательно должна собрать как минимум один цветок при каждом проходе. После каждого такого прохода на выходе она получает один кусочек сыра.

Следовательно, имеет место следующая формула: [latex]p=(m-1)\cdot (n-1)+1[/latex], где [latex]p[/latex] — наибольшее количество кусочков сыра, которое может получить Анфиса. Действительно, если [latex]m=2[/latex], [latex]n=3[/latex], то получаем [latex]p=3[/latex].

KM17. Крестьянин на развилке

04/07/2017 by Гуменюк Марина

Задача из журнала «Квант» №4 1970 г.

Крестьянин, подойдя к развилке двух дорог, расходящихся под углом 60°, спросил: «Как пройти в село [latex]NN[/latex]?». Ему ответили: «Иди по левой дороге до деревни [latex]N[/latex] — это в восьми верстах отсюда,— там увидишь, что направо под прямым углом отходит большая ровная дорога,— это как раз дорога в [latex]NN[/latex]. А можешь идти другим путём: сейчас по правой дороге; как выйдешь к железной дороге,— значит, половину пути прошёл; тут поверни налево и иди прямо по шпалам до самого [latex]NN[/latex]». — «Ну, а какой путь короче-то будет?» — «Да всё равно, что так, что этак, никакой разницы.» И пошёл крестьянин по правой дороге. Сколько вёрст ему придётся идти до [latex]NN[/latex]? Больше десяти или меньше? А если идти от развилки до [latex]NN[/latex] напрямик? (Все дороги прямые)

Более лаконичная версия:
Крестьянин стоит на развилке дорог, которые расходятся под углом 60°, и хочет попасть в село [latex]NN[/latex]. Выбрав левую дорогу, он должен будет пройти n вёрст прямо, затем повернуть направо под прямым углом и идти до [latex]NN[/latex]. Выбрав правую, он должен будет преодолеть участок некоторой длины прямо, затем повернуть налево и пройти такой же по длине участок. При этом известно, что длины левой и правой дорог одинаковы. От нас требуется найти длину пути по одной из дорог и длину пути напрямик.

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

Длина пути от развилки до [latex]N[/latex].

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

Длины путей по дороге и напрямик.

Тесты

№	Входные данные	Выходные данные
	[latex]n[/latex]	[latex]{ s }_{ 1 }[/latex]	[latex]{ s }_{ 2 }[/latex]
1	0	0	0
2	8	11.0416	8.55871
3	0.5	0.690101	0.534919
4	21	28.9843	22.4666
5	13.45	18.5637	14.3893

Решение

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double s1, s2, n, x;
		Scanner in = new Scanner(System.in);
		n = Double.parseDouble(in.nextLine());
		x = n * (5 - Math.sqrt(3) - Math.sqrt(6 * Math.sqrt(3) - 4))/(8 * (2 - Math.sqrt(3)));
		s1 = 4 * x; //Длина пути по дороге
		s2 = Math.sqrt(2 * (n * n - 4 * x * n + 8 * x * x));//Длина пути напрямую
		System.out.println(s1 + " " + s2);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Ideone

{

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

{

double s1, s2, n, x;

Scanner in = new Scanner(System.in);

n = Double.parseDouble(in.nextLine());

x = n * (5 - Math.sqrt(3) - Math.sqrt(6 * Math.sqrt(3) - 4))/(8 * (2 - Math.sqrt(3)));

s1 = 4 * x; //Длина пути по дороге

s2 = Math.sqrt(2 * (n * n - 4 * x * n + 8 * x * x));//Длина пути напрямую

System.out.println(s1 + " " + s2);

}

Код можно увидеть и проверить его правильность тут: ideone

Пояснение

Обозначим развилку как [latex]A[/latex] как, село [latex]B[/latex], место пересечения правой дороги с рельсами как [latex]D[/latex], и проведём [latex]DH \bot AB[/latex] и [latex]DK \bot BC[/latex].

Пусть [latex]AD = 2x[/latex], тогда [latex]AH = x[/latex]; Из треугольника [latex]AHD[/latex]: [latex]BK = DH = x\cdot\sqrt { 3 }[/latex];

[latex]KC=KB-BC=n+x \cdot \left(\sqrt{3}-4\right)[/latex].
Из треугольника [latex]CKD[/latex] по теореме Пифагора: [latex]{KC}^{2}+{KD}^{2}={CD}^{2}[/latex]. Подставив значения, раскрыв скобки и проведя математические преобразования, получим квадратное уравнение [latex]{x}^{2}\cdot (-4\sqrt{3}+8)-x \cdot n \cdot (\sqrt{3}-5)+{n}^{2}=0[/latex].
Найдём дискриминант [latex]D={n}^{2}\cdot(6\sqrt{3}-4)[/latex]. [latex]KD=n-x[/latex] и [latex]KD > 0[/latex], значит, [latex]n-x > 0[/latex] и [latex]x < n[/latex]. Для первого из корней полученного квадратного уравнения это условие не выполняется, соответственно, мы имеем лишь один корень. Найдя его, мы найдём половину длины [latex]AD[/latex]. Выведем формулу для его расчёта:[latex]x=\frac{n\cdot(5-\sqrt{3}-\sqrt {6\cdot\sqrt {3}-4 })}{8\cdot (2-\sqrt {3})}[/latex] Тогда длина пути по дороге будет равна [latex]4\cdot x[/latex], а длину пути напрямик мы найдём из треугольника [latex]ABC[/latex] по теореме Пифагора: [latex]{s}_{2}=\sqrt{2\cdot ({n}^{2}-4x\cdot n+8{n}^{2})}[/latex].

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Author Archives: Гуменюк Марина

e-olymp 2165. Лишние пробелы

Ю4.3

MS 7. Средняя зарплата

e-olymp 128. Счастливые билеты

e-olymp 63. Анфиса и цветы

Задача. Анфиса и цветы

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

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

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

Тестирование

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

KM17. Крестьянин на развилке