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