e-olymp 8891. Ровно одно условие из двух

15/09/2020 by Владислав Стасюк

Задача

Для заданного целого числа $n$ вывести YES, если выполняется ровно одно из следующих условий и NO в противном случае.

число $n$ четное.
число $n$ отрицательное и кратное трем.

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

Одно целое число $n$.

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

Вывести YES или NO в зависимости от выполнения условий.

Тесты

ВВОД	ВЫВОД
22	YES
7	NO
-30	NO
-9	YES
0	YES

Код

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


class Main
{
    public static void main (String[] args)
    {
        int n;
        Scanner in = new Scanner(System.in);
        n = in.nextInt();

        System.out.println((n%2 == 0) == (n%3 == 0 & n<0)? "NO": "YES");
    }
}

import java.util.*;

import java.lang.*;

class Main

{

public static void main (String[] args)

{

int n;

Scanner in = new Scanner(System.in);

n = in.nextInt();

System.out.println((n%2 == 0) == (n%3 == 0 & n<0)? "NO": "YES");

}

Решение

Если оба условия выполняются или оба не выполняются, то нужно вывести «NO», а иначе — «YES».

В первом случае проверяем четность числа $n$.
Во втором случае проверяем кратность трем и является ли $n$ отрицательным.
В обеих случаях исключаем варианты, когда оба условия могли бы выполнятся, то есть исключаем отрицательные числа и кратность трем для первого, и четность числа для второго случая.

Ссылки

e-olymp
ideone

A301. Количество точек в полукругах

13/11/2017 by Вадим Гордийчук

Задача

Даны действительные числа [latex]x_1, y_1[/latex], [latex]x_2, y_2[/latex], [latex]\ldots[/latex], [latex]x_{20}, y_{20}[/latex], [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex], [latex]\left( 0 < r_1 < r_2 < \ldots < r_{11} \right)[/latex]. Пары [latex]\left( x_1, y_1 \right)[/latex], [latex]\left( x_2, y_2 \right)[/latex], [latex]\ldots[/latex] [latex]\left( x_{20}, y_{20} \right)[/latex] рассматриваются как координаты точек плоскости. Числа [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex] рассматриваются как радиусы одиннадцати полукругов в полуплоскости [latex]y > 0[/latex] с центром в начале координат. Найти количество точек, попадающих внутрь каждого полукруга (границы-полуокружности не принадлежат полукругам).

Примечание: будем рассматривать задачу с произвольным количеством точек [latex]n[/latex] и полуокружностей [latex]m[/latex].

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

[latex]n[/latex], [latex]m[/latex], [latex]x_i, y_i[/latex], [latex]i = \overline{1, n}[/latex], [latex]r_j[/latex], [latex]j = \overline{1, m}[/latex]

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

[latex]a_j[/latex] — количество точек в [latex]j[/latex]-том полукруге, [latex]j = \overline{1, m}[/latex].

Тест

Входные данные	Выходные данные
20 11 14 4 5 -4 4 90 2 4.91 8 9.0 8.3 4.111 20 49.0 0 301.419 8.01 34.5 2.1 -49.1 0.01 0.03 56 1.91 4.04918 34.49294 -1.85892 5.01674 51 214 14.94 44.09 41.4 -154 -581.49 495 14.39 -81.682 77 194.4 0.3 20.82 50.9 51 65.845 90.37 109.58 170.83 217 301.58901 314	1 6 9 9 11 12 12 12 13 15 15

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

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

20 11

14 4
5 -4
4 90
2 4.91
8 9.0
8.3 4.111
20 49.0
0 301.419
8.01 34.5
2.1 -49.1
0.01 0.03
56 1.91
4.04918 34.49294
-1.85892 5.01674
51 214
14.94 44.09
41.4 -154
-581.49 495
14.39 -81.682
77 194.4
0.3
20.82
50.9
51
65.845
90.37
109.58
170.83
217
301.58901
314

1
6
9
9
11
12
12
12
13
15
15

Иллюстрация к тесту:

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

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

class Dot
{
	public double x, y;

	public Dot() {}

	public Dot(double x, double y)
	{
		this.x = x;
		this.y = y;
	}
}

public class Main
{
	public static double euclidianDistanceToZero(Dot a)
	{
		return Math.sqrt(a.x*a.x+a.y*a.y);
	}

	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n_dot = in.nextInt();
		int n_circ = in.nextInt();

		Vector <Dot> dots = new Vector<Dot>();

		for(int i = 0; i < n_dot; ++i)
		{
			Dot a = new Dot(in.nextDouble(), in.nextDouble());
			if (a.y > 0)
				dots.addElement(a);
		}

		double rads[] = new double[n_circ];
		int amounts[] = new int[n_circ];

		for(int i = 0; i < n_circ; ++i)
		{
			rads[i] = in.nextDouble();
			amounts[i] = 0;
		}

		if (n_circ == 1)
		{
			for(int i = 0; i < dots.size(); ++i)
				if (euclidianDistanceToZero(dots.elementAt(i)) < rads[0])
					++amounts[0];
		}
		else
			for(int i = 0; i < dots.size(); ++i)
			{
				int j = n_circ;
				double r = euclidianDistanceToZero(dots.elementAt(i));
	
				if (r < rads[n_circ-1]) // if dot belongs to one of the semicircles
				{
					if (r < rads[0]) // if dot belongs to the first semicircle
						j = 0;
					else if (rads[n_circ-2] <= r) // if dot belongs to the last semicircle
						j = n_circ-1;
					else // binary search of the smallest semicircle, which includes dot
					{
						int prev_l = 0, prev_r = n_circ, k;

						while(j == n_circ)
						{
							k = (prev_l+prev_r)/2;

							if (rads[k-1] <= r && r < rads[k])
								j = k;
							else if (r >= rads[k])
								prev_l = (prev_l+k)/2;
							else //if (r < rads[k-1])
								prev_r = (prev_r+k)/2;
						}
					}

					++amounts[j]; //increasing amount of dots, which belong to [j, n_circ-1] circles.
				}
			}

		for(int accumulated_amount = 0, i = 0; i < n_circ; ++i)
		{
			accumulated_amount += amounts[i];
			amounts[i] = accumulated_amount;
		}

		for(int i = 0; i < n_circ; ++i)
			out.println(String.valueOf(amounts[i]));
		out.flush();
	}
}

100

import java.util.*;

import java.lang.*;

import java.io.*;

class Dot

{

public double x, y;

public Dot() {}

public Dot(double x, double y)

{

this.x = x;

this.y = y;

}

public class Main

{

public static double euclidianDistanceToZero(Dot a)

{

return Math.sqrt(a.x*a.x+a.y*a.y);

}

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

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n_dot = in.nextInt();

int n_circ = in.nextInt();

Vector <Dot> dots = new Vector<Dot>();

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

{

Dot a = new Dot(in.nextDouble(), in.nextDouble());

if (a.y > 0)

dots.addElement(a);

}

double rads[] = new double[n_circ];

int amounts[] = new int[n_circ];

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

{

rads[i] = in.nextDouble();

amounts[i] = 0;

}

if (n_circ == 1)

{

for(int i = 0; i < dots.size(); ++i)

if (euclidianDistanceToZero(dots.elementAt(i)) < rads[0])

++amounts[0];

}

else

for(int i = 0; i < dots.size(); ++i)

{

int j = n_circ;

double r = euclidianDistanceToZero(dots.elementAt(i));

if (r < rads[n_circ-1]) // if dot belongs to one of the semicircles

{

if (r < rads[0]) // if dot belongs to the first semicircle

j = 0;

else if (rads[n_circ-2] <= r) // if dot belongs to the last semicircle

j = n_circ-1;

else // binary search of the smallest semicircle, which includes dot

{

int prev_l = 0, prev_r = n_circ, k;

while(j == n_circ)

{

k = (prev_l+prev_r)/2;

if (rads[k-1] <= r && r < rads[k])

j = k;

else if (r >= rads[k])

prev_l = (prev_l+k)/2;

else //if (r < rads[k-1])

prev_r = (prev_r+k)/2;

}

++amounts[j]; //increasing amount of dots, which belong to [j, n_circ-1] circles.

}

for(int accumulated_amount = 0, i = 0; i < n_circ; ++i)

{

accumulated_amount += amounts[i];

amounts[i] = accumulated_amount;

}

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

out.println(String.valueOf(amounts[i]));

out.flush();

}

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

Из входного потока считываем координаты всех точек, и отсеиваем из них те, у которых координата [latex]y \le 0[/latex], так как они по условию не могут принадлежать данным полуокружностям, остальные же добавляем в вектор точек dots. После этого, создаём два массива: первый rads — массив радиусов — считываем из входного потока, второй amounts — обнуляем. В i-ой ячейке массива amounts будем хранить количество точек, которые принадлежат [latex]i[/latex]-тому, и большим чем он полукругам. После этого, используя алгоритм бинарного поиска, находим наименьший полукруг, который содержит точку, и запоминаем его номер. Затем количество точек, содержащихся в данном и больших, чем данный полукругах, увеличиваем на единицу.

После обработки вектора точек, массив amounts преобразуем в массив количеств точек, содержащихся в конкретных полукругах, так как до этой обработки он содержит количество точек, которые «аккумулированы» i-тым, и большими чем i-тый полукруги.

Таким образом, общая асимптотика программы составит [latex]O \left(m+n \cdot \log_{2}{m}\right)[/latex], где [latex]n[/latex] — количество точек, а [latex]m[/latex] — полукругов.

Ссылки

Код на ideone.com;
Условие задачи, страница 126.

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

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

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

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

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

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

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

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

Тесты

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

Решение

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

import java.util.*;

class Task2

{

public static void main (String[] args)

{

int N;

Scanner in = new Scanner(System.in);

N = in.nextInt();

if (N % 100 >= 65)

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

if (N % 20 > 15)

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

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

}

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

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

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

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

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

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

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

e-olymp 904. Увеличить на 2

11/10/2016 by Эдуард Брагар

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

Задан одномерный массив [latex]A[/latex] целых чисел. Увеличить на [latex]2[/latex] каждый неотрицательный элемент массива.

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

В первой строке задано натуральное число [latex]n[/latex] — количество элементов массива [latex]n <= 100[/latex]. Во второй строке через пробел заданы сами элементы массива, значение каждого из которых по модулю не превышает 100.

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

В единственной строке вывести через пробел [latex]n[/latex] чисел: новые значения элементов массива, в том же порядке, в котором они были заданы.

Код

import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
	public static void main (String[] args) {
		
		Scanner in = new Scanner(System.in);
			
		int n = in.nextInt();
		int a = 0;
			
		for(int i = 0; i < n; i++){
			a = in.nextInt();
			System.out.printf("%d", (a < 0)? a : a + 2);	
		}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int a = 0;

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

a = in.nextInt();

System.out.printf("%d", (a < 0)? a : a + 2);

}

Тесты

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

Решение

Вводим число [latex]n[/latex]. Используем цикл for и вводим число [latex]a[/latex]. Выводим неотрицательное число [latex]a[/latex], либо без изменений, либо увеличенное на два.
e-olymp.com
ideone.com

e-olimp 7365 — Молоко и пирожок

01/07/2016 by Иоанна Васильева

Задача на e-olimp.

Условие

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

Решение

Возьмем количество пирожков за счетчик. Используя for найдем количество пирожков для детей, вес которых не превышает 30кг. По количеству пирожков мы можем найти количество упаковок молока. При этом мы можем получить не целое число. Чтобы избежать этого, используем метод ceil из класса Math для округления до целого.

Код

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		 Scanner in = new Scanner(System.in);
		 int n = in.nextInt();
		 int pie = 0; 
  		 for (int i=0; i<n; i++)
  		 {
  		 	int w = in.nextInt();
  		 	if (w < 30)
  		 		pie++;
  		 }
  		 int pack = (int)Math.ceil((pie*0.2)/0.9);
  		 System.out.print(pack+ " " + pie);
	}
}

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int pie = 0;

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

{

int w = in.nextInt();

if (w < 30)

pie++;

}

int pack = (int)Math.ceil((pie*0.2)/0.9);

System.out.print(pack+ " " + pie);

}

Ссылка на Ideone.

Тест

Входящие данные		Выходящие данные
n	w(вес)	pack	pie
4	30 29 40 25	1	2
7	21 20 22 29 26 27 26	2	7

Проверка решения на e-olimp.

e-olymp 388. Превращение

30/06/2016 by Иоанна Васильева

Задача на e-olimp.

Условие

Возьмем какое-нибудь натуральное число $N$ . Будем изменять его следующим образом: если число четное, то разделим его на 2, если нечетное, прибавим 1. После нескольких таких изменений мы всегда получаем число 1. Например, из числа 11 получается число 12, затем 6, 3, 4, 2 и, наконец, 1. Таким образом, для получения 1 из 11 нужно проделать 6 изменений.

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

Число $N$ (1 ≤ $N$ ≤ 10⁹).

Решение

Пусть $N$ – это число, которое мы будем изменять, а $counter$ – количество превращений. Цикл должен выполняться до того момента, пока $N \neq 1$ . Чтобы проверить число на чётность/нечётность, делим его по модулю и сравниваем остаток с нулём. Если число – чётное, то делим его на 2, в противном случае – добавляем единицу, и при выполнении каждого действия, увеличиваем количество превращений на 1.

Код на Ideone.

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main {
  public static void main (String[] args) {
  	Scanner x = new Scanner(System.in);
	int n = x.nextInt();
	int counter = 0;
	if (n >= 1){
		while (n != 1) {
			counter++;
			if (n % 2 == 0) n = n / 2;
			else n++;
 		}
 		System.out.print(counter);
 	} else System.out.print( "Wrong number" );
  }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main (String[] args) {

Scanner x = new Scanner(System.in);

int n = x.nextInt();

int counter = 0;

if (n >= 1){

while (n != 1) {

counter++;

if (n % 2 == 0) n = n / 2;

else n++;

}

System.out.print(counter);

} else System.out.print( "Wrong number" );

}

Тест

Входные данные	Выходные данные
-5	Wrong number
1	0
6	4

Ссылка на решение на e-olimp.

А58а

30/06/2016 by Иоанна Васильева

Задача. Дано действительное число $a$ . Для функции $f\left(x \right)$ , график которой изображен, вычислить $f\left(a \right)$ .

58a

Для решения данной задачи требуется лишь проверка знака числа $a$ . Если $a> 0$ , то $f\left(a \right)$ вычисляется как $-a^{2}$ , а если $a< 0$ , то $f\left(a \right)$ равна $-a$ . При $a=0$ , $f\left(a \right)=0$ .

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

class Ideone{
	public static void main (String[] args){
		Scanner x = new Scanner(System.in);
		int a = x.nextInt();
		int y;
		if(a>0)   y = -a*a;
		else    y = -a;
		System.out.print(y);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone{

public static void main (String[] args){

Scanner x = new Scanner(System.in);

int a = x.nextInt();

int y;

if(a>0) y = -a*a;

else y = -a;

System.out.print(y);

}

Код на Ideone.

Тест

Входные данные	Выходные данные
-7	7
7	-49
0	0