Runda 6 - Plusy i minusy

26.10.2009 - Damian Rusak
TrudnośćTrudność

Zawody stałe, runda 6

Limit czasowy 2s; Limit pamięciowy 32MB

 


Plusy i Minusy

Cały świat oszlał na punkcie plusów i minusów! Ludzie na ulicy wciąż rozmawiają o plusach i minusach, tematyka dodawania i odejmowania opanowała telewizję, gazety i radio. Trochę dziwna moda, ale co możemy z tym zrobić? Najlepiej podporządkować się trendom i polubić proste działania. Oczywiście informatycy wolą rzeczy trochę ambitniejsze i zawsze muszą wymyślić sobie ciekawszy problem. Miasta i wsie pogrążają się w oparach plusominusowego absurdu, ale na horyzoncie pojawiło się światełko nadziei - interesujący problem!

Mamy dany ciąg liczb naturalnych. Pomiędzy każdymi dwoma kolejnymi możemy wstawić plus albo minus. Możemy też otoczyć dowolny blok liczb nawiasami. Wykonujemy działania zgodnie z ich normalną kolejnością, np:

(5 + 3) - (6 - 3) = 8 - 3 = 5

(5 + 3 - 6) - 3 = 2 - 3 = -1

Słyszałeś, że ktoś w popularnym programie telewizyjnym zadaje gościom pytania o takie ciągi - czy da się w ciągu liczb tak poustawiać plusy, minusy i nawiasy, aby otrzymać dany wynik? Napisz program, który zaszokuje wszystkich i odpowie szybko i sprawnie na takie pytanie!

Zadanie:

Napisz program, który dla danego ciągu liczb naturalnych i pewnej liczby zapytań, odpowie dla każdego zapytania, czy można otrzymać podaną sumę z tego ciągu, poprzez nawiasowanie i ustawienie plusów i minusów pomiędzy liczbami. Znak minus może stać przed pierwszą liczbą.

Wejście:

W pierwszej linii wejścia znajdują się dwie liczby naturalne $ n, k \left(1 \leq n \leq 100, 1 \leq k \leq 10^{5}\right) $, oznaczające kolejno ilość liczb w ciągu i ilość zapytań. W kolejnej linii znajduje się $ n $ liczb naturalnych $ a_{i} \left(0 \leq a_{i} \leq 1000\right) $. W kolejnych $ k $ liniach znajdują się liczby $ b_{j} \left(-10^{9} \leq b_{j} \leq 10^{9}\right) $, oznaczające kolejne zapytania.

Wyjście:

Wyjście powinno składać się z $ k $ linii, po jednej dla każdego zapytania. W j-tej linii powinno się znaleźć słowo TAK , jeśli liczbę $ b_{j} $ można otrzymać jako wynik dodawań i odejmowań ponawiasowanych elementów ciągu $ a_{1}, a_{2}, ... , a_{n} $.


Przykład:


Wejście:

4 4
1 2 3 4
10
-7
0
-10


Wyjście:

TAK
NIE
TAK
TAK

1) 1 + 2 + 3 + 4 = 10
2) -7 nie da się uzyskać w ten sposób
3) - 1 + (2 + 3) - 4  = 0
4) - (1 + 2 + 3 + 4) = -10

Zapraszamy do dyskusji na temat zadania na forum.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Kuba Skudlarski1012:31:55
2Maciej Szeptuch1062:16:42
3Darek Bukowski10151:42:22
4Wojciech Kuprianowicz10153:32:59
5Grzegorz Milka10898:38:00
6Łukasz Hanuszczak101402:43:46
7Przemysław Derengowski101577:18:10
8Michal Zgliczynski102051:02:20
9Mateusz Wasilewski103391:55:28
10Anna Piekarska103591:39:06
11Kamil Łukasz103634:40:43
12Krzysztof Jamróz104444:13:20
13Maciej Kisiel105769:13:04
14Michał Karpiński108162:47:26
15Jadwiga Andryszak387:45:02
16Agnieszka Dudek3153:39:29
17Adam Laskowski3989:44:42
18Krzysztof Cirocki27897:44:42
19Miłosz Łakomy1875:56:56
20Michał Szmidt14492:45:06
21Kuba Skałecki18389:28:14
22Emacs Master18390:55:43
5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com