Zadanie 7
Najneskorší termín odovzdania: 6.4.2025 (nedeľa) o 18:00
Odovzdávané súbory: Cards.java, Tyber.java
Kartičky (7 bodov)
Matematik Karol sa počas prednášok z analýzy veľmi nudil. A tak si vymyslel takúto zaujímavú matematickú hru. Na M papierových kartičiek si na každú stranu kartičky napísal nejaké (náhodné) celé číslo od 0 po 100. Teda na každej kartičke sú napísané celkovo 2 čísla (jedno na jednej strane, druhé na druhej). Potom požiadal vedľa seba sediaceho kolegu, aby mu povedal nejaké celé číslo N. Otázka, ktorú sa rozhodol vyriešiť bola takáto: Je možné pootáčať kartičky tak, aby súčet čísel na kartičkách (na tých stranách, ktoré sú nahor – viditeľné) bol práve N?
Vstup: Dvojrozmerné pole čísel určujúce hodnoty kartičiek. Pole má rozmer Mx2, kde M určuje počet kartičiek a platí 1≤M≤2000. Hodnoty na kartičkách sú v rozsahu 0≤X≤100. Druhým parametrom je number (N) – hádané číslo.
Výstup: true alebo false, podľa toho, či M kartičiek ide pootáčať tak, aby súčet čísel na viditeľných stranách bol N (parameter number).
Príklad:
Uvažujme kartičky [19,40], [23 40], [17, 24], [18, 24], [71, 96].
Pre hodnotu number=185 je výsledok false.
Pre hodnotu number=175 je výsledok true (40+23+17+24+71=175).
2
3
4
5
6
7
public boolean solve(int[][] cards, int number) {
return false;
}
}
Poznámka/pomôcka: keď počet kartičiek môže byť až 2000, backtrack nezafunguje. Treba však využiť, že čísla na kartičkách sú nanajvýš 100. A to dáva priestor na dynamické programovanie (treba sa inšpirovať úlohami, ktoré sa robili na cvičení a prednáške).
Tyber (6 bodov)
Tibor sa rozhodol založiť nízkonákladovú spoločnosť na prepravu osôb. Jeho originálny prístup spočíva v tom, že jeho vozidlo je motorka a pohybuje sa len po vopred určenej trase. Biznis sa mu postupne rozrástol a miestami chce cestovať viac, ako len jeden zákazník a tak si chce nechať vypracovať rozpis zvolených cestujúcich, ktorý by mu maximalizoval zisky. Každý z C cestujúcich má určené, na ktorom stanovisku chce nastúpiť (N) a vystúpiť (V) a koľko je ochotný zaplatiť za prepravu (P). Podľa platnej legislatívy smie naraz viezť len jedného zákazníka.
Zistite, koľko najviac je Tibor schopný zinkasovať za jeden prechod.
Vstup: Súbor, kde sa v prvom riadku nachádza číslo C. Nasleduje C riadkov s číslami N, V a P pre jednotlivých cestujúcich.
Platia obmedzenia:
1 ≤ C,P ≤ 10000
0 ≤ N < V ≤ 1000
Výstup: najväčší možný príjem pre danú situáciu popísanú v súbore.
Príklad: Pre nasledujúci vstupný súbor je výsledok 1100.
2
3
4
5
6
0 1000 1000
0 100 250
101 200 250
200 500 300
600 900 300
2
3
4
5
6
7
8
9
10
11
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Tyber {
public int solve(File file) {
return 0;
}
}
Pomôcka: označme si R[J] – maximálny dosiahnuteľný príjem v okamihu, keď auto na zastávke J zastavilo, aby z neho vystúpil pasažier, alebo prechádza zastávkou J prázdne.