All Ireland Schools Programming Competition

Day 2 Problems

All Ireland Schools Programming Competition. How to enter Time Table Rules DCU Computers Guidelines Sample Problems Sample Problems IOI

Introduction

There are three problems contained in this document. The first problem day2a is the main problem for the day. The other two problems (day2b and day2c) are the Tie Break problems 1 and 2.

Note there are many more marks going for the main problem than there are for Tie Break problems. You should only do the Tie Break problem if you feel that you can’t improve on the main problem.

With each problem there will be a number of examples. For the main problem, some of the examples will be used (in addition to other unseen tests) to test your program. In the Tie Break problems all the tests will be will be unseen. The example files and solutions will be on the hard disk. The names of these files will be as given in the problem.

When you are finished, ensure that you have saved your files onto the root directory of the D: drive. (That is, a BASIC program for problem A should be saved as D:\day2a.bas.) You will also be given a floppy disk at the end, and you must also save your files to this disk and give it to a supervisor.

Please note that you cannot write to the C: drive.

Best of luck

Problem A Raucous Rockers

Description

You just inherited the rights to n previously unreleased songs recorded by the popular group Raucous Rockers. You plan to release a set of m compact disks with a selection of these songs. Each disk can hold a maximum of t minutes of music, and a song can not overlap from one disk to another.

Since you are a classical music fan and have no way to judge the artistic merits of these songs, you decide on the following criteria for making the selection:

a) The songs will be recorded on the set of disks in the order of the dates that they were written.

b) The total number of songs included will be maximized.

Input

The first line contains the values of n, t and m (integer numbers) followed by a line containing a list of the lengths of n songs, ordered by the date they were written. No song will be too long to fit on a disk, and it will not be possible to put all the songs on the disks

Output

The output will be an integer indicating the number of songs that, following the above selection criteria will fit on m disks.

Example 1

Input

10 5 3
5, 5, 5, 5, 5, 5, 5, 5, 5, 5

Output

3
In this example there are ten songs, and three disks. Each disk can hold 5 minutes worth of songs. In this case, all the songs last five minutes, so obviously only three songs can be recorded.

Example 2

Input

5 6 4
4, 3, 4, 4, 5

Output

4
Here there are 5 songs and 4 disks that can hold 6 minutes each. However it is not possible to hold more than one song on any disk, so only four songs can be recorded.

Example 3

Input

10 5 3
3, 5, 1, 2, 3, 5, 4, 1, 1, 5

Output

6
In this example there are ten songs, and three disks. The second line contains the lengths of each of the songs. E.G. the first song that was recorded lasts three minutes. The maximum number of songs that can fit on one disk is 6. (Remember that they have to be in date order.)

Instructions

Your program should be called day2a.bas if it is a BASIC program, day2a.pas if it is a Pascal program, day2a.c if it is a C program, day2a.cpp if it is a C++ program and day2a.lg if it is a logo program.

It should read its input from a file called day2a.dat, and write its output to a file called day2a.sol. The two example input files and the solutions are on the D: drive. The names of the input files are test2a1 and test2a2. The solution files are called test2a1.sol and test2a2.sol.

Note that if your program generates correct results for these files, it does not mean that your program is correct.

N.B. If you are writing a BASIC program ensure that it terminates with a system command, so that it exits to DOS. This is essential if it is to be processed automatically. You will get zero marks for the program if you neglect to do this.

Problem B Greedy Gift Givers

Description

You are to determine, 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.

Input

The input is a group of gift-givers which 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.

Output

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.

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.

Example 1

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

Output

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

Example 2

Input

3
liz steve dave
liz 30 1 steve
steve 55 2 liz dave
dave 0 2 steve liz

Output

liz -3
steve -24
dave 27

Instructions

Your program should be called day2b.bas if it is a BASIC program, day2b.pas if it is a Pascal program, day2b.c if it is a C program, day2b.cpp if it is a C++ program and day2b.lg if it is a logo program.

It should read its input from a file called day2b.dat, and write its output to a file called day2b.sol. The two example input files and the solutions are on the D: drive. The names of the input files are test2b1 and test2b2. The solution files are called test2b1.sol and test2b2.sol.

Note that if your program generates correct results for these files, it does not mean that your program is correct.

N.B. If you are writing a BASIC program ensure that it terminates with a system command, so that it exits to DOS. This is essential if it is to be processed automatically. You will get zero marks for the program if you neglect to do this.

Problem C The Cat in the Hat

Description

A clever cat walks into a messy room which he needs to clean. Instead of doing the work alone, it decides to have its helper cats do the work. It keeps its (smaller) helper cats inside its hat. Each helper cat also has helper cats in its own hat, and so on. Eventually, the cats reach a smallest size. These smallest cats have no additional cats in their hats. These unfortunate smallest cats have to do the cleaning.

The number of cats inside each (non-smallest) cat's hat is a constant, n. The height of these cats-in-a-hat is 1/(n+1) times the height of the cat whose hat they are in.

All heights are positive integers.

Given the height of the initial cat and the number of worker cats (of height one), find the number of cats that are not doing any work (cats of height greater than one) and also determine the sum of all the cats' heights (the height of a stack of all cats standing one on top of another).

Input

The input is a single line consisting of two positive integers, separated by white space. The first integer is the height of the initial cat, and the second integer is the number of worker cats.

Output

Print the number of cats that are not working, followed by a space, followed by the height of the stack of cats.

Example 1

Input

216 125

Output

31 671

Example 1

Input

5764801 1679616

Output

335923 30275911

Instructions

Your program should be called day2c.bas if it is a BASIC program, day2c.pas if it is a Pascal program, day2c.c if it is a C program, day2c.cpp if it is a C++ program and day2c.lg if it is a logo program.

It should read its input from a file called day2c.dat, and write its output to a file called day2c.sol. The two example input files and the solutions are on the D: drive. The names of the input files are test2c1 and test2c2. The solution files are called test2c1.sol and test2c2.sol.

Note that if your program generates correct results for these files, it does not mean that your program is correct.

N.B. If you are writing a BASIC program ensure that it terminates with a system command, so that it exits to DOS. This is essential if it is to be processed automatically. You will get zero marks for the program if you neglect to do this.