Przekroczenie limitu czasowego, nieskończony ciąg

Question

Program przekracza limit czasowy, nie wiem co można tu jeszcze skrócić :/ 

//#include <cstdio>
#include <iostream>

using namespace std;

int T[65536];
int d;
unsigned short N;
    //int T[65536]={3,14,7,6};
//int T[65536]={4096,2212,2213,3241};

//int T[65536]={2147483647,2147483646,2147483644,2147483645};

int main()
{

    ios_base::sync_with_stdio(0);
//    N=4;

    cin>>N;
    for (int j=0; j<N; j++)
    {
        cin>>T[j];
    }

    for (int j=0; j<N;j++)
    {
        d=0;
        T[j]--;
        while (T[j]>0)
        {
            d++;
            T[j]=T[j]-d;
        }
        if (T[j]==0) cout <<"1 ";
            else cout <<"0 ";
    }
}

Rozpatrzmy nieskończony ciąg cyfr złożony z rosnących potęg 10 zapisanych jedna po drugiej. Początek takiego ciągu będzie wyglądał następująco: 110100100010000... Twoim zadaniem jest stwierdić jaka cyfra znajduje się na określonej pozycji w tym ciągu.

Wejście:

W pierwszej linii wejścia znajduję się liczba naturalna N < 65536. Kolejne N linii zawierają liczby naturalne i < 2^31 – numer pozycji w ciągu.

Wyjście:

Wyjściem powinno być N cyfr 0 lub 1 pooddzielanych spacją. i-ta cyfra powinna odpowiadać i-tej cyfrze w ciągu z i-tej pozycji wejścia.

Przykład:

Wejście:

4
3
14
7
6

Wyjście:

0 0 1 0

EDIT 

Po zmianie kodu na wzór wyskakuje błędny wyniki :( oto zmieniony  kod, ktoś ma pomysł gdzie może być błąd? (standardowo dla wszystkich sprawdzanych przykładów wychodzi tak jak powinno) 

#include <iostream>
#include <math.h>

using namespace std;

int jaka_liczba (int a)
{
    double pd=0;
    int d=0;
    double y=0;
    d=1-(4*(-2*(a-1)));
    pd=sqrt(d);
    if ((int) pd!=pd) return 0;
    else
    {
        y=(-1+pd)/2;
        if ((int)y==y) return 1;
        else return 0;
    }

}
int x=0;
int n=0;
int main()
{
   cin>>x;
   //x=100;
   for(int i=0;i<x;i++)
   {
        cin>>n;
        cout<<jaka_liczba(n)<<" ";
   }


return 0;}

 

Comments

1

10

100

1000

10000

100000

1000000

Problem naleśnikowy (the number of pieces created when slicing the pancake with the nip). Ogólnie jest wzór na to, na co pewnie i tak byś wpadł, gdybyś to rozpisał. ((n(n+1))/2)+1. Skorzystaj z niego.

---

czym jest w tym wzorze n?

---

Konkretnie w tym ilością części naleśników. Miejscem jedynki, licząc od 0.

---

Dzięki, wzór super, zmieniłam kod ale tym razem w sprawdzarce zwraca złą odpowiedź, do pytania dokleiłam poprawioną wersję kodu.

---

#include <iostream>

unsigned long long positionN_thOne(unsigned long long which)
{
    return ((which*(which+1)/2)+1);
}

bool isOne(unsigned long position)
{
    if(position == 1)
    {
        return true;
    }
    for(unsigned long long i{1}; position >= positionN_thOne(i); ++i)
    {
        if(positionN_thOne(i) == position)
            return true;
    }
    return false;
}

int main()
{
    std::cout<<isOne(7);
}

 

---

trochę nie rozumiem o co chodzi w twoim kodzie :/

---

Jak napiszesz czego nie rozumiesz, to łatwiej będzie mi się ustosunkować.

---

nie spotkałam się nigdy z notacją z "for(unsigned long long i{1}; position >= positionN_thOne(i); ++i)" konkretnie mam na myśli to "i{1}" co konkretnie tu się dzieje?

---

for(unsigned long long i{1}; position >= positionN_thOne(i); ++i) jest równoważne(na potrzeby tej dyskusji) z for(unsigned long long i = 1; position >= positionN_thOne(i); ++i)

Jeżeli chcesz doczytać https://cppstyle.wordpress.com/narrowing-conversions-in-c-11/ słowo klucz to narrowing.

---

Okej ale wrzuciłam do sprawdzarki twój kod i przekracza limit czasowy

---

Jestem w lekkim szoku. 

bool isOneSecond(unsigned long position)
{
    double temp = sqrt(1+8*position);
    if(temp == static_cast<int>(temp))
      return true;
    return false;
}

O ile wszystko dobrze przekształciłem. 

---

bool isOneSecond(unsigned long long int position)
{
    double temp = sqrt(1+(8*(position-1)));

    if(temp == static_cast<int>(temp))
    return true;
    return false;
}

Po drobnej korekcie  zadziałało, dzięki! 

---

Ahhh no tak, oczywiście Twój wzór jest poprawniejszy. Rozpisałem go, zaczynając od 10, nie od 1.