#UVa:10170-The Hotel with Infinite Rooms

灆洢 2018-09-26 23:21:02

根據題目敘述可以得到答案即為第 S 團 ~ 第 n 團所待的天數大於等於 D 天中 n 最小的那位,寫成數學式:
\( S + (S+1) + (S+2) + …… + n = \frac{(S + n) \times (n – S + 1)}{2} \text{(等差級數梯形公式)} \leq D \text{(n 為最小符合此式的整數值)} \)

經過整理後可以得到一個一元二次方程式,利用公式解得到相等時 n 應為多少。如果 n 剛好是整數就是答案;如果有小數位則對其大於它的最小整數即是答案。

P.S. 注意此題數值大小需使用到 long long int

C++(0.000)

/*******************************************************/
/* UVa 10170 The Hotel with Infinite Rooms             */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/09/26                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
  int S, D;
  while(scanf("%d%d", &S, &D) != EOF){
    printf("%d\n", (int)ceil((-1 + sqrt(1 - 4 * (-S*S + S - 2*D))) / 2));
  }

  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料