Nie zakładam nowego wątku tylko się podczepię tutaj. Na początek kilka wniosków:
W zadaniu chodzi o znalezienie najdłuższego wspólnego niekoniecznie spójnego podciągu (czyli o to co jest opisane w sekcji "Wyjście"). Nie wiem dlaczego autor każe Jasiowi w treści zadania pytać o podciąg rosnący. By uniknąć konfuzji proponuję by zmienić treść pytania Jasia np. na "Co dziś na obiad?"
Zestawy danych testowych nie są zgodne ze specyfikacją. Ciąg Fasoli zawiera powtórzone liczby, co łatwo sprawdzić programem:
[code]#include
include
include
int main(void) {
int i, n, t;
char mark[25501];
// n
scanf("%d", &n);
// ciag jasia
memset(mark, 0, sizeof(mark));
for (i = 0; i < n; ++i) {
scanf("%d", &t);
assert(mark[t] == 0);
mark[t] = 1;
}
// ciag fasoli
memset(mark, 0, sizeof(mark));
for (i = 0; i < n; ++i) {
scanf("%d", &t);
assert(mark[t] == 0);
mark[t] = 1;
}
return 0;
}[/code]W programie zaznaczamy w tablicy mark każdą wczytaną liczbę. Program wyleci na drugim assercie (SIGABRT)
- Nawet mając na uwadze powyższe program użyty przez autora do wygenerowania "poprawnych" wyników sam najprawdopodobniej był błędny. Przykład:
7
1 4 2 6 3 5 7
4 2 7 2 6 3 3
Najdłuższy wspólny niekoniecznie spójny podciąg to np. 4, 2, 6, 3, jednak mój program który zwracał 4 wylatywał ze statusem WA, zaakceptowany został natomiast program który zwracał odpowiedź... 6 (sic!), uwzględniając wszystkie "powtórzone" elementy, czyli robiąc z tego ciąg 4, 2, 2, 6, 3, 3
Inne testy:
5
4 1 5 3 2
1 4 3 5 5
program który dostaje WA: 2
program który dostaje AC: 3
7
4 3 1 6 5 7 2
3 7 2 7 6 2 1
program który dostaje WA: 3
program który dostaje AC: 4
6
2 4 6 5 1 3
2 1 5 2 2 1
program który dostaje WA: 3
program który dostaje AC: 4
Dla nie powtórzonych liczb w ciągu oba programy zwracają takie same wyniki, czyli dla danych:
10
9 4 2 8 3 7 1 6 5 10
5 9 8 3 10 1 6 2 4 7
oba zwrócą 5, jednak wydaje mi się że większość SPOJowiczów poległa właśnie na owym niezgodnym ze specyfikacją teście, którego rozwiązaniem wydaje się nie być wcale długość najdłuższego wspólnego niekoniecznie spójnego podciągu, tylko długość przedstawionej przeze mnie "hybrydy" z powtórzeniami.
- Oczywiście istnieje prawdopodobieństwo, że mój program dostał AC przez przypadek, ale cóż - nikt nie jest doskonały