UVa 119

From Algorithmist
Jump to navigation Jump to search

119 - Greedy Gift Givers[edit]

Summary[edit]

A typical Simulation problem. Follow the instruction carefully.

Explanation[edit]

N can be at most 10, so the naive array implementation will do.

#include <iostream>
#include <fstream>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

using namespace std;

int stt;
char tennguoi[130],ten[11][15];
int songuoi,tiencho,songuoinhan;
int tien[11][2];
char nguoicho[15];
char nguoinhan[15];


int timten(char a[],char b[11][15])
{
	int i,j;
	for(i=0;i<songuoi;i++)
		for(j=0;j<15;j++)
		{
			if(b[i][j]==' ' && a[j]=='\0')
				return i;
			if(a[j]!=b[i][j])
				break;
		}
}

void solve()
{
	int z,du;
	du=tiencho%songuoinhan;
	z=timten(nguoicho,ten);
	tien[z][0]=tien[z][0]-tiencho+du;
}

void solve2()
{
	int x;
	x=timten(nguoinhan,ten);
	tien[x][0]=tien[x][0]+tiencho/songuoinhan;
}

void output()
{
	int i,j;
	if(stt!=0)
		printf("\n");
	for(i=0;i<songuoi;i++)
		{	
			for(j=0;j<12;j++)
			{
				if(ten[i][j]==' ')
					break;	
				printf("%c",ten[i][j]);	
			}
			printf(" %d\n",tien[i][0]);
		}

}

void reset(char a[])
{
	int i;
	for(i=0;i<130;i++)
		a[i]='\0';
}

void khoitri(int a[11][2])
{
	int i,j;
	for(i=0;i<11;i++)
		for(j=0;j<11;j++)
			a[i][j]=0;
}

int main()
{
	int i,j,k;
	
	stt=0;
	while(scanf("%d\n",&songuoi)>0)
	{
		khoitri(tien);
		if(songuoi==0)
			break;
		else
		{	
			reset(tennguoi);
			gets(tennguoi);
			k=0;
			for(i=0;i<songuoi;i++)
			{	
				for(j=0;j<12;j++)
				{
					ten[i][j]=tennguoi[k];
					k++;
					if(tennguoi[k]==' ' || tennguoi[k]=='\0')
					{
						j++;
						k++;
						ten[i][j]=' ';
						break;
					}	
				}
			}
			for(i=0;i<songuoi;i++)
			{
				reset(nguoicho);
				scanf("%s",&nguoicho);
				scanf("%d",&tiencho);
				scanf("%d",&songuoinhan);
				if(songuoinhan>0)
				{
					solve();
					
					for(j=0;j<songuoinhan;j++)
					{
						reset(nguoinhan);
						scanf("%s",&nguoinhan);
						solve2();
					}	
				}
			}
			output();
			stt++;
		}
	}
	return 0;
}

Java Solution using HashMap

import java.util.HashMap;
import java.util.Scanner;

/**
 * 
 * 
 * @author Md Johirul Islam<johirbuet@gmail.com>
 *
 */
public class UVA119 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int counter=0;
		while(sc.hasNext())
		{
			int n=sc.nextInt();
			HashMap<String, Integer> map=new HashMap<>();
			String [] names=new String[n];
			for(int i=0;i<n;i++)
			{
				String s=sc.next();
				names[i]=s;
				map.put(s, 0);
			}
			for(int p=0;p<n;p++)
			{
				String giver=sc.next();
				int money=sc.nextInt();
				int getters=sc.nextInt();
				if(getters==0)
				{
					continue;
				}
				int perPerson=money/getters;
				map.put(giver,map.get(giver)-(perPerson*getters));
				for(int i=0;i<getters;i++)
				{
					String per=sc.next();
					map.put(per, map.get(per)+perPerson);
				}
			}
			if(counter>0)
                               System.out.println();
                        counter++;
			for(int i=0;i<n;i++)
			{
				System.out.println(names[i]+" "+map.get(names[i]));
			}
			
		}
		sc.close();
	}
}

Gotcha's[edit]

Names should be printed in the order they appeared. Put one more line at the end will give your feedback as wrong answer (not presentation error as usual).

One trick to avoid this is to print a newline before output the answers for every group except the first group. For example, use a counter,

if (counter>1) cout << endl;

Input[edit]

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

Output[edit]

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

liz -3
steve -24
dave 27

Solution[edit]