Showing posts with label PNOI 2008. Show all posts
Showing posts with label PNOI 2008. Show all posts

Sunday, March 16, 2008

Michael Samson's Commentary On Problems Given During The Philippine National Olympiad In Informatics (PNOI 2008)

Notes:

Last Saturday, 15 March 2008, I was the contest director of the 1st Philippine National Olympiad in Informatics (PNOI 2008) held in Ateneo de Manila University.

Please refer to the following blogsposts for details:

http://raffysaldana.blogspot.com/2008/03/conratulations-john-anglo-and-enzo.html

http://raffysaldana.blogspot.com/2008/03/more-photos-philippine-national.html

http://raffysaldana.blogspot.com/2008/03/photos-opening-session-philippine.html

http://raffysaldana.blogspot.com/2008/03/program-of-activities-philippine.html

http://raffysaldana.blogspot.com/2008/03/philippine-national-olympiad-in.html

http://raffysaldana.blogspot.com/2008/03/computing-society-of-philippines-csp.html


Six problems were given during the contest. The PNOI 2008 problems are available for viewing in the following link:

http://raffysaldana.blogspot.com/2008/03/problem-set-1st-philippine-national.html

Mr. Michael Daniel "Mike" Samson, an alumnus and former teacher of the Philippine Science High School (PSHS or Pisay) Main Campus and currently a mathematics graduate student of Ateneo de Manila University (Mike was my former student in computational methods or Numberical Analysis), is a member of the PNOI 2008 Board of Judges.

Like me, Mike also maintains a blog. In his blog, Mike made a commentary on the problems given during PNOI 2008.

Below are the links to Mike's commentary:

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 Shooping Spree

Saturday, March 15, 2008

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).

Congratulations, John Anglo and Enzo Dayrit: Winners in Philippine National Olympiad in Informatics (PNOI 2008)

John Anglo (of Philippine Science High School - Main Campus), 1st Place Winner, receives his certificate of achievement from Dr. Rafael Saldaña, PNOI 2008 Contest Director.

Fabian Lorenzo Dayrit (of Ateneo de Manila University-High School), 2nd Place Winner, receives his certificate of achievement from Dr. Rafael Saldaña, PNOI 2008 Contest Director.


Congratulations to all winners and finalists in the 1st Philippine National Olympiad in Informatics (PNOI 2008) held on March 15, 2008 in Ateneo de Manila University.

First Place: John Anglo, Philippine Science High School - Main Campus

Second Place: Fabian Lorenzo Dayrit, Ateneo de Manila University (High School Department)

All finalists and winners in PNOI 2008 are eligible to join the 2nd Asia Pacific Informatics Olympiad (APIO 2008) - Philippine Site, to be held in Cebu City (tentative venue) on May 10, 2008.

PNOI 2008 was organized by the Grid and Cluster Computing Group (AGHPC) of the School of Science and Engineering of Ateneo de Manila University in cooperation with the Computing Society of the Philippines with the Department of Information Systems and Computer Science (DISCS) of Ateneo de Manila University as host.

Click on the following links to view photos of PNOI 2008:

http://booleanlogic.multiply.com/photos/album/95/Opening_Session_Phil._Natl._Olympiad_in_Informatics

http://booleanlogic.multiply.com/photos/upload-ajax/96

For more information, contact:

Dr. Rafael Saldaña
Contest Director
PNOI 2008/
APIO 2008 (Philippine Site)
Telephones: (02) 4266125, (02) 7090907, 0928-5043121
E-mail: raffysaldana@gmail.com
Website: http://raffysaldana.blogspot.com/

More Photos: Philippine National Olympiad in Informatics (PNOI 2008)

Some of the participants in the 1st Philippine National Olympiad in Informatics (PNOI 2008).

Photos taken during the 1st Philippine National Olympiad in Informatics (PNOI 2008) held on March 15, 2008 in Ateneo de Manila University. From the photo collection of Raffy Saldaña (http://raffysaldana.blogspot.com)
To view photos taken during the contest proper and the Awarding Ceremony, click on the following link:
(Select 'Slideshow' for a better view.)

Friday, March 14, 2008

Photos: Opening Session, Philippine National Informatics Olympiad (PNOI 2008)


Philippine National Informatics Olympiad (PNOI 2008)
March 15, 2008
Ateneo de Manila University
To view more photos, click on the following link:
and select 'Slideshow' for a better view.
From,
Contest Director
PNOI 2008

Tuesday, February 19, 2008

PNOI 2008: Philippine National Olympiad in Informatics -- Update

PNOI 2008
Philippine National Olympiad in Informatics
Organized by the Computing Society of the Philippines and Ateneo de Manila University
Website: http://www.math.admu.edu.ph/pnoi

INVITATION


Greetings!

The Computing Society of the Philippines (CSP) and the School of Science and Engineering of Ateneo de Manila University (ADMU) will hold the First Philippine National Olympiad in Informatics (PNOI 2008) on March 15, 2008 in Ateneo de Manila University, Loyola Heights, Quezon City.

The event will consist of two parts:

1. Seminar on Computer Programming Competitions for High School Teachers/Coaches and Students to be given by experts in the field of computing and information technology.

2. Informatics Olympiad (Programming Competition) for High School Students. This is an individual contest open to all high school students rom second year to fourth year levels. Students may use either C, C++, or JAVA. The top three winners will receive trophies and cash prizes.

Also, the top 25 winners in PNOI 2008 will be trained by the Computing Society of the Philippines and Ateneo de Manila University to compete in the 2nd Asia Pacific Informatics Olympiad (APIO 2008) being organized scheduled on May 10, 2008.

3. Registration

The registration fee for teachers/coaches is PhP 500 while the fee for students is PhP 300. The fee includes light snacks, lunch, and certificate of participation.

Attached is a copy of the tentative program and registration details.

For more information, visit the PNOI 2008 website: http://www.math.admu.edu.ph/pnoi

Sincerely yours,

(Sgd.) Dr. Rafael P. Saldaña
Project Director
1st Philippine National Olympiad in Informatics (PNOI 2008)
c/o Rm. 317, SEC Bldg. A, Ateneo de Manila University
Loyola Heights, Quezon City 1108
Telephones: (02) 4266125 and (02) 7090907
Mobile Phone: 0928-5043121
E-mail: raffysaldana@gmail.com

================================================

1st Philippine National Olympiad in Informatics
15 March 2008, Ateneo de Manila University
Organized by the Computing Society of the Philippines
and Ateneo de Manila University
Website: http://www.math.admu.edu.ph/pnoi

PROGRAM (Tentative).
Venue: Faura Building, Ateneo de Manila University

TIME/ ACTIVITY

Morning

08:00 – 09:00 a.m. Registration
09:00 – 10:20 Opening Session
Introduction of Participants
Seminar on Computer Programming Competitions, Part 1 (Lecture)
10:20 – 10:40 Break
10:40 – 12:00
Seminar on Computer Programming Competitions, Part 2 (Computer Laboratory Session)
12:00 – 01:00 p.m. Lunch

Afternoon

01:00 – 01:30 p.m. Practice Session for Student Contestants
01:30 – 04:30 Contest Proper
04:30 – 05:00 Awarding Ceremony


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



REPLY FORM

The Secretariat
1st Philippine National Olympiad in Informatics (PNOI 2008)
c/o Rm. 317, SEC Bldg. A, Ateneo de Manila University
Katipunan Avenue, Loyola Heights, Quezon City 11080
Telephones/Fax: (02) 4266125, (02) 4266011 loc. 5681, (02) 7090907
Mobile Phone: 0928-5043121
E-mail: PNOIsecretariat@gmail.com

____I / We would like to participate in PNOI 2008.


FULL NAME/S:

Position: [Teacher (T) or Student (S)]:

School:

Tel. No/s.

Mobile Phone/s:

E-mail Addresses:

Name of School Principal or Head of IT/Computer Science Department:

Sunday, December 23, 2007

Invitation: PNOI 2008 (Philippine National Informatics Olympiad 2008)

ANNOUNCEMENT:

The Computing Society of the Philippines (CSP) and Ateneo de Manila University (ADMU) are organizing PNOI 2008 (Philippine National Programming Olympiad) scheduled on February 9, 2007 at ADMU, Loyola Heights, Quezon City.

PNOI 2008 is an individual programming contest for high shool students in the Philippines. It is a preliminary event related to the APIO '08 (Asia Pacific Programming Olympiad 2008) and the International Olympiad in Informatics (IOI). High school students in the Philippines may send at most five individual contestants. The mechanics of the contest will be announced soon.

The top winners in PNOI 2008 will be trained to compete in APIO '08. The CSP and Ateneo de Manila University will train high school students to be able to compete in the Asia-Pacific Informatics Olympiad and the International Olympiad in Informatics (IOI).

For more information, contact:

Dr. Rafael P. Saldaña
Project Director
Philippine National Olympiad in Informatics (PNOI 2008)
Tel: (02) 426-6125, (02) 7090907
Fax.: (02) 426-6125
Mobile: 0928-504321
E-mail: raffysaldana@ gmail.com