切換
舊版
前往
大廳
主題

ZeroJudge - e519: 10633 - Rare Easy Problem 解題心得

Not In My Back Yard | 2019-11-09 23:52:39 | 巴幣 0 | 人氣 344

題目連結:


題目大意:
給定一正整數(介於 10 ~ 10 ^ 18 之間。等於 0 時代表輸入結束),代表 N - M 的值,其中 N 是一個至少為 2 位數的正整數、 M 是 N 去掉最後一位(最低位)之後的數字。

求 N 可能為哪些數字?



範例輸入:
18
0


範例輸出:
19 20


解題思維:
窮舉一些 N 值可以看到,當 N 的尾數為 9 和 0 (相鄰的數字,例如 19 和 20 或是 29 和 30)時,他們產生出來的 N - M 之值(以下以 X 代稱 )皆相同,且其值皆為 9 的倍數。而其他的 N - M 皆是一對一對應。

因此,當 X 是 9 的倍數時,答案是 X × 10 ÷ 9 - 1 以及 X × 10 ÷ 9 這兩個數字;至於其他的狀況,答案為 floor(X × 10 ÷ 9) 。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

心彩
那個這裡可能要改一下 floor(X × 10 ÷ 9) 真的在程式裡寫floor 結果反而沒過
2023-06-12 15:57:30
Not In My Back Yard
Hmmmm
我還沒有想通為什麼會出錯。可以把出錯的程式碼給我看嗎?
2023-06-12 19:31:35
心彩
我要怎麼傳給你? 是C++的floor 不支援 unsigned long long?
2023-06-13 08:52:09
Not In My Back Yard
就先扔到 codepile(現在好像強制要登入?)或是 codepad 等等的地方再傳網址即可。
2023-06-13 19:32:50
心彩
http://codepad.org/TgHdbcfK 這樣 看行不行
2023-06-13 20:23:05
Not In My Back Yard
OK,是我想的那樣沒有錯。

C++ 的 floor() 會把你傳入的參數轉成 double 型態,一般來說 short 、 int 、 unsigned int 等轉到 double 不會有問題,但是 long long 和 unsigned long long 就會有浮點數誤差出現了(double 型態的精確度大約為 15 位數)。

你可以試試看輸出 double(123456789012345678ULL) 就會看到結果是不精確的了。

回到文章來看,我為何提及 floor()?因為這邊確實需要 floor() 函數,不過也可以寫成 X × 10 ÷ 9 取整數部分(因為數字都是正數,所以不用擔心會錯)。這邊的敘述因為比較老舊,所以我是直接寫 floor(),到某時期之後我基本上會補充說明這邊的 floor() 是等價於無條件捨去小數點(當然,是對正數來說)。

那不用 floor() 怎麼求整數部分?很簡單,C++ 已經有內建的除法取整的功能了,直接寫 n / 9 就會只剩整數部分了。
2023-06-13 20:55:22
Not In My Back Yard
至於為何我這麼愛寫 floor() 在文章之中,說實話我不知道。

比較新的文章有試著把 floor() 戒掉了,不過這也代表著有時候說明會變得比較冗長、語句結構比較複雜。可能這就是我一開始使用 floor() 的原因?畢竟每次都提及「OOXX 取整數部分」有點長。

如果造成你的困擾了,請見諒。
2023-06-13 21:00:09
心彩
我會覺得既然特別提到floor 的概念 代表程式要實做這件事 但這用整數除法就能做到的事 概念都懂 也沒甚麼感到困擾的地方啦
2023-06-13 21:19:55

相關創作

更多創作