Zadanie

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy. Stačí, že pôjdeš na stránku nášho testovača a budeš riešiť sadu Úvod do programovania. Každou z úloh Najmenší, Akéže je znamienko?, Prostredný si vieš nahradiť 5 bodov z tejto úlohy. Pomôcť si vieš Python tutoriálom, ktorý sme pre teba nachystali. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na testovači.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Krtkovi na krtko@ksp.sk

Včera sa stalo niečo neslýchané! Niečo, čo bude mať katastrofálne následky! A ostáva nám len dúfať, že to neovplyvní našu časť vesmíru.

Ešte predvčerom pokojní obyvatelia planéty Sysľov lietali na ufách krížom krážom galaxiou, zúčastňovali sa všetkých možných programátorských súťaží a všetky do jednej vyhrávali. Včera však utrpeli strašnú porážku, prvýkrát v histórii, a to práve od obyvateľov planéty Žiab. Aby si zachovali česť, neostáva im nič iné, ako planéte Žiab vyhlásiť vojnu. Nie programátorskú, tam si už nie sú takí istí, ale fyzickú a likvidačnú.

V skratke, v neďalekom vesmíre vypukol Krvilačný Súboj Planét.

Najdôležitejším krokom vo vojne je produkcia bojových robotov. Syslí návrhári vytvorili prototyp, na základe ktorého sa budú stavať. Pri stavbe robota sa však využívajú niektoré prototypom definované suroviny, ktorých je len obmedzene veľa, obmedzený je teda aj počet robotov, ktorých vedia vyrobiť.

Na planéte Sysľov sa však nachádza aj jedna špeciálna surovina – žolícium. Tá sa vyznačuje tým, že sa ňou dá nahradiť ľubovoľná iná surovina. Z dostatku žolícia dokonca môžete postaviť celého robota. Ak sa teda žolícium správne prerozdelí medzi zvyšné suroviny, môže sa zvýšiť počet robotov, ktorých vedia na planéte Sysľov vytvoriť. Obyvatelia planéty Sysľov však nevedia, ako žolícium rozdeliť a naprogramovať si to už netrúfajú.

Úloha

Dostanete cenu jedného robota vyjadrenú ako počet jednotlivých surovín, ktoré na jeho výrobu treba. Okrem toho dostanete aktuálny počet každej zo surovín a počet špeciálnej suroviny, žolícia, ktoré môže byť použité ako ľubovoľná surovina. Riešiť potom musíte dva typy úloh: * Obrana – dostanete navyše počet robotov, ktorý by sme chceli vytvoriť a vašou úlohou je zistiť, či sa daný počet da vytvoriť zo zadaných surovín. * Útok – zistite maximálny možný počet robotov, ktorých vieme poskladať zo zadaných surovín.

Ak viete vyriešiť iba jednu z podúloh, nezúfajte, určite sa vám újdu nejaké body.

Formát vstupu

Na prvom riadku vstupu je jedno slovo, a to Obrana alebo Utok, podľa toho, či teraz treba brániť alebo útočiť.

Na druhom riadku vstupu sú dve čísla, \(n\) \((1 \leq n \leq 10^5)\) – počet rôznych typov surovín, a \(b\) \((0 \leq b \leq 10^{14})\) – počet špeciálnych surovín, ktoré môžete rozdeliť ako chcete.

Na treťom riadku vstupu je \(n\) čísel, \(i\)-te z nich znamená, že máte k dispozícií \(A_i\) \((0 \leq A_i \leq 10^{7})\) \(i\)-teho typu surovín.

Na štvrtom riadku vstupu je \(n\) čísel, \(i\)-te z nich znamená, že počet potrebných surovín \(i\)-teho typu na jedného robota je \(B_i\) \((0 \leq B_i \leq 10^{6})\). Navyše máte garantované, robot stojí aspoň \(1\) z nejakej suroviny.

Ak sa jedná o obranu, vstup má ešte jeden riadok, na ňom je jedno kladné celé číslo – počet robotov, ktorých treba vyrobiť, aby sme sa ubránili.

Navyše platí, že bez ohľadu nato, či sa Sysľovčania bránia alebo útočia, nemôžu vyrobiť viac robotov ako počet atómov na planéte Sysľov, teda viac ako \(10^{10}\) robotov.

Formát výstupu

Ak sa jedná o útok, vypíšte jedno číslo – najväčší počet robotov, ktoré môžeme vyrobiť.

Ak sa jedná o obranu, vypíšte Ano, ak sa daný počet robotov dá postaviť, a Nie ak sa nedá.

Hodnotenie

Je 5 sád vstupov a za každú je možné získať 3 body.

sada max n max b
\(1\) \(10^3\) \(0\)
\(2\) \(10^3\) \(10^5\)
\(3\) \(10^3\) \(10^14\)
\(4\) \(10^5\) \(10^14\)
\(5\) \(10^5\) \(10^14\)

Navyše platí, že v druhej sade sú len obrany.

Upozornenie: Počet vyrobených robotov aj počty surovín môžu byť veľmi veľké čísla. Preto si treba uvedomiť, že v niektorých jazykoch majú bežné celočíselné premenné obmedzený rozsah. Napríklad v C++ int má klasicky 32 bitov, čo nemusí stačiť. Chcete preto použiť 64 bitové premenné (napr. long long v C++, Int64 v Pascale).

Príklad

Input:

Utok
9 15
6 8 3 7 7 4 9 4 5
1 2 4 2 4 4 2 4 1

Output:

2

Ak si pridáme 5 z druhého typu, 1 z štvrtého typu a 4 z piateho typu a 4 zo siedmeho typu, budeme mať dostatok na 2 robotov. Ak by sme chceli vyrobiť 3, potrebovali by sme pridať aspoň 9 druhého typu, a 8 z piateho typu. Bohužiaľ máme iba 15 bonusových surovín

Input:

Obrana
9 15
6 8 3 7 7 4 9 4 5
1 2 4 2 4 4 2 4 1
3

Output:

Nie

Bez žolícia

Keďže nie sú žiadne bonusové suroviny, robotov treba vyrobiť iba z normálnych surovín. Z každej suroviny treba použiť na výrobu jedného robota určený počet, takže stačí zisťovať koľko najviac sa dá poskladať z každej suroviny robotov. Keď je niektorej suroviny dostatok len na \(k\) robotov, tak určite sa nedá postaviť viac ako \(k\) robotov, lebo z danej suroviny nie sú suroviny ani na robota naviac. Teda celkovo najväčší počet robotov je minimum z počtov robotov, ktorých sa dá poskladať z nejakej suroviny. Ak ide o obranu, je potrebné iba zistiť, či je to dostatočný počet alebo nie. Ak ide o útok, výstupom je spomínaný počet. Spracovanie každej suroviny zaberie len niekoľko numerických operácií, teda časová zložitosť je \(O(n)\).

Len obrana

Keďže je presne určené koľko robotov treba vyrobiť, je známe aj koľko na to treba z každej suroviny. Jednoducho sa teda dá zistiť, koľko z každej suroviny chýba a teda je potrebné doplniť žolíciom. Ak by chýbalo viac ako \(b\) surovín, nedá sa vyrobiť daný počet robotov, keďže nie je dostatok žolícia. Inak je možné vyrobiť toľko robotov. Toto sa dá opäť zistiť v \(O(n)\), keďže je potrebné niekoľko numerických operácií na spracovanie každej suroviny.

Pomalé riešenie

Pomocou algoritmu na obranu sa teraz dá postupne skúšať či je možné postaviť jedného robota, dvoch, … Takto sa určite raz stane, že nebude možné postaviť daný počet robotov, lebo nebude dostatok nejakej suroviny na postavenie daného počtu robotov, teda počet robotov už nebude väčší, čím je zistený maximálny počet robotov. Problémom ale je, že počet robotov môže byť veľmi veľký a teda riešenie bude pomalé.

Vzorové riešenie

K vzorému riešeniu chýba už len rozvinúť vyššie načrtnutú myšlienku – postupným skúšaním či sa dá daný počet robotov vyrobiť. Najprv bude odpoveď áno, kým je možné daný počet vyrobiť. Potom nastane zmena a odpoveď bude vždy nie. Vďaka tomu nie je potrebné skúšať všetky možné počty robotov, ale dá sa binárne vyhľadať najväčší počet robotov, ktorý je možné vyrobiť. Stačí si pamätať aký najväčší a aký najmenší počet robotov je možné vyrobiť. Na začiatku je určite možné vyrobiť \(0\) robotov, a zároveň určite nie je možné vyrobiť viac ako \(x\) robotov, kde \(x\) je najväčší počet robotov, napríklad súčet všetkých surovín plus jedna.

Vždy bude platiť, že minimum označuje počet, ktorý sa dá vyrobiť a maximum počet, ktorý sa už vyrobiť nedá. Tieto dve hodnoty tvoria nejaký úsek, interval hodnôt, ktoré by mohli byť odpoveďou na našu otázku. Takýto interval však vieme po krokoch zlepšovať. V každom kroku je potrebné zistiť, či sa dá vyrobiť počet robotov, ktorý je v strede medzi krajnými hodnotami úseku. Ak sa daný počet vyrobiť dá, posunieme minimum koľko sa dá vyrobiť na túto hodnotu. Ak sa daný počet nedá vyrobiť, posunieme maximum. Po každom kroku bude úsek polovičný, to znamená, že dokopy spravíme určite najviac logaritmus krokov. To, prečo je to naozaj tak, je nad rámec tohto vzoráku. Pamäťová zložitosť je \(O(n)\), časová \(O(n \log x)\),

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool dasa(const vector<long long>& mam, const vector<long long>& treba, long long kolko, long long b) {
	for (int i = 0; i < mam.size(); ++i) {
		b -= max(0ll, treba[i]*kolko-mam[i]);
		if (b < 0) return false;
	}
	return true;
}

int main() {
	string s;
	long long n, b;
	cin >> s >> n >> b;

	vector <long long> mam(n), treba(n);

	for (int i = 0; i < n; ++i) cin >> mam[i];
	for (int i = 0; i < n; ++i) cin >> treba[i];

	if (s == "Obrana" ) {
		long long kolko;
		cin >> kolko;

		if (dasa(mam, treba, kolko, b)) cout << "Ano\n";
		else cout << "Nie\n";

	} else {
		long long l = 0, r = 10000000000000;
		while(r-l-1) {
			long long m = (l+r)/2;
			if (dasa(mam, treba, m, b)) l = m;
			else r = m;
		}
		cout << l << '\n';
	}
	return 0;
}
s = input()
n, b = map(int,input().split())
mam = [int(i) for i in input().split()]
treba = [int(i) for i in input().split()]
maximum = 10000000000000

def dasa(kolko, b):
  global mam, treba
  for i in range(n):
    b -= max(0, treba[i]*kolko-mam[i])
    if b < 0: return False
  return True

if s == "Obrana" :
  kolko = int(input())

  if dasa(kolko, b):
    print("Ano")
  else:
    print("Nie")

else:
  l = 0
  r = maximum+1
  while r-l > 1:
    m = (l+r)//2
    if dasa(m, b):
      l = m
    else:
      r = m
  print(l)

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.