Thursday, December 08, 2011

[UVa] 11150 - Cola

It was pretty disgusting for me all this time that I couldn't solve this one. I've been a pro at all of it's similar ones. This one actually gave me a very generalized approach.
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.

Connect Rapoo MT750S with Linux (Tested on Manjaro)

 I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...