Omówienie zadania Bony – II etap Olimpiady Informatycznej

Omówienie zadania Bony – II etap Olimpiady Informatycznej

Szczegółowe omówienie zadania Bony:

Link do powyższego omówienia zadania Bony:
https://youtu.be/OC_xrHSMYlA?t=1162
Link do treści zadania Bony:
——-
Zadanie Bony jest typowym zadaniem na pomysł, małą optymalizacją rozwiązania brutalnego.
——-
Zadanie pochodzi z II etapu Olimpiady Informatycznej Licealistów.
Warto zrobić – daje dużą satysfakcję i wiarę, że spokojnie możemy walczyć o finał Olimpiady i więcej!
https://youtu.be/OC_xrHSMYlA?t=33
——-
Zadanie omawia Mikołaj Bulge, prowadzący zajęcia Olimpijskiego Koła Informatycznego:
https://youtu.be/OC_xrHSMYlA?t=1087

——–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625

——-
Kod C++ programu Bony, który jest omówiony w powyższym filmie i który otrzymuje 100%


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

constexpr int M=1e6+7;
vector<long long>vctr;
int last[M];
bool cb[M];
bool bought[M];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	long long klejent=0;
	int n,m,a,used;
	cin>>m;
	
	for(int i=1; i<=m; i++){
		cin>>a;
		cb[a]=1;
	}
	
	cin>>n;
	
	for(int i=1; i<=n; i++){
		cin>>a;
		used=0;
		
		for(int j=last[a]+a; j<=1000000; j+=a){
			if(used==a) break;
			if(bought[j]) continue;
			last[a]=j;
			bought[j]=1;
			used++;
			klejent++;
			if(cb[j]) vctr.push_back(klejent);
		}
		klejent+=a-used;
	}
	
	cout<<vctr.size()<<'\n';
	for(auto w:vctr) cout<<w<<'\n';
	
	return 0;
}
Link do pliku ze wzorcowym kodem C++ zadania Bony 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz