Challenges Week 5

SVATRA - 25 points

As the summer approaches, you are very motivated to start cycling again. You thought it would be fun to keep track of things, so you and your friends downloaded an app called SVATRA. This app allows you to track your various tours. Over a given time period, you can see a list of every single journey your friends have taken. This list contains, for each journey, the name of the person in question and the number of kilometres. At the end, you want to know how many kilometres in total some of your friends have cycled.

Input: The first line contains two integers n and p. n is the number of journeys of your SVATRA friends, and p is the number of friends you have on SVATRA (note: this does not mean that they must appear on the list of requests; it simply means that they exist!) The next n lines contain a string s, which represents the name of a SVATRA friend (all lowercase letters) and an integer c, which represents the number of kilometres that friend has cycled during that particular journey.

This is followed by a line with one integer m. Following, there are m lines of strings, representing the names of the SVATRA friends you are interested in knowing their total kilometres cycled of. Note that this does not mean that these names are mentioned before; they could be new ones! In these cases, simply print 0.

Output: m lines, each containing a single integer a that represents the total number of kilometres the requested friends have cycled, in the same order as the requests.

Constraints:

Example

WAR - 45 points

You may be familiar with the strategy board game Risk1 . You and your friends have invented a variant of this game, namely War. You are playing a game, and would like some help from a computer to find the optimal strategy. War is being played on a large grid map of size n × m, where every cell is either a country or an ocean. Every country has a little army for itself. You start in the upper left corner (which is always a country that you own), and you can only move east or south from any given country.

There are two types of countries: countries you already own, and countries which belong to an enemy. The size of their armies are indicated on the map as a positive number (say, 10) if the country is yours, and a negative number (say, −3) if the country belongs to an enemy. If you step into a country you already own, you’re lucky: these warriors are added to your army. Otherwise, you must battle the enemy! In this case, every warrior of the enemy is able to take down one of your warriors, before (s)he is killed. This decreases your army: if you are left with an army of size only 1, you should not step into an enemy country, because you would be killed in battle if you do. Finally, before moving into a new country, you must leave behind one of your warriors to guard the old country.

Your army does not have boats, so you can’t cross oceans. An ocean is indicated on a map by a number 0.

Your goal is to reach the lower right corner, and you want your army to be as large as possible when you get to that country. Given the contents of the War grid, write a program that outputs the maximum number of warriors you could have in your army when reaching the lower right corner. It is guaranteed that the map allows you to reach your destination, with an army size of at least 1.

Input: The first line will contain two integers indicating the grid size, n and m. The next n lines will contain m signed integers each, wij , representing the size of an army, or an ocean, in cell (i, j).

Output: A single integer representing the maximum number of warriors in your army, after reaching the lower right corner.

Constraints:

 for any indices i and j on the map

, and also  (if we take the map grid to be 0-indexed)

There will always be a path over countries from the upper left cell to the lower right cell, and there will always be a path which leaves you with a final army of at least 1 warrior.

Example