I exhaustively checked for every possible borrowing. For one thing to be noted, you can borrow a max of 2 bottles. How? Just examine the 200 case without borrowing. In the end you'll have 2 unused bottles. Since it's the highest case, so there can be a max of 2 unused bottles, so a max of 2 returnable bottles/borrowable bottles. :|
/* Faith-M */ //Headers #include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <climits> #include <clocale> //Defines #define pow2(i) (1<<i) #define bit(i) (1<<i) #define isOdd(i) (i&1) #define isEven(i) (!(i&1)) #define isPrime(i) ((i==2) || ((i&1) && !pTest[i])) //pTest has to be the bool array's name #define sz(i) i.size() #define vec(type,name) vector< type > name #define rep(i,a,b) for(int i=a ; i<=b ; i++) #define swap(type,a,b) {type t=a; a=b; b=t;} #define sum(a,n) ( (n*(n+1)/2) - (a-1)*a/2 ) #define iscap(i) (i>='A'&&i<='Z') #define issmall(i) (i>='a'&&i<='z') #define isnum(i) (i>='0'&&i<='9') #define issymbol(i) (!(i>='a'&&i<='z') && !(i>='A'&&i<='Z') && !(i>='0'&&i<='9')) #define mk(i,j) make_pair(i,j) #define ERROR 1e-11 //Type Defs typedef long long lint; typedef unsigned long long ulint; typedef long double ldouble; using namespace std; int proc(int n, int borrow) { int cola = 0-borrow; while (n>=3) { cola += n; cola -= n%3; n = (n/3 + (n%3)); } cola += n; if (n<borrow) return -1; else return cola; } int results[300]; int main() { int i, res1, res2, res3; for (i=0 ; i<=200 ; i++) { res1 = proc(i, 0); res2 = proc(i+1, 1); res3 = proc(i+2, 2); results[i] = max(max(res1,res2),max(res2,res3)); } //freopen("input.txt","r+",stdin); //freopen("output.txt","w+",stdout);/**/ // TEST CASE // /*int kase=1, kounter=1;/**/ while (scanf("%d",&i)==1) { printf("%d\n",results[i]); } return 0; }
No comments:
Post a Comment
Post your comment here. If you want to say something about programming problems, scripts, software etc, please try to be as descriptive as possible.