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

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

Problem 1 : Fence :
You have a rectangular farm which consists of R*C fields arranged in a grid consisting of R rows and C columns. Each field is a 1 x 1 square. Some of these fields have been planted with potatoes while the others lie uncultivated. We say that two fields are adjacent if one lies immediately to the left or to the right or above or below the other. (Note that two fields which touch each other at just one corner are not considered adjacent). If two fields are adjacent then we say we may walk from one to the other.

A patch is a collection of all the cultivated fields such that one may walk from any field in the patch to any other field in the same patch only via cultivated fields. There are no uncultivated fields in a patch. That is, all the cultivated fields in the farm can be partitioned into patches, and you can walk from one cultivated field to another cultivated field, if and only if, both of them belong to the same patch.

To prevent wild animals from destroying the cultivated fields you plan to enclose each patch within fences constructed all along the boundaries of the patch. Wild animals infest the uncultivated fields, and also beyond the R*C farm. We need to ensure that the fences protect all the boundaries of each patch, so that the wild animals cannot get to any cultivated field without crossing a fence.

Clearly, the length of the fence needed for each patch may differ. If your patch consists of just a single field then the fence will be of length 4. If it consists of two adjacent fields then the fence will be length 6. Your task is to output the maximum length of fence needed to enclose a patch, among all the patches in your farm. The input to your program will be a description of the positions of all the cultivated fields in your farm. (X,Y) refers to the field on the Xth row and Yth column. So, (1,1) refers to the top-left corner field, and (R,C) refers to the bottom-right corner.

Explanation :
There are two patches. One patch, which includes only the (1,4) field needs a fence of length 4. The other
patch, which has 8 fields in it, needs fence of length 16. A length of 12 to cover its outer boundary, and length
4 to cover its inner boundary.
Maximum(4,16) = 16. Hence, the answer is 16

Problem 2 : Training :
Ash and his Pokemon Pikachu are going on a journey. Ash has planned his route for the journey so that it passes through N cities, numbered 1, 2, …, N, and in this order. When they set out, Pikachu has an initial strength of Sin as well as an experience value (XV) of 0. As they travel they may increase his strength and experience value in a manner to be described below. In each city, Ash can choose either to train Pikachu or let Pikachu battle the Gym-leader (but not both). The Gym-leader in ith city has experience E[i].

If Pikachu enters a city i with strength S and decides to train, then this increases his strength by the cube of the sum of the digits in his current strength. For example, if he entered a city with a strength of 12, then training will increase his strength to 12 + (1+2)3 = 39. On the other hand, if he enters city i with strength S and battles the Gym-leader, then this increases his experience value XV by S*E[i]. Ash wants your help to find out the maximum XV that Pikachu can attain at the end of his journey.

Explanation 1 :
Suppose Pikachu trains in the first city, his strength will increase to 39, because as explained above, 12 + (1+2)3 = 39. If he battles in the first city, his XV will increase by (12*5) = 60.
If Pikachu trains in the first city, and then battles in the second city, his XV will increase by 39*10 = 390. So, the final XV will be 0+390 = 390. You can check that you cannot do better than this. Hence the answer is 390.

Explanation 2
Pikachu battles in the first city, trains in the second and third, and then battles in the fourth city. So his strength going into each of the four cities is (1, 1, 2, 10). And so he gains 1*100 XV from the first city and 10*2 XV from the fourth city. This gets him a total of 120 XV, and you can verify that nothing better can bedone.