Problem hidden

This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Zadanie w systemie SPOJ (srednie)

783. Mniejsze niż

Kod zadania: LESSTHAN

Dany jest zbiór A złożony z n liczb naturalnych. Mając liczbę naturalną i wyznacz, ile jest w zbiorze A liczb od niej mniejszych.

Wejście

W pierwszym wierszu podana jest liczba n<10⁶ , czyli moc zbioru A. Następnie kolejne n wierszy zawiera elementy A. Są to liczby naturalne z zakresu [1..10³⁰-1]

Następnie podana jest liczba k<10⁶ oraz w kolejnych k wierszach podawane są liczby naturalne i₁,..., i_k z zakresu [1..10³⁰-1].

Wyjście

Dla każdej liczby i_s należy podać ile elementów w zbiorze A jest mniejszych od i_s.

Przykład

Wejście:
10
5
4
2
3
1
1
10
20
15
100

3
7
1
18

Wyjście:
6
0
8

Dodane przez:	Adam Nadolski
Data dodania:	2006-03-17
Limit czasu wykonania programu:	1s
Limit długości kodu źródłowego	50000B
Języki programowania:	ADA C C++ 4.0.0-8 C99 strict JAVA PAS fpc PAS gpc PERL PYTH 2.5 RUBY

ukryj komentarze

2012-05-09 21:04:45 Korus Konrad
Czemu nie C# ?

2011-05-23 00:05:14 Jakub Pierewoj
@Piotr Kąkol
[tu była podpowiedź] weszło na 5pkt

Edit by kokosek: To za dużo podpowiadało. ;-)
Wiem, też tak zrobiłem. ;-)

Ostatnio edytowany: 2011-05-24 14:31:06

2011-02-20 11:53:31 Piotr Kąkol
@Krzysztof Waszak - Faktycznie. :-) Napisałem na forum, żeby poprawili. + dla Ciebie, że uważnie czytasz!

2011-02-19 20:32:11 Krzysztof Waszak
Zadanie nie jest zgodne z definicją zbioru. To jest multizbiór nie zbiór :(

2010-06-22 09:01:02 Piotr Kąkol
@Michał Woś - O. Ciekawe, nie pomyślałem o tym. Jednak to chyba nic nie zmieni, bo skoro piszesz w C++ to pewnie używasz sorta, a jego formuła będzie taka sama niezależnie od typu zmiennych, więc nie widzę sensu.

2010-06-22 01:18:36 Michał Woś
2 ostatnie testy mam przekroczony limit czasu. Wszytuje jako string, sortuje, szukam indeksu metodą połowiczną, żeby jeszcze szybciej było i lipa.

A może spróbować z warunkiem? jeżeli liczba którą mamy porównywać (zadaniowe 'k') bedzie mniejsza od sizeof(unsigned long long) to wtedy rozpatrywac jako liczby, w przeciwnym wypadku jako stringi?

2010-05-21 21:26:15 Daniel Masiukiewicz
Thx, tera już trochę lepiej to ogarniam i nie powinienem mieć większych problemów z tym zadaniem :)

2010-02-13 16:16:34 Krzysiek Gała
heh... jak robię na stringach to zalicza mi pierwsze 3 testy, jak na long long to 2 ostatnie. Dziwne nie?

2010-02-07 22:15:14 Piotr Kąkol
@Daniel Masiukiewicz - Powinieneś właśnie wczytywać liczby jako stringi, bo nawet long long jest za mały dla liczb do 10^30, jak to jest w specyfice zadania.
@Paweł Matwiejuk - Spróbuj wczytać liczby jako stringi, potem je posortować i użyć lower_bound (albo upper_bound nie pamiętam).

2009-12-27 19:54:27 Paweł Matwiejuk
na każdym teście mam prawie 2sec za długo ;/

POLSKI SPOJ