e-olymp 219. Центральное отопление

28/03/2019 by Никита Пушкин

Задача

Кар Карыч с Пином восемнадцать часов подряд распивали холодные молочные коктейли и закусывали их мороженым. После этого Кар Карыч свалился со страшной простудой, а Пин решил провести в домик своему другу центральное отопление. Расчет количества отопительных приборов необходимо производить строго по ГОСТу 800333-90-06*. Для простоты Пин решил купить простые батареи. Согласно таблице 14.1.3 этого ГОСТа, каждая батарея обогревает определённый объём воздуха — ровно [latex]d[/latex] кубометров. Комната, которую собирается для своего друга обогреть Пин, имеет следующие размеры:

• высота [latex]a[/latex],

• ширина [latex]b[/latex],

• длина [latex]c[/latex].

Определите минимальное количество батарей, которое необходимо купить Пину. Учтите только, что если в домике у Кар Карыча температура будет ниже, чем по ГОСТу, Кар Карыч никогда не поправится.

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

Четыре целых числа [latex]a, b, c, d (a, b, c \leq 10^{5}, d \leq 2 \cdot 10^{9})[/latex].

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

Выведите минимальное количество батарей, которое необходимо купить Пину.

Тесты

#	Входные данные	Выходные данные
1	2 3 4 2	12
2	4 5 7 3	47
3	75 61 88 50	8052
4	986 764 390 54	5440529
5	1 1 1 2000000	1

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long  a, b, c, d, v;
		Scanner in = new Scanner (System.in);
		a=in.nextLong();
		b=in.nextLong();
		c=in.nextLong();
		d=in.nextLong();
		v = a * b * c;
		System.out.println(( v + d - 1 ) / d);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

long a, b, c, d, v;

Scanner in = new Scanner (System.in);

a=in.nextLong();

b=in.nextLong();

c=in.nextLong();

d=in.nextLong();

v = a * b * c;

System.out.println(( v + d - 1 ) / d);

}

Алгортм решения

Находим объём комнаты по заданным сторонам по формуле [latex]V=a \cdot b \cdot c[/latex].
Делим полученный объём на объём, обогреваемый одной батареей.
Округляем при необходимости полученный ответ вверх, чтобы найти минимальное количество батарей.

Округление

Если разделить объём [latex]V[/latex] на [latex]d[/latex] нацело, то в остатке у нас может получиться [latex]0, 1, 2, \ldots , d-1[/latex]. Добавив [latex]d-1[/latex] к объёму [latex]V[/latex] мы получим в делении нацело остатки [latex]d-1, d, d+1, \ldots , 2d-2[/latex]. Первое число [latex]d-1<d[/latex], поэтому при делении нацело оно даёт [latex]0[/latex]. Остальные числа больше либо равны [latex]d[/latex], но меньше [latex]2d[/latex], значит любое из них при делении нацело на [latex]d[/latex] даст [latex]1[/latex].

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

e-olymp 209. Защита от копирования

27/12/2018 by Саша Рябова

Условие

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

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

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

Hа первой строке два числа $N(N\leq 100)$ и $M$ — количество смешариков и количество пар смешариков, которые обмениваются мультфильмами. На последующих $M$ строках перечисляются пары чисел $U$ и $V$, означающих, что смешарик U и смешарик V знакомы друг с другом и обмениваются мультфильмами.

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

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

Тесты

Входные данные	Выходные данные
$5$ $5$ $1$ $2$ $3$ $2$ $2$ $4$ $3$ $5$ $2$ $5$	$1$
$5$ $5$ $1$ $3$ $3$ $5$ $5$ $2$ $2$ $4$ $4$ $1$	$2$
$2$ $1$ $2$ $1$	$1$

Код решения

import java.util.*;

public class Main {

    static int maxn = 100;
    static int bestCost = Integer.MAX_VALUE;
    static int[][] relations = new int[Main.maxn][Main.maxn];

    public static void mincut(int N) {
        Vector<Vector<Integer>> compressed_vertices = new Vector<Vector<Integer>>();
        for (int i = 0; i < N; i++) {
            compressed_vertices.add(new Vector<Integer>());
            compressed_vertices.get(i).add(i);
        }

        int[] weights;
        weights = new int[N];
        boolean[] exist;
        exist = new boolean[N];
        boolean[] in_A;
        in_A = new boolean[N];
        for (int i = 0; i < N; i++) {
            exist[i] = true;
        }
        for (int ph = 0; ph < N - 1; ++ph) {
            for (int i = 0; i < N; i++) {
                in_A[i] = false;
            }
            for (int i = 0; i < N; i++) {
                weights[i] = 0;
            }
            int prev = 0;
            for (int it = 0; it < N - ph; ++it) {
                int sel = -1;
                for (int i = 0; i < N; ++i) {

                    if ((exist[i] == true) && (in_A[i] == false) && (sel == -1 || weights[i] > weights[sel])) {
                        sel = i;
                    }
                }
                if (it == N - ph - 1) {
                    if (weights[sel] < bestCost) {
                        bestCost = weights[sel];
                    }

                    compressed_vertices.get(prev).addAll(compressed_vertices.get(sel));

                    for (int i = 0; i < N; ++i) {
                        relations[prev][i] = relations[i][prev] += relations[sel][i];
                    }
                    exist[sel] = false;
                } else {

                    in_A[sel] = true;
                    for (int i = 0; i < N; ++i) {
                        weights[i] += relations[sel][i];
                    }
                    prev = sel;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        for (int i = 0; i < M; i++) {
            int U = in.nextInt() - 1;
            int V = in.nextInt() - 1;
            relations[U][V] = 1;
            relations[V][U] = 1;
        }
        mincut(N);
        System.out.print(bestCost);
    }

}

import java.util.*;

public class Main {

static int maxn = 100;

static int bestCost = Integer.MAX_VALUE;

static int[][] relations = new int[Main.maxn][Main.maxn];

public static void mincut(int N) {

Vector<Vector<Integer>> compressed_vertices = new Vector<Vector<Integer>>();

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

compressed_vertices.add(new Vector<Integer>());

compressed_vertices.get(i).add(i);

}

int[] weights;

weights = new int[N];

boolean[] exist;

exist = new boolean[N];

boolean[] in_A;

in_A = new boolean[N];

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

exist[i] = true;

}

for (int ph = 0; ph < N - 1; ++ph) {

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

in_A[i] = false;

}

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

weights[i] = 0;

}

int prev = 0;

for (int it = 0; it < N - ph; ++it) {

int sel = -1;

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

if ((exist[i] == true) && (in_A[i] == false) && (sel == -1 || weights[i] > weights[sel])) {

sel = i;

}

if (it == N - ph - 1) {

if (weights[sel] < bestCost) {

bestCost = weights[sel];

}

compressed_vertices.get(prev).addAll(compressed_vertices.get(sel));

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

relations[prev][i] = relations[i][prev] += relations[sel][i];

}

exist[sel] = false;

} else {

in_A[sel] = true;

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

weights[i] += relations[sel][i];

}

prev = sel;

}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int N = in.nextInt();

int M = in.nextInt();

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

int U = in.nextInt() - 1;

int V = in.nextInt() - 1;

relations[U][V] = 1;

relations[V][U] = 1;

}

mincut(N);

System.out.print(bestCost);

}

Решение

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

Ссылки

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

e-olymp 8. Спички

28/10/2018 by Алиса Ворохта

Задача

Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости [latex]n[/latex] квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами – сами спички.

Напишите программу, которая по количеству квадратов [latex]n[/latex], которое необходимо составить, находит минимальное необходимое для этого количество спичек.

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

Одно целое число [latex]n[/latex] [latex](1 ≤ n ≤ 10^9)[/latex].

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

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

Тесты

Входные данные	Выходные данные
[latex]1[/latex]	[latex]4[/latex]
[latex]2[/latex]	[latex]7[/latex]
[latex]4[/latex]	[latex]12[/latex]
[latex]7[/latex]	[latex]20[/latex]
[latex]150[/latex]	[latex]325[/latex]
[latex]10000[/latex]	[latex]20200[/latex]

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);
		double n = in.nextDouble();
		double length = Math.floor(Math.sqrt(n));
		double width = Math.ceil(n / length);
		double k = 2 * n + length + width;
		System.out.print((int)(k));
	}
}

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

double n = in.nextDouble();

double length = Math.floor(Math.sqrt(n));

double width = Math.ceil(n / length);

double k = 2 * n + length + width;

System.out.print((int)(k));

}

Один квадрат можно составить из [latex]4[/latex] спичек. Два квадрата — из [latex]7[/latex] спичек. Очевидно, что квадраты следует располагать так, чтобы они образовывали прямоугольник, “близкий” к квадрату.
Например, на рисунке 1 мы использовали меньшее количество спичек, чем на рисунке 2, хотя количество квадратов одинаковое:

Зададим размеры прямоугольника. Пусть [latex]w = \sqrt n[/latex] — его ширина. Округлим значение [latex]w[/latex] к наибольшему целому числу, не превышающему данное. Тогда его длина будет [latex]l = \displaystyle\frac {n} {w}[/latex]. Если округлить значение [latex]l[/latex] к наибольшему целому числу, не превышающему данное, то мы сможем построить лишь те квадраты, которые входят в наш прямоугольник. Округляя же значение [latex]l[/latex] к наименьшему целому числу, которое не меньше данного, мы сможем достроить квадраты, не поместившиеся в наш прямоугольник.
Если отложить вниз количество спичек, равное [latex]w[/latex], и вправо — [latex]l[/latex], получается следующий рисунок (разумеется, количество отложенных спичек меняется в зависимости от [latex]n[/latex]):

Очевидно, что достроить треубемые квадраты можно, положив «уголки» из двух спичек, начиная с левого верхнего угла и двигаясь сверху вниз и слева направо.
«Уголок»:

Отсюда и получается формула: [latex]k = 2 \cdot n + l + w[/latex], где [latex]k[/latex] — количество спичек, требуемое в задаче.

Ссылки

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

KM31. Бумажные многоугольники

23/11/2016 by Коваль Максим

Задача

Задача из журнала «Квант» №7 1970 г.
Квадратный лист бумаги разрезают по прямой на две части. Одну из полученных частей снова разрезают на две части, и так делают много раз. Какое наименьшее число разрезов $r$ нужно сделать, чтобы среди полученных частей оказалось $n$ $k$ -угольников?

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

Количество многоугольников $n$ .
Количество углов многоугольника $k$ .

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

Количество разрезов $r$ .

%d1%81%d0%bd%d0%b8%d0%bc%d0%be%d0%ba

Пример получения двух шестиугольников за 5 разрезов

Тесты

	Входные данные		Выходные данные
№	$n$	$k$	$r$
1	100	20	1699
2	14	3	13
3	1	3	1
4	40	360	14279
5	2	6	5

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

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

class Ideone {
        public static void main (String[] args) {
             Scanner sc = new Scanner(System.in);
             double r,n,k;
             n = sc.nextInt();
             k = sc.nextInt();
             r=k>3? n*(k-3)-1 : n>1? n-1 : 1;
             System.out.println(r);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import static java.lang.Math.*;

class Ideone {

public static void main (String[] args) {

Scanner sc = new Scanner(System.in);

double r,n,k;

n = sc.nextInt();

k = sc.nextInt();

r=k>3? n*(k-3)-1 : n>1? n-1 : 1;

System.out.println(r);

}

Решение

При каждом разрезе количество кусков бумаги $n$ увеличивается на $1$ . Общее количество вершин $k$ будет увеличиваться в зависимости от места разреза. Таким образом при разрезе через две стороны общее количество вершин будет увеличиваться на $4$ . При разрезе через две вершины общее количество вершин увеличивается на $2$ , а при разрезе через сторону и вершину — на $3$ .

При $k>3$ сначала разделим лист на $n$ четырёхугольников при помощи разрезов через противоположные стороны. На это нам понадобиться $n-1$ разрезов. Затем можем, при помощи разрезов через соседние стороны, превращать каждый четырехугольник в $k$ — угольник, на что понадобиться $k-4$ разрезов.Выходит, что на получение $n$ $k$ — угольников нужно сделать не меньше $n(k-4)+n-1$ разрезов, значит $r=n(k-3)-1$ .

Если же $k=3$ , то нам нужно, наоборот, уменьшить количество вершин. Тогда первый разрез сделаем через две вершины квадрата — получаем два треугольника, затем каждым разрезом через вершину и сторону увеличиваем количество треугольников на $1$ пока не получим $n$ . В таком случае $r= n-1$ . Исключение: если $n=1$ , то $r=1.$

Ссылка на Ideone

http://ideone.com/X0D8jF

java@Cat

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

Tag Archives: минимальное количество

e-olymp 219. Центральное отопление

Задача

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

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

Тесты

Алгортм решения

Округление

e-olymp 209. Защита от копирования

Условие

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

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

Тесты

Код решения

Решение

Ссылки

e-olymp 8. Спички

Задача

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

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

Тесты

Ссылки

KM31. Бумажные многоугольники

Задача

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

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

Тесты

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

Решение

Ссылка на Ideone