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-olymp 165. Симметрия

16/12/2018 by Даниил Крутоголов

Задача

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

1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;

2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];

3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].

Напишите программу, которая помогла бы автоматизировать подбор цвета бусинки в ряду по её порядковому номеру.

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

В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

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

В первой строке одно целое число – номер цвета заданной бусинки.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]10[/latex]	[latex]2[/latex]
2	[latex]116[/latex]	[latex]3[/latex]
3	[latex]1[/latex]	[latex]1[/latex]
4	[latex]454[/latex]	[latex]2[/latex]
5	[latex]12301230[/latex]	[latex]2[/latex]

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

import java.util.Scanner;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m;
		double k;
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = (int)(Math.log(n)/Math.log(2));
		k = (double)(Math.log(n)/Math.log(2));
		while (m != k){
			n = (int)(n - (Math.pow(2,m)));
			m = (int)(Math.log(n)/Math.log(2));
			k = (double)(Math.log(n)/Math.log(2));
		}
	System.out.print(m + 1);
	}
}

import java.util.Scanner;

class Main

{

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

{

int n, m;

double k;

Scanner scan = new Scanner(System.in);

n = scan.nextInt();

m = (int)(Math.log(n)/Math.log(2));

k = (double)(Math.log(n)/Math.log(2));

while (m != k){

n = (int)(n - (Math.pow(2,m)));

m = (int)(Math.log(n)/Math.log(2));

k = (double)(Math.log(n)/Math.log(2));

}

System.out.print(m + 1);

}

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

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Mif 2. Максимум из трех

12/12/2017 by Сидоровский Дмитрий

Задача

Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Получить [latex]max (x, y, z)[/latex].

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

Действительные числа $latex x,y,z$.

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

[latex]max (x, y, z)[/latex]

Тесты

x	y	z	max
8	3	5	8
9	16	7	16
5	125	150	150

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

class Ideone
{
  public static void main (String[] args) throws java.lang.Exception
  {
    double x, y, z;
    Scanner in = new Scanner(System.in);
    x = in.nextDouble();
    y = in.nextDouble();
    z = in.nextDouble();
    double max = z;
    if ( y > max)
      {
        max = y;
      }
    if ( x > max ) 
      {
        max = x;
      }
    System.out.println(max);
  }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double x, y, z;

Scanner in = new Scanner(System.in);

x = in.nextDouble();

y = in.nextDouble();

z = in.nextDouble();

double max = z;

if ( y > max)

{

max = y;

}

if ( x > max )

{

max = x;

}

System.out.println(max);

}

Решение

Пусть даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Нужно получить [latex]max(x,y,z)[/latex]. Для этого вводим [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Предполагаем, что $latex z$ хранит максимальное значение. Затем, используя оператор if, сравниваем $latex y, x$. Выводим максимальное значение.

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

Mif 1

06/07/2017 by Болдин Валерий

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

Даны действительные числа [latex]x, y[/latex]. Получить [latex]max(x,y)[/latex].

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

Два действительных числа — [latex]x[/latex] и [latex]y[/latex].

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

Число, являющееся максимумом из двух чисел — [latex]maxOfTwo[/latex]

Тесты

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

Решение:

class SecondLab
{
	public static void main (String[] args)
	{
		double x, y, maxOfTwo;
		Scanner input = new Scanner(System.in);
		x = input.nextDouble();
		y = input.nextDouble();
		if(x>y){
			maxOfTwo = x;
		}else{
			maxOfTwo = y;
		}
		System.out.println(maxOfTwo);
	}
}

class SecondLab

{

public static void main (String[] args)

{

double x, y, maxOfTwo;

Scanner input = new Scanner(System.in);

x = input.nextDouble();

y = input.nextDouble();

if(x>y){

maxOfTwo = x;

}else{

maxOfTwo = y;

}

System.out.println(maxOfTwo);

}

Альтернативное решение:

class SecondLab
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double x, y, maxOfTwo;
		Scanner input = new Scanner(System.in);
		x = input.nextDouble();
		y = input.nextDouble();
		maxOfTwo = x>y? x : y;
		System.out.println(maxOfTwo);
	}
}

class SecondLab

{

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

{

double x, y, maxOfTwo;

Scanner input = new Scanner(System.in);

x = input.nextDouble();

y = input.nextDouble();

maxOfTwo = x>y? x : y;

System.out.println(maxOfTwo);

}

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

Объявляем три переменные типа int — x, y, maxOfTwo . Вводим с клавиатуры значения для x и y . После чего с помощью условного оператора if-else проверяем x>y . Если истинно, присваиваем переменной maxOfTwo значение переменной x , а иначе MaxOfTwo = y . Выводим значение MaxOfTwo с помощью функции System.out.println() .

Описание альтернативного решения:

Объявляем три переменные типа int — x, y, maxOfTwo . Вводим с клавиатуры значения для x и y . Используя тернарный оператор ?: проверяем истинность выражения x>y и присваиваем результат операции переменной maxOfTwo . Выводим значение MaxOfTwo с помощью функции System.out.println() .

Mif 5

02/07/2017 by Присяжный Михаил

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

Даны действительные числа [latex]x, y, z[/latex]. Вывести наименьшее и наибольшее из них. Если наименьших или наибольших чисел окажется несколько, то укажите в скобках количество.

Входные данные: действительные числа [latex]x, y, z.[/latex]

Выходные данные: Максимальное значение (Highest value), количество максимальных значений (Count of highest values), минимальное значение (Lowest value), количество минимальных значений (Count of lowest values)

Тесты

	Входные данные	Выходные данные
№	[latex]x, y, z[/latex]	Максимум	Количество максимумов	Минимум	Количество минимумов
1	10	20	1	10	2
2	10
3	20

Решение

import java.util.Scanner;

 class Task2 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        float number;
        float max = 0;
        float min = 0;
        int countMax = 0;
        int countMin = 0;

        for (int x = 0; x < 3; x++) {
            number = input.nextInt();

            if (x == 0 || number > max) {
                countMax = 1;
                max = number;
            } else if (number == max) {
                countMax++;
            }
            if (x == 0 || number < min) {
                countMin = 1;
                min = number;
            } else if (number == min) {
                countMin++;
            }
        }

        System.out.println("Highest value: " + max);

        System.out.println("Count of highest values: " + countMax);

        System.out.println("Lowest value: " + min);

        System.out.println("Count of lowest values: " + countMin);
    }
}

import java.util.Scanner;

class Task2 {

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

float number;

float max = 0;

float min = 0;

int countMax = 0;

int countMin = 0;

for (int x = 0; x < 3; x++) {

number = input.nextInt();

if (x == 0 || number > max) {

countMax = 1;

max = number;

} else if (number == max) {

countMax++;

}

if (x == 0 || number < min) {

countMin = 1;

min = number;

} else if (number == min) {

countMin++;

}

System.out.println("Highest value: " + max);

System.out.println("Count of highest values: " + countMax);

System.out.println("Lowest value: " + min);

System.out.println("Count of lowest values: " + countMin);

}

Ссылка на решение задания на онлайн компиляторе Ideone.com

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

Для нахождения нахождения найбольшего max и найменьшего min значений используем цикл for. Если текущее число больше максимального, то ставим счетчик countMax на 1 и сохраняем новое максимальное значение max. Если последующее число равно текущему максимальному max, то увеличиваем счетчик countMax. Аналогично и для поиска найменьшего min значения.

ML36. Движение катера

28/06/2017 by Черноглазов Николай

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

Катер движется по течению реки из пункта A в пункт B и обратно с собственной скоростью $latex v$ км/час. Скорость течения постоянна — $latex u$ км/час. Расстояние между пунктами составляет $latex s$ км. Для любых действительных неотрицательных значений расстояния и скоростей вычислить время в пути $latex t_{boat}$.

Тесты

Входные данные: физические величины $latex v$, $latex u$, $latex s$

Выходные данные: физическая величина $latex t_{boat}$

№	Входные данные	Выходные данные
1	3 2 10	12.0
2	1.4 0.4 3.6	5.6
3	3 6 10	Infinity
4	2 1 0	0.0

Код

import java.util.Scanner;

class ML36
{
	public static void main (String[] args)
	{
		double v, u, s, t;
		double inf = Double.POSITIVE_INFINITY;
		Scanner scanner = new Scanner(System.in);
		
		v = scanner.nextDouble();
		u = scanner.nextDouble();
		s = scanner.nextDouble();
		
		t = (v>=u) ? s/(v+u) + s/(v-u) : inf;
		
		System.out.println(t);
	}
}

import java.util.Scanner;

class ML36

{

public static void main (String[] args)

{

double v, u, s, t;

double inf = Double.POSITIVE_INFINITY;

Scanner scanner = new Scanner(System.in);

v = scanner.nextDouble();

u = scanner.nextDouble();

s = scanner.nextDouble();

t = (v>=u) ? s/(v+u) + s/(v-u) : inf;

System.out.println(t);

}

Код доступен на ideone

Пояснение

Скорость катера, когда он идет по течению, равна $latex (v+u)$, а когда против — $latex (v-u)$. Время $latex t$ вычисляется по формуле $latex t = \frac{s}{v}\\ $, где $latex s$ — расстояние, $latex v$ — скорость, соответственно общее время пути катера составит $latex t_{boat} = {\frac{s}{v+u}\\+\frac{s}{v-u}\\} $. При этом время — величина неотрицательная, а делитель дроби не должен быть нулевым, соответственно имеем ограничение $latex v-u > 0, v > u $.

А136и

07/07/2016 by Игорь Варламов

Задача: Даны натуральное число n, действительные числа [latex]k_{1}, k_{2}, \dots, k_{n}[/latex] Вычислить [latex]\frac{k_{1}}{0!} + \frac{k_{2}}{1!} + \dots + \frac{k_{n}}{(n-1!)} [/latex]

Тесты

Число-n	Действительные числа	Результат
5	4 5 6 7 8	13,5
7	5 4 7 9 2 8 3	14,1542
3	6 9 3	16,5

Код:

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

class Ideone{
	public static void main (String[] args) throws java.lang.Exception{
		double k;
		double d = 0;
		int b=1;
		Scanner x = new Scanner(System.in);
		int n=x.nextInt();
		for (int i=1;i<=n;i++){
			k = x.nextDouble();
			k/=b;
			b*=i;
			d+=k;
		}
		System.out.print(d);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone{

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

double k;

double d = 0;

int b=1;

Scanner x = new Scanner(System.in);

int n=x.nextInt();

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

k = x.nextDouble();

k/=b;

b*=i;

d+=k;

}

System.out.print(d);

}

Решение:

Вводим n, k (действительные числа);
Получаем очередное действительное число k.
Делим на факториал и суммируем;

Решение на Ideone

A278

06/07/2016 by Дарья Пиндус

Задача A278

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

Даны натуральные числа $n_{1},\dots,n_{m}$ , действительные числа $x_{1},\dots,x_{m}$ . Вычислить $\frac{n_{1}\cdot x_{1}+\dots+n_{m}\cdot x_{m}}{n_{1}+\dots+n_{m}}$ .

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

№	Входные данные	Выходные данные
1.	1 2 4 -1	-0.4
2.	1 2 3 4 5 0.6	1.88889
3.	5 -2 1 0.2 3 -3 2 0	-1.70909
4.	10 3.3 4 0.4 6 0.01 8 1 1 8	1.7469
5.	3 -0.5 2 -0.4 1 -0.3 5 32 11 5 20 -1	4.58095

Код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class A278 {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner scanner = new Scanner(System.in);
		double numerator = 0;
		int denominator = 0;
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			double x = scanner.nextDouble();
			numerator += n * x;
			denominator += n;
		}
		double result = numerator / denominator;
		System.out.println(result);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class A278 {

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

Scanner scanner = new Scanner(System.in);

double numerator = 0;

int denominator = 0;

while (scanner.hasNext()) {

int n = scanner.nextInt();

double x = scanner.nextDouble();

numerator += n * x;

denominator += n;

}

double result = numerator / denominator;

System.out.println(result);

}

Алгоритм решения (потоковая обработка)

Считываем числа до конца входного потока и поочередно записываем их в переменные $n$ и $n$ соответственно.
Пока вводятся данные:

Вычисляем значение выражения $n_1\cdot x_1+\dots+n_m\cdot x_m$ , накапливая сумму в числитель $n$ .
Вычисляем значение выражения $n_1+\dots+n_m$ , накапливая сумму в делителе $n$ .
Находим результат $n$ от деления $n$ на $n$

Код на ideone.com