d189 - 11150 - Cola

🔗 前往 ZeroJudge 原題

題目描述

題目描述了利用空可樂瓶換取新可樂的過程，要求計算在給定初始可樂數量 N 的情況下，最多可以喝到的可樂總數。可以向朋友借空瓶，但最終需要歸還相同數量的空瓶。

解題思路

題目可以簡化為一個數學問題。初始有 N 瓶可樂，喝完後有 N 個空瓶。每 3 個空瓶可以換 1 瓶可樂。因此，可以換到的可樂數量為 N / 3。換到的可樂喝完後又會產生新的空瓶。為了最大化可樂的總數，可以先向朋友借 1 個空瓶，這樣初始空瓶數量為 N + 1。然後，不斷地用 3 個空瓶換 1 瓶可樂，直到空瓶數量不足 3 個。最後，將借來的 1 個空瓶還給朋友。

程式碼直接計算了可樂總數：N + N / 2。這是因為初始 N 瓶加上可以換到的 N/3 瓶，再加上借來的空瓶換到的可樂，總共可以喝到 N + N/3 + 1 瓶。由於題目允許借空瓶，所以可以先借一個空瓶，然後計算總的可樂數。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include<stdio.h>
int main(){
	int c;
	while(scanf("%d",&c)>0)
		printf("%d\n",c/2+c);
}