12207 – That is Your Queue UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3359

Data structures, Linked List.

How I did it

• I read the number of elements and queries.
• If the number of elements is equal or less than 1000 I push the number of element into a linked list, otherwise I push 1000 elements.
• Read the queries, if the querie is  “N” print the front element of the list and pop the element and push it into the tail. If the querie is “E” read the value, remove the value from the list and push in the front of the list.

Hints

• When the querie is E I dont print any value.
• I initialize the list at most 1000 elements because the number of queries are 1000, and the idea is handle a queue.
• If you initialize the linked list, deque or queue with 1000000000 you will get time limit.

Code

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <list>

using namespace std;

list<int> lista;

void init(int N)
{
    lista.clear();
    int lim = min(N, 1000);
    for(int i=1; i<=lim; i++)
        lista.push_back(i);
}

int main()
{
    int dim, queries, pos, tmp, casos = 1;
    char ins;
    while(scanf("%d %d", &dim, &queries))
    {
        if(!dim && !queries)
           break;

        init(dim);
        printf("Case %d:\n", casos++);
        for(int i=1; i<=queries; i++)
        {
            cin>>ins;
            if(ins == 'N')
            {
                tmp = lista.front();
                printf("%d\n", tmp);
                lista.pop_front();

                //if(dim <= 1000)
                  lista.push_back(tmp);
            }
            else
            {
                scanf("%d", &pos);
                lista.remove(pos);
                lista.push_front(pos);
            }
        }
    }
return 0;
}

11804 – Argentina UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2904

Complete search.

How I did it

• I read the number of cases.
• For each case read the player and atk def points. I save each player inside a struct.
• I save the ten players into a vector.
• I sort the vector in lexicography order by name.
• To get the answer is necessary nest 5 loops and filter the atk first. If there is a tie filter by def. and if is a tie in atk and def, filter by lexicography atk order.
• Print the result.

Hints

• The input is really small so n^5 algorithm it is ok.
• The sorting is first by atk, if there is two equals atks, sort by def if there is a tie, sort the atk player by name.

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

struct pepe
{
    string name;
    int atk;
    int def;
};

vector<pepe> vec, atkAns,defAns;

bool cmp(pepe a, pepe b)
{
    return a.name < b.name;
}

int getDef(int a,int b,int c,int d,int e)
{
    map<int,int> pMap;
    pMap[a] = 1;pMap[b] = 1;pMap[c] = 1;
    pMap[d] = 1;pMap[e] = 1;

    int ans = 0;
    for(int i=0; i<10; i++)
    {
        if(pMap[i] == 0)
          ans += vec[i].def;
    }
return ans;
}

void setAns(int a,int b,int c,int d,int e)
{
    map<int,int> pMap;
    pMap[a] = 1;pMap[b] = 1;pMap[c] = 1;
    pMap[d] = 1;pMap[e] = 1;

    atkAns.clear(), defAns.clear();

    for(int i=0; i<10; i++)
    {
        if(pMap[i] == 1)
          atkAns.push_back(vec[i]);
        else
            defAns.push_back(vec[i]);
    }
}
void checkOrder(int a,int b,int c,int d,int e)
{
    vector<pepe> tmp;
    tmp.push_back(vec[a]);tmp.push_back(vec[b]);tmp.push_back(vec[c]);
    tmp.push_back(vec[d]);tmp.push_back(vec[e]);
    bool flag = false;

    for(int i=0; i<atkAns.size(); i++)
    {
        if(tmp[i].name < atkAns[i].name)
        {
            flag = true;
            break;
        }
        else if(tmp[i].name > atkAns[i].name)
                break;
    }
    if(flag)
       setAns(a,b,c,d,e);
}
int main()
{
    string name;
    pepe p;
    int casos, atk, def;
    int vAtk, vDef, tmp, tmpDef;

    scanf("%d", &casos);
    for(int z=1; z<=casos; z++)
    {
            for(int i=1; i<=10; i++)
            {
                cin>>p.name;
                scanf("%d %d", &p.atk, &p.def);
                vec.push_back(p);
            }
            sort(vec.begin(), vec.end(), cmp);

            vAtk = vDef = -1000;

            for(int a=0; a<vec.size(); a++)
                for(int b=a+1; b<vec.size(); b++)
                   for(int c=b+1; c<vec.size(); c++)
                       for(int d=c+1; d<vec.size(); d++)
                           for(int e=d+1; e<vec.size(); e++)
                           {
                                tmp = vec[a].atk + vec[b].atk + vec[c].atk + vec[d].atk + vec[e].atk;
                                if(tmp > vAtk)
                                {
                                    vAtk = tmp;
                                    vDef = getDef(a,b,c,d,e);
                                    setAns(a,b,c,d,e);
                                }
                                else if(tmp == vAtk)
                                {
                                    tmpDef = getDef(a,b,c,d,e);
                                    if(tmpDef > vDef)
                                    {
                                        vAtk = tmp;
                                        vDef = tmpDef;
                                        setAns(a,b,c,d,e);
                                    }
                                    else if(tmpDef == vDef)
                                    {
                                        checkOrder(a,b,c,d,e);
                                    }
                                }
                           }
            printf("Case %d:\n", z);
            for(int i=0; i<atkAns.size(); i++)
            {
                if(i==0)
                  printf("(%s, ", atkAns[i].name.c_str());
                else if(i == atkAns.size() - 1)
                       printf("%s)\n", atkAns[i].name.c_str());
                else
                    printf("%s, ", atkAns[i].name.c_str());
            }

            for(int i=0; i<defAns.size(); i++)
            {
                if(i==0)
                  printf("(%s, ", defAns[i].name.c_str());
                else if(i == defAns.size() - 1)
                       printf("%s)\n", defAns[i].name.c_str());
                else
                    printf("%s, ", defAns[i].name.c_str());
            }
            vec.clear(), atkAns.clear(),defAns.clear();
    }
return 0;
}

696 – How Many Knights UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=637

Brute force.

How I did it

• I read the number of rows and columns.
• If rows = 1 or columns = 1 I return row * columns.
• If the rows = 2 or columns = 2 I simulate the process. The recurrence for this case is:

KK..KK..kk..kk
KK..KK..kk..kk

• Otherwise I simulate the process. The recurrence for any other case is:

K.K.K
.K.K.
K.K.K
.K.K.

• Print the number of knights.

Hints

• Solve the problem in paper.
• This solution is slow, you can solve this problem with a direct formula too.

Code

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int getAns(int r, int c)
{
    int val, ans = 0;
    if(r == 1 || c == 1)
       return r * c;
    else if (r == 2 || c == 2)
    {
        if(c == 2)
           swap(r, c);
        int cont = 0;
        for(int i=1; i<=c; i++)
        {
            cont++;
            if(cont <= 2)
                ans++;
            else if(cont == 4)
                cont = 0;
        }

    return ans * 2;
    }

    ans = 0;
    for(int i=1; i<=r; i++)
    {
        for(int j=1; j<=c; j++)
        {
            if(i % 2 != 0)
            {
                if(j % 2 != 0)
                {
                    ans++;
                }
            }
            else
            {
                if(j % 2 == 0)
                  ans++;
            }
        }
    }
    return ans;
}

int main()
{
    int row, col, ans;

    while(scanf("%d %d", &row, &col))
    {
        if(!row && !col)
           break;

        ans = getAns(row, col);
        printf("%d knights may be placed on a %d row %d column board.\n", ans, row, col);
    }
return 0;
}