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;
}

Sunday, December 04, 2011

[UVa] 116 - Unidirectional TSP

#include <stdio.h>

int dir[100][100];
int mtx[100][100];
int path[100];

int main()
{
 int a, b, c, min;
 int i, j, row, col, a_dir, c_dir;

 while (scanf("%d %d",&row,&col)==2)
 {
     for (i=1 ; i<=row ; i++)
            for (j=1 ; j<=col ; j++)
                scanf("%d",&mtx[i][j]);

        for (j=col-1 ; j>=1 ; j--)
        {
            for (i=1 ; i<=row ; i++)
            {
                if (i-1<1)
                {
                    a_dir = -1;
                    a = mtx[i][j] + mtx[row][j+1];
                } else
                {
                    a_dir = 0;
                    a = mtx[i][j] + mtx[i-1][j+1];
                }
                if (i+1>row)
                {
                    c_dir = -1;
                    c = mtx[i][j] + mtx[1][j+1];
                } else
                {
                    c_dir = 0;
                    c = mtx[i][j] + mtx[i+1][j+1];
                }
                b = mtx[i][j] + mtx[i][j+1];

                if (a<=b && a<=c)
                {
                    mtx[i][j] = a;

                    if (a_dir<0)
                    {
                        if (a==b) { dir[i][j] = i; }
                        else if (a==c) { dir[i][j] = i+1; }
                        else { dir[i][j] = row; }
                    } else {
                        if (a==c && c_dir<0) dir[i][j] = 1;
                        else dir[i][j] = i-1;
                    }
                }
                else if (b<=a && b<=c)
                {
                    mtx[i][j] = b;


                    if (b==a)
                    {
                        if (a_dir<0)
                        {
                            dir[i][j] = i;
                        } else
                        {
                            dir[i][j] = i-1;
                        }
                    } else if (b==c)
                    {
                        if (c_dir<0)
                        {
                            dir[i][j]=1;
                        } else
                        {
                            dir[i][j]=i;
                        }
                    } else
                    {
                        dir[i][j] = i;
                    }

                }
                else if (c<=a && c<=b)
                {
                    mtx[i][j] = c;
                    if (c_dir<0)
                    {
                        dir[i][j] = 1;
                    } else {
                        if (c==a) { dir[i][j]=i-1; }
                        else if (c==b) { dir[i][j]=i; }
                        else { dir[i][j]=i+1; }
                    }
                }

            }
        }

        for (i=1, min=mtx[1][1], path[1]=1 ; i<=row ; i++)
        {
            if (mtx[i][1]<min)
            {
                min = mtx[i][1];
                path[1] = i;
            }
        }
        printf("%d",path[1]);
        for (j=2 ; j<=col ; j++)
        {
            path[j] = dir[path[j-1]][j-1];
            printf(" %d",path[j]);
        }


        printf("\n%d\n",min);

 }

 return 0;
}

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...