Omówienie zadania “Test na inteligencję” (Olimpiada Informatyczna)

Omówienie zadania “Test na inteligencję” (Olimpiada Informatyczna)

Szczegółowe omówienie zadania Test na inteligencję:

Link do powyższego omówienia zadania Test na inteligencję:
https://youtu.be/V6axb24D1dw?t=4928

Zadanie Test na inteligencję wymaga odpowiedniego przechowywania danych (tablica wektorów) i użycia algorytmy Binary Search. Zadanie pochodzi z I etapu Olimpiady Informatycznej Licealistów.

Omawia Janek – uczestniczek Olimpijskiego Koła Informatycznego, uczeń VIII klasy Szkoły Podstawowej w Sławnie:
https://youtu.be/V6axb24D1dw?t=6175

Bardzo dziękuję!

—–
Jak się uczyć na podstawie tego zadania?
https://tiny.pl/7x1gg

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


#include <bits/stdc++.h>
using namespace std;
	
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//wejscie
	int n, p;
	cin>>n;
	int ciag[n];
	for (int i = 0; i < n; i++)
		cin >> ciag[i];
	int m;
	cin >> m;
	int n_y[m];
	vector <vector <unsigned int> > zapytania(m);
	for(int i = 0; i < m; i++){
		cin >> p;
		n_y[i] = p;
		unsigned int x;
		for (int w = 0; w < p; w++){
			cin >> x;
			zapytania[i].push_back(x);
		}
	}
	//koniec wejscia
	vector <vector <unsigned int> > indeksy(1000009);
	bool podwynik;
	unsigned int minimum;
	for (int i = 0; i < n; i++){
		indeksy[ciag[i]].push_back(i);
	}
	unsigned int poc = 0, k = n-1, sr, goal;
	for (int i = 0; i < m; i++){
		podwynik = true;
		
		if (indeksy[zapytania[i][0]].size() > 0)
			minimum = indeksy[zapytania[i][0]][0];
		else
			podwynik = false;
		if (podwynik)
			for (int w = 1; w < n_y[i]; w++){
				if (indeksy[zapytania[i][w]].size() > 0){
					poc = 0;
					k = indeksy[zapytania[i][w]].size()-1;
					if (indeksy[zapytania[i][w]].back() > minimum){
						if (indeksy[zapytania[i][w]].size() > 1){
							while (poc <= k){
								sr = (poc+k)/2;
								if (sr < 0 || sr >= indeksy[zapytania[i][w]].size()){
									break;
								}
								if (indeksy[zapytania[i][w]][sr] <= minimum){
									poc = sr+1;
								}
								else{
									goal = sr;
									k = sr-1;
								}
							}
							minimum = indeksy[zapytania[i][w]][goal];
						}else{
							if(indeksy[zapytania[i][w]][0] > minimum)
								minimum = indeksy[zapytania[i][w]][0];
							else{
								podwynik = false;
								break;
							}
						}
					}
					else{
						podwynik = false;
						break;
					}
				}
				else{
					podwynik = false;
					break;
				}
			}
		if (podwynik)
			cout << "TAK\n";
		else
			cout << "NIE\n";
	}
	return 0;
}
Link do pliku ze wzorcowym kodem C++ zadania Test na inteligencję 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz