Решение задачи Письма с Codeforces

Без пояснения   Просмотров: 54


В Берляндском государственном университете всего n общежитий, пронумерованных целыми числами от 1 до n. Каждое общежитие состоит из квартир, в i-м общежитии ai квартир. Квартиры в i-м общежитии нумеруются с 1 до ai.

При получении почты на адрес одной из квартир какого-то общежития иногда не указывается номер квартиры в конкретном общежитии, но указывается номер квартиры среди всех квартир n общежитий. В таком случае, считается что в нумерации сначала идут квартиры первого общежития, затем квартиры второго общежития и так далее. Таким образом, в этой нумерации присутствуют числа от 1 до a1+a2+⋯+an. Квартиры каждого общежития в этой нумерации идут подряд в порядке возрастания номеров.

Например, в случае n=2, a1=3 и a2=5 на конверте может быть написано произвольное целое число от 1 до 8. Если на конверте написано число 7, то это письмо следует доставить в квартиру номер 4 второго общежития.

Для каждого из m писем по номеру квартиры среди всех n общежитий найдите конкретное общежитие и номер квартиры в нём, куда следует доставить это письмо.

Код

#include <bits/stdc++.h>
using namespace std; 

signed main() { 
	int n, m; 
	cin>>n>>m;
	vector<long long> v;
	v.push_back(0);
	for(int i = 0; i < n; i++){
		long long a;
		cin>>a;
		v.push_back(a + v.back());
	}
	int j = 1;
	for(int i = 0; i < m; i++){
		long long a;
		cin>>a;
		while(a > v[j]){
			j++;
		}
		cout<<j<<" "<<a-v[j-1]<<"\n";
	}
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться