| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_31_08 - Dwa ciągi |
Dzielimy ciąg liczb całkowitych an na dwa ciągi w taki sposób, że pierwszy zawiera początkowe i wyrazów (1 ≤ i ≤ n) natomiast drugi pozostałe wyrazy. Należy tak dobrać indeks i aby po usunięciu możliwie najmniejszej liczby wyrazów z obydwu ciągów, pierwszy był rosnący, natomiast drugi malejący.
Uwagi do zadania
- dopuszczamy sytuację, że jeden z ciągów nie ma wyrazów, wtedy ten drugi podciąg musi być rosnący lub malejący
- jeden lub dwa ciągi mogą być jednowyrazowe, np. dla ciągu 1 2 2 otrzymujemy 1 2 i 2, w tej sytuacji nie usuwamy żadnego wyrazu.
Wejście
W pierwszym wierszu jedna liczba t określająca liczbę zestawów danych (nie więcej niż 100).
Każdy zestaw testowy składa się z dwóch wierszy. W pierwszym wierszu jedna liczba n, która określa liczbę wyrazów w ciągu (nie więcej niż 100 000).
W drugim wierszu n liczb, każda mieści się w przedziale [0..107].
Wyjście
Dla każdego zestawu testowego należy określić najmniejszą liczbę wyrazów do usunięcia, tak aby ciągi (ciąg) spełniały kryteria zadania.
Przykład
Wejście: 2 5 1 2 3 2 1 5 1 2 2 1 2 Wyjście: 0 1
| Dodane przez: | Marcin Kasprowicz |
| Data dodania: | 2017-01-06 |
| Limit czasu wykonania programu: | 1s-1.200s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM64 GOSU |
| Pochodzenie: | ALGOLIGA |
ukryj komentarze
|
2017-01-08 14:59:26 Maciej Boniecki
Nie trzeba usuwać tyle samo. |
|
|
2017-01-08 14:50:06
tak dla ścisłości: "po usunięciu możliwie najmniejszej liczby wyrazów z obydwu ciągów" - usuwamy tyle samo z obydwu ciągow, tzn gdy odp=2 to z pierwszego usuwamy 2 i z drugiego 2, czy np z pierwszego 0 i drugiego 2? |
RSS