天天看點

網易2017秋招程式設計題:買蘋果 [python]

'''

[程式設計題] 買蘋果

時間限制:1秒

空間限制:32768K

小易去附近的商店買蘋果,奸詐的商販使用了捆綁交易,隻提供6個每袋和8個每袋的包裝(包裝不可拆分)。 

可是小易現在隻想購買恰好n個蘋果,小易想購買盡量少的袋數友善攜帶。如果不能購買恰好n個蘋果,小易将不會購買。 

輸入描述:

輸入一個整數n,表示小易想購買n(1 ≤ n ≤ 100)個蘋果

輸出描述:

輸出一個整數表示最少需要購買的袋數,如果不能買恰好n個蘋果則輸出-1

輸入例子1:

20

輸出例子1:

3

'''

'''

解題思路:最小公倍數

   這道題目思路很簡單,先盡量買8個裝的蘋果,若還不夠,則繼續買6個裝的蘋果,

   如果不能恰好買6個裝的蘋果就先退一個8個裝的蘋果,那麼問題就是退幾次8個裝的蘋果,

   答案是退三次,因為6和8的最小公倍數是24,也就是8的三倍,如果退三次8個裝的蘋果都沒能比對,

   那麼多退也是沒用的,問題的複雜度數O(3)

'''

'''

代碼運作結果:

答案正确:恭喜!您送出的程式通過了所有的測試用例

'''

n = int(input())

bag_num = n // 8
remains = n % 8

for i in range(3):
    if remains % 6 == 0:
        if remains == 0:
            break
        else:
            bag_num += remains // 6
            remains = 0
    else:
        remains += 8
        bag_num -= 1

if remains:
    print(-1)
else:
    print(bag_num)