XChiChiX


這不是很戲劇化的發展嗎

e555: 10170 - The Hotel with Infinite Rooms

  • 883 字
  • 次阅读
  • 条评论
  1. 1. 內容
  2. 2. 範例輸入
  3. 3. 範例輸出
  4. 4. 想法
  5. 5. 程式碼

CPE 一顆星選集 49 道必考題

題目連結:https://zerojudge.tw/ShowProblem?problemid=e555

內容

有一家奇怪的酒店，房間無限。
來這家酒店的團體，請遵循以下規則：
a）同時，只有能有一個旅行團可以租用酒店。
b）每個旅行團在入住日的早晨到達，並在退房日的晚上離開酒店。
c）後入住的旅行團需要在前一團退房後的隔天早晨，才能入住
d）除了第一團，其他旅行團人數都比前一團多一人
e）有n名成員的旅行團則會在酒店停留n天。

輸入每一列包含第一組旅行團人數 S (1 <= S <= 10000)、第幾天查找 D (1 <= D < 10^15)。
輸出第 D 天入住旅行團人數。

範例輸入

1 6
3 10
3 14

範例輸出

3
5
6

想法

假設 X = 第 D 天入住旅行團人數。

使用等差數列公式得到 (S+X)(X-S+1) / 2 >= D。
化簡為 X^2 + X - S^2 + S - 2D >= 0。
解一元二次方程式，對 X 向上取整即為所求。

程式碼

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;

int main(){
    fastio;
    int S;
    long long D, C;
    long long ans;
    while(cin >> S >> D){
        C = -S*S+S-2*D;
        ans = ceil((-1.0 + sqrt(1-4*C)) / 2.0);
        cout << ans << "\n";
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, ,