Name of the Organization : IARCS | Indian Association for Research in Computing Science
Name Of The Exam : Zonal Informatics Olympiad 2017
Document Type : Sample Question Paper
Year : 2017

Website : http://www.iarcs.org.in/inoi/2017/#qpaper
Download Model/Sample Question Papers : http://www.indianjobtalks.com/upload...o2017paper.pdf

Zonal Informatics Olympiad, 2017 :
Instructions to candidates :
1. The question paper carries 80 marks, broken up into four problems of 20 marks each. Each problem has three Test Cases. If you solve all three Test Cases correctly, you get 20 marks for that problem. Otherwise, you get 5 marks for each Test Case that you solve correctly.

2. All the 4 * 3 = 12 Test Cases appear as separate Questions in the right panel (\Question Palette").The first three Questions correspond to the three Test Cases of Problem 1, the next three correspond to the three Test Cases of Problem 2 and so on. A question icon turning green in the Question Palette, does not mean that it is correct. It just denotes that you have attempted it. All the questions will be evaluated later.

3. Attempt all questions. There are no optional questions.
4. There are no negative marks.
5. All expected answers are integers. Type in only the in- teger. So, if your answer is \162", enter only \162". Not \0162", or \162.0", etc.

6. Remember to save each answer. Only your nal saved answers will be considered.
7. Near the top-right corner, you should be able to see a calculator icon. Clicking it pops up a calculator which you may use.

Questions :
1. In this task you will give a sequence of numbers S of length N. Every element will be greater than or equal to 1. We write S[i] to refer to the ith element of the sequence. For example S = (1; 2; 3; 4; 5; 4) is of length 6 and S[2] = 2, S[6] = 4 and so on. You will also be given a number T, called the target. We would like to nd four elements of the sequence S whose sum is T. More precisely, we would like to nd four numbers i, j, k, ` with 1 i < j < k < ` N such that T = S[i] + S[j] + S[k] + S[`].

For instance with S as above, for T = 13, we can take i = 2, j = 3, k = 4 and ` = 6. It can also be generated with i = 1, j = 3, k = 4 and ` = 5 as well as i = 1, j = 3, k = 5 and ` = 6. You can verify that these are only three ways to pick four positions summing upto 13.

2. A group of N people are on a hiking trip. It starts raining heavily and the group starts looking for places where they can be protected from the rain. There are 2 enclosures nearby where people can nd shelter. Let's call them A and B. EnclosureA can accommodate X people, and Enclosure B can accommodate Y people. It is guaranteed that (X + Y ) N, and so everyone can be accommodated.

The group has genuine camaraderie, so they decide that they want to minimize the total distance traveled by their group members altogether to reach their respective enclosures. Note that this may mean that some individuals don't end up at theenclosure which is closest to them|the aim is to minimize the sum of the distances traveled by the members of the group.
Given N, X, Y and the distances, your aim is to compute this minimum value.
For example, if N = 4, X = 2, Y = 2, and the distances are
Adist[1] = 10, Bdist[1] = 12
Adist[2] = 23, Bdist[2] = 20
Adist[3] = 15, Bdist[3] = 8
Adist[4] = 5, Bdist[4] = 20
Then the optimal strategy would be for 1 and 4 to go to A and for 2 and 3 to go
to B. In this case the total distance traveled is
Adist[1] + Adist[4] + Bdist[2] + Bdist[3] = 10 + 5 + 20 + 8 = 43:
You can check that they cannot do any better.
Compute the corresponding minimum values for the following 3 inputs.

(a) N = 8, X = 3, Y = 10
Adist[1] = 4; Bdist[1] = 6
Adist[2] = 13; Bdist[2] = 8
Adist[3] = 12; Bdist[3] = 21
Adist[4] = 7; Bdist[4] = 9
Adist[5] = 51; Bdist[5] = 37
Adist[6] = 20; Bdist[6] = 25
Adist[7] = 5; Bdist[7] = 17
Adist[8] = 8; Bdist[8] = 7

(b) N = 12, X = 6, Y = 6
Adist[1] = 10; Bdist[1] = 4
Adist[2] = 13; Bdist[2] = 12
Adist[3] = 13; Bdist[3] = 27
Adist[4] = 54; Bdist[4] = 52
Adist[5] = 6; Bdist[5] = 9
Adist[6] = 15; Bdist[6] = 11
Adist[7] = 21; Bdist[7] = 26
Adist[8] = 26; Bdist[8] = 14
Adist[9] = 37; Bdist[9] = 33
Adist[10] = 4; Bdist[10] = 3
Adist[11] = 11; Bdist[11] = 11
Adist[12] = 20; Bdist[12] = 17

(c) N = 20, X = 5, Y = 18
Adist[1] = 3; Bdist[1][B] = 1
Adist[2] = 11; Bdist[2] = 19
Adist[3] = 20; Bdist[3] = 24
Adist[4] = 31; Bdist[4] = 13
Adist[5] = 72; Bdist[5] = 102
Adist[6] = 13; Bdist[6] = 51
Adist[7] = 36; Bdist[7] = 38
Adist[8] = 41; Bdist[8] = 40
Adist[9] = 4; Bdist[9] = 9
Adist[10] = 59; Bdist[10] = 47
Adist[11] = 19; Bdist[11] = 21
Adist[12] = 3; Bdist[12] = 49
Adist[13] = 28; Bdist[13] = 32

3. A group of N children, who are numbered 1; 2; : : : ;N, want to play hide and seek. In a single round of hide and seek, there will one seeker, and N ??1 hiders. Children ike to hide and not seek and each child has her own idea of how many times she would like to hide. You will be given for each child i, a number H[i] denoting the number of rounds she would like to be a hider. She will be satised only if she gets to be a hider in at least H[i] rounds.
(a) N = 7 H[1] = 6, H[2] = 13, H[3] = 9, H[4] = 5, H[5] = 15, H[6] = 8, H[7] = 9.
(b) N = 12 H[1] = 6, H[2] = 7, H[3] = 7, H[4] = 8, H[5] = 9, H[6] = 9, H[7] = 9, H[8] = 9, H[9] = 9, H[10] = 9, H[11] = 9, H[12] = 9.
(c) N = 15 H[1] = 131, H[2] = 135, H[3] = 130, H[4] = 138, H[5] = 132, H[6] = 140, H[7] = 137, H[8] = 133, H[9] = 131, H[10] = 137, H[11] = 138, H[12] = 132, H[13] = 135, H[14] = 136, H[15] = 134.