e-olymp 2671. Сапер

28/12/2018 by Андрей Святозар Чернецкий

Задача

Дан список мин. Требуется составить поле для игры в сапер.

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

Даны числа $N$ и $M$ (целые, положительные, не превышают $32$) — количество строк и столбцов в поле соответственно, далее число $W$ (целое, неотрицательное, не больше $100$) — количество мин на поле, далее следует $W$ пар чисел, координаты мины на поле (первое число — строка, второе число — столбец).

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

Требуется вывести на экран поле. Формат вывода указан в примере.

Тесты

Входные данные	Выходные данные
3 2 2 1 1 2 2	* 2 2 * 1 1
2 2 0	0 0 0 0
10 10 5 1 1 3 3 5 5 7 7 9 9	* 1 0 0 0 0 0 0 0 0 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 1
1 1 1 1 1	*
32 32 10 1 1 2 2 4 4 4 3 3 4 5 5 27 28 30 30 22 31 32 32	* 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 * 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 4 * 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * * 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 bomb = scanner.nextInt();
		int count = 0;
		char[][] A = new char[34][34];
		for (int i = 0; i < bomb; i++){
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        A[x][y] = '*';
    	}
    	for (int i = 1; i < n + 1; i++){
        for (int j = 1; j < m + 1; j++){ 
            if (A[i][j] != '*'){
                if (A[i-1][j] == '*') count++;
                if (A[i-1][j-1] == '*') count++;
                if (A[i-1][j+1] == '*') count++;
                if (A[i+1][j+1] == '*') count++;
                if (A[i+1][j-1] == '*') count++;
                if (A[i+1][j] == '*') count++;
                if (A[i][j-1] == '*') count++;
                if (A[i][j+1] == '*') count++;
                System.out.print(count);
                count = 0;
            }
            else System.out.print(A[i][j]);
            if (j != m) System.out.print(" ");;
        }
        System.out.print("\n");
    	}
	}
}

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 bomb = scanner.nextInt();

int count = 0;

char[][] A = new char[34][34];

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

int x = scanner.nextInt();

int y = scanner.nextInt();

A[x][y] = '*';

}

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

for (int j = 1; j < m + 1; j++){

if (A[i][j] != '*'){

if (A[i-1][j] == '*') count++;

if (A[i-1][j-1] == '*') count++;

if (A[i-1][j+1] == '*') count++;

if (A[i+1][j+1] == '*') count++;

if (A[i+1][j-1] == '*') count++;

if (A[i+1][j] == '*') count++;

if (A[i][j-1] == '*') count++;

if (A[i][j+1] == '*') count++;

System.out.print(count);

count = 0;

}

else System.out.print(A[i][j]);

if (j != m) System.out.print(" ");;

}

System.out.print("\n");

}

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

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

Ссылки

Условие задачи на сайте e-olymp

код задачи на ideone

e-olymp 1154. Кружок хорового пения

28/12/2018 by Андрей Святозар Чернецкий

Задача

В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex]-й для распевки поёт гамму.

Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]N[/latex] и [latex]M[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.

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

Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]N[/latex] и [latex]M[/latex]. ([latex]1 ≤ N, M ≤ 103[/latex]).

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

Для каждого тестового случая в отдельной строке выведите «YES», если в разминке примут участие все участники хора, в противном случае выведите «NO».

Тесты

Входные данные	Выходные данные
1000 1000 1 1	NO YES
2 5 3 7 14 15 49 37	YES YES YES YES
14 16 891 6 441 9 777 111	NO NO NO NO
4 1 6 3	YES NO

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

import java.util.Scanner;
 
public class Main {
	   public static int gcd(int p, int q) {
       	if (q == 0) return p;
       	else return gcd(q, p % q);
   	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String a;
		while(sc.hasNextInt()){
    		int p = sc.nextInt();
    		int q = sc.nextInt();
    		a = gcd(p, q)==1? "YES":"NO";
    		System.out.print(a + "\n");
		}
	}
}

import java.util.Scanner;

public class Main {

public static int gcd(int p, int q) {

if (q == 0) return p;

else return gcd(q, p % q);

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String a;

while(sc.hasNextInt()){

int p = sc.nextInt();

int q = sc.nextInt();

a = gcd(p, q)==1? "YES":"NO";

System.out.print(a + "\n");

}

Решение

Пусть у нас есть [latex]N[/latex] певцов. Пронумеруем их по порядку от [latex]0[/latex] до [latex]N — 1[/latex]. Распевается каждый [latex]M[/latex]-й. И пусть НОД ([latex]M, N) = k \geq 2[/latex]. Тогда, например, [latex]k — 1[/latex]-ый певец никогда не распоется.

Ссылки

Условие задачи на сайте E-Olymp

код задачи на Ideone

e-olymp 338. Моя любимая, несократимая…

28/12/2018 by Андрей Святозар Чернецкий

Задача

“Название задачи можно напевать на мотив марша или строевой песни…”

Сколько существует правильных несократимых дробей на промежутке [[latex]0[/latex]..[latex]1[/latex]], знаменатель которых не превышает [latex]n[/latex]?

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

Натуральное число [latex]n[/latex] ([latex]n < 10001[/latex]).

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

Вывести количество правильных несократимых дробей на промежутке [[latex]0..1[/latex]], знаменатель которых не превышает [latex]n[/latex].

Тесты

Входные данные	Выходные данные
1	0
10000	30397485
5	9
80	1965
37	431
5168	8119803
9973	30237929

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

import java.util.Scanner;
 
public class Main {
	public static int eulerf(int n) {
		int result = n;
		for (int i = 2; i * i <= n; ++i) {
    	    if (n % i == 0) {
    	        while (n % i == 0) n /= i; 
    	        result -= result / i; 
    	    } 
    	}
    	if (n > 1) result -= result / n; 
    	return result; 
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n;
		n = sc.nextInt();
		int sum = 0;
    	for (int i = 2; i <= n; ++i) {
        	sum += eulerf(i);
    	}
    	System.out.print(sum);
	}
}

import java.util.Scanner;

public class Main {

public static int eulerf(int n) {

int result = n;

for (int i = 2; i * i <= n; ++i) {

if (n % i == 0) {

while (n % i == 0) n /= i;

result -= result / i;

}

if (n > 1) result -= result / n;

return result;

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n;

n = sc.nextInt();

int sum = 0;

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

sum += eulerf(i);

}

System.out.print(sum);

}

Решение

Для решения данной задачи вопользуемся функцией Эйлера [latex] \varphi (n)[/latex], равной количеству натуральных чисел, меньших [latex]n[/latex] и взаимно простых с ним. Очевидно, что количество правильных несократимых дробей со знаменателем [latex]n[/latex] равно [latex] \varphi (n)[/latex]. И тогда количество правильных дробей со знаменателем, не превыщающим [latex]n[/latex] равно [latex] \sum\limits_{i=2}^{n}{\varphi (n)}[/latex] (тут мы учли, что при [latex]i[/latex] = 1 знаменатель дроби равен 1 и дробь не будет правильной).

Ссылки

Условие задачи на сайте E-Olymp

код задачи на Ideone

описание функции Эйлера на Wikipedia

e-olymp 7460. Поездка на экскурсию

19/09/2018 by Андрей Святозар Чернецкий

Задача

Ученики 10-Б класса на осенние каникулы решили поехать на экскурсию в столицу. Зная количество мальчиков $n$ и девочек $m$ , определить, сколько необходимо заказать комнат в отеле, в котором имеются комнаты на $k$ мест каждая, при условии что мальчиков и девочек поселять вместе запрещено.

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

В одной строке записаны три числа $n, m, k \: (n, m, k \leq 100).$

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

Вывести одно число — количество комнат, которое необходимо забронировать в отеле.

Тесты

Входные данные	Выходные данные
6 12 3	6
100 100 100	2
0 0 1	0
37 34 42	2
51 44 22	5

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

import java.util.Scanner;
import java.lang.Math; 
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		double n, m, k;
		n = sc.nextInt();
		m = sc.nextInt();
		k = sc.nextInt();
		System.out.print((int)(Math.ceil(n / k) + Math.ceil(m / k)));
	}
}

import java.util.Scanner;

import java.lang.Math;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

double n, m, k;

n = sc.nextInt();

m = sc.nextInt();

k = sc.nextInt();

System.out.print((int)(Math.ceil(n / k) + Math.ceil(m / k)));

}

Решение

Поскольку девочек с мальчиками заселять вместе нельзя, отдельно вычислим количество комнат, необходимых для заселения мальчиками и отдельно — девочками. Складываем количество комнат для мальчиков с таковым у девочек.

Ссылки

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

java@Cat

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

Author Archives: Андрей Святозар Чернецкий

e-olymp 2671. Сапер

Задача

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

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

Тесты

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

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

Ссылки

e-olymp 1154. Кружок хорового пения

Задача

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

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

Тесты

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

Решение

Ссылки

e-olymp 338. Моя любимая, несократимая…

Задача

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

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

Тесты

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

Решение

Ссылки

e-olymp 7460. Поездка на экскурсию

Задача

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

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

Тесты

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

Решение

Ссылки