ciag

[encoreeFTW]

czesc, mam takie dwa zadania do zrobienia:

 

 

	Wykreślanka


	Limit pamięci: 32 MB

Jasio wypisał ciąg liczb całkowitych. Ciągiem dobrym nazwiemy
ciąg kolejnych liczb naturalnych 1,2,3 .. itd. Jasio chciałby wykreślić
jak najmniej liczb w taki sposób, aby pozostałe liczby utworzyły dobry ciąg. Jeśli Jasio nie może utworzyć żadnego z dobrych ciągów, to powinien wykreślić wszystkie liczby.


	Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (1<=n<=10 6 ), oznaczająca ilość liczb w ciągu Jasia. Kolejny wiersz zawiera ciąg n liczb całkowitych a1, a2, ...,an, oznaczających kolejne wartości liczb w ciągu Jasia.


	Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę
całkowitą równą minimalnej ilości liczb, które powinien wykreślić Jaś.


	Przykład

Dla danych wejściowych:


7


2 1 3 2 5 3 4

poprawną odpowiedzią jest:


3

 

2.

 

 

Edek
napisał kredą na chodniku wszystkie liczby od 1 do n w losowej
kolejności. Następnie poszedł do sklepu. Po powrocie zauważył, że
brakuje jednej liczby. Pomóż Edkowi i powiedz, której liczby brakuje!


Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 500 000), oznaczającą ilość liczb, które wypisał Edek.
Kolejny
wiersz zawiera n − 1 liczb całkowitych l1, l2, . . . , ln−1 (1 ≤ li ≤
n), gdzie li oznacza i-tą liczbę na chodniku (po powrocie Edka ze
sklepu).

Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną
liczbę całkowitą, równą wartości liczby, której brakuje na chodniku.
Przykład Dla danych wejściowych


Przykład

5
2 3 1 5

poprawnym wynikiem jest:
4

 

 

nie wiem wogole jak sie za nie zabrac, moglibyscie mi jakos pomoc je ogarnac? nie chodzi mi nawet o kod, chodzi o sposob rozwiazania

[Sopelek997]

1. Lecisz po kolei po tablicy i jeśli liczba x jest większa od następnej to ją wykreślamy (tzn. dodajemy jeden do licznika wykreslen)

2. Na szybko. Tworzysz tablicę o rozmiarze n. Lecisz po liczba po kolei i za każdą kolejną liczbą robiasz (tablica[ta liczba] = true)

potem lecisz jeszcze raz i szukasz wartości false

[encoreeFTW]

 

#include <iostream>
using namespace std;
 
int main()
{
        int a,b,c;
        cin>>a;
        int tablica [a];
        for (int i = 0; i < a; i++)
        {
                cin>>tablica [i];
        }
        for(int licznik = 0; licznik<a; licznik++)
        {
                if(tablica [licznik]>tablica [licznik+1])
                        c++;
        }
        cout<<c;
}

 

dla danych wejsciowych z przykladu i takiego kodu wywala mi:

134513896

a wczesniej wywalalo jakies bad alloc.

[iLikeGood]

@Sopelek

Do drugiego zadania tablice ? n ≤ 500 000 czyli dla n = 500 000 sama tablica zajmie około 2MB a pewnie jest jakiś limit.

Chociaż ciężko wymyślić coś innego, można np wykorzystać char który ma 1 bajt a nie 4. Ewentualnie na stringach lecieć.

Chyba, że tak jak w zdaniu 1 masz max 32 mb więc nie ma się czym martwić.

[Sopelek997]

@Sopelek

Do drugiego zadania tablice ? n ≤ 500 000 czyli dla n = 500 000 sama tablica zajmie około 2MB a pewnie jest jakiś limit.

Chociaż ciężko wymyślić coś innego, można np wykorzystać char który ma 1 bajt a nie 4. Ewentualnie na stringach lecieć.

Chyba, że tak jak w zdaniu 1 masz max 32 mb więc nie ma się czym martwić.

napisałem pierwszy lepszy pomysł, bo się spieszyłem

 

najlepsze rozwiązanie.

Sumować wszystkie liczby po kolei i odjąć tą sumę od (n*n-n)

wychodzi ta liczba

[encoreeFTW]

zrobilem takie cos, ze sumuje wszystkie wprowadzane liczby, i odejmuje to od n*n-n, ale tylko 1 wynik jest dobry, 2 proba juz wywala bledny, 3 timed out

[Krycho]

Zadne n*n-n. Pomysl logicznie sam to sie dowiesz ze jest to zle.

 

Rozwiazaniem jest suma od 1 do n odjac suma czesciowa zliczona z podanych liczb. Kodu nie dam bo jest banalny. Pseudokodo wyglada tak.

 

wczytaj ilosc liczb;
suma calkowita += ilosc liczb;
dopoki ilosc liczb > 1
  wczytaj liczbe;
  suma czesciowa += liczba;
  suma calkowita += --ilosc liczb;
wypisz suma calkowita - suma czesciowa

 

To samo sie tyczy zadania pierwszego. W takich przypadkach nie uzywa sie tablic, bo nie ma to sensu. Wszystko mozna wykonac na 2,3 zmiennych w czasie stalym. Limity pamieci nas nie obchodza bo calosc jest rozwiazana na 4-5 intach.

 

wczytaj ilosc liczb;
dopoki ilosc liczb > 0
  wczytaj liczbe;
  jesli liczba == pozycja // pozycja na starcie == 1
    pozycja++;
  w innym wypadku
    licznik++;
  ilosc liczb--;
wypisz licznik
 

[Sopelek997]

sume liczb w ciągu <1, n> można obliczyć za pomocą wzoru (n*n+n)/2 lekko się pomyliłem poprzednio

[encoreeFTW]

dzieki za pomoc, udalo sie, do zamkniecia