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;
//LICZYMY ILE ZMIAN TRZEBA WYKONA DO i BY a ORAZ b BYY RWNE DO INDEKSU i
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];
}
//SZUKAMY JAK NAJDALSZEGO INDEKSU od LEWEJ GDZIE CYFRA NOWEGO a BDZIE RӯNA I MNIEJSZA OD b
//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) {
//Jeli b[i] jest zero to a[i] nie moe by mniejsze - ten indeks i odpada 
//jako ten ktry decyduje ze a bdzie mniejsze od b czyli pierwszy taki ze a[i]<b[i]
if(b[i] == '0')       
continue;
//ile_bylo_zmian - ile zmian musielibymy do tej port wykona
//by wczesniejsze cyfr a byly rowne b
ile_bylo_zmian = 0;
if(i != 0)
ile_bylo_zmian = ile_roznych_cyfr_od_1[i - 1];
//jeli a[i] jest wiksze rwne b[i] to a[i] te musimy zmniejszy
// by by to ten indeks ktry decyduje ze a bdzie mniejsze od b 
//czyli pierwszy taki ze a[i]<b[i]
if(a[i] >= b[i])
++ile_bylo_zmian;
//ile jest znakw na prawo pod nas (od i) acznie bez pozycji i
ile_zostalo_znakow = a.length() - i - 1;
//Nasz pozycj a[i] mniejsz od b[i] te moemy doda jako t na ktrej moemy
//wykona zmian tak by i byo ierwszym od lewej takim, e a[i<b[i]
//chyba, e b[i] jest 1 a a[i] = 0;
//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 - tyle k nam jeszcze zostao ktre MUSIMY wykorzystac
pozostale_k = k-ile_bylo_zmian;    
//nasz indeks i moe by pierwsz [ierwszym indeksem ktry decyduje 
//ze a bdzie mniejsze od b czyli pierwszym takim ze a[i]<b[i]
//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;
//Nie moemy ze jesli ile_bylo_zmian > k to nie ma sensu dalej rozpatrywac
//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 ];
//Najlepiej jeli c[i] jest o 1 mniejsze od b[i]
if( (pozostale_k>0) && (a[i] != b[i]-1) ) {
c[i] = b[i] - 1;
--pozostale_k;
 } else	{
//Jeli si nie da to c[i] musi pozosta a[i] - wiemy ze moze 
//na podstawie wczesniejszej analizy
c[i] = a[i];
}
//Pozostae c[i] zamieniamy na '9'
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
//wowczas zostawiamy 9 ale zmnieszamy pozostaego k
//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