21-st International Olympiad In Informatics TASKS AND SOLUTIONS
August8-15,2009
Plovdiv,Bulgaria
221-st International Olympiad In Informatics Day0
Task0.1AREA
A large agricultural corporation is undertaking an audit of its N land proper-ties.As afirst step,they would like to know the total area of their properties. Each property has a rectangular shape,and no two properties overlap.You realize that this is a trivial calculation,but you understand that you need to solve this problem in order to test your ability to properly handle large amounts of data and large numbers under the IOI2009contest system.
TASK
Write a program that,given the dimensions of the N land properties,deter-mines the sum of their areas.
CONSTRAINTS
1≤N≤500000–The number of land properties
1≤A k,B k≤20000–The lengths of the sides of property k
INPUT
Your program should read from the standard input the following data:
中考标语
•Thefirst line contains a single integer:the number of properties N.
•The next N lines describe the properties,one property per line.The k th of the lines describes property number k and it contains two integers parated by a single space:the lengths of the sides of the property A k and B k measured in meters.
OUTPUT
Your program should write to the standard output a single line containing a single integer:the total area of all properties,measured in square meters.
IMPORTANT NOTE
Thefinal answer may notfit in32bits.You have to u a64-bit data type, such as long long in C/C++or int64in Pascal,in order to compute and store the answer in a single variable.Plea e the technical info sheet for details.
2009August8-15,Plovdiv,Bulgaria3 EXAMPLE
幼儿园环创主题墙图片
Sample Input Sample Output
408
3
1525
56
31
Task0.2HILL(propod by Iskren Chernev)
An extraterrestrial team of contestants,known as the aliens,is coming to Plov-div for the IOI.They wo
uld like to land theirflying saucer on one of Plovdivs hills, but they have no map of the city,so they need to u their lar scanner tofind a hill.The aliens have divided the city into a grid of N by M cells,and each time they u the scanner they can determine the altitude of a single cell.Their scanner is so preci that no two cells would ever have the same altitude.
The aliens define a hill as a cell that has higher altitude than all of its adjacent cells.Two cells are considered adjacent if they share a side.Thus typically each cell has four adjacent ones,with the cells on the border of the grid being the exception(they have less than four adjacent cells).
The aliens have time for only3050scans before their saucer hits the ground. Help the aliensfind a hill before they run out of time.
TASK
Write a program that,given the dimensions of the grid,interactively us the scanner to determine the location of a hill,while doing no more than3050scans in total.潘径中学
CONSTRAINTS
月亮啊月亮1≤N,M≤1000–The dimensions of the grid
1≤A x,y≤2000000000–The altitude of cell<x,y>
INPUT
Your program should read from the standard input a single line with two integers N and M,parated by a single space.
421-st International Olympiad In Informatics
INTERACTION
After reading the input data,your program should start using the lar scanner. Each time you want to u the scanner for a cell with coordinates x and y(1≤x≤N,1≤y≤M),you should print a single line on the standard output,containing three integers parated by single spaces:0(a literal zero),x and y,in this order.
After submitting your request to the scanner,you should read a single line on the standard input.It will contain a single integer:the altitude of the cell with coordinates x and y in some alien units.
OUTPUT
When your program has determined the location of a hill<a,b>(1≤a≤N, 1≤b≤M),you should report your answer by printing a single line on the standard output,containing three integers parated by single spaces:1(a literal one),a and b,in this order.
IMPORTANT NOTE:In order to interact properly with the scanner,your program needs toflush the standard output after every line that you print on the standard output.Plea e the technical info sheet for instructions on how to do this properly.
EXAMPLE
Sample Input Sample Output
32
3 4 1 7 6011[flush stdout/output] 021[flush stdout/output] 031[flush stdout/output] 012[flush stdout/output] 022[flush stdout/output] 112[flush stdout/output]
2009August8-15,Plovdiv,Bulgaria5
高山上的花环
0.3MUSEUM(propod by Boyko Bantchev)
The Plovdiv Muum of Modern Art has an exhibition of ancient Thracian vas.There are N vas total.Thefirst one is a miniature of height1centimeter. The cond one is of height2centimeters;the third one is3centimeters tall and so on until the N th va,which is N centimeters tall.
Since this a modern art muum and the vas are ancient,the organizers of the exhibition would like to add a modern,chaotic twist to the prentation of the vas.They have decided to arrange the vas in a line that satisfies the following condition:For any three vas A,B and C,such that B s height is exactly the average of the heights of A and C,either B must be positioned to the left of both
A and C,or
B must be positioned to the right of both A and C(in other words,
B may not be positioned between A and
C on the line).
家宴菜单TASK
Write a program that,given the number of vas,determines a linear arrange-ment of the vas that satisfies the condition of the exhibition organizers.
CONSTRAINTS
1≤N≤2000–The number of vas
德育教育案例
INPUT
You are givenfive problem instances in thefiles muum.1.in to muum.5.in. Eachfile contains a single line,which in turn contains a single integer:the number of vas N.
尖椒炒肉丝OUTPUT
You are to submitfive outputfiles,named muum.1.out to muum.5.out, each corresponding to one of the inputfiles.Thefiles should be in the following format:
There should be N lines,each reprenting the N positions in the arrangement, in order from left to right.Line k should contain a single integer H k,the height of the va you decided to place on position k.All N heights should be distinct integers between1and N inclusive.
