Pomniejszenie – Omówienie zadania z Olimpiady Informatycznej Licealistów

Pomniejszenie – Omówienie zadania z Olimpiady Informatycznej Licealistów

Szczegółowe omówienie zadania Pomniejszenie:

Link do powyższego omówienia zadania Pomniejszenie:
https://youtu.be/kH-_PQyAs9A?t=1129
Skrót omówienia zadania Pomniejszenie:
https://youtu.be/kH-_PQyAs9A?t=5020
Omówienie kodu zadania Pomniejszenie:
https://youtu.be/kH-_PQyAs9A?t=3449

——-
Link do treści zadania Pomniejszenie:
——
Zadanie Pomniejszenie jest prostym do wymyślenia zadaniem.
Wymaga jedynie narysowania i rozpatrzenia przypadków.
Jego implementacja jest trochę trudniejsza – jest kilka przypadków granicznych – “corner case’ów”
Zrobienie tego zadania – bez względu na punktu – daje ogromną motywację do rozwoju bo widzimy, że Olimpiada Informatyczna jest w naszym zasięgu.
—–
Zadanie Pomniejszenie pochodzi z I etapu 27 Olimpiady Informatycznej Szkół Ponadpodstawowych.
Link do wszystkich zadań z Olimpiady Informatycznej:
https://szkopul.edu.pl/task_archive/oi/
——–
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
——-

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int ile_roznych_cyfr_od_1[N];

void ObliczWynik(string a, string b, int k) {
 string c;
 int i, ile_bylo_zmian, ile_zostalo_znakow, pozostale_k;
 int decydujacy_index_ze_C_mniejszy_od_B;

 ile_roznych_cyfr_od_1[0] = 0;
 if(a[0] != b[0])
    ile_roznych_cyfr_od_1[0] = 1;
 for(i = 1; i < (int)a.size(); ++i) {
    ile_roznych_cyfr_od_1[i] = ile_roznych_cyfr_od_1[i - 1];
	if(a[i] != b[i])
	   ++ile_roznych_cyfr_od_1[i];
 }

//Na poczatku nie mamy zadnego indeksu ktory by dal ze a < b 
 decydujacy_index_ze_C_mniejszy_od_B = -1;
 for(i = 0; i < (int)a.size(); ++i) {
    if(b[i] == '0')       
	   continue;
//by wczesniejsze cyfr a byly rowne b
	ile_bylo_zmian = 0;
	if(i != 0)
	   ile_bylo_zmian = ile_roznych_cyfr_od_1[i - 1];
//czyli pierwszy taki ze a[i]<b[i]
	if(a[i] >= b[i])
	   ++ile_bylo_zmian;
	ile_zostalo_znakow = a.length() - i - 1;
//na przyklad b[i] = 5 zas a[i] = 4 to tu moze byc pierwsza zmiana i a[i] ustawimy na 3
	if( (a[i]<b[i]) && (b[i]!='1') )
	   ++ile_zostalo_znakow;
	pozostale_k = k-ile_bylo_zmian;    
//jesli spelnione sa 2 warunki:
//   - do tej pory nie wykonalismy wiecej niz zmian cyfr a tak by byly rowne cyfrom b
//   - mozemy jeszcze wykonac tyle zmian na cyfrach po prawej stronie ile pozostalo k 
	if ( ile_bylo_zmian <= k ) 
	   if ( ile_zostalo_znakow >= pozostale_k )
	      decydujacy_index_ze_C_mniejszy_od_B = i;
//gdyz aktualna pozycja moze sie wliczac klub nie
 }

//Jesli nie znalezlismy zadnego indeksu ze a < b to wypisujemy -1 dla tego przypadku
 if(decydujacy_index_ze_C_mniejszy_od_B == -1) {
    cout << "-1\n";
    return;
 }

//c to nasze zmodyfikowane a - mniejsze od b ale najwieksze z mozliwych
//do indeksu decydujacy_index_ze_C_mniejszy_od_B c (nowe a) musi miec cyfry rowne b
 c = b;

//OBLICZAMY CYFRE NA POZYCJI NA KTOREJ NOWE a (CZYLI c) JEST PIERWSZY RAZ MNIEJSZ OD B
 i = decydujacy_index_ze_C_mniejszy_od_B;
//pozostale_k - ile jeszcze musimy zmienic cyfr w dalszej czesci a
 pozostale_k = k;
 if( i != 0 )
    pozostale_k = k - ile_roznych_cyfr_od_1 [ i-1 ];
 if( (pozostale_k>0) && (a[i] != b[i]-1) ) {
    c[i] = b[i] - 1;
	--pozostale_k;
 } else	{
//na podstawie wczesniejszej analizy
    c[i] = a[i];
 }
 
 for(++i; i < (int)a.size(); ++i) {
    if( (pozostale_k>0) && (a[i]!='9') ) {
 	   c[i] = '9';
	   --pozostale_k;
	} else
//chyba, ze a[i] bylo dziewiatka
//rowniez jesli pozostale k siekonczylo to po prostu bierzemy
//a[i] jak jest
	   c[i] = a[i];
 }
//jesli zostalo nam troche pozostalych k (bylo duzo 9 w a)
//to te pozycje zamieniamy na 8 - o 1 mniejsze
 for(i = (int)a.size() - 1; i >= 0; --i) {
    if(pozostale_k > 0 && c[i] == a[i]) {
  	   c[i] = c[i] - 1;
	   --pozostale_k;
	}
 }
;
 cout << c << "\n";
}


int main () {
	int n, k, i;
	string a, b;

	cin >> n;

	for(i = 1; i <= n; ++i) {
		cin >> a >> b >> k;
		ObliczWynik(a, b, k);
	}
	
	return 0;
}
Kod C++ programu Pomniejszenie, który jest omówiony w powyższym filmie i który otrzymuje 100% 

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz