e-olymp 7623. Счастливые случаи

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

Счастливые случаи

Счастливый случай — это лотерея. Каждый лотерейный билет имеет игровое поле и закрытую область. Игровое поле представляет собой прямоугольник размера $r \times c$, заполненный числами. Закрытая область скрывает номер строки и колонки, на пересечении которых находится игровая ячейка.
Существует четыре возможных выигрышных направления: вверх, вниз, влево и вправо. Направление считается выигрышным, если все числа в этом направлении от игровой ячейки в точности меньше числа в самой игровой ячейке. Если игровая ячейка находится на краю таблицы, то Вы автоматически имеете выигрышное направление!

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

В первой строке находятся два целых числа $r$ и $c$ $(1 \leqslant r, c \leqslant 100)$ — количество строк и колонок в таблице.
Каждая из следующих $r$ строк содержит $c$ чисел — значения на игровом поле. Каждое число положительно и не превосходит 1000.

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

Вывести одно число $w$ — общее количество выигрышных направлений для заданной таблицы.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	$1$ $1$ $4$	$4$
2	$2$ $4$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$	$12$
3	$3$ $2$ $10$ $10$ $10$ $10$ $4$ $5$	$13$
4	$2$ $2$ $1$ $2$ $3$ $4$	$12$
5	$0$ $0$	$0$

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

import java.util.Scanner;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int w = 0, a, b, l, d;
		Scanner scan = new Scanner(System.in);
		int r = scan.nextInt();
		int c = scan.nextInt();
		int[][] x = new int [r][r];
		for (int i = 0; i < r; i++) 
			x[i] = new int[c];
		for (int i = 0; i < r; i++){
			for (int j = 0; j < c; j++){
				x[i][j] = scan.nextInt();
			}
		}
		for (int i = 0; i < r; i++){
			for (int j = 0; j < c; j++){
				a = b = l = d = 1;
			for (int q = 0; q < i; q++){
				if (x[i][j] <= x[q][j])
					a = 0;
			}
			for (int q = i+1; q < r; q++){
				if (x[i][j] <= x[q][j])
					 b = 0;
			}
			for (int k = 0; k < j; k++){
				if (x[i][j] <= x[i][k])
					l = 0;
			}
			for (int k = j+1; k < c; k++){
				if (x[i][j] <= x[i][k])
					d = 0;
			}
			w+= a + b + l + d;
			}
		}
		System.out.print(w);
	}
}

import java.util.Scanner;

class Main

{

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

{

int w = 0, a, b, l, d;

Scanner scan = new Scanner(System.in);

int r = scan.nextInt();

int c = scan.nextInt();

int[][] x = new int [r][r];

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

x[i] = new int[c];

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

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

x[i][j] = scan.nextInt();

}

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

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

a = b = l = d = 1;

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

if (x[i][j] <= x[q][j])

a = 0;

}

for (int q = i+1; q < r; q++){

if (x[i][j] <= x[q][j])

b = 0;

}

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

if (x[i][j] <= x[i][k])

l = 0;

}

for (int k = j+1; k < c; k++){

if (x[i][j] <= x[i][k])

d = 0;

}

w+= a + b + l + d;

}

System.out.print(w);

}

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

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

Ссылки

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

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

e-olymp 7492. Будильник

15/12/2018 by Георгий Мартынюк

Задача

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

Часы Алисы содержат четыре цифры: две для часов и две для минут. Например, часы ниже показывают [latex]9[/latex]:[latex]30[/latex] (ведущий ноль высвечивается).

Часы имеют следующее представление цифр:

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

Одно целое число [latex]n (0≤ n ≤30)[/latex] — количество подсвеченных сегментов на часах Алисы во сне.

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

Вывести пять символов в формате [latex]hh:mm[/latex] — время, показываемое часами Алисы во сне. Время должно быть корректным: [latex]0 ≤ hh < 24[/latex] and [latex]0 ≤ mm < 60[/latex]. Если существует несколько решений, то вывести любое. Если решения не существует, то вывести [latex]Impossible[/latex].

Тесты

Входные данные	Выходные данные
23	00:02
28	Impossible
0	Impossible
15	01:12

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

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;
		while (in.hasNextInt()) {
			n = in.nextInt();
			int[] seg = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
			for (int i = 0; i < 24; i++)
				for (int j = 0; j < 60; j++) {
					int a = 0;
					a = a + seg[i / 10];
					a = a + seg[i % 10];
					a = a + seg[j / 10];
					a = a + seg[j % 10];
					if (a == n) {
						if (i < 10) System.out.printf("0%d", i);
						else System.out.print(i);
						System.out.print(":");
						if (j < 10) System.out.printf("0%d", j);
						else System.out.print(j);
						return;
					}
				}
				System.out.print("Impossible");
		}
		in.close();
		return;
	}
}

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;

while (in.hasNextInt()) {

n = in.nextInt();

int[] seg = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

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

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

int a = 0;

a = a + seg[i / 10];

a = a + seg[i % 10];

a = a + seg[j / 10];

a = a + seg[j % 10];

if (a == n) {

if (i < 10) System.out.printf("0%d", i);

else System.out.print(i);

System.out.print(":");

if (j < 10) System.out.printf("0%d", j);

else System.out.print(j);

return;

}

System.out.print("Impossible");

}

in.close();

return;

}

Решение

Перебираем [latex]i[/latex] и [latex]j[/latex] (от [latex]0[/latex] до [latex]24[/latex] и [latex]60[/latex] соответственно). [latex]a=seg[i/10][/latex] (для десятков) и [latex]a=seg[i[/latex]%[latex]10][/latex] (для остальных чисел) то же самое делаем для [latex]j[/latex]. Тем самым, мы перебираем все возможные варианты количества сегментов. Если [latex]a==n[/latex] (количество сегментов) при переборе и в входных данных совпадает, то выводим наше время и выходим из цикла. Если же при переборе не было такого же числа сегментов, как в входных данных, то решения нет и мы, соответственно, выводим Impossible

Ссылки

e-olymp
Ideone

e-olymp 48. Красные и синие квадраты

14/12/2018 by Павел Жуков

Задача

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

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

В первой строке находится количество синих квадратов $n$ ($0 < n < 40404$). Далее идут $n$ строк, каждая из которых содержит координаты $x$, $y$ ($-101 \leq x, y \leq 101$) левых нижних углов синих квадратов.

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

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

Вывести количество красных квадратов.

Тесты

Входные данные	Выходные данные
$3$ $1$ $2$ $2$ $1$ $3$ $1$	$3$
$3$ $1$ $1$ $2$ $2$ $1$ $3$	$6$
$10$ $1$ $1$ $2$ $2$ $1$ $3$ $2$ $4$ $1$ $5$ $2$ $6$ $1$ $7$ $2$ $8$ $1$ $9$ $2$ $10$	$90$

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

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		String[] params1 = bufferedReader.readLine().split(" ");
		int max_page_size = 210;
		boolean[][] squares = new boolean[max_page_size][max_page_size];
		for (int i = 0; i < max_page_size; ++i){
			for (int j = 0; j < max_page_size; ++j){
				squares[i][j] = false;
			}
		}
		int n;
		n = Integer.parseInt(params1[0]);
		for (int i = 0; i < n; ++i){ 
			String[] params2 = bufferedReader.readLine().split(" ");
			int x, y; 
			x = Integer.parseInt(params2[0]);
			y = Integer.parseInt(params2[1]);
			squares[x + max_page_size / 2][y + max_page_size / 2] = true;
		}
		int perimiter = 0;
		for (int i = 0; i < max_page_size; ++i){
			for (int j = 0; j  0; ++j){ 
			int i = (perimiter - 2 * j) / 2; 
			if (i * j - n > max) {
				max = i * j - n;
			}
		}
		System.out.print(max);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

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

{

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

String[] params1 = bufferedReader.readLine().split(" ");

int max_page_size = 210;

boolean[][] squares = new boolean[max_page_size][max_page_size];

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

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

squares[i][j] = false;

}

int n;

n = Integer.parseInt(params1[0]);

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

String[] params2 = bufferedReader.readLine().split(" ");

int x, y;

x = Integer.parseInt(params2[0]);

y = Integer.parseInt(params2[1]);

squares[x + max_page_size / 2][y + max_page_size / 2] = true;

}

int perimiter = 0;

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

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

int i = (perimiter - 2 * j) / 2;

if (i * j - n > max) {

max = i * j - n;

}

System.out.print(max);

}

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

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

Чтобы доказать это, пусть сторона квадрата равна $1$. Тогда периметр фигуры, составленной из этих квадратов, всегда будет делится на $2$ (это легко понять, строя такие фигуры на листке бумаги: добавление каждого нового квадрата в фигуру может изменить периметр только на $-4, -2, 0, 2, 4$). А так как периметр прямоугольника равен $2 * (a + b)$, где $a, b$ – стороны прямоугольника, то для существования прямоугольника с таким-же периметром должно выполняться условие $\forall p \in \mathbb{N} , p > 2 \rightarrow \exists a,b \in \mathbb{N} : 2p = 2*( a + b )$. Очевидно, что условие действительно выполняется для всех $p>2$.

Запишем нашу фигуру в массив squares. После чего посчитаем ее периметр: каждый непустой квадратик фигуры добавляет $1$ к периметру за каждую пустую клеточку слева, справа, сверху или снизу от него. Далее будем искать все подходящие прямоугольники, записывая максимальную площадь в переменную max: перебирая значения первой стороны $j$, высчитываем через периметр вторую сторону $i = \displaystyle \frac{p}{2} — j$. Площадь будем считать, как разницу площади прямоугольника и изначальной фигуры (число $n$ равно площади фигуры, потому что площадь каждого квадрата равна $1$).
В конце, выводим разницу максимальной площади и площади изначальной фигуры (площадь изначальной фигуры равна $n$, ведь площадь каждого квадрата равна $1$).

Ссылки

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

e-olymp 2669. Поворот

09/12/2018 by https://tripbusting.com/

Поворот

Дан массив [latex]n\times m[/latex]. Требуется повернуть его по часовой стрелке на [latex]90[/latex] градусов.

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

В первой строке даны натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 50)[/latex]. На следующих [latex]n[/latex] строках записано по [latex]m[/latex] неотрицательных чисел, не превышающих [latex]109[/latex] — сам массив.

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

Выведите перевернутый массив в формате входных данных.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 2 1 2 3 4	2 2 3 1 4 2
2	3 3 1 2 3 4 5 6 7 8 9	3 3 4 7 1 8 5 2 9 6 3
3	3 4 4 5 7 8 3 6 8 7 2 2 4 5	4 3 2 3 4 2 6 5 4 8 7 5 7 8
4	1 2 5 4	2 1 5 4
5	1 1 2	1 1 2

ВХОДНЫЕ ДАННЫЕ

ВЫХОДНЫЕ ДАННЫЕ

2 2

1 2

3 4

2 2

3 1

4 2

3 3

1 2 3

4 5 6

7 8 9

3 3

4 7 1

8 5 2

9 6 3

3 4

4 5 7 8

3 6 8 7

2 2 4 5

4 3

2 3 4

2 6 5

4 8 7

5 7 8

1 2

5 4

2 1

1 1

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

class Main
{
    public static void main (String[] args)
    {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        int x[][] = new int[n][];
        for (int i = 0; i < n; i++)
            x[i] = new int[m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                x[i][j] = input.nextInt();
        System.out.println(m + " " + n);
        for (int j = 0; j < m; j++){
            for (int i = n - 1; i >= 0; i--)
                System.out.print(x[i][j] + " ");
            System.out.println();
        }   
    }
}

import java.util.*;

import java.lang.*;

class Main

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n = input.nextInt();

int m = input.nextInt();

int x[][] = new int[n][];

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

x[i] = new int[m];

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

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

x[i][j] = input.nextInt();

System.out.println(m + " " + n);

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

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

System.out.print(x[i][j] + " ");

System.out.println();

}

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

Алгоритм решения данной задачи состоит в том, чтоб при выводе матрицы, начать выводить ее элементы не по строкам, а по столбцам, снизу вверх, начиная с первого столбца (левого нижнего угла матрицы).

Задача на сайте e-olymp
Код решения в Ideone

e-olymp 2667. Змейка

09/12/2018 by Карина Миловская

Задача

Напишите программу, которая выводит элемент из строки $x$ и столбца $y$ матрицы размера $n \times m$, которая заполнена змейкой:

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

Даны натуральные числа $n$, $m$, $x$, $y$ $ \left ( 1 \leq x \leq n \leq 50, 1 \leq y \leq m \leq 50 \right )$. Здесь $n$ — количество строк матрицы, $m$ — количество столбцов матрицы, $x$ и $y$ — номера строки и столбца искомого элемента.

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

Вывести элемент из строки $x$ и столбца $y.$

Тесты

Входные данные	Выходные данные
$5 \ 2 \ 3 \ 1$	$4$
$6 \ 3 \ 4 \ 3$	$9$
$10 \ 5 \ 10 \ 2$	$48$

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

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();
		int m = in.nextInt();
		int x = in.nextInt();
		int y = in.nextInt();
		int[][] arr = new int [n][m];
		int num = 0;
		for(int i = 0; i < n; ++i) {
			int dir, j;
			if(i % 2 == 0){
				j = 0;
				dir = 1;
			}
			else {
				j = m - 1;
				dir = -1;
			}
			for(; j < m && j >= 0; j += dir) {
				arr[i][j] = num;
				++num;
			}
		}
		System.out.print(arr[x - 1][y - 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);

int n = in.nextInt();

int m = in.nextInt();

int x = in.nextInt();

int y = in.nextInt();

int[][] arr = new int [n][m];

int num = 0;

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

int dir, j;

if(i % 2 == 0){

j = 0;

dir = 1;

}

else {

j = m - 1;

dir = -1;

}

for(; j < m && j >= 0; j += dir) {

arr[i][j] = num;

++num;

}

System.out.print(arr[x - 1][y - 1]);

}

Решение

Читаем входные данные и объявляем массив $n$ на $m$, $num = 0$ — число элемента в этом массиве, далее будем заполнять его в цикле. Делаем перебор строк, для каждой строки есть число $j$ — номер элемента (в текущей строке), с которого мы записываем числа и число $dir$ — направление, в которое мы эти числа записываем (оно у нас 1 или -1). Если строка четная, то начинаем движение слева направо, если нечетная, то справа налево. Далее перебираем каждый элемент строки и записываем ему свой номер. В ответе выводим выбранный элемент.

Ссылки

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

Код решения задачи ideone

e-olymp 907. Первый не больший чем 2.5

09/12/2018 by Карина Миловская

Задача

Задан массив вещественных чисел. Найти первый элемент массива, значение которого не превышает 2.5.

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

В первой строке задано количество элементов массива $n\left ( 0 < n \leq 100 \right )$. В следующей строке задано $n$ вещественных чисел.

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

Вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. В случае отсутствия такого элемента в массиве вывести «Not Found» (без кавычек).

Тесты

Входные данные	Выходные данные
$5 \\ 6 \ 7.5\ 2.1 \ 2.0 \ 0$	$3 \ 2.10$
$5 \\ 6 \ 7.5 \ 5.1 \ 7.0 \ 80$	$Not \ Found$
$7 \\ 5 \ 4.7 \ 50 \ 8.9 \ 2.7 \ 3 \ 1.5$	$7 \ 1.5$

Решение задачи с помощью потоковой обработки

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double n;
    	int size;
    	boolean checker = false;
    	Scanner in = new Scanner(System.in);
		size = in.nextInt();
		for (int i = 0; i < size && checker == false; i++) {
			n = in.nextDouble();
			if (n <= 2.5) {  
				System.out.print(i + 1 +  " ");
				System.out.printf("%.2f", n); 
				checker = true;
			} 
		}
		if(checker == false) {
             System.out.println("Not Found");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

double n;

int size;

boolean checker = false;

Scanner in = new Scanner(System.in);

size = in.nextInt();

for (int i = 0; i < size && checker == false; i++) {

n = in.nextDouble();

if (n <= 2.5) {

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

System.out.printf("%.2f", n);

checker = true;

}

if(checker == false) {

System.out.println("Not Found");

}

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

Будем просматривать все веденные элементы и для каждого осуществлять проверку, если элемент не превышает 2.5, тогда в ответе выводим в одной строке сначала индекс найденного первого указанного элемента и его значение с 2 десятичными знаками. Если же такого элемента нет, выводим на экран $Not \ Found.$

Решение задачи с помощью массивов

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

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();
    	double[] x = new double[n];
    	for (int i = 0; i < n; i++) {
        	x[i] = in.nextDouble();
    	}
    	boolean checker = false;
    	for (int i = 0; i < n; i++) {
        	if (x[i] <= 2.5 && checker == false) {
            	System.out.print(i + 1 +  " ");
				System.out.printf("%.2f", x[i]);
            	checker = true;
        	}
    	}
    	if (checker == false) {
    		System.out.println("Not Found");
    	}
	}
}

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

double[] x = new double[n];

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

x[i] = in.nextDouble();

}

boolean checker = false;

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

if (x[i] <= 2.5 && checker == false) {

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

System.out.printf("%.2f", x[i]);

checker = true;

}

if (checker == false) {

System.out.println("Not Found");

}

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

Введем обозначения: $x$ – имя массива, $n$ – количество элементов в массиве, $i$ – индекс элемента массива. Нам необходимо просмотреть весь массив. Если значение просматриваемого элемента не превышает 2,5, то в ответе вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. Если же такого элемента в массиве нет, вывести $Not \ Found.$

Ссылки

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

Код решения с помощью потоковой обработки на ideone

Код решения с помощью массивов на ideone

e-olymp 50. Разрезанное число

07/12/2018 by Алиса Ворохта

Задача

Василий на бумажке в виде полоски написал число, кратное $d$. Его младший брат Дмитрий разрезал число на $k$ частей. Василий решил восстановить написанное число, но столкнулся с проблемой. Он помнил только число $d$, а чисел, кратных $d$, можно сложить несколько.
Сколько чисел, кратных числу $d$, может составить Василий, если составляя исходное число, он использует все части.

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

В первой строке записано два числа $d$ и $k$ $\left(1 ≤ k < 9, 1 ≤ d ≤ 100\right)$. В следующих $k$ строках находятся части числа. Количество цифр в разрезанных частях не превышает $10.$

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

Количество разных чисел.

Тесты

Входные данные	Выходные данные
$5$ $3$ $13$ $85$ $45$	$4$
$11$ $2$ $1$ $111$	$1$
$11$ $3$ $11$ $8$ $11$	$0$
$71$ $8$ $4018916609$ $7495223237$ $3405637482$ $3166003637$ $8998228133$ $1141886496$ $9124347310$ $7736090711$	$584$

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

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

class Main
{
	public static int k, d, quantity = 0;
	public static long[] was = new long[40320];
	public static long[] nums = new long[9];
	public static boolean Was(long h) {
    	long c = 0;
    	for (int i = 0; i < quantity; i++) {
        	if (was[i] == h) c++;
    	}
    	if (c == 0) {
        	was[quantity] = h;
        	return true; 
    	}
    	else
    	return false;
	}
	public static void Swap(int a, int b) {
    	long t = nums[a];
    	nums[a] = nums[b];
    	nums[b] = t;
	}
	public static void Generate(int n) {
	    if (n == k) {
	        long sum = 0;
	        long p = 1;
	        long h = 0;
	        long hash = 1;
	        for (int i = k - 1; i >= 0; i--) {
	            long subs = nums[i];
	            sum += nums[i] % d * p;
	            p *= Math.pow(10, (long)Math.log10(nums[i]) + 1);
	            p = p%d;
	            while (subs!= 0) {
	                h += subs % 10 * hash;
	                hash *= 101;
	                subs /= 10;
	            }
	        }   
	        if (sum%d == 0 && Was(h) == true) {
	            quantity++; 
	        }
	    }
	    else { 
	        for(int j = n; j < k;j++) {
	            Swap(n,j);
	            Generate(n+1);
	            Swap(n,j);
	        }
	    }   
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		d = in.nextInt();
		k = in.nextInt();
    	for(int i = 0; i < k; i++) {
    		nums[i] = in.nextLong();
    	}
    	Generate(0);
    	System.out.println(quantity);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static int k, d, quantity = 0;

public static long[] was = new long[40320];

public static long[] nums = new long[9];

public static boolean Was(long h) {

long c = 0;

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

if (was[i] == h) c++;

}

if (c == 0) {

was[quantity] = h;

return true;

}

else

return false;

}

public static void Swap(int a, int b) {

long t = nums[a];

nums[a] = nums[b];

nums[b] = t;

}

public static void Generate(int n) {

if (n == k) {

long sum = 0;

long p = 1;

long h = 0;

long hash = 1;

for (int i = k - 1; i >= 0; i--) {

long subs = nums[i];

sum += nums[i] % d * p;

p *= Math.pow(10, (long)Math.log10(nums[i]) + 1);

p = p%d;

while (subs!= 0) {

h += subs % 10 * hash;

hash *= 101;

subs /= 10;

}

if (sum%d == 0 && Was(h) == true) {

quantity++;

}

else {

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

Swap(n,j);

Generate(n+1);

Swap(n,j);

}

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

{

Scanner in = new Scanner(System.in);

d = in.nextInt();

k = in.nextInt();

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

nums[i] = in.nextLong();

}

Generate(0);

System.out.println(quantity);

}

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

Согласно свойствам остатков от деления, остаток от деления суммы двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает сумма их остатков. А также остаток от деления произведения двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает произведение их остатков.
Значит, мы можем решить обычным перебором, но на каждом действии берем остаток от деления на $d$.
Также части чисел могут совпадать, в связи с чем необходима проверка на то, что мы составленное число еще не записывали. Для этого мы будем хешировать полученное число следующим образом: последнюю цифру умножим на $101^0$, предпоследнюю — на $101^1$ и так далее.
Если наш конечный результат делится на $d$ без остатка и если составленное число встречается в первый раз, то увеличиваем счетчик на $1$.

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 2261. Защита королевства

02/12/2018 by https://tripbusting.com/

Защита королевства

Теодор реализует новую стратегию игры «Оборона Царства». На каждом уровне игрок защищает королевство, которое представлено прямоугольной сеткой ячеек. В некоторых клетках игрок строит арбалетные башни. Башня защищает все клетки в той же строке и том же столбце. Никакие две башни не находятся на одной строке или столбце.

Штрафом положения является количество клеток в крупнейшем незащищенном прямоугольнике. Например, положение, показанное на рисунке имеет штраф [latex]12[/latex].
Помогите Теодору написать программу, вычисляющую штраф в заданной позиции.

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

Первая строка содержит три целых числа: [latex]w[/latex] — ширина сетки, [latex]h[/latex] — высота сетки и [latex]n[/latex] — количество арбалетных башен [latex](1 ≤ w, h ≤ 40000; 0 ≤ n ≤ min(w, h))[/latex].

Каждая из следующих n строк содержит два целых числа [latex]x_i[/latex] и [latex] y_i[/latex] — координаты клетки с башней [latex](1 ≤ x_i ≤ w; 1 ≤ y_i ≤ h)[/latex].

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	10 10 3 1 1 2 2 3 3	49
2	15 15 4 4 4 5 5 7 8 13 15	30
3	30 30 5 13 14 16 27 29 30 5 5 10 15	132
4	100 100 2 1 1 100 100	9604
5	3 3 3 1 1 2 2 3 3	0

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

import java.util.*;
import java.lang.*;
import java.util.Arrays.*;
 
class Main
{
	public static void main (String[] args)
	{
		int a = 0, b = 0;
		Scanner input = new Scanner(System.in);
		int x_max = input.nextInt();
		int y_max = input.nextInt();
		int n = input.nextInt();
		int x[] = new int[n+2];
		int y[] = new int[n+2];
		for(int i = 1; i < n + 1; i++)
		{
			x[i] = input.nextInt();
			y[i] = input.nextInt();
		}	
		x[0] = y[0] = 0;
        x[n + 1] = x_max + 1; 
        y[n + 1] = y_max + 1;
        Arrays.sort(x);
        Arrays.sort(y);
        for(int i = 0; i < n + 1; i++)
        { 
             if(x[i + 1]-x[i]>a) a = x[i + 1]-x[i];
             if(y[i + 1]-y[i]>b) b = y[i + 1]-y[i];
        }
        System.out.print((a-1)*(b-1));
	}
}

import java.util.*;

import java.lang.*;

import java.util.Arrays.*;

class Main

{

public static void main (String[] args)

{

int a = 0, b = 0;

Scanner input = new Scanner(System.in);

int x_max = input.nextInt();

int y_max = input.nextInt();

int n = input.nextInt();

int x[] = new int[n+2];

int y[] = new int[n+2];

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

{

x[i] = input.nextInt();

y[i] = input.nextInt();

}

x[0] = y[0] = 0;

x[n + 1] = x_max + 1;

y[n + 1] = y_max + 1;

Arrays.sort(x);

Arrays.sort(y);

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

{

if(x[i + 1]-x[i]>a) a = x[i + 1]-x[i];

if(y[i + 1]-y[i]>b) b = y[i + 1]-y[i];

}

System.out.print((a-1)*(b-1));

}

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

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

Для решения данной задачи нужно создать два массива в [latex]x[/latex] и [latex]y[/latex] (в первом будут находится [latex]x_i[/latex] координаты, а во втором [latex]y_i[/latex]) размера на [latex]2[/latex] больше чем количество заданных башен, так как нужно учитывать рамки поля, для чего достаточно добавить две башни c координатами ([latex]0[/latex];[latex]0[/latex]) и ([latex]x[/latex] [latex]max+1[/latex]; [latex]y[/latex] [latex]max+1[/latex]). Далее нужно отсортировать эти массивы и найти максимальную разность между соседними элементами ([latex]a[/latex] — максимальная разность между [latex]x_i[/latex] элементами, [latex]b[/latex] — максимальная разность между [latex]y_i[/latex]). Далее, по формуле [latex](a-1)\cdot(b-1)[/latex] находим площадь самого большого незащищенного прямоугольника, которая равна количеству клеток в нем, что и является ответом задачи.

Задача на сайте e-olymp
Код решения в Ideone

e-olymp 634. Вклад «Антикризисный»

30/11/2018 by Яна Колчинская

Задача

Постоянные клиенты одного очень крупного банка (ООКБ) недавно получили возможность открыть новый вклад — «Антикризисный». Этот вклад отличается непростой схемой начисления процентов, поэтому вам, как единственному сотруднику ИТ-отдела банка, было поручено написание программы, которая будет вычислять сумму вклада с начисленными процентами.

Вклад «Антикризисный» может быть открыт на любой срок, но дата окончания вклада должна быть не позже $31$ декабря $2009$ года, процентная ставка по вкладу составляет $p$ процентов годовых. Это означает, что если в начале некоторого периода в $d$ дней, в течение которого сумма вклада не менялась, сумма вклада составляла $x$ рублей, то по окончании этого периода она будет составлять $x\cdot\left(1+\frac{p}{100}\cdot\frac{d}{365}\right)$.

Начисление процентов на вклад осуществляется ежемесячно, в последний день месяца (или в последний день действия вклада), при этом сумма процентов присоединяется ко вкладу. Таким образом, если на первое мая сумма вклада составляла $x$ рублей, то $31$ мая ко вкладу будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{31}{365}\right)$ рублей, и на первое июня сумма вклада составит $x\cdot\left(1+\left(\frac{p}{100}\right)\cdot\left(\frac{31}{365}\right)\right)$, а в июне проценты будут начисляться уже на эту сумму.

Если же последний день вклада был $20$ мая, то в этот день ко вкладу будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{20}{365}\right)$ рублей, а сумма вклада, которую получит клиент банка составит $x\cdot\left(1+\left(\frac{p}{100}\right)\cdot\left(\frac{20}{365}\right)\right)$. Аналогично выполняются расчеты и для случая, когда вклад был открыт не в первый день месяца. Так, например, если вклад был открыт $18$ февраля, то $28$ февраля к сумме вклада будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{11}{365}\right)$ рублей, а если же он был открыт $28$ февраля, то в тот же день $28$ февраля к сумме будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{1}{365}\right)$ рублей.

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

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

Первая строка входного файла содержит три целых числа: исходную сумму вклада $x$, процентную ставку $p$ и длительность вклада $d \left(1 ≤ x ≤ 100000, 1 ≤ p ≤ 200, 1 ≤ d ≤ 365\right)$. Вторая строка входного файла содержит дату открытия вклада в формате «день-месяц-год». День и месяц обозначаются числами, при этом у чисел, меньших десяти, присутствуют ведущие нули. Гарантируется,что вклад открыт в $2009$ году, и дата его окончания также находится в $2009$ году.

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

В выходной файл выведите ответ на задачу c точностью $6$ знаков после десятичной точки.

Тесты

#	Входные данные	Выходные данные
1	1000 10 27 18 07 2009	1007.410921
2	1000 12 70 29 06 2009	1023.172779
3	1000 12 37 17 08 2009	1012.200053
4	1000 15 37 21 10 2009	1015.253781
5	1000 15 85 12 08 2009	1035.351224

Код

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

class Main {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner in = new Scanner(System.in).useDelimiter("[\\s+-]");
		int[] dM = {31, 28, 31, 30 ,31, 30, 31, 31, 30, 31, 30, 31};
		double s = in.nextDouble();
		int p = in.nextInt();
		int d = in.nextInt();
		int day = in.nextInt();
		char a;
		int month = in.nextInt();
		month--;
		int dP = 0;
		for(int i = month; dP < d; i++) {
			double z = 0;
			for(int j = (i==month?day : 1); j <= dM[i] && dP < d; j++) {
				dP++;
				z += s*(p/100.0)*(1/365.0);
			}
			s += z;
		}
		System.out.printf("%.6f", s);
	}
}

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main {

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

Scanner in = new Scanner(System.in).useDelimiter("[\\s+-]");

int[] dM = {31, 28, 31, 30 ,31, 30, 31, 31, 30, 31, 30, 31};

double s = in.nextDouble();

int p = in.nextInt();

int d = in.nextInt();

int day = in.nextInt();

char a;

int month = in.nextInt();

month--;

int dP = 0;

for(int i = month; dP < d; i++) {

double z = 0;

for(int j = (i==month?day : 1); j <= dM[i] && dP < d; j++) {

dP++;

z += s*(p/100.0)*(1/365.0);

}

s += z;

}

System.out.printf("%.6f", s);

}

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

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

Ссылки

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

e-olymp 2668. Спираль

21/11/2018 by Костя Григорян

Задача

Заполнить массив размера $n × n$ единичками по спирали (см. пример).

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

Одно нечетное натуральное число $n$, не превышающее $50$.

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

Вывести построенную спираль. Центральная клетка должна содержать $0$.

Тесты

Входные данные	Выходные данные
[latex]7[/latex]	[latex]1111111 \\ 0000001 \\ 1111101 \\ 1000101 \\ 1011101 \\ 1000001 \\ 1111111[/latex]
[latex]1[/latex]	[latex]0[/latex]
[latex]3[/latex]	[latex]111 \\ 001 \\ 111[/latex]
[latex]5[/latex]	[latex]11111 \\ 00001 \\ 11001 \\ 10001 \\ 11111[/latex]

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

import java.util.Scanner;
 
public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int [][] s = new int[50][50];
		for(int i=0; i<n; i++)
		{
			s[0][i]=1;
			s[n-1][i]=1;
			s[i][n-1]=1;
		}
		int h=n-2, d=n-2;
		int pointx=n-1, pointy=0; 
		while(true)
		{
			for(int i=0; i<h; i++)
			{
			    s[pointx-i][pointy]=1;
			}
			pointx-=h-1;
			h-=2;
			if(h<=0)
			    break;
			for(int i=0; i<d; i++)
			{
			    s[pointx][pointy+i]=1;
			}
			pointy+=d-1;
			d-=2;
			if(d<=0)
			    break;
		    for(int i=0; i<h; i++)
			{
			    s[pointx+i][pointy]=1;
			}
			pointx+=h-1;
			h-=2;
			if(h<=0)
			    break;
			for(int i=0; i<d; i++)
			{
			    s[pointx][pointy-i]=1;
			}
			pointy-=d-1;
			d-=2;
			if(d<=0)
			    break;
		}
		s[n/2][n/2]=0;
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<n; j++)
			{
			    System.out.print(s[i][j]);
			}
			System.out.println();
		}
	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int [][] s = new int[50][50];

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

{

s[0][i]=1;

s[n-1][i]=1;

s[i][n-1]=1;

}

int h=n-2, d=n-2;

int pointx=n-1, pointy=0;

while(true)

{

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

{

s[pointx-i][pointy]=1;

}

pointx-=h-1;

h-=2;

if(h<=0)

break;

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

{

s[pointx][pointy+i]=1;

}

pointy+=d-1;

d-=2;

if(d<=0)

break;

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

{

s[pointx+i][pointy]=1;

}

pointx+=h-1;

h-=2;

if(h<=0)

break;

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

{

s[pointx][pointy-i]=1;

}

pointy-=d-1;

d-=2;

if(d<=0)

break;

}

s[n/2][n/2]=0;

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

{

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

{

System.out.print(s[i][j]);

}

System.out.println();

}

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

Для начала мы верхнюю, нижнюю и правую грани зразу заполним единицами. Далее идем поочередно в четырех направления (вверх, вправо, вниз, влево). Мы имеем два параметра: ширину и высоту заполняемого единицами отрезка (ширине соответствуют движения вправо и влево, высоте — вверх и вниз). На каждом шаге уменьшаем соответствующий заполняемый отрезок (ширину или высоту) на $2$ и проверяем, чтобы он был больше $0$, иначе заканчиваем. На протяжении всего решения храним еще два параметра: координаты точки, откуда начнем следующий шаг.
P.s. На сайте www.e-olymp.com это решение не проходит полностью из-за неправильности $5$-го теста. У них в $5$-ом тесте центральный элемент $1$, что противоречит условию.

Ссылки

Условие задачи на e-olymp
Код решения