Матч 18, Яблочный сад (ApplePie)

Яблочный сад имеет вид прямоугольника с вершинами (0, 0), (0, 100), (100, 100), (100, 0). i - ое яблоко падает на землю в день day[i], и имеет координаты (x[i], y[i]). Вы можете подобрать яблоко, если только оно упало на землю в границах прямоугольного сада. Определить день, в который можно собрать howMany яблок. Если этого совершить невозможно, вернуть -1.

Класс: ApplePie

Метод: int getApples(vector<int> x, vector<int> y,

vector<int> day, int howMany)

Ограничения: x, y и day содержат одинаковой количество элементов, от 1 до 50, -1000 £ x[i], y[i] £ 1000, 1 £ day £ 365, day[i] £ day[i+1], 1 £ howMany £ n, где n – количество элементов в x.

Вход. Два массива целых чисел x и y – координаты упавших яблок, массив day, описывающий дни падения яблок и количество яблок howMany, которое требуется собрать.

Выход. День, в который можно собрать howMany яблок. Если этого совершить невозможно, вернуть -1.

Пример входа

low	high
1	5
7	7
56	99

Пример выхода

4

0

16

РЕШЕНИЕ

элементарные вычисления

Для каждого яблока проверяем, упало ли оно в границах сада. Если да, то увеличиваем количество собранных яблок в переменной res. Как только соберется howMany яблок, возвращаем день падения последнего подобранного яблока. Если массивы просмотрены до конца, а howMany яблок не собрано, то возвращаем -1.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

class ApplePie

{

public:

int getApples(vector<int> x, vector<int> y, vector<int> day, int howMany)

{

int i,res = 0;

for(i=0;i<x.size();i++)

{

if (!((x[i] > 100) || (x[i] < 0) || (y[i] > 100) || (y[i] < 0))) res++;

if (res == howMany) return day[i];

}

return -1;

}

};