QOJ.ac

QOJ

시간 제한: 2.0 s 메모리 제한: 512 MB 총점: 100 해킹 가능 ✓

#16708. 广告策略

통계

最近,你被一家不愿透露名称的公司雇佣,负责在其 Itube 频道上推广视频。该频道有 $n$ 名订阅用户。视频病毒式传播的规则非常复杂:一方面,每天看过该视频的订阅用户数量可以翻倍;另一方面,在尚未看过该视频的订阅用户中,最多只有一半会观看它。

为了推广一部新视频,你获得了 $k$ 卢布(burles)的预算。在每天开始时,你可以花费 $x$ 卢布让 $x$ 个人观看该视频。显然,你会选择那些尚未看过视频的订阅用户。每天你可以选择不同的 $x$ 值,但总共花费的资金不能超过 $k$。正式地,在第 $i$ 天会发生以下事情:

  1. 设 $a_i$ 为目前为止已经看过视频的订阅用户数。在一天开始时,你花费 $x_i$ 卢布,此时看过视频的订阅用户数变为 $b_i = a_i + x_i$。
  2. 在这一天中,该数量会根据上述规则增加,因此 $a_{i+1} = b_i + \min(b_i, \lfloor \frac{n-b_i}{2} \rfloor)$。

你已经注意到,根据上述规则,你至少必须为第一个观看视频的人和最后一个观看视频的人付费。现在你想知道,在总花费不超过 $k$ 卢布的前提下,让所有 $n$ 名订阅用户都看到该视频最少需要多少天?

输入格式

输入的唯一一行包含两个整数 $n$ 和 $k$($1 \le n \le 10^{18}$,$2 \le k \le 100\,000$)—— 频道的订阅用户数和可用的资金总额(以卢布为单位)。

输出格式

输出一个整数 —— 让所有订阅用户都看到视频所需的最少天数。

样例

输入样例 1

7 4

输出样例 1

3

输入样例 2

10 2

输出样例 2

6

说明

在第一个样例中,一种最优方案如下:

  1. 在第一天开始时支付 1 卢布。在一天结束时,看过视频的订阅用户数为 2。
  2. 再支付 1 卢布使得 $b_3 = 3$,在一天结束时将有 5 名订阅用户受到影响。
  3. 支付 2 卢布让所有人看到视频。

在第二个样例中,你在第一天开始时支付 1 卢布,然后看过视频的订阅用户数变化如下:2, 4, 7, 8, 9,接着你再付费让最后的订阅用户看到视频。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.