e-olymp 8283. Музыка

13/09/2020 by Евгений Радчин

Задача

Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.

Малыши часто просили его научить играть на каком-нибудь инструменте. Гусля не отказывал, но сначала предлагал взять инструмент с первым номером, а если ученику хотелось играть на другом, то он выбирал шестой следующий по кругу и так далее. Напишите программу, которая определяла номер попытки, с которой ученик мог получить желаемый инструмент с номером $k$.

Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.

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

Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.

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

Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.

Тесты

№	Входные данные	Выходные данные
1	11 3	5
2	6 2	0
3	13 13	3
4	9 8	0
5	5 5	5

Код

import java.util.Scanner;

class Main {
	public static void main (String[] args) {
		int counter = 1;
		Scanner in = new Scanner(System.in);
		int quantity = in.nextInt();
		int instrument = in.nextInt();
		if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {
			System.out.print(0);
		} else if (quantity == instrument) {
			for (int num = 1; num % quantity != 0; num += 6) {
				if (num != 1 && num % quantity == 1){
					System.out.print(0);
					System.exit(0);
				} else {
					counter++;
				}
			}
			System.out.print(counter);
		} else {
			for (int num = 1; num % quantity != instrument; num += 6) {
				if (num != 1 && num % quantity == 1) {
					System.out.print(0);
					System.exit(0);
				} else {
					counter++;
				}
			}
			System.out.print(counter);
		}
	}
}

import java.util.Scanner;

class Main {

public static void main (String[] args) {

int counter = 1;

Scanner in = new Scanner(System.in);

int quantity = in.nextInt();

int instrument = in.nextInt();

if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {

System.out.print(0);

} else if (quantity == instrument) {

for (int num = 1; num % quantity != 0; num += 6) {

if (num != 1 && num % quantity == 1){

System.out.print(0);

System.exit(0);

} else {

counter++;

}

System.out.print(counter);

} else {

for (int num = 1; num % quantity != instrument; num += 6) {

if (num != 1 && num % quantity == 1) {

System.out.print(0);

System.exit(0);

} else {

counter++;

}

System.out.print(counter);

}

Решение

Для решения задачи нам необходимо рассмотреть ряд натуральных чисел, начиная с единицы и прибавляя каждый раз $6$. С помощью операции деления с остатком мы можем реализовать алгоритм нахождения номера музыкального инструмента. Однако логика решения изменяется в зависимости от введенных пользователем данных. Имеется два случая:

Если пользователь вводит разные числа.
Если пользователь вводит одинаковые числа.

В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.

Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

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 1494. Санта Клаус

23/12/2018 by Томас Пасенченко

Задача

Санта Клаус готовится к Рождеству. В этот праздник он хочет вручить подарки $n$ детям. Его помощники Эльфы уже собрали два мешка, с которыми он отправится в новогоднее путешествие по всем странам мира. И чтобы Санта не запутался, Эльфы составили список детей, чьи подарки уже лежат в каждом из мешков. Санта хочет помочь Эльфам, и поэтому решил положить в третий мешок подарки для тех детей, которым они еще не подготовлены.

Помогите Санте, составьте список детей, чьи подарки надо положить в третий мешок.

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

Первая строка входного файла содержит три целых числа: $n$ — число детей, $m$ и $k$ — число подарков в первом и втором мешке соответственно $(1\leq n,\;m,\;k\leq 100;m+k\leq n)$. Вторая строка входного файла содержит $m$ целых чисел — номера детей, подарки для которых лежат в первом мешке. Третья строка входного файла содержит $k$ целых чисел — номера детей, подарки для которых лежат во втором мешке.

Гарантируется что Эльфы положили для каждого ребенка не более одного подарка. Номера всех детей являются целыми положительными числами не превосходящими $n$. Все дети должны получить подарок на Рождество, иначе Санта расстроится.

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

В первой строке выведите одно число $a$ — сколько подарков должно быть в третьем мешке. Во второй строке выведите в произвольном порядке $a$ чисел — номера детей, которым эти подарки должны быть доставлены.

Тесты

Входные данные	Выходные данные
2 1 1 2 1	0
3 1 2 1 2 3	0
7 2 1 7 3 1	4 2 4 5 6
100 14 4 2 93 30 56 17 19 75 22 23 5 49 11 8 33 91 40 81 54	82 1 3 4 6 7 9 10 12 13 14 15 16 18 20 21 24 25 26 27 28 29 31 32 34 35 36 37 38 39 41 42 43 44 45 46 47 48 50 51 52 53 55 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 76 77 78 79 80 82 83 84 85 86 87 88 89 90 92 94 95 96 97 98 99 100
10 3 5 2 5 8 3 7 1 4 9	2 6 10
61 40 5 61 20 5 3 4 9 8 49 31 20 33 35 34 61 1 32 53 51 7 21 44 46 47 2 60 50 19 25	36 5 6 10 11 12 13 14 15 16 17 18 22 23 24 26 27 28 29 30 36 37 38 39 40 41 42 43 45 48 52 54 55 56 57 58 59
12 3 3 1 2 3 11 10 8	6 4 5 6 7 9 12

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

import java.util.Scanner;
public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		int k = scanner.nextInt();
		int num;
		boolean children[] = new boolean[n];
		for (int i = 0; i < n; i++) {
			children[i] = false;
		}
		for (int i = 0; i < m + k; i++) {
			num = scanner.nextInt();
			num--;
			children[num] = true;
		}
		System.out.println(n - m - k);
		for (int i = 0; i < n; i++) {
			if (!children[i]) {
				System.out.print((i + 1) + " ");
			}
		}
	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int m = scanner.nextInt();

int k = scanner.nextInt();

int num;

boolean children[] = new boolean[n];

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

children[i] = false;

}

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

num = scanner.nextInt();

num--;

children[num] = true;

}

System.out.println(n - m - k);

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

if (!children[i]) {

System.out.print((i + 1) + " ");

}

Решение

Создадим массив типа boolean , в котором каждому $i$-ому ребёнку соответствует элемент с индексом $i-1$ , принимающий значение $0$, если для ребёнка ещё нет подарка, и $1$, если подарок уже имеется в одном из мешков. Далее, отмечаем детей, подарки для которых уже лежат в мешках. Наконец, выводим номера тех детей, подарки для которых не были найдены ни в одном из мешков.

Ссылки

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

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