Zadanie żarówki c++ ze szkopuł

0

Witam,
Rozwiązuję zadanie żarówki ze strony szkopuł .
Zadanie Żarówki - Treść zadania - SZKOpuł

Żarówki

Limit pamięci: 64 MB

W pokoju znajduje się n żarówek. Początkowo wszystkie żarówki są zgaszone. Z każdą żarówką połączony jest jeden wyłącznik, którego naciśnięcie powoduje zmianę stanu żarówki (zaświecenie zgaszonej lub zgaśnięcie zapalonej). Miecio postanowił pobawić się wyłącznikami i k razy dokonał naciśnięcia któregoś z wyłączników. Ile żarówek jest teraz zapalonych?

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite oddzielone spacją, n i k ( $1 \le n \le 1000$ , $1 \le k \le 1 000 000$ ). W drugiej linii znajduje się k liczb całkowitych $a_1, ... , a_k$ ( $1 \le a_i \le n$ ) poodzielanych spacjami. Liczby te oznaczają numery wyłączników naciskanych przez Miecia.

Wyjście

Program powinien wypisać jedną liczbę oznaczającą liczbę zapalonych żarówek po zakończeniu zabawy Miecia.

Przykład

Dla danych wejściowych:
3 8
1 1 2 1 3 2 2 1
poprawną odpowiedzią jest:
2

Napisałam program, jednak przekracza limit czasowy.
Czy ktoś mógłby mi powiedzieć, jak zmienić kod, by działał szybciej?

Oto kod:

#include <bits/stdc++.h>

using namespace std;

int main()
{
int n;
int k;
cin>>n;
cin>>k;
int zarowki;
int zapalone;
int tab[k];

for(int i=0; i<k;i++)
{
    cin>>tab[i];
}
int podstawa=1
for(int g=0;g<k;g++){
for(int t=0; t<k;t++)
{
    if(tab[t]==podstawa)
    {
       zarowki++;
    } }
    if(zarowki%2!=0)
    {
        zapalone++;}
    zarowki=0;
    podstawa++;
    }
cout<<zapalone;

  return 0;
}

(Jestem początkująca, więc prosiłabym o dokładne wytłumaczenie)

1

Dla każdego numeru przycisku sprawdzasz, czy na wejściu znajdują się jakieś wywołania go. Po czym zmieniasz odpowiednio liczbę elementów w zależności od ilości wywołań.

Rozwiązanie to nie jest zbyt optymalne, bo wymaga przeszukiwania całego wejścia dla każdego rodzaju przycisku. Przy większej ilości danych wymaga to tysięcy cykli pętli.

Ja bym zrobił to tak: dla każdej żarówki tworzysz element boolean (bool), w sensie tworzysz tablicę o długości jaka jest podana w wejściu.

bool zarowki[n];

//Zakresowa pętla for
for (auto& i : zarowki) {
   //Początkowy stan 
   i = false;
}

Następnie każdy z numerów będzie wykonywał zmianę stanu żarówki o odpowiednim numerze.

for(auto& i : tab) {
   //-1: korekcja przesunięcia indeksów tablicy.
   if (zarowka[i-1] == false)
      zarowka [i-1] = true;
   else
      zarowka[i-1] = false;
}

Po tym po prostu zsumować liczbę żarówek które są na true i wypisać.

Tutaj każdy element wejścia jest obsługiwany tylko raz, a dzięki referencjom w pętlach (to takie coś, że zamiast kopiować wartość działamy na oryginalnej zmiennej "&") oszczędzasz czas na kopiowaniu i alokowaniu.

0

Napisałam drugi kod:

#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
int k;
cin>>n;
cin>>k;
bool zarowki [n];
int zapalone;
int tab[k];

for(int i=0; i<k;i++)
{
    cin>>tab[i];
}
for(auto& i:zarowki)
{
    i=false;
}

for(auto& i:tab)
{
    if(zarowki[i]==false)
    {
        zarowki[i]=true;
        zapalone++;
    }
    else{zarowki[i]=false;
    zapalone--;}
}

cout<<zapalone;
return 0;
}

ale na stronie pokazuje błędne wyniki. Co muszę poprawić?

0

Dopiero wczoraj założyłam konto i nie wiem jak się tu formatuje.
A błędy wyglądają następująco:

1 WRONG: line 1: expected "1", got "135162698"
2 WRONG: line 1: expected "3", got "135162700"
3 WRONG: line 1: expected "0", got "135162697"
4 WRONG: line 1: expected "48", got "135162743"
5 WRONG: line 1: expected "486", got "135163181"

0

Dobra rada. main powinno być głupie jak but.
To co najważniejsze należy umieszczać w osobnej funkcji. Dzięki temu kod jest łatwiejszy w czytaniu i można pisać testy.

Retoryczne pytanie: Jaka jest wartość początkowa: ~~bool zarowki [n];~~int zapalone;?

0

https://godbolt.org/z/WW9vvPPYr

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
#include <vector>

using DataIter = std::istream_iterator<int>;

int countLightBulbs(int n, int k, DataIter iter)
{
    std::array<bool, 1000> trunOn {};
    while (k--) {
        trunOn[*iter++ - 1] ^= true;
    }
    return std::count(trunOn.begin(), trunOn.begin() + n, true);
}

int countLightBulbs_v2(int n, int k, DataIter iter)
{
    std::vector<char> trunOn(n);
    while (k--) {
        trunOn[*iter++ - 1] ^= true;
    }
    return std::count(trunOn.begin(), trunOn.end(), true);
}

void setupIO()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

int main()
{
    setupIO();

    int n, k;
    std::cin >> n >> k;
    std::cout << countLightBulbs(n, k, DataIter { std::cin }) << '\n';

    return 0;
}

0

Milena Robak napisał(a):

Dopiero wczoraj założyłam konto i nie wiem jak się tu formatuje.
A błędy wyglądają następująco:

1 WRONG: line 1: expected "1", got "135162698"
2 WRONG: line 1: expected "3", got "135162700"
3 WRONG: line 1: expected "0", got "135162697"
4 WRONG: line 1: expected "48", got "135162743"
5 WRONG: line 1: expected "486", got "135163181"

Spróbuj skopiować to do jakiegoś IDE na komputerze to zobaczysz jakie dane konkretnie wypisuje przy jakich danych wejściowych. Być może zadanie oczekuje jakiegoś specjalnego formatowania wyjścia. Ale przede wszystkim skompiluj i uruchom jako normalny program.
Trzeba będzie wtedy jednak zaincludować inną bibliotekę ("iostream" zamiast "bits/stdc++.h") bo "normalne" kompilatory tego nie obsługują.
Jeżeli nie chcesz pobierać żadnego oprogramowania (dla początkującego poleciłbym np. dev C++) to zawsze są jeszcze internetowe narzędzia pozwalające przetestować taki kod (np. ideone.com).

0

Wystarczy dobrze ustawiony kompilator: https://godbolt.org/z/1q543GxvP

<source>: In function 'int main()':
<source>:26:21: error: 'zapalone' may be used uninitialized [-Werror=maybe-uninitialized]
   26 |             zapalone--;
      |             ~~~~~~~~^~
<source>:10:9: note: 'zapalone' was declared here
   10 |     int zapalone;
      |         ^~~~~~~~
cc1plus: all warnings being treated as errors

a potem jeszcze naprawić buffer overflow.

0

Milena Robak napisał(a):

Napisałam drugi kod:
[...]
ale na stronie pokazuje błędne wyniki. Co muszę poprawić?

To nie jest kwestia tego, że inkrementujesz zapalone przy każdym włączeniu światła?
Dla wejścia:
1 10 1 1 1 1 1 1 1 1 1 1
Dostaniesz odpowiedź 5, zamiast 0 ?
W efekcie jak 10 razy przełączysz nr 1, to dostaniesz 5 zapalonych, mimo że zapalonych będzie 0?

No i tak jak wyżej wspomniał Marek brakuje int zapalone = 0

edit:
Mój błąd nie zauważyłem -- w else

0

Straszne zamieszanie się tu zrobiło. Marek ma racje. Problemy są dwa.

zapalone nie ma ustawionej wartości początkowej. Jest tam "losowa" wartość. Używanie jej prowadzi do nieoczekiwanych wyników.
tablica zarowki jest za mała (edit: albo numery przełączników trzeba dopasować). n jest liczbą przełączników ale miejsca(indeksy) w tablicy liczy się od zera. Dlatego przełącznik numer n nie mieści się w tablicy.

Po poprawieniu tych błędów kod będzie działał jak należy. Jednak nie znaczy to że jest dobry, bo tu Marek też ma racje. Sam jestem amatorem więc tu się zatrzymam.

0

int k;
cin>>k;
int tab[k];

// or

int n;
cin>>n;
bool zarowki [n];

powyższy sposób deklarowania tablicy jest niepoprawny
Rozmiar tablicy musi być znany w momencie kompilacji programu.
korzystaj z dynamicznej alokacji pamięci new[] i delete[]
https://cpp0x.pl/kursy/Kurs-C++/Poziom-5/Zarzadzanie-pamiecia-new-delete/581
a najlepiej z kontenera std::vector
https://cpp0x.pl/kursy/Kurs-C++/Poziom-5/Kontener-std-vector/588
lub z innych źródeł