e-olymp 971. Задача Иосифа Флавия

27/12/2018 by Дима Мороз

Задача

Существует легенда, что Иосиф Флавий — известный историк первого века — выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным — он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю.

В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от $1$ до $N$, и будем исключать каждого $k$-ого до тех пор, пока не уцелеет только один человек. (Например, если $N=10$, $k=3$, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним — 5-й, и потом 10-й. Таким образом, уцелеет 4-й.)

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

Во входном файле даны натуральные числа $N$ и $k$. $1 ≤ N ≤ 500, 1 ≤ k ≤ 100$.

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

Выходной файл должен содержать единственное число — номер уцелевшего человека.

Тесты

Входные данные	Выходные данные
10 3	4
17 5	11
76 32	58

Код решения

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

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), k = in.nextInt();
		ArrayList<Integer> ns = new ArrayList<Integer>(n);
		for (int i = 1; i <= n; i++) 
			ns.add(i);
		
		int i = 0, j = 0;
		while(n > 1) {
			j = (++j) % k;
			if(j == 0) {
				n--;
				ns.remove(i);
			} else {
				i = (++i) % n;
			}
		}
		System.out.println(ns.get(0));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt(), k = in.nextInt();

ArrayList<Integer> ns = new ArrayList<Integer>(n);

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

ns.add(i);

int i = 0, j = 0;

while(n > 1) {

j = (++j) % k;

if(j == 0) {

n--;

ns.remove(i);

} else {

i = (++i) % n;

}

System.out.println(ns.get(0));

}

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

Все делается по алгоритму: убирается каждый $k$-тый человек до тех пор, пока не останется один.

Ссылки

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

e-olymp 1281. Простая задачка Шарика

27/12/2018 by Дима Мороз

Задача

Ещё задолго до того, как Шарик нашёл умную книжку, утерянную Печкиным, когда он только начинал свои эксперименты по распиливанию шахматных досок, когда ещё на шахматной доске белые поля были белыми, а чёрные – чёрными, он задал одну из своих первых задачек Матроскину.

«Сколько разных последовательностей длины $n$ можно составить из клеток распиленных шахматных досок, если ни в одной из последовательностей никакие три белых поля не должны идти подряд«?

Матроскин так и не решил ещё эту задачку, так что ваша задача помочь ему.

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

Длина последовательности $n (n ≤ 64)$.

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

Вывести количество указанных последовательностей.

Тесты

Входные данные	Выходные данные
1	2
2	4
3	7
4	13

Код задачи

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 x1, x2, x3, x4 = 0;
        long n = in.nextLong();
        x1 = 2;
        x2 = 4;
        x3 = 7;
        for (int i = 3; i < n; i++) {
            x4 = x1 + x2 + x3;
            x1 = x2;
            x2 = x3;
            x3 = x4;    
        }
        if (n == 1) 
            System.out.println(2); 
        else if (n == 2) 
            System.out.println(4); 
        else if (n == 3)
            System.out.println(7); 
        else 
            System.out.println(x4);
    }
}

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 x1, x2, x3, x4 = 0;

long n = in.nextLong();

x1 = 2;

x2 = 4;

x3 = 7;

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

x4 = x1 + x2 + x3;

x1 = x2;

x2 = x3;

x3 = x4;

}

if (n == 1)

System.out.println(2);

else if (n == 2)

System.out.println(4);

else if (n == 3)

System.out.println(7);

else

System.out.println(x4);

}

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

Для решения задачи воспользуемся рекуррентным соотношением $f(n)=f(n−1)+f(n−2)+f(n−3)$ $f (n) = f (n - 1) + f (n - 2) + f (n - 3)$ , где $f$ — функция, возвращающая ответ на поставленную задачу. Из условия следует, что для любой последовательности рассматривать следует только три варианта её последних элементов: …Ч, …ЧБ, …ЧББ (где Ч — чёрная клетка, Б — белая), так как в случае, если конец последовательности квадратов содержит только чёрный квадрат, чёрный и белый или чёрный и два белых, то нарушить последовательность могли только предшествующие этим окончаниям, которые имеют длины $1, 2,$ и $3$ соответственно, последовательности. Именно это и влечёт справедливость указанного выше рекуррентного соотношения. Значения $f(n)$ при $n≤3$ можно вычислить вручную и сохранить, а остальные вычислять в цикле с использованием предыдущих, вплоть до получения требуемого.

Ссылки

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

e-olymp 1872. Снеговики

27/12/2018 by Дима Мороз

Задача

Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и снеговиков: клонирования снеговиков. Вы конечно знаете, но мы вам напомним, что снеговик состоит из нуля или более вертикально поставленных друг на друга шаров, а клонирование — это процесс создания идентичной копии (клона).

В местечке Местячково учитель Андрей Сергеевич Учитель купил через интернет-магазин «Интернет-магазин аппаратов клонирования» аппарат для клонирования снеговиков. Теперь дети могут играть и даже играют во дворе в следующую игру. Время от времени один из них выбирает понравившегося снеговика, клонирует его и:

либо добавляет ему сверху один шар;
либо удаляет из него верхний шар (если снеговик не пустой).

Учитель Андрей Сергеевич Учитель записал последовательность действий и теперь хочет узнать суммарную массу всех построенных снеговиков.

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

Первая строка содержит количество действий $n (1 ≤ n ≤ 200000)$. В строке номер $i + 1$ содержится описание действия:

$t m$ — клонировать снеговика номер $t (0 ≤ t < i)$ и добавить сверху шар массой $m (0 < m ≤ 1000)$;
$t 0$ — клонировать снеговика номер $t (0 ≤ t < i)$ и удалить верхний шар. Гарантируется, что снеговик не пустой.

В результате действия $i$, описанного в строке $i + 1$ создается снеговик номер $i$. Изначально имеется пустой снеговик с номером ноль.

Все входные числа целые.

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

Выведите суммарную массу построенных снеговиков.

Тесты

Входные данные	Выходные данные
8 0 1 1 5 2 4 3 2 4 3 5 0 6 6 1 0	74
4 0 3 1 2 2 1 1 1	18
2 0 1 1 5	7
5 1 2 3 4 5 5 1 7 5 6	26

Код задачи

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(), count = 0, t, m;
		int a[][] = new int[n + 1][2];
		a[count][1] = 0;
		a[count][0] = -1;
		count++;
		long sumr = 0;
		for(int i = 0; i < n; i++){
			t = in.nextInt();
			m = in.nextInt();
			if(m == 0){
				a[count][1] = a[a[t][0]][1];
				a[count][0] = a[a[t][0]][0];
			}else{
				a[count][1] = a[t][1] + m;
				a[count][0] = t;
			}
			sumr += a[count][1];
			count++;
		}
		System.out.println(sumr);
	}
}

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(), count = 0, t, m;

int a[][] = new int[n + 1][2];

a[count][1] = 0;

a[count][0] = -1;

count++;

long sumr = 0;

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

t = in.nextInt();

m = in.nextInt();

if(m == 0){

a[count][1] = a[a[t][0]][1];

a[count][0] = a[a[t][0]][0];

}else{

a[count][1] = a[t][1] + m;

a[count][0] = t;

}

sumr += a[count][1];

count++;

}

System.out.println(sumr);

}

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

Считываем n — количество действий. Задаем двухмерный массив размером [n+1][2] . Указываем значение первого элемента равное $0$ и нулевого элемента равного $-1$, чтобы он ни на что не ссылался в начале. В цикле считываем номер снеговика, которого нужно клонировать и массу шара, которую нужно добавить. Если масса шара равна $0$, то мы клонируем снеговика и убираем последний его шар, ссылаясь на снеговика в котором этого шара еще не было. Если же масса шара не равно $0$, то мы клонируем снеговика и добавляем ему шар массой $m$. Во второй ячейке указываем предка с которого строится новый снеговик. Выводим общую массу снеговиков.

Ссылки

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

e-olymp 5082. Степени вершин

27/12/2018 by Дима Мороз

Задача

Дан простой неориентированный невзвешенный граф. Требуется для каждой вершины подсчитать ее степень.

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

В первой строчке находится число $N (1 ≤ N ≤ 1000)$. В следующих $N$ строчках находится матрица смежности.

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

Выведите $N$ чисел – степени всех вершин.

Тесты

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

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

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

class Main
{
	static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter out = new PrintWriter(System.out);
	static int nextInt() throws IOException  {
		in.nextToken();
		return (int)in.nval;
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		int n = nextInt();
		for (int i = 0; i < n; i++) {
			int counter = 0, x;
			for (int j = 0; j < n; j++) {
				x = nextInt();
				if (x > 0) counter += (i == j ? 2 : 1);
			}
			out.print (counter + " ");
			out.flush();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

static PrintWriter out = new PrintWriter(System.out);

static int nextInt() throws IOException {

in.nextToken();

return (int)in.nval;

}

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

{

int n = nextInt();

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

int counter = 0, x;

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

x = nextInt();

if (x > 0) counter += (i == j ? 2 : 1);

}

out.print (counter + " ");

out.flush();

}

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

Для решении задачи даже не нужно запоминать значения элементов матрицы. Выполняем данные действия $N$ раз, для каждой строки матрицы. Храним ответ в переменной counter , изначально $0$. По очереди считываем все ее элементы и, если текущий элемент равен $1$, то прибавялем степени $2$, если элемент принадлежит главной диагонали (т.к. тогда это петля, а при подсчете степени ребро-петля учитывается дважды), иначе — $2$. Затем выводим результат через пробел.

Ссылки

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

e-olymp 3912. Реверс удавов

21/12/2018 by Дима Мороз

Задача

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

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

Первая строка содержит одно число $N(1≤N≤100000)$ – количество удавов. В следующих $N$ строках написаны имена удавов в том порядке, в котором они ползут. Имя удава – строчка, содержащая не более $10$ маленьких латинских букв.

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

Выведите единственную строку – название стаи после команды «Реверс».

Тесты

Входные данные	Выходные данные
3 abc def ghi	ghidefabc
3 zxcgh i db	dbizxcgh
4 mn kjl iu ghj	ghjiukjlmn
8 kdh jg lqwoc kfxvk iduhx nsh s kjwyv	kjwyvsnshiduhxkfxvklqwocjgkdh

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		String N = r.readLine();
		int n = Integer.parseInt(N);
		String[] flock = new String[n];
		for (int i = 0; i < n; i++)
			flock[i] = r.readLine();
		for (int i = n - 1; i >= 0; i--)
			System.out.print(flock[i]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

String N = r.readLine();

int n = Integer.parseInt(N);

String[] flock = new String[n];

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

flock[i] = r.readLine();

for (int i = n - 1; i >= 0; i--)

System.out.print(flock[i]);

}

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

Записываем каждого удава в одномерный массив flock типа String размера N , а затем выводим его, начиная с конца.

Ссылки

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

e-olymp 396. Дождь

18/12/2018 by Дима Мороз

Задача

Как это выглядит на координатной плоскости

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

Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

Напишите программу, которая по координате $X_0$ точки появления капли над землей вычисляет координату $X$ точки соприкосновения капли с землей $Y=0$.

Входные данные: во входном файле в первой строке содержатся два целых числа через пробел – координата $X_0$ точки появления капли $(0 < X_0 < 10000)$ и количество отрезков-препятствий $N(0≤N≤100)$. Далее следует $N$ строк, каждая из которых содержит четыре разделенные пробелами числа $x_1, y_1, x_2, y_2$ – координаты левого и правого концов отрезка-препятствия $($все числа целые и находятся в диапазоне от $0$ до $10000, x_1 < x_2, y_1 ≠y_2)$. Отрезки не пересекаются и не соприкасаются.

Выходные данные: в выходной файл вывести одно целое число – координату $X$ точки соприкосновения капли с землей.

Тесты

Входные данные	Выходные данные
30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19	18
12 5 12 9 13 5 17 8 19 5 13 10 10 7 6 17 4 12 13 4 5 12	13
40 3 12 30 21 39 41 5 45 70 20 30 25 35	40
70 6 45 75 598 37 489 48 726 47 673 873 46 36 60 735 373 762 483 73 364 59 462 375 583 457	726

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

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

class Main
{
	static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter out = new PrintWriter(System.out);
	static int nextInt() throws IOException  {
		in.nextToken();
		return (int)in.nval;
	}
	public static void main (String[] args) throws java.lang.Exception
	{
    	int x = nextInt(), n = nextInt();
    	int N[][] = new int[n][4];;
    	int tmp = 0;
    	for (int i = 0; i < n; i++)
    	    for (int j = 0; j < 4; j++)
    	        N[i][j] = nextInt();
    	for (int i = 0; i < n; i++) 
    	    for (int j = 0; j < n; j++) 
    	        for (int q = 0; q < 4; q++)
    	            if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) ) {
    	                tmp = N[i][q];
    	                N[i][q] = N[j][q];
    	                N[j][q] = tmp;
    	            }
    	for (int i = 0; i < n; i++) {
    	    if (x >= N[i][0] && x <= N[i][2]) 
    	        x = (N[i][1] < N[i][3]) ? N[i][0] : N[i][2];
    	    for (int j = 0; j < 4; j++)
    	        N[i][j] = 0;
    	}
    	out.println(x);
    	out.flush();
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

static PrintWriter out = new PrintWriter(System.out);

static int nextInt() throws IOException {

in.nextToken();

return (int)in.nval;

}

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

{

int x = nextInt(), n = nextInt();

int N[][] = new int[n][4];;

int tmp = 0;

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

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

N[i][j] = nextInt();

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

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

for (int q = 0; q < 4; q++)

if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) ) {

tmp = N[i][q];

N[i][q] = N[j][q];

N[j][q] = tmp;

}

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

if (x >= N[i][0] && x <= N[i][2])

x = (N[i][1] < N[i][3]) ? N[i][0] : N[i][2];

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

N[i][j] = 0;

}

out.println(x);

out.flush();

}

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

Сортируем наш динамический массив по наибольшим координатам $y$ и, если $y$ равны, по координатам $x$.

Далее составим алгоритм решения задачи:

Если $X\in[x_1,x_2]$, то наша капля пересечется с данной прямой. В противном случае мы просто игнорируем данное препятствие.
Тогда мы сравниваем координаты $y_1$ и $y_2$, выбираем из них наименьшее и присваиваем соответствующую координату $x_1$ или $x_2$ координате
нашей капли $X$.
Повторяем до тех пор, пока не будут обработаны все препятствия и выводим последнюю присвоенную координату $X$ нашей капли, так как она и будет координатой $x$ соприкосновения капли с зимой.

Ссылки

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

e-olymp 6350. Изированная вода

11/12/2018 by Дима Мороз

Задача

Изированная вода

В Бердичеве ещё в советские времена продавалась знаменитая изированная вода. Собственно это была обычная газировка на разлив, но продавал её Изя, поэтому и воду все называли изированной. Продавец газировки был человеком не только очень умным и добродушным, но и очень сообразительным. О складе его ума говорит хотя бы тот факт, что у него было $2$ диплома о высшем образовании: он закончил физмат пединститута и мехмат университета, а о сообразительности – то, что имея два диплома, он продавал газировку и довольно успешно. Старожилы утверждают, что попить его газировки прилетали в те времена даже с самой Москвы…

Изя, герой задачи

С постоянными покупателями, и не только с ними, Изя был очень общительным человеком, и иногда, как говорится «под настроение клиента», задавал им свои задачки на сообразительность, которых у него в запасе было великое множество. Одна из подобных его задачек приведена в задаче «Покупка воды». Задав подобную задачку, он ждал от клиента быстрого, сообразительного и, главное, верного ответа на неё, если же ответ запаздывал, или был не верным, Изя всегда говорил что-то типа: «Молодой человек, придёте завтра – Вы сегодня не заслужили на обслуживание». Естественно, это была шутка и клиент всё равно имел возможность приобрести очень вкусную изированную воду.

Перед тем как сформулировать наш вопрос, напомним задачку, упоминаемую выше: «Стоимость бутылки воды, учитывая стоимость пустой бутылки, составляет $1$ руб. $20$ коп., а стоимость пустой бутылки – $20$ коп. Сколько бутылок воды можно выпить на $N$ руб., учитывая, что пустые бутылки можно сдавать, и на полученные деньги приобретать новые бутылки воды?».

Нас же будет интересовать ответ на следующий вопрос: «А сколько покупателей услышали сегодня от Изи фразу «Приходите завтра!»?».

Входные данные
В первой строке входных данных находится единственное число $N(1≤N≤106)$ — количество покупателей, которым Изя задавал упоминаемую в условии задачку.

В последующих $N$ строках задано через пробел $N$ пар чисел, первое из которых — количество денег в кошельке перед началом операции «Покупка ГазВоды», а второе — ответ покупателя.

Все входные данные — целые неотрицательные числа, не превышающие $10^6$.

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

Тесты

Входные данные	Выходные данные
5 2 1 2 2 1 2 1 1 2 1	3
3 45 45 38 37 12 10	2
3 5 4 7 6 3 2	0
2 1280 1280 1900 1899	1
7 1 1 2 2 3 2 6 5 6 6 7 3 2 2	5

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

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

class Main {
	static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter out = new PrintWriter(System.out);
	static int nextInt() throws IOException  {
		in.nextToken();
		return (int) in.nval;
	}
	public static void main (String[] args) throws java.lang.Exception {
		Scanner in = new Scanner(System.in);
		int n = nextInt(), j = 0;
		for (int i = n; i > 0; i--) {
			int a = nextInt(), b = nextInt();
			if (b != a - 1) j++;
		}
		out.println(j);
		out.flush();
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

static PrintWriter out = new PrintWriter(System.out);

static int nextInt() throws IOException {

in.nextToken();

return (int) in.nval;

}

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

Scanner in = new Scanner(System.in);

int n = nextInt(), j = 0;

for (int i = n; i > 0; i--) {

int a = nextInt(), b = nextInt();

if (b != a - 1) j++;

}

out.println(j);

out.flush();

}

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

Для решения этой задачи необходимо решить задачу «Покупка воды». Решение очень простое: количество бутылок воды, которое можно выпить на $n$ грн. равно $n — 1$.

Используем это в цикле для проверки на правильность ответа покупателя. Если ответ неправильный, то увеличиваем переменную j , которая считает количество неправильных ответов, на один, и, после завершения цикла, выводим ее значение.

Так же для реализации задачи на Java нам необходимо ускорить ввод и вывод данных. Метод, который использовался, приведен в одной из статей на сайте – Ввод данных: Scanner vs StreamTokenizer.

Ссылки

Код задачи на e-olymp.com
Решение задачи на ideone.com

e-olymp 27. Циклические сдвиги

02/10/2018 by Дима Мороз

Задача

Циклический сдвиг

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

Например, если $n = 11$, то в двоичной системе это $1011_2$, его циклические сдвиги: $0111_2$, $1110_2$, $1101_2$, $1011_2$. Максимальное значение $m$ у всех полученных таким образом чисел будет иметь число $1110_2 = 14_{10}$.

Для заданного числа $n$ определить максимальное значение $m$.

Входные данные: одно число $n (1 ≤ n ≤ 2\cdot 10^9)$.

Выходные данные: искомое число $m$.

Тесты

Входные данные	Выходные данные
11	14
23	30
256	256
257	384
34132	43664

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

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 in_val = in.nextInt(), tmp_val = in_val, power = 1;
		while (tmp_val != 0) {
			tmp_val /= 2;
			power *= 2;
		}
		tmp_val = in_val;
		long max_val = in_val;
		do{
			in_val = in_val << 1;
			in_val = in_val % power + (in_val >= power ? 1 : 0);
			if (max_val < in_val) max_val = in_val;
		}while (tmp_val != in_val);
		System.out.println(max_val);
	}
}

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 in_val = in.nextInt(), tmp_val = in_val, power = 1;

while (tmp_val != 0) {

tmp_val /= 2;

power *= 2;

}

tmp_val = in_val;

long max_val = in_val;

do{

in_val = in_val << 1;

in_val = in_val % power + (in_val >= power ? 1 : 0);

if (max_val < in_val) max_val = in_val;

}while (tmp_val != in_val);

System.out.println(max_val);

}

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

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

Ссылки

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

e-olymp 43. Количество участников олимпиады

21/09/2018 by Дима Мороз

Задача

Как известно, на вопрос о том, сколько у него учеников, древнегреческий учёный Пифагор отвечал так: «Половина моих учеников изучает математику, четвертая часть изучает природу, седьмая часть проводит время в молчаливом размышлении, остальную часть составляют три девы».

Секретарь олимпиады на вопрос: «Сколько зарегистрировано участников олимпиады по информатике?», отвечал подобно Пифагору: «$k$-тая часть участников начала решать первую задачу, $m$-тая часть – вторую, а $n$-ая – третью.

В то же время $d$ участников решают проблему: «С чего начать?». Ваша задача определить количество участников олимпиады $s$ или вывести $-1$, если секретарь ошибся.

Входные данные: в одной строке заданы числа $k, n, m, d (1 ≤ k, n, m, d ≤ 1000)$.

Выходные данные: вывести количество участников олимпиады $s$, или $-1$, если секретарь ошибся в своём сообщении.

Тесты

$k$	$n$	$m$	$d$	Выходные данные
2	4	7	3	28
4	5	2	1	20
3	7	5	4	-1
6	6	6	1	-1
2	3	6	4	-1
3	2	5	8	-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);
		float k = in.nextInt(), n = in.nextInt(), m = in.nextInt(), d = in.nextInt(), s = (d * k * n * m) / (k * n * m - k * m - k * n - m * n);
		if ((1 / k + 1 / n + 1 / m >= 1) | (Math.floor(s / k) != s / k | Math.floor(s / n) != s / n | Math.floor(s / m) != s / m) | !(Math.floor(s) == s))
			System.out.println(-1);
		else System.out.println(Math.round(s));
	}
}

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

float k = in.nextInt(), n = in.nextInt(), m = in.nextInt(), d = in.nextInt(), s = (d * k * n * m) / (k * n * m - k * m - k * n - m * n);

if ((1 / k + 1 / n + 1 / m >= 1) | (Math.floor(s / k) != s / k | Math.floor(s / n) != s / n | Math.floor(s / m) != s / m) | !(Math.floor(s) == s))

System.out.println(-1);

else System.out.println(Math.round(s));

}

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

Пусть $x$ — количество учеников Пифагора. Тогда $\displaystyle\frac{x}{2}$ — половина его учеников, тех, которые изучают математику. Следовательно, $\displaystyle\frac{x}{4}$ — ученики, которые изучают природу, а $\displaystyle\frac{x}{7}$ — ученики, которые проводят время в молчаливом размышлении. И, по условию задачи, есть так же три девы.

Получили уравнение вида $\displaystyle\frac{x}{2} + \frac{x}{4} + \frac{x}{7} + 3 = x$, в общем виде $\displaystyle\frac{x}{k} + \frac{x}{m} + \frac{x}{n} + d = x$.
Отсюда выходит, что $\displaystyle\frac{1}{k} + \frac{1}{m} + \frac{1}{n} + dx = 1;$

$\displaystyle\frac{mnx + knx + kmx + kmnd} {kmnx} = 1;$

$\displaystyle(mn + kn + km)x + kmnd = kmnx;$

Отсюда получаем формулу $\displaystyle x = \frac{kmnd} {kmn — mn — kn — km}$.

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

Для того, чтобы проверить, является ли переменная x целым числом или нет, используем метод floor() из класса Math.

Помимо этого делаем проверку для суммы чисел $\displaystyle\frac{1}{k}$, $\displaystyle\frac{1}{n}$ и $\displaystyle\frac{1}{m}$, так как если оно больше $1$, то количество учеников становится отрицательным, что невозможно. В случае, если $\displaystyle\frac{1} {k} + \frac{1} {n} + \frac{1} {m} = 1$, а $d > 0$, то, это тоже невозможно, а значит, секретарь ошибся.

Так же делаем проверку, которая определяет, не являются ли числа $\displaystyle\frac{q}{k}$, $\displaystyle\frac{q}{n}$ и $\displaystyle\frac{q}{m}$ дробными, так как это бы тоже было ошибкой секретаря (напрмер, если $k = 6$, $m = 6$, $n = 6$, $d = 1$, то при подстановке в формулу мы получаем, что количество участников равно $2$, но тогда получается, что один участник решал сразу три задачи, что, по условию задачи, невозможно).

Если условие не проходит проверки, то выводится «$-1$».

Ссылки

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

e-olymp 7337. Скидки

12/09/2018 by Дима Мороз

Задача

В супермаркете электроники, если верить телерекламе, существует система скидок: из двух купленных товаров полностью оплачивается только стоимость товара, который дороже, а другой отдается бесплатно. Какой суммы достаточно, что бы оплатить покупку трёх товаров, если известна цена каждого?
Входные данные: три натуральных числа $a, b, c$ — цены трёх товаров $(1\leq a, b, c\leq10000)$.
Выходные данные: стоимость покупки.

Тесты

Входные данные	Выходные данные
213 6554 234	6767
320 3670 5555	5875
15 47 13	60
215 30 73	245
370 53 823	876

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) 
	{
		Scanner in = new Scanner(System.in);
		int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
		System.out.println(Math.max(Math.max(a, b), c) + Math.min(Math.min(a, b), c));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();

System.out.println(Math.max(Math.max(a, b), c) + Math.min(Math.min(a, b), c));

}

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

Для нахождения самого дорогого и самого дешёвого товаров мы используем встроенные методы Math.max() и Math.min() из класса Math. Находим минимальное число из чисел $a, b$ и $c$: Math.min(Math.min(a, b), c) (например: Math.min(Math.min(1, 2), 3) будет равно $1$). Далее проводим такую же операцию с нахождением максимального числа среди $a, b, c$: Math.max(Math.min(a, b), c) (пример: Math.max(Math.min(1, 2), 3) будет равно $3$). Затем суммируем полученные минимальное и максимальное числа и получаем ответ.

Ссылки

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

Задача

Тесты

Код решения

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

Ссылки

Задача

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

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

Тесты

Код задачи

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

Ссылки

Задача

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

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

Тесты

Код задачи

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

Ссылки

Задача

Тесты

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

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

Ссылки

Задача

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

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

Тесты

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

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

Ссылки

Задача

Тесты

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

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

Ссылки

Задача

Тесты

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

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

Ссылки

Задача

Тесты

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

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

Ссылки

Задача

Тесты

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

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

Ссылки

Задача

Тесты

213 6554 234

6767

320 3670 5555

5875

15 47 13

60

215 30 73

245

370 53 823

876

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

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

Ссылки