uva 119 : Greedy Gift Givers

Greedy Gift Givers

The Problem

This problem involves determining, for a group of gift-giving friends, how much more each person gives than they receive (and vice versa for those that view gift-giving with cynicism).

In this problem each person sets aside some money for gift-giving and divides this money evenly among all those to whom gifts are given.

However, in any group of friends, some people are more giving than others (or at least may have more acquaintances) and some people have more money than others.

Given a group of friends, the money each person in the group spends on gifts, and a (sub)list of friends to whom each person gives gifts; you are to write a program that determines how much more (or less) each person in the group gives than they receive.

The Input

The input is a sequence of gift-giving groups. A group consists of several lines:

• the number of people in the group,
• a list of the names of each person in the group,
• a line for each person in the group consisting of the name of the person, the amount of money spent on gifts, the number of people to whom gifts are given, and the names of those to whom gifts are given.

All names are lower-case letters, there are no more than 10 people in a group, and no name is more than 12 characters in length. Money is a non-negative integer less than 2000.

The input consists of one or more groups and is terminated by end-of-file.

The Output

For each group of gift-givers, the name of each person in the group should be printed on a line followed by the net gain (or loss) received (or spent) by the person. Names in a group should be printed in the same order in which they first appear in the input.

The output for each group should be separated from other groups by a blank line. All gifts are integers. Each person gives the same integer amount of money to each friend to whom any money is given, and gives as much as possible. Any money not given is kept and is part of a person's ``net worth'' printed in the output.

Sample Input

5
dave laura owen vick amr
dave 200 3 laura owen vick
owen 500 1 dave
amr 150 2 vick owen
laura 0 2 amr vick
vick 0 0
3
liz steve dave
liz 30 1 steve
steve 55 2 liz dave
dave 0 2 steve liz

Sample Output

dave 302
laura 66
owen -359
vick 141
amr -150

liz -3
steve -24
dave 27

Solution :




#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<map>
using namespace std;
int main()
{
    //freopen("input.txt","r",stdin);
    int n,y=0;
    while(scanf("%d",&n)==1)
    {
        if(y>0)printf("\n");
        y=100;
        string name[n],s;
        int account[n],m,b,l;
        map<string,int>w;
        for(int i=0;i<n;i++)
        {
            cin >> name[i];
            w[name[i]]=i;
            account[i]=0;
        }
        for(int i=0;i<n;i++)
        {
            cin >> s >> b >> m;
            int p=w[s];
            if(m==0)continue;
            account[p]=account[p]+b%m-b;
            for(int j=0;j<m;j++)
            {
                cin >> s;
                p=w[s];
                account[p]=account[p]+b/m;
            }
        }
        for(int i=0;i<n;i++)
        cout << name[i] << " "<<account[i]<< endl;
    }
    return 0;
}

uva : 136 - Ugly Number

Ugly Numbers

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...


shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 1500'th ugly number.

Input and Output

There is no input to this program. Output should consist of a single line as shown below, with <number> replaced by the number computed.

Sample output

The 1500'th ugly number is <number>.

Solution :

#include<stdio.h>
int main()
{
    printf("The 1500'th ugly number is 859963392.\n");
}

uva : 113 - Power of Cryptography

Power of Cryptography

Background

Current work in cryptography involves (among other things) large prime numbers and computing powers of numbers modulo functions of these primes. Work in this area has resulted in the practical use of results from number theory and other branches of mathematics once considered to be of only theoretical interest.
This problem involves the efficient computation of integer roots of numbers.

The Problem

Given an integer  and an integer  you are to write a program that determines  , the positive  root of p. In this problem, given such integers n and p, p will always be of the form  for an integer k (this integer is what your program must find).

The Input

The input consists of a sequence of integer pairs n and p with each integer on a line by itself. For all such pairs  , and there exists an integer k,  such that  .

The Output

For each integer pair n and p the value  should be printed, i.e., the number k such that  .

Sample Input

2
16
3
27
7
4357186184021382204544

Sample Output

4
3
1234

Solution: 

#include<stdio.h>

#include<math.h>
int main()
{
    double n,p;
    while(scanf("%lf %lf",&n,&p)==2)
    {
        printf("%.0lf\n",(pow(p,1/n)));
    }
    return 0;
}

uva 112 : Tree Summing

 

Tree Summing

Background

LISP was one of the earliest high-level programming languages and, with FORTRAN, is one of the oldest languages currently being used. Lists, which are the fundamental data structures in LISP, can easily be adapted to represent other important data structures such as trees.
This problem deals with determining whether binary trees represented as LISP S-expressions possess a certain property.

The Problem

Given a binary tree of integers, you are to write a program that determines whether there exists a root-to-leaf path whose nodes sum to a specified integer. For example, in the tree shown below there are exactly four root-to-leaf paths. The sums of the paths are 27, 22, 26, and 18.

Binary trees are represented in the input file as LISP S-expressions having the following form.

empty tree              ::=            ()

tree             ::=            empty tree    (integer tree tree)

The tree diagrammed above is represented by the expression (5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )
Note that with this formulation all leaves of a tree are of the form (integer () () )
Since an empty tree has no root-to-leaf paths, any query as to whether a path exists whose sum is a specified integer in an empty tree must be answered negatively.

The Input

The input consists of a sequence of test cases in the form of integer/tree pairs. Each test case consists of an integer followed by one or more spaces followed by a binary tree formatted as an S-expression as described above. All binary tree S-expressions will be valid, but expressions may be spread over several lines and may contain spaces. There will be one or more test cases in an input file, and input is terminated by end-of-file.

The Output

There should be one line of output for each test case (integer/tree pair) in the input file. For each pair I,T (I represents the integer, T represents the tree) the output is the string yes if there is a root-to-leaf path in T whose sum is I and no if there is no path in T whose sum is I.

Sample Input

22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))

20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))

10 (3 

     (2 (4 () () )

        (8 () () ) )

     (1 (6 () () )

        (4 () () ) ) )

5 ()

Sample Output

yes

no

yes

no

Solution: 

#include <stdio.h>

#define empty 0

int ans;

int solve(int sum, int target, char *c) {

        int flag = 0, leaf = 0, token, neg;

        while(*c == ' ' || *c == '\n')

               *c = getchar();

        if(*c == '(') {

               token = 0, flag = 0, neg = 1;

               while(*c = getchar()) {

                       if(*c >= '0' && *c <= '9')

                               token = token*10 + *c-'0', flag = 1;

                       else {

                               if(*c == '-')  neg = -1;

                               else break;

                       } 

               }

               token *= neg;

               while(*c == ' ' || *c == '\n')

                       *c = getchar();

               if(flag == 0) {

                       return empty;

               }

               int left = solve(sum+token, target, c);

               while((*c = getchar()) != '(');

               int right = solve(sum+token, target, c);

               while((*c = getchar()) != ')');

               if(left == 0 && right == 0) {

                       if(sum+token == target)

                               ans = 1;

               }

               return 1;

        }

}

int main() {

        int target;

        char c;

        while(scanf("%d", &target) == 1) {

               ans = 0;

               c = getchar();

               solve(0, target, &c);

               if(ans == 1)

                       puts("yes");

               else

                       puts("no");

        }

    return 0;

}

uva : 111 History Grading

History Grading

Background

Many problems in Computer Science involve maximizing some measure according to constraints.

Consider a history exam in which students are asked to put several historical events into chronological order. Students who order all the events correctly will receive full credit, but how should partial credit be awarded to students who incorrectly rank one or more of the historical events?

Some possibilities for partial credit include:

1.     1 point for each event whose rank matches its correct rank

2.     1 point for each event in the longest (not necessarily contiguous) sequence of events which are in the correct order relative to each other.

For example, if four events are correctly ordered 1 2 3 4 then the order 1 3 2 4 would receive a score of 2 using the first method (events 1 and 4 are correctly ranked) and a score of 3 using the second method (event sequences 1 2 4 and 1 3 4 are both in the correct order relative to each other).

In this problem you are asked to write a program to score such questions using the second method.

The Problem

Given the correct chronological order of n events  as  where  denotes the ranking of event i in the correct chronological order and a sequence of student responses  where  denotes the chronological rank given by the student to event i; determine the length of the longest (not necessarily contiguous) sequence of events in the student responses that are in the correct chronological order relative to each other.

The Input

The first line of the input will consist of one integer n indicating the number of events with  . The second line will containn integers, indicating the correct chronological order of n events. The remaining lines will each consist of n integers with each line representing a student's chronological ordering of the n events. All lines will contain n numbers in the range  , with each number appearing exactly once per line, and with each number separated from other numbers on the same line by one or more spaces.

The Output

For each student ranking of events your program should print the score for that ranking. There should be one line of output for each student ranking.

Sample Input 1

4

4 2 3 1

1 3 2 4

3 2 1 4

2 3 4 1

Sample Output 1

1

2

3

Sample Input 2

10

3 1 2 4 9 5 10 6 8 7

1 2 3 4 5 6 7 8 9 10

4 7 2 3 10 6 9 1 5 8

3 1 2 4 9 5 10 6 8 7

2 10 1 3 8 4 9 5 7 6

Sample Output 2

6

5

10

9

Solution: 

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <cctype>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <sstream>

#include <set>

#include <math.h>

using namespace std;

#define MAXN 22

int Orginal[MAXN],Rank[MAXN],Store[MAXN];

int N, X[MAXN];

void ReadOrginal() 

{

       int i;

       scanf("%d",&N);

       for(i = 0; i<N; i++)

          scanf("%d",&Orginal[i]);

}

void LIS() 

{

         int i, j, max;

             int largest = 0;

         for(i = 1; i<= N; i ++) 

        {

             max = 0;

             for(j = i-1; j >= 0; j --) 

            {

                 if(Store[i]>Store[j])

                   if(X[j] > max)

                      max = X[j];

             }

             X[i] = max+1;

             if(max>largest)

              largest = max;

          }

          printf("%d\n",largest+1 );

}

int main() 

{

       int temp, i ;

       ReadOrginal();

       while(scanf("%d",&temp) == 1) 

      {

          Store[temp] = Orginal[0];

          for(i = 1; i<N; i++) 

         {

             scanf("%d",&temp);

             Store[temp] = Orginal[i];

          }

          LIS();

       }

     return 0;

}

uva 105 : the Skyline Problem

The Skyline Problem

The Problem

With the advent of high speed graphics workstations, CAD (computer-aided design) and other areas(CAM, VLSI design) have made increasingly effective use of computers. One of the problems with drawing images is the elimination of hidden lines | lines obscured by other parts of a drawing. You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. To make the problem tractable, all buildings are rectangular in shape and

they share a common bottom (the city they are built in is very at). The city is also viewed as two-dimensional. A building is specified by an ordered triple (Li;Hi;Ri) where Li and  Ri  are left and right coordinates, respectively, of building i and Hi is the height of the building. In the diagram below buildings are shown on the left with triples (1; 11; 5); (2; 6; 7); (3; 13; 9); (12; 7; 16); (14; 3; 25); (19; 18; 22); (23; 13; 29); (24; 4; 28) the skyline, shown on the right, is represented by the sequence:

(1; 11; 3; 13; 9; 0; 12; 7; 16; 3; 19; 18; 22; 3; 23; 13; 29; 0)

The Input

The input is a sequence of building triples. All coordinates of buildings are integers less than 10,000 and there will be at least one and at most 5,000 buildings in the input file. Each building triple is on a line by itself in the input file. All integers in a triple are separated by one or more spaces. The triples will be sorted by Li, the left x-coordinate of the building, so the building with the smallest left x-coordinate is first in the input file.

The Output

The output should consist of the vector that describes the skyline as shown in the example above. In the skyline vector (v1; v2; v3; : : : ; vn-2; vn-1; vn), the vi such that i is an even number represent a horizontal line (height). The vi such that i is an odd number represent a vertical line (x-coordinate).The skyline vector should represent the \path" taken, for example, by a bug starting at the minimum

X-coordinate and traveling horizontally and vertically over all the lines that define the skyline. Thus the last entry in all skyline vectors will be a 0.

Sample Input

1 11 5

2 6 7

3 13 9

12 7 16

14 3 25

19 18 22

23 13 29

24 4 28

Sample Output

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Solution : 

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <cctype>

#include <stack>

#include <list>

#include <vector>

#include <map>

#include <sstream>

#include <utility>

#include <set>

#include <math.h>

using namespace std;

int main()

{

 int height[10001] = {0};

 int left, right, buildingHeight;

 // read our buildings

 while (cin >> left >> buildingHeight >> right)

 {

  for (int i = left; i < right; ++i)

  {

   if (buildingHeight > height[i])

    height[i] = buildingHeight;

  }

 }

 bool notFirst = false; // only show a preceeding space on the non-first entries

 int currentHeight = 0;

 for (int pos = 0; pos != 10000; ++pos)

 {

  if (height[pos] != currentHeight)

  {

   if (notFirst)

    cout << ' ';

   else    notFirst = true;

   cout << pos << ' ' << height[pos];

   currentHeight = height[pos];

  }

 }

 cout << endl;

 return 0;

}