[Algorytmy] Zadanie Ciąg

Suchy2137
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 16 paź 2020, o 16:10
Płeć: Mężczyzna
wiek: 17

[Algorytmy] Zadanie Ciąg

Post autor: Suchy2137 »

Mam takie zadanie

Kod: Zaznacz cały

https://szkopul.edu.pl/problemset/problem/JcJfB1VlW4cFdrCI6yDcQig0/site/?key=statement
, napisałem do OKI i podali mi taki kod:

Kod: Zaznacz cały

#include <iostream>
#include <vector>
/*
Liczymy ciag dopoki znane, pamietajc cale przedzial
*/
using namespace std;
const int N = 1000*100;
int Ost[N];
int main(){
    long long int n,znane;
    long long int j,i,k,ktory,wsk;
    bool koniec_petli = false;
    cin >> n;
    if (n==1) {
       cout << "1\n";
       return 0;
    }
    if ( n<=3 ) {
       cout << "2\n";
       return 0;
    }
    if ( n<=5 ) {
       cout << "3\n";
       return 0;
    }
    if ( n<=8 ) {
       cout << "4\n";
       return 0;
    }
    if ( n<=11 ) {
       cout << "5\n";
       return 0;
    }
//ost - ostatni element który wystepuje index razy
    Ost[1] = 1;
    Ost[2] = 3; //3 jest ostatnia ktora wystepuje 2 razy
    //ost[3] = 5
    //ost[4] = 8
    //ost[5] == 11
    k = 2;      //index dla ost
    wsk = 3;    //index dla ost
    znane = 11;
    ktory = 5;
/*
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8  8  8  8  9  9  9  9  9  10 10
1 wyraz który występuje 1 raz
2 wyrazy które wyystępują 2 razy (2 2 oraz 3 3)
2 wyrazy które wyystępują 3 razy (4 4 4 oraz 5 5 5)
3 wyrazy które wyystępują 4 razy
*/
    while(znane < n) {
        Ost[wsk] = Ost[wsk-1]+k;
        for(i=Ost[wsk-1]+1; i<=Ost[wsk]; i++){
            if (znane + i*wsk > n) {
			   koniec_petli = true;
    	       break;
            }
            znane += i*wsk;
            ktory += wsk;
        }
        if (koniec_petli == true) {
  	       break;
        }
        wsk++;
        if(wsk > Ost[k]) k++;
    }
    while(znane < n){
        znane += i;
        ktory++;
    }
    cout << ktory << "\n";
    return 0;
}
ALe nie przechodzi wszystkich testów, czy ktoś mógłby mi pomóc ?
Ostatnio zmieniony 18 paź 2020, o 10:16 przez Afish, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Ponury123
Użytkownik
Użytkownik
Posty: 128
Rejestracja: 5 lip 2015, o 14:48
Płeć: Mężczyzna
Lokalizacja: nie wiem
Podziękował: 11 razy
Pomógł: 24 razy

Re: [Algorytmika]Zadanie Ciąg

Post autor: Ponury123 »

Może dlatego, że dla wartości \(\displaystyle{ n \in {1,2,..,11}}\) zwracasz String, a nie wartość liczbową.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

Re: [Algorytmy] Zadanie Ciąg

Post autor: Afish »

Dlaczego nie przechodzi? Zła odpowiedź? Przekroczenie czasu? Przekroczenie pamięci?
Suchy2137
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 16 paź 2020, o 16:10
Płeć: Mężczyzna
wiek: 17

Re: [Algorytmika]Zadanie Ciąg

Post autor: Suchy2137 »

Ponury123 pisze: 17 paź 2020, o 17:58 Może dlatego, że dla wartości \(\displaystyle{ n \in {1,2,..,11}}\) zwracasz String, a nie wartość liczbową.
Dla sprawdzarki to bez różnicy

trzeba było dodać jeszcze jeden warunek bo poprzedni kod niepotrzebnie iterował po mniejszych "wyrazach",

Kod: Zaznacz cały

#include <bits/stdc++.h>
using namespace std;
const int N = 30000;
long long Ost[N];
long long int n, znane;
long long int i, k, ktory, wsk;
long long beg, en, mid, pos;
bool koniec_petli;
long long suma(long long a, long long b)
{
    return b*(b+1)/2 - (a-1)*a/2;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    if (n==1) {
       cout << "1\n";
       return 0;
    }
    if ( n<=3 ) {
       cout << "2\n";
       return 0;
    }
    if ( n<=5 ) {
       cout << "3\n";
       return 0;
    }
    if ( n<=8 ) {
       cout << "4\n";
       return 0;
    }
    if ( n<=11 ) {
       cout << "5\n";
       return 0;
    }
    Ost[1] = 1;
    Ost[2] = 3;
    k = 2;
    wsk = 3;
    znane = 11;
    ktory = 5;
    while(znane < n)
    {
        Ost[wsk] = Ost[wsk-1]+k;
        if(znane + suma(Ost[wsk-1]+1, Ost[wsk])*wsk <= n)  //jesli n nie jest w tym "wyrazie" to przechodzimy dalej
        {
            znane += suma(Ost[wsk-1]+1, Ost[wsk])*wsk;
            ktory += (Ost[wsk]-Ost[wsk-1])*wsk;
        }
        else
        {
            for(i=Ost[wsk-1]+1; i<=Ost[wsk]; i++){
            if (znane + i*wsk > n) {
               koniec_petli = true;
               break;
            }
            znane += i*wsk;
            ktory += wsk;
        }
        }
        if (koniec_petli)
           break;
        wsk++;
        if(wsk > Ost[k])
           k++;
    }
    while(znane < n)
    {
        znane += i;
        ktory++;
    }
    cout << ktory << "\n";
}
ODPOWIEDZ