IARCS Zonal Informatics Olympiad Question Paper 2015

Name of the Organisation : IARCS | Indian Association for Research in Computing Science
Name of the Paper : Zonal Informatics Olympiad Question Paper 2015
Year : 2015

Website : http://www.iarcs.org.in/inoi/
Download Sample Question Paper : https://www.pdfquestion.in/uploads/8176zonal.pdf

IARCS Zonal Informatics Olympiad Question Paper

Instructions to candidates :
1. The duration of the examination is 3 hours.
2. Calculators, log tables and other aids are not permitted.

Related : Brilliant International Olympiad of Social Science – BIOSS Question Paper : www.pdfquestion.in/13684.html

3. The question paper carries 80 marks, broken up into four questions of 20 marks each. Each question has three parts. If you solve all three parts correctly, you get 20 marks for that question. Otherwise, you get 5 marks for each part that you solve correctly.

4. Attempt all questions. There are no optional questions.
5. There is a separate Answer Sheet. To get full credit, you must write the nal answer in the space provided on the Answer Sheet.
6. Write only your nal answers on the Answer Sheet. Do not use the Answer Sheet for rough work. Submit all rough work on separate sheets.
7. Make sure you ll out your contact details on the Answer Sheet as completely and accurately as possible. We will use this information to contact you in case you qualify for the second round.

Questions :
1. ScamJet Inc. would like to advertise a festival sale where they plan to sell a number of their seats for just one rupee.
ScamJet Inc. has hired Ms. Rama to put up a big board at the main airport at Siruseri announcing the number of cheap tickets. Ms. Rama is meticulous about way she bills her customers and charges a specic amount for each symbol she writes.

You are given her current rate for writing any of the digits 0; 1; 2; : : : ; 9 (since painting any number only involves these symbols). Unfortunately for ScamJet, and fortunately for the passengers of Siruseri, the contract to Ms. Rama did not specify the number of free tickets, but only that the cost of writing the sign should not exceed B rupees.

Ms. Rama, being a good citizen of Siruseri, would like to write as large a number as possible while ensuring that the cost of writing falls within B rupees.

Let the budget B be 6. Then the following are some numbers that can be written within the budget: 9; 91; 111111; 333; 456. You can verify that the largest integer that can be painted within the budget is 777777.
Your task is the calculate the largest value that Ms. Rama may paint for the charges and budgets in the three instances below.

(a) B = 33 and the writing charges are given by
Digit 0 1 2 3 4 5 6 7 8 9
Charges 3 10 12 4 9 9 13 5 15 8

(b) B = 62 and the writing charges are given by
Digit 0 1 2 3 4 5 6 7 8 9
Charges 9 12 8 9 10 13 17 23 80 75

(c) B = 72 and the writing charges are given by
Digit 0 1 2 3 4 5 6 7 8 9
Charges 9 9 20 15 8 23 7 83 50 9

2. Siruseri Metro Corporation Limited has a new shunting yard. The yard has an incoming track and an outgoing track as indicated in the gure below. In each step, the yard manager instructs whether to let the next incoming train Enter the yard or allow a train to Leave the yard.

Observe that the design of the yard means that the trains leave the yard in a last-in-rst-out manner. The instruction Enter is allowed only when there is at least one train on the incoming track, and the instruction Leave is allowed only when there is at least one train in the yard. The yard is long enough to accommodate as many trains as needed.

The yard manager wants to know, for a given N and K, the number of possible output arrangements that he can produce using legal instruction sequences. Recall that all N trains must be moved from the incoming track to the outgoing track. Your task is to solve this problem for the following instances
(a) N = 6 and K = 8.
(b) N = 8 and K = 4.
(c) N = 10 and K = 4.

3. Siruseri Inc. has launched its next blockbuster single player game. It is a rather simple, yet challenging, game. On pressing the start button, you nd a list of N numbers on the screen. Moreover, each number appears in a particular colour.

For instance, the the sequence might look like
Position 1 2 3 4 5
Number 1 -2 3 1 2
Colour R G R B R

The player must select a subset of the positions. Then the value at each position changes as follows
a. If a position is not selected its value is set to 0.
b. The value of the leftmost selected position is multiplied by 3.
c. For any other selected position, if the closest selected position on the left has the same colour then the value is left unchanged.
d. Otherwise, i.e. any selected position for which the closest selected position on the left has a dierent colour, the value is multiplied by 3.