25597. 6, 8 i 343 [AL_25_03]

[bunker96]

Witam,
Czy mógłby ktoś udostępnić kilka zadań testowych do tego zadania?
http://pl.spoj.com/problems/AL_25_03/
Już 4 raz próbowałem rozwiązać to zadanie jednak za każdym razem pokazuje błędną odpowiedź.
A to kod:

#include<iostream>
#include<string>
using namespace std;
int main(){
    string liczba;
    unsigned long long int t,s,mn,x;
    cin>>t;
    while(t--){
        cin>>liczba;
        x=liczba.length();
        s=(int)liczba[x-1]-48;
        for(int i=1;i<liczba.length();i++){
            mn=1;
            for(int j=0;j<i;j++){
                mn*=7;
            }
            s+=(mn*((unsigned long long int)liczba[x-1-i]-48));
        }
        cout<<s<<endl;
        if(s==0){
            cout<<"NIE NIE NIE"<<endl;
        }
        else{
            if(s%6==0) cout<<"TAK"<<" ";
            else cout<<"NIE"<<" ";
            if(s%8==0) cout<<"TAK"<<" ";
            else cout<<"NIE"<<" ";
            if(s%343==0) cout<<"TAK"<<endl;
            else cout<<"NIE"<<endl;
        }
    }
}

[rzaba]

W treści zadania napisane jest, że wejście składa się z n-cyfrowych liczb gdzie n ≤ 100000. To oznacza, że - korzystając z unsigned long long - konwersja na system dziesiętny się nie uda gdy n jest wystarczająco duże.

[bunker96]

czyli mam zastosować większy typ? czy może nie konwertować na system dziesiętny i szukać innego sposobu?

[rzaba]

Z tego co widzę, limity czasowe w tym zadaniu są dosyć surowe, więc sądzę, że konwertując na system dziesiętny Twój kod dostałby TLE. Da się to zadanie rozwiązać w inny sposób.

[avrilq]

Poirytowany kilkoma WA, proszę o jakiś test/wskazówkę ^.^
Mój kod: -Tu Był Sobie Kod-
Z góry Wielkie Dzięki

[narbej]

Przeczytaj wskazówkę-podpowiedź nad twoim pytaniem.

PS
Pewnie chodzi o to, że n cyfr dotyczy liczby dziesiętnej a nie siódemkowej.
99 dziesiętnie - liczba 2 cyfrowa = 201 [w systemie siódemkowym]
9999999999 dziesiętnie - liczba 10 cyfrowa = 502544411643 [w systemie siódemkowym]
dowolna liczba dziesiętna n-cyfrowa [gdzie n <10000] = ?? w systemie 7
ale i tak przewiduję twoim sposobem TLE.

PS 2

  int wynik = wsp[0];
     for(int i=1;i<=st;i++)
    wynik=(7*wynik+wsp[i])%x;

prawidłowo np:

  int wynik = 0;
     for (int i = 0; i < st; i++)
     wynik = (7*wynik + wsp[i]) % x;

PS 3
Twoje testy są nie przemyślane - takie na pałę, tylko aby były. W systemie siódemkowym nie ma cyfr 7, 8 i 9.

[avrilq]

Tak, testy były wpisywane na pałę. Myślenie o 3 w nocy coś mi ostatnio nie służy. Jeszcze raz dzięki, po poprawieniu jest TLE jak pisałeś, a więc czas zmienić na bardziej wydajny sposób liczenia [AC]

[xk404]

To jeszcze ja. Liczę w sposób względnie optymalny(mam nadzieję), ale dostaję TLE. Czy istnieje sposób na zczytywanie danych szybszy niż console.readline w c#?

[fastus001]

Witam

Cały czas mam WA w zadaniu. Czy może ktoś zerknąć co jest nie tak.
Na Ideone podstawowe testy przechodzi poprawnie plus kilka co sam wymyśliłem.
Poniżej link do kodu:
tu był wcześniejszy kod

Dzięki za pomoc.

[narbej]

1. Prawdopodobnie gubi Cię nadmiar warunków, sam się w nich gubię, więc tym bardziej kompilator. W takich przypadkach należy pododawać nawiasy - kompilator nie wypisywał warringów?
   Można też zmienić tak kod, aby nie sprawdzać tych warunków, np na początku:
   jeżeli x == 1 && liczba[0] == '0' to wypisujemy i wracamy do while(t--) <-- np continue

Takia drobna kosmetyka:

2 Tablica tab jest całkowicie zbędna. Można przecież od razu:
sum0 += liczba[i] - '0';
else ....
3. cout << "TAK" << " "; =====> cout << "TAK ";
cout << "TAK" << endl; lepiej: cout << "TAK\n";

PS
Ten warunek if (x < 4) jest zbędny - jeżeli na początku sprawdzisz czy liczba ==0
sprawdzasz oczywiście: if ((liczba[x - 3] == '0' .....

PS 2
sorry, oczywiście nie tak jak wyżej, ale:
if ((liczba[x - 1] == '0' && .... && ... ) //gdy tylko będzie 1 fałsz dalej nie jest sprawdzane, np 10, 100 itd., a czy 0 sprawdziłeś na początku. Nie ma liczb 00 ani 000

[fastus001]

Rzeczywiście dało się uprościć ten kod znacznie. Dzięki za wszystkie wskazówki.
Niestety dalej WA, teraz to już nie wiem czy problem leży w warunkach czy cały algorytm sprawdzania jest zły.
Czy jest możliwość sprawdzić na jakim teście wychodzi błąd?

Poniżej poprawiony kod z WA:
Tutaj był kod [AC]

[narbej]

1. Czy 0 dzieli się bez reszty przez 6?
2. Ten warunek || (sum0 - sum1) == 0 nie jest błędem ale jest nadmiarowy i zbędny .
3. Dodaj koniecznie ios_base::sync_with_stdio(0);, bo bez tego tle.
4. Pierwszy warunek można uprościć do: if (liczba == "0") // tym razem podwójny cudzysłów.

PS
5. zamiast: if (i % 2 == 0) można: if (i & 1 == 0) lub if (i & 1) + zmiana kolejności bo i & 1 = i%2 == 1
PS 2
6. t_sum jest nadmiarowy i potrzebny jednorazowo Możesz if((sum0 + sum1) % .......)

[fastus001]

Ad.1 a czy to ma jakieś znaczenie? jak jest 0 to się ta część kodu nie wykonuje, chyba że odnosi się to do pkt.2, wtedy rzeczywiście "|| (sum0 - sum1) == 0" ta część była zbędna.
Ad.3 Cały czas miałem WA, wiec nie dodałem.
Wskazówki pomocne, jednak cały czas WA.

Edit:
W końcu zaliczone. Wielkie dzięki Narbej za porady Głupie przeoczenie z mojej strony.

[narbej]

Pytanie 1 odnosi się do podstawowego pytania "to be or not to be" czyli TAK/NIE:
if (x == 1 && liczba[0] == '0')
Czy bez reszty 0 dzieli się bez 6 bez 8 i bez 343 !?

[damman961]

witam, sędzia wyrzuca mi złą odpowiedź, pomimo że w wielu testach uzysuję poprawne odpowiedzi
mój kod: https://pastebin.com/rqG4emDY

[mariusz193]

witam, sędzia wyrzuca mi złą odpowiedź, pomimo że w wielu testach uzysuję poprawne odpowiedzi

zupełnie nie rozumiem, co znaczy, że w wielu testach uzyskujesz poprawne odpowiedzi - czy znasz takie testy dla których uzyskujesz niepoprawne ?

natomiast rozumiem, dlaczego sędzia ci daje WA - powód prosty, nie zrozumiałeś treści zadania, przeczytaj jeszcze raz dokładnie, albo dwa, trzy ... razy, aż do pełnego zrozumienia

PS. istnieje bardzo małe prawdopodobieństwo, że używając Python-a zmieścisz się w czasie - tylko dwa zaliczone rozwiązania nie są C/C++, jedno Pascal, i jedno w ASM

[damman961]

"pomimo że w wielu testach uzysuję poprawne odpowiedzi"

pisząc to miałem po prostu na myśli to, że wprowadzałem wiele liczb podzielnych przez 6,8 czy 343 i program działa bez zarzutu tzn. prawidłowo klasyfikuje to czy liczba jest pozielna przez powyższe wartości czy nie
teraz dopiero zauważyłem dlaczego dostaję WA , jednak warto dokładnie czytac polecenia
udało mi się naprawić błąd i tak jak wspomniałeś używając Pythona nie mieszczę się w czasie (ale spróbuję może to jakos ulepszyć)

[tosemja47]

Mała podpowiedź dlaczego to nie przechodzi (Błędna odpowiedź).

[tarpauwatratar]

Uzyskałem Twoim kodem AC po poprawieniu aż JEDNEGO przypadku będącego JEDNĄ liczbą, dla którego 3x zwracasz złą odpowiedź. Sądząc po testach na Ideone, przeczuwasz, o którą liczbę może chodzić

[tosemja47]

Dzięki. Zaliczone gdzieś mi to umknęło bo byłem pewien że sprawdzałem jak to jest z tym przypadkiem.