1242. Zliczacz liter [JZLICZ]

[szio]

Wskazówka: co znajduje się w elemencie vectora o indeksie równym jego rozmiarowi?

[wiktorjan]

Cześć.
Mam mały problem z tym zadankiem, sprawdzałem na wielu testach, wszystko w porządku. Na ideone też jest ok. Spoj mi nie przyjmuje wyrzuca błąd kompilacji. Nie ma problemu, moge to zrobić w inny sposób, jednak jestem ciekaw, dlaczego to nie chce pyknąć, za wszystkie uwagi byłbym bardzo wdzięczny
http://ideone.com/5SJVSh

[narbej]

1. Kliknij na swoim zgłoszeniu na napis błąd kompilacji i wyświetli się powód błędu - wyjście kompilacji.
2. Użyj nowszej wersji kompilatora c++, na SPOJu jest dostępny 6.3.
3. Ewentualnie popraw to co powoduje błąd kompilacji i wtedy powinno też pyknąć na starym c++ v 4.3

PS
Zarówno na ideone.com jak i u siebie zapewne użyłeś nowszych kompilatorów (> 4.3) niż na SPOJ'u.

[wiktorjan]

Dzięki śliczne, działa, wystarczyło wybrać 6.3.
Z tym błędem kompilacji też już wcześniej próbwałem, ale nie do końca rozumiałem co mi wyskakiwało, za małą wiedze mam na ten moment.

[sensej]

Hey.
Dostaje błędną odpowiedź, chociaż sprawdzałem na różnych testach i według mnie działa poprawnie.

`#include

using namespace std;

int main()
{
int ile,dlugosc;
string zdanie;
cin>>ile;

int tab_male[26]= {};
int tab_duze[26]= {};
char male='a';
char duze='A';

for(int i=0; i<ile; i++)
{
    cin.sync();
    getline(cin, zdanie);
    dlugosc=zdanie.length();

    for(int m=97;  m<=122; m++)
    {
        for(int k=0; k<dlugosc; k++)
        {
            if(zdanie[k]==m) tab_male[m-97]+=1;
        }
    }

    for(int m=65;  m<=90; m++)
    {
        for(int k=0; k<dlugosc; k++)
        {
            if(zdanie[k]==m) tab_duze[m-65]+=1;
        }
    }
}

for(int i=0; i<26; i++)
{
    if(tab_male[i]==0) ;
    else cout<<male<<" "<<tab_male[i]<<endl;
    male+=1;
}

for(int i=0; i<26; i++)
{
    if(tab_duze[i]==0) ;
    else cout<<duze<<" "<<tab_duze[i]<<endl;
    duze+=1;
}
return 0;

}
`

[narbej]

Dostaje błędną odpowiedź, chociaż sprawdzałem na różnych testach i według mnie działa poprawnie.

Według mnie nie, a jakie było pytanie? http://discuss.spoj.com/t/czy-spoj-forum-pomaga-w-pisaniu-dobrych-popdowiedzi/23397

[michal911]

Ideone.com

Przechodzi wszystkie moje testy, ale dostaje WA. Nie wiem gdzie mogłem zrobić błąd. Jakieś wskazówki?

[mariusz193]

ach te (pozorne) oszczędności paru bajtów, a potem płacz na forum

sprawdź wynik testu dla:

4
zzzzzzz
ZZZZZZZ
aaaaaaa
AAAAAAA

nie jest to jedyny problem - bo twój program działa niezupełnie zgodnie ze specyfikacją podaną w zadaniu

[kurok]

Cześć, mogę zastąpić bibliotekę conio.h jakąś inną, żeby wykryć “enter”, bo z tą biblioteką wywala mi błąd :(?

Ideone.com

[narbej]

Po prostu jej nie używaj. Zamiast getch() użyj getchar() i pamiętaj, że w unix, a więc na spoju i ideone enter = 10, a nie 13.
getchar() jest w bibliotece standartowej [cstdio ~= stdio.h]

[kurok]

Ideone Skorzystałem z rady, ale na SPOJu wyskakuje mi błędna odpowiedź, a na Ideone przekroczenie limitu czasu, mimo, że na komputerze kompiluje się w ułamku sekundy Czy lista to w tym wypadku zły pojemnik na dane? Powinienem zmienić koncepcję?

[tarpauwatratar]

(…) na SPOJu wyskakuje mi błędna odpowiedź, a na Ideone przekroczenie limitu czasu, mimo, że na komputerze kompiluje się w ułamku sekundy

Jeżeli zdanie to zinterpretuję jako ukrytą implikację typu “jeżeli u mnie kompiluje się (w ułamku sekundy) to nie może być, że na SPOJu mam WA i nie może być, że na Ideone mam TLE” to na prawdę nie rozumiem o co Ci chodzi.

Kompilować się kompiluje. I nie działa. Tyle. Na pocieszenie: to dotyczy ponad 90% kodów, jakie kiedykolwiek zostały stworzone

Czy lista to w tym wypadku zły pojemnik na dane

Formalnie możesz używać nawet drzewa czerwono-czarnego, mapy itd. SPOJ puści największą bzdurę, jak już się przekonałeś dotyczy to także listy

Powinienem zmienić koncepcję?

Tak. Nie wiem skąd pomysł na użycie listy chyba, że po prostu w celu edukacyjnym i faktycznie wiesz co robisz.

[kurok]

Formalnie możesz używać nawet drzewa czerwono-czarnego, mapy itd. SPOJ puści największą bzdurę, jak już się przekonałeś dotyczy to także listy

(…)Nie wiem skąd pomysł na użycie listy chyba, że po prostu w celu edukacyjnym i faktycznie wiesz co robisz.

Czemu lista jest złym pomysłem w tym przypadku? Pytam poważnie i prosiłbym o uzasadnienie, bo taka lista wydawała mi się lepszym pomysłem niż stworzenie dużej tablicy i marnowanie pamięci. Jeśli nie lista, to w takim razie jaki inny pojemnik na dane?
Nie bardzo też rozumiem mechanizmu działania Ideone. Jeśli limit czasu to 5s, to czy przy tak małym programie i jednym teście jest możliwe, abym przekroczył ten czas tylko ze względu na użycie listy jako pojemnika na dane?

[tarpauwatratar]

Czemu lista jest złym pomysłem w tym przypadku? Pytam poważnie i prosiłbym o uzasadnienie, bo taka lista wydawała mi się lepszym pomysłem niż stworzenie dużej tablicy i marnowanie pamięci. Jeśli nie lista, to w takim razie jaki inny pojemnik na dane?

Jeżeli Twoim celem jest oszczędzenie pamięci to oczywiście zmienia postać rzeczy i może nawet lista jest dobrym rozwiązaniem (nie chce mi się nad tym myśleć). Nad czym myśleć? Nie wiem jak Twoje rozumowanie ma się do wady listy, że każdy element listy ciągnie więcej pamięci niż każdy element tablicy Mam też pewną obawę (z tego co widzę w kodzie całkiem zasadną), że w swoim rozwiązaniu używasz w cholerę pamięci w porównaniu ze zwykłą tablicą około 50-elementową Pomijam już kwestię sortowania, które nie jest potrzebne w przypadku tablicy, a kosztuje czasowo dość wiele.

Powiem tak - w celach edukacyjnych można wiele. Sam pamiętam zadanie, nad którym nie chciało mi się myśleć więc kilka z możliwych rozwiązań zabrałem z neta a resztę liczyłem na bieżąco w trakcie wykonywania programu Nota bene kultowa technika w konkursach algorytmicznych, której nazwę możesz sobie wygooglować, a która jest kluczem do rozwiązania niektórych zadań na SPOJu, a rozwiązanie innych ułatwia.

W celach dydaktycznych możesz spróbować ogarnąć to zadanie na mapach/setach. Wybór właściwego kontenera z wymienionych zostawiam Tobie.

Nie bardzo też rozumiem mechanizmu działania Ideone. Jeśli limit czasu to 5s, to czy przy tak małym programie i jednym teście jest możliwe, abym przekroczył ten czas tylko ze względu na użycie listy jako pojemnika na dane?

Można stworzyć nawet mniejszy o tym samym działaniu. Program dostaje TLE ponieważ najpewniej nie wychodzisz z pętli i wykonujesz go w nieskończoność.

[narbej]

Czemu lista jest złym pomysłem w tym przypadku? Pytam poważnie i prosiłbym o uzasadnienie, bo taka lista wydawała mi się lepszym pomysłem niż stworzenie dużej tablicy i marnowanie pamięci.

Dlaczego uważasz, że lista jest nie marnowaniem pamięci? Przecież w liście dodatkowo trzeba gdzieś pamiętać wskaźniki [co najmniej jeden do następnego elementu, plus ewentualnie do poprzednika]. Jak myślisz, gdzie one są pamiętane? W powietrzu, czy w marnowanej pamięci?. Jesyeś początkującym adeptem, więc na razie nie martw się marnowaniem pamięci. Najpierw zrób działający program, a potem go optymalizuj, pod względem zużycia pamięci, prędkości itd. W tym zadaniu najlepsza i najprostsza metoda, to umiejętne użycie tablicy [małej].

PS
Na ideone podałeś zły test, typu:
3
dane [enter]
dane [enter]
dane [EOF]
więc zabrakło ostatniego entera i program czeka w nieskończoność w pętli.
Popraw[ny] test do tego zadania to:
3
dane [enter]
dane [enter]
dane [enter]
[EOF]

[kurok]

Dlaczego uważasz, że lista jest nie marnowaniem pamięci?(…)

Chodziło mi o “marnotrawienie” pamięci. Intuicja podpowiadała mi, że bardziej elegancko będzie zużyć pamięć na wskaźniki, niż na deklarowanie za dużej tablicy na zapas, jak widać nie do końca dobrze, ale chciałem też wykorzystać w praktyce jakiś pojemnik na dane, inny niż tablica, bo do tej pory ich nie używałem.

Teraz Ideone pokazuje mi inny wynik testu, niż jakbym wpisał go ręcznie: Ideone pokazuje poprawny wynik, gdy fragment kodu jest zakomentowany, natomiast w konsoli wyświetla mi się taki sam wynik, gdy usunę komentarz.
Kolejne pytanie, być może trywialne, ale czy na końcu danych wejściowych w zadaniu też jest [enter]?

[tarpauwatratar]

(…) chciałem też wykorzystać w praktyce jakiś pojemnik na dane, inny niż tablica, bo do tej pory ich nie używałem

No i ok.

Intuicja podpowiadała mi, że bardziej elegancko będzie zużyć pamięć na wskaźniki, niż na deklarowanie za dużej tablicy na zapas, jak widać nie do końca dobrze,

Bardzo niedobrze. Po pierwsze wskaźniki jako twór bardziej skomplikowany są mniej eleganckie - najlepsze rozwiązania to najprostsze rozwiązania. Po co komplikować? Po drugie osiągnąłeś efekt przeciwny od zamierzonego - zmarnowałeś w cholerę pamięci (raz, że uroki listy a dwa, że Twoja lista musi zapamiętać każdy znak), a przy tym czasowo Twój algorytm jest mizerny.

Poza tym wciąż nie pojmuję, po co chcesz używać za dużej tablicy? Ja użyłem tablicy zawierającej 130 elementów a więc za dużej z lenistwa. Chcesz zoptymalizować pamięć? Użyj tablicy mającej jakoś 2*24 czy ileś tam elementów (policz).

Teraz Ideone pokazuje mi inny wynik testu, niż jakbym wpisał go ręcznie: Ideone pokazuje poprawny wynik, gdy fragment kodu jest zakomentowany, natomiast w konsoli wyświetla mi się taki sam wynik, gdy usunę komentarz.

Musiałbym widzieć co faktycznie masz w konsoli i czy faktycznie Ci się to skompilowało. Inne działanie tego samego kodu jest możliwe, ale raczej rzadkie - uroki różnych kompilatorów.

Kolejne pytanie, być może trywialne, ale czy na końcu danych wejściowych w zadaniu też jest [enter]?

Entery i spacje gdzieś tam są mało trywialną sprawą i potrafią napsuć krwi. Ja robię tak: najpierw wysyłam rozwiązanie dla przypadku gdy ich nie ma, a jeżeli dostaje ono WA - wysyłam rozwiązanie dla przypadku, gdy one są

[kurok]

Mam dokładnie ten sam wynik, tylko bez ostatniej litery i ilości jej wystąpień, w tym wypadku “t”, gdy usunę komentarz, Ideone wyświetla 2x ostatnią literkę.

[narbej]

gdy usunę komentarz, Ideone wyświetla 2x ostatnią literkę.

Przecież w pętli zmniejszasz wielkość listy [.pop_front()] i niezależnie jaką miała ona wielkość na początku, to w końcu zmniejszy się do size() = 1.

Powinieneś jeszcze:

1. dokładnie przeczytać treść zadania, a potem porównać swój output [ten niby poprawny, bez podwójnego t] z outputem autorskim.
2. jeżeli nie widzisz różnicy, to albo goto 1 albo może najwyższy czas goto [udać się] do okulisty [wiemm bo jestem okularnikiem ].

PS

Kolejne pytanie, być może trywialne, ale czy na końcu danych wejściowych w zadaniu też jest [enter]?

Prawdopodobnie tak, jest, ale twoim obowiązkiem jako programista-koder jest takie napisanie i przetestowanie swojego kodu, żeby działał niezawodnie i dla takiego i dla takiego przypadku, tym bardziej, że może mogłoby się zdarzyć, że w części testów będzie tak [enter na końcu danych], a w jednym/kilku EOF i wtedy metoda @tarpauwatratar’a nie zadziała.

[kurok]

Dzięki wielkie za wyczerpujące odpowiedzi!

2. jeżeli nie widzisz różnicy, to albo goto 1 albo może najwyższy czas goto [udać się] do okulisty [wiemm bo jestem okularnikiem ].

Też jestem okularnikiem i myślę, że powinienem się jednak udać do głowy - po rozum. No nic, ważne, że już wiem co mam robić