Szerintem ahhoz is komoly matek kell, hogy az ember egyáltalán rájöjjön, hogy a gombok tekinthetők műveleteknek
Szerintem alap linalg, amit programozóknak tudnia kellene.
Még csak most olvastam a feladatot, (meg amúgy is csak jöttment senki vagyok) ezért bocs, ha baromságokat írok:
A joltage vektor elemszáma a tér (ami amúgy Manhattan-tér) dimenziója. Egy gomb definíciója, hogy ezen térbeli egységvektorok közül melyek összege. Így ezek a vektorok tuti lineárisan függetlenek.
Nagyon leegyszerűsített példa: (0,1) (1,0) {12,18}. Ebből próbálgatás nélkül kiszámítható, hogy 18*(0,1) + 12*(1,0) megoldás az egyetlen, és 30 gombnyomást jelent. Ha van még (1,1) gomb is, akkor is megoldás az előző, de így a legkevesebb gombnyomás 12*(1,1) + 6*(0,1) = 18 adódik. A valódi input-ban persze sokkal bonyolultabb adatok vannak, gondolom arra gondoltál fentebb, hogy a tisztán (rekurzív) bruteforce módszer milliárd év alatt is esélytelen.
Így elsőre azt mondanám, hogy minden gombra könnyen kiszámítható egy felső korlát. A feladatban megadott példák közül az elsőnél:
(3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
(3) < 7; (1,3) < 5; (2) < 4; (2,3) < 4; (0,2) < 3; (0,1) < 3
Mert pl. a 0. cél érték 3, tehát a 0-t tartalmazó gomb 3+ megnyomása biztosan nem adhat helyes eredményt. (Elvileg ezeknél = is lehet, szélsőséges esetben.) Vagy akár mondhatjuk, hogy ha a (2) gomb már kétszer és a (0,2) kétszer meg van nyomva, akkor nincs értelme (...,2,...) gombot nyomni. Így csökkenthető a rekurzív hívások száma, bár most fogalmam sincs, hogy ez elég-e arra, hogy emberi idő alatt lefusson.
Ha egy adatsorra teljesül, hogy gombok száma = cél vektor dimenziója, akkor ott pontosan 1db, próbálgatás nélül kiszámítható megoldása lenne.