Problem Set: 1st Philippine National Olympiad in Informatics (PNOI 2008)

1st Philippine National Olympiad in Informatics (PNOI)
15 March 2008, Ateneo de Manila University, Philippines

Organized by

Grid and High Performance Computing Group,
School of Science and Engineering,
Ateneo de Manila University (ADMU)

in cooperation with the
Computing Society of the Philippines (CSP)

Hosted by

Department of Information Systems and Computer Science (DISCS)
Ateneo de Manila University



PROBLEM SET



Directions: (TO THE CONTESTANTS)

Do not open this problem set UNLESS you are given the signal by the Contest Director to do so.

NOTES are not allowed during the contest.

This is a three-hour programming contest and there are SIX problems to be solved. Budget your time so that you will be able to solve as many problems as you can.



(Sgd.) Rafael P. Saldaña, Ph.D.
Contest Director
PNOI 2008

----------------------------------------------------------------------------

Problem A: A Simple Task
Problem B: Rina's Triangles
Problem C: Checking Collinearity
Problem D: How Many Groups?
Problem E: Text Messages
Problem F: Shopping Spree




----------------------------------------------------
Problem A: A Simple Task
Input: C stdin, or Java System.in
Output: C stdout, or Java System.out
Execution Time Limit: 1 second
----------------------------------------------------

Given a positive integer n, find the odd integer o and the non-negative integer p such that n = o2p.

Example:

For n = 24, o = 3 and p = 3.

Task: Write a program which for each data set:

* reads a positive integer n,
* computes the odd integer o and the non-negative integer p such that n=o*2^p,
* writes the result.

Input

The first line of the input contains exactly one positive integer d equal to the number of data sets, where 1 ≤ d ≤ 20. The data sets follow. Each data set consists of exactly one line containing exactly one integer n, where 1 ≤ n ≤ 2147483647.

Output

The output should consists of exactly d lines, one line for each data set. Line i, 1 ≤ i ≤ d, corresponds to the i-th input and should contain the remark “Set i:” and the two integers o and p separated by a single space such that n = o*2^p.

Sample Input

2
24
36

Output for Sample Input

Set 1: 3 3
Set 2: 9 2










---------------------------------------------------
Problem B: Rina's Triangles
Input: C stdin, or Java System.in
Output: C stdout, or Java System.out
Execution Time Limit: 1 second
---------------------------------------------------

Given four integers, all positive or zero, Rina's Triangle is formed by using these four integers as the base of the triangle, and computing each remaining value in the triangle as the absolute difference of the two values immediately below it. For example, given 89, 78, 12, 13 we can construct Rina's Triangle as follows:

10
55 65
11 66 1
89 78 12 13

We say that a sequence of four positive integers is acceptable if no integer appears more than once in the Rina's Triangle it generates. So the sequence of four integers given above is acceptable.

Create a program that determines whether a sequence of four integers (all positive or zero) is acceptable or not.

Input. The first line of input will contain the number N of data sets (N will not exceed 20). This is followed by N lines, representing the N data sets. Each line contains four integers, all between zero and 65000 inclusive, belonging to the data set.

Output. For each data set, print “Set K:”, where K is the data set number, starting from 1. Then print “acceptable” or “not acceptable”, depending on the data set.

Sample Input

2
89 78 12 13
13 1 28 85

Output for Sample Input

Set 1: acceptable
Set 2: not acceptable








------------------------------------------------------
Problem C: Checking Collinearity
Input: C stdin, or Java System.in
Output: C stdout, or Java System.out
Execution Time Limit: 1 second
-------------------------------------------------------
The problem consists of several data sets. Each data set contains three (3) or more points on the Cartesian Plane. Your job is to determine if the points are collinear – that is, if they fall on a straight line, and if so, to determine the equation of the line passing through those points.

Example 1. Given the four points (0, 1), (1, 3), (2, 5), and (3, 7), we see that the line with equation 2x-y+1=0 passes through all the four points.

Example 2. Given the three points (5, 0), (5, 2), and (5, 7), we see that the line with equation x-5=0 passes through all the three points.

Example 3. Given the three points (1, 3), (2, 5), and (4, 8), we see that the three points are not collinear.

Input. Input will consist of at most 20 data sets. Each data set will start with a line containing the value of N, the number of points (N ≤ 100). This is followed by N lines, with each line containing the x and y coordinates of one point. The x and y coordinates will be given as integers, and x will not exceed 256 in absolute value. All points will be distinct. The first data set is immediately followed by one line containing the value of N for the next data set, and this is followed by N lines of x and y coordinates for that data set. A value of N = 0 indicates the end of input data, and input processing must stop.

Ouput. For each data set, print “Set K: “, where K is the data set number, starting from 1. Then print one of the following answers:

Ax+By+C=0
Not collinear

depending on the solution to the data set. The coefficients A, B, and C must must have no common factors, and A ≥ 0. If A is 1, just print x. If A is -1, just print -x. Similarly for B and y. If A or B or C is zero, just omit the x-term or the y-term or the constant term. If either B or C is negative, say A=2, B=-3, C=-5, then do not print the + sign before the – sign; print the answer simply as 2x-3y-5=0; do not print as 2x+-3y+-5=0.

Sample Input

40 11 32 53 7
35 05 25 73
1 32 54 8
0

Output for Sample Input

Set 1: 2x-y+1=0
Set 2: x-5=0
Set 3: Not collinear


-------------------------------------------------------
Problem D: How Many Groups?
Input: C stdin, or Java System.in
Output: C stdout, or Java System.out
Execution Time Limit: 1 second
-------------------------------------------------------

We have a collection of M persons { 1, 2, 3, . . . , M }, and we want to divide these M persons into groups. A person will be placed in a group if he “knows” at least one person in that group. For example, if we have 10 persons { 1, 2, 3, . . . , 10 }, and if the following pairs know each other: 1 and 3, 3 and 4, 3 and 5, 5 and 6, 5 and 7, 2 and 8, 2 and 9, and 8 and 10, then we can put 1, 3, 4, 5, 6, 7 in one group, and 2, 8, 9, 10 in another. Each person in the first group knows at least one person in that group. Each person in the second group knows at least one person in the second group. However, no one in the first group knows anyone in the second group, and vice-versa.

Your problem is to write a program that determines the number of groups into which you can divide M persons.

Input. Input will consist of at most 20 data sets. Each data set will consist of several lines. The first line will contain the values of M and P, where M is the number of persons, and P is the number of pairs that know each other. Here M will not exceed 200 people, and P will not exceed 100 pairs. This is followed by P lines, each line containing a pair of numbers x and y, separated by space, which means that x and y know each other. The values of x and y will be between 1 and M inclusive. The values of x and y will never be equal. Also, no pairs will be repeated. Data lines for the next data set will immediately follow the data lines for the previous data set. A data set with M = 0 and P = 0 will indicate the end of input, and input processing should stop.

Output. For each data set, print “Set K:”, where K is the data set number, starting from 1. Then print the number of groups into which the M persons can be divided.

Sample Input

10 8
1 3
3 4
3 5
5 6
5 7
2 8
2 9
8 10
10 2
1 2
2 3
10 0
10 4
1 2
1 3
1 4
1 5
0 0

Output for Sample Input

Set 1: 2
Set 2: 8
Set 3: 10
Set 4: 6






---------------------------------------------------
Problem E: Text Messages
Input: C stdin, or Java System.in
Output: C stdout, or Java System.out
Execution Time Limit: 1 second
---------------------------------------------------

On most mobile phones the numeric keys must be repeatedly pressed to produce letters for text messages. A common keypad layout looks like this:

[1 ] [2 abc] [3 def ]
[4 ghi ] [5 jkl ] [6 mno ]
[7 pqrs] [8 tuv] [9 wxyz]
[* ] [0 _ ] [ # ]

Furthermore, most phones will have a circular navi-key with which you can produce the navigation actions UP, DOWN, LEFT, RIGHT, and this navi-key is used to separate key presses for two letters on the same key. For example, to spell “cat” on this keypad, press [2] three times to produce “c”, then press RIGHT, then press [2] once to produce “a”, then press [8] once to produce “t”. Thus we need a total of six key presses to spell “cat”. Note that the character “_” on the [0] key stands for SPACE, and to generate SPACE, we need only press [0] once.

Create a computer program that counts the number of key presses needed to produce a text message. Assume that your phone can only produce lower-case letters and SPACE, and that we only need to send text messages containing lower-case letters and SPACE.

Input. Input will consist of at most 20 data sets. The first line of input will contain the value of N, the number of data sets. This will be followed by N lines, with each line containing one data set, namely the text message to send. The length of the message will not exceed 160 characters, including blanks. There will be exactly one blank character between words.

Output. For each data set, print “Set K:”, where K is the data set number, starting from 1. Then print the number of key presses needed to produce the given text message.

Sample Input

2
i love you
cab money

Output for Sample Input

Set 1: 24
Set 2: 22







---------------------------------------------------
Problem F: Shopping Spree
Input: C stdin, or Java System.in
Output: C stdout, or Java System.out
Execution Time Limit: 1 second
---------------------------------------------------

You have received a local pass from the grocery store for a one day shopping bonanza. At the start of the day, you are given a pushcart of capacity M and can get all the items you want as long as it can fit into the pushcart.

As a programmer and expert shopper you want to maximize the total value of the items that you have bought by designing a simple program to identify what items you will buy.

Input. The first line contains an integer X, indicating the number of one-day shopping spree occasions you won; X is also the number of data sets. The first line of each data set contains two integers N and M indicating the number of various items available in the shop and the capacity of the pushcart respectively. The next N lines will contain the name of the item n[i] as a 20 character alphanumeric string, and a pair of integers indicating the cost c[i] and size s[i] of each item. The sizes will be given in ascending order.

Output. For each data set, will print the data set number, starting from 1, the name and number of each item bought, and the total value of the shopping purchase, as shown in the sample below. Items should be arranged in ascending lexicographical (alphabetical) order.

Sample Input
1
5 17
A 4 3
B 5 4
C 10 7
D 11 8
E 13 9

Output for Sample Input
Set 1: A–1, B-0, C–2, D–0, E–0, Total PHP24


Copyright, 2008. Computing Society of the Philippines, Ateneo de Manila University, and Philippine National Olympiad in Informatics Committee (c/o Dr. Rafael Saldaña).