Решение задачи "Высота функции" с Codeforces

С пояснением   Просмотров: 20


Задан набор из 2n+1 целочисленных точек на декартовой плоскости. Точки пронумерованы от 0 до 2n включительно. Пусть Pi — i-я точка. Тогда x-координата точки Pi равна i. y-координата точки Pi равна нулю (изначально). Таким образом, изначально Pi=(i,0).

Заданный набор точек является вершинами графика кусочной функции. j-й кусок функции — отрезок PjPj+1. За один ход вы можете увеличить на 1 y-координату любой точки с нечетной x-координатой (то есть точек P1,P3,…,P2n−1). Заметьте, что соответствующие отрезки тоже меняются.

Например, график ниже иллюстрирует функцию для n=3 (количество точек равно 2⋅3+1=7), в которой мы увеличили y-координату точки P1 три раза и y-координату точки P5 один раз:


Пусть площадь графика равна площади под графиком, но над координатной прямой OX. Тогда площадь графика на картинке выше равна 4 (голубая площадь на картинке выше — это площадь графика, нарисованного на ней).

Пусть высота графика равна максимальной y-координате среди всех изначальных точек графика (то есть точек P0,P1,…,P2n). Высота графика на картинке выше равна 3.

Ваша задача — найти, какую минимальную высоту может иметь график, состоящий из 2n+1 вершин с площадью, равной k. Заметьте, что необязательно минимизировать количество ходов.

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

Код

#include <bits/stdc++.h>
using namespace std;
long long n,k;
int main(){
    cin>>n>>k;
    cout<<(k+n-1)/n;
}

         


<div style=

A PHP Error was encountered

Severity: Notice

Message: Undefined index: first_name

Filename: templates/tasksdecision_view.php

Line Number: 133

Backtrace:

File: /var/www/u0984434/data/www/hsecodes.com/application/views/templates/tasksdecision_view.php
Line: 133
Function: _error_handler

File: /var/www/u0984434/data/www/hsecodes.com/application/controllers/Tasksdecision.php
Line: 120
Function: view

File: /var/www/u0984434/data/www/hsecodes.com/index.php
Line: 315
Function: require_once

Администратор Photo" /> Автор:


Легко заметить, что площадь графика равна сумме площадей всех треугольников этого графика. Каждый ход увеличивает площадь на единицу. Мы не можем получить ответ меньший, чем ⌈kn⌉, но мы всегда можем получить такой ответ.

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться