IARCS Indian National Olympiad in Informatics INOI Question Paper 2017
Name of the Organisation : IARCS | Indian Association for Research in Computing Science
Name of the Paper : Indian National Olympiad in Informatics INOI 2017
Year : 2016,2017,2015
Website : https://www.iarcs.org.in/inoi/2017/#qpaper
Download Sample Question Paper :
2017 : https://www.pdfquestion.in/uploads/22923-inoi2017.pdf
2016 : https://www.pdfquestion.in/uploads/22923-inoi2016.pdf
2015 : https://www.pdfquestion.in/uploads/22923-inoi2015.pdf
IARCS INOI Olympiad Question
** The Indian National Olympiad in Informatics, 2017 (INOI-2017) took place on Sunday, 8 January, 2017. Of the 326 students who participated in INOI-2017,
Related : IARCS Zonal Computing Olympiad ZIO Question Paper : www.pdfquestion.in/22915.html
** 27 students have qualified for the International Olympiad in Informatics Training Camp, 2017 (IOITC-2017) to select the Indian team for the International Olympiad in Informatics, 2017 (IOI-2017), and
** 64 students are deemed to have qualified through ZCO-2017, based on their performance in INOI-2017.
Instructions to Candidates
(a) You will have to return this question paper at the end of the examination with relevant parts lled out.
(b) There are two questions. You have to write working programs in C, C++, Java or Pascal to solve each of these questions.
** Only your source code will be submitted for evaluation. Your program will be re- compiled and run on the evaluation computer.
** Make sure your C/C++ programs compile with the GNU C compiler (dev-cpp or Code::Blocks under Windows). Programs written using Turbo C++ may not compile and run in the evaluation environment and may hence lose marks.
** If you work in C/C++, make sure you do not write #include <conio.h> in your program or use any functions dened in conio.h. If you do so, your program will not compile and you will get no marks.
(c) At the end of each question, there is a space to indicate the location of the source code le for your solution. Please ll up this information without fail. Otherwise, your solution cannot be evaluated.
(d) All input for your programs will come from the keyboard. All output from your programs should be written to the screen.
(e) On the computer where you are working, you will nd a collection of sample inputs and outputs for each problem to test your programs. Please ask your centre supervisor if you cannot locate these sample inputs and outputs. This set of sample inputs is not exhaustive. Additional test cases will be used for nal evaluation. Even if your program correctly solves all these sample inputs, there is no guarantee that your program will pass all the cases in the nal evaluation.
(f) Please ll out your contact details on the reverse of this page as completely as you can. If you qualied under multiple categories, use your ZIO roll number. Ask your centre supervisor if you do not know your roll number.
INOI 2017 Questions
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 atch 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. Input The first line contains three space separated integers, R, C and N, which are the number of rows, number of columns and the number of cultivated fields, respectively. The next N lines contain two space separated integers, Xi and Yi, which signify that (Xi, Yi) is a cultivated field. Output A single integer which is the maximum length of fence needed for any patch.
Constraints :
For all test cases you may assume that :
0 = Number of cultivated fields = N = 100000
1 = Xi = R
1 = Yi = C
Subtask 1: For 15% of the score,
1 = R,C = 20
Subtask 2: For further 45% of the score,
1 = R,C = 2500
Subtask 3: For 40% of the score,
1 = R,C = 1000000**
Example
Input:
4 4 9
1 4
2 1
2 2
2 3
4 3
4 1
4 2
3 1
3 3
Output:
16
Explanation : The input corresponds to the figure
. . . x
x x x .
x . x .
x x x .
‘x’ corresponds to a cultivated field, and ‘.’ corresponds to an uncultivated field. 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.
Input :
The first line contains two space separated integers, N and Sin, which are the number of cities, and the initial strength, respectively. The second line contains N space separated integers, which correspond to E[1], E[2],…, E[N].
Output :
A single integer which is the maximum XV that Pikachu can attain.
Constraints :
For all test cases you may assume that:
1 = N = 5000
0 = Sin = 109
0 = E[i] = 104
Subtask 1: For 10% of the score,
N = 20 and Sin = 1
Subtask 2: For further 40% of the score,
E[i] = k for all i
i.e. E[i] is some constant k, for all i
Subtask 3: For further 50% of the score,
No further constraints.
Example
Input 1 :
2 12
5 10
Output 1:
390
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.
Input 2 :
4 1
100 1 6 2
Output 2 :
120
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 be done.