Big Number

[esmitt]

Big Number or Hashtable is accepted for this judge ??
Thanks.

Esmitt Ramirez J.
-- 3dealers --

[Adrian_Kosowski]

Big Number or Hashtable is accepted for this judge ??

Guess so, since they are included in SUN JDK 1.5. Only the things that have no business in an online judge (e.g. awt) are unavailable.

Anyway, if you encounter problems it is enough to look at a compilation error to see what is missing.

[Spykaj]

np. do char[31];

Trzeba tylko samemu napisać funkcję porównującą ;]

[yxs]

Mam taki problem ponieważ w zadaniu jest bardzo duża moc zbioru n<10^6 no iwłaśnie same liczby możemy przecież wczytać do stringa albo do tablicy charów ale przecież nie zrobimy tych tabel czy stringów aż milion. W jaki sposób można wczytać tak wiele liczb? A jeśli ktoś rozwiązał te zadanie to może wie czy tzreba jak w teście zliczać również powtarzające się elementy czy też nie?

[Spykaj]

Zrobimy, tylko takie duże tablice trzeba deklarować albo globalnie, albo dynamicznie. Pamięci na pewno wystarczy.

[ronwsh]

No ok. Ja zrobiłem to w oparciu o klasę vector ale niestety przekraczam limit czasu. Przerobiłem na tablice dynamiczne już nie przekracza limitu czasu ale daje błędną odpowiedź.

#include <iostream>
using namespace std;
int main()
{
    int n, k;
    unsigned long long *a = new unsigned long long[1000000],
                        *b = new unsigned long long[1000000],
                        *wynik = new unsigned long long[1000000];
    unsigned long long tmp;
    cin >> n;
for(int i = 0; i < n; i++) {
    cin >> tmp;
    a[i] = tmp;
}
cin >> k;
for(int i = 0; i < k; i++) {
    cin >> tmp;
    b[i] = tmp;
}
for(int i = 0; i < k; i++) {
    tmp = 0;
    for(int j = 0; j < n; j++)
        if(a[j] < b[i]) tmp++;
    wynik[i] = tmp;
}
for(int i = 0; i < k; i++)
    cout << wynik[i] << endl;

return 0;
}

[Spykaj]

W tym zadaniu trzeba zastosować wyszukiwanie binarne, twój sposób jest za wolny.

[ronwsh]

aaa... no rozumiem, trzeba posortować, wyszukać binarnie liczbę i jej pozycja będzie ilością mniejszych liczb. Powinno być szybciej .

[Spykaj]

Dokładnie

[maksior15]

Mam problem bo zrobiłem to zadanko raczej tak jak trzeba tzn. sortowanie + wyszukiwanie binarne a jednak zalicza mi tylko 2 ostatnie testy, a w pierwszych trzech mam przekroczony limit czasu. Nie wiem co jest nie tak. Piszę w c++, używam gotowych algorytmów z biblioteki algorithm a zbiór A wczytuję do wektora. Jak macie jakieś spostrzeżenia i rady jak to przyspieszyć to walcie

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(0);
	unsigned int n,k;
	cin>>n;
	vector<unsigned long long>tab(n);
	for (unsigned int i=0;i<n;i++)
		cin>>tab[i];
	vector<unsigned long long>::iterator low;
    sort(tab.begin(),tab.end());

cin>>k;
unsigned long long y;
unsigned int x;
for (unsigned int i=0;i<k;i++)
{	
	cin>>y;
	low=lower_bound (tab.begin(), tab.end(), y);
	x=low- tab.begin();
	cout<<x<<"\n";
}
return 0;
}

[goosha]

zazwyczaj wszyscy mają na odwrót - w 2 ostatnich time limit.
z resztą było kilka wątków na temat tegoż zadania, szukajka nie gryzie ;D

[maksior15]

z resztą było kilka wątków na temat tegoż zadania, szukajka nie gryzie ;D

Przeczytałem je wszystkie zanim napisałem tego posta

Wiem że zakres liczb do 30 znaków nie mieści się w long longu (bodajże 19 cyfr się mieści) i wiem jak to załatwić na stringach ale chciałem sprawdzić ile testów przejdzie bez babrania się dużymi liczbami I tu ku mojemu zaskoczeniu wyskakuje mi wynik 2/5. A co jeszcze bardziej zaskakujące program przeszedł 2 ostatnie testy a na 3 pierwszych komunikat "przekroczono limit czasu". Więc tu nasuwa się pytanko wtf ???? Poniżej zamieszczam dokładne wyniki:

0 przekroczono limit czasu 1.43s : 1.00s 2684kB

1 przekroczono limit czasu 1.13s : 1.00s 2684kB

2 przekroczono limit czasu 1.40s : 1.00s 2684kB

3 zaakceptowano 0.66s : 1.00s 2684kB

4 zaakceptowano 0.57s : 1.00s 2684kB

Więc pytanko co jest nie tak z testami i moim programem (poza tym trzymaniem w long long zamiast w stringach)?

[yxs]

Czesc w moim programie jest coś dziwnego...

Numer testu Rezultat Czas : Limit Pamięć
1pkt za test

0 przekroczono limit czasu 0.55s : 1.00s 2684kB

1 przekroczono limit czasu 0.81s : 1.00s 2684kB

2 przekroczono limit czasu 0.70s : 1.00s 2684kB

3 przekroczono limit czasu 0.63s : 1.00s 3468kB

4 przekroczono limit czasu 0.48s : 1.00s 3312kB

Wynik: 0.0pkt.

W którym miejscu jest przekroczony limit czasu???

[Krev]

Mógłby ktos powiedziec czemu ten o to kod zwraca bład WA?

#include <iostream>
using namespace std;
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}
int main()
{
	long long  n,*a,k,*b;
	scanf("%lld",&n);
	a=new long long  [n];
	for(int i=0;i<n;i++)
	{scanf("%lld",&a[i]);}
	qsort(a,n,sizeof(long long),compare);
	scanf("%lld",&k);
	b= new long long [k];
	for(int i=0;i<k;i++)
	{
		scanf("%lld",&b[i]);
		long long j=0;
		for(j;j<n;j++)
		{
			if(a[j]>=b[i])
			{break;}
		}
		printf("%lld\n",j);
	}
    
system("pause");
}

program sortuje tablice a nastepnie podaje indeks pierwszej liczby wiekszej od sprawdzanej

[kokosek_sof1]

Liczby z tego zadania są tak duże, że nie zmieszczą się w long long incie.
Musisz to zrobić stringami.

[Krev]

o.0 faaajnie...
Atoi sie na cos zda?

[kokosek_sof1]

No raczej nie, bo atoi pobiera stringa i przypisuje go do jakiejś zmiennej o formacie np. long long int. A te stringi się nie zmieszczą w formacie long long int.

[Spykaj]

A tak poza tym poczytaj o wyszukiwaniu binarnym, to twój program w najlepszym razie i tak dostanie tylko Time Limit

[kokosek_sof1]

No ja akurat robię tak, jak kiedyś napisałeś - sortuję, a potem wyszukuję binarnie (z lower_bound) i i tak mam TLE w 4 i 5 teście.

[Marko911]

Witam:)

Problem jest tego typu ze TLE;( Moze ktos rzuci okiem i powie jak to przyspieszyc:

#include <iostream>
#include <string>
using namespace std;
int main ()
{
int i,j,k,m1,m2,licznik=0;
string *zl1,*zl2,l;
cin >> m1;
zl1 = new string[m1];
for(i=0;i<m1;i++)
{
cin >> l;
zl1[i]=l;
}
cin >> m2;
zl2 = new string[m2];
for(i=0;i<m2;i++)
{
cin >> l;
zl2[i]=l;
}
for(i=0;i<m2;i++)
{
for(j=0;j<m1;j++)
if(zl1[j].size() < zl2[i].size())
licznik+=1;
else if(zl1[j].size() == zl2[i].size())
for(k=0;k<zl1[j].size();k++)
if(zl1[j]<zl2[i])
{
licznik+=1;
break;
}
cout << licznik << endl;
licznik = 0;
}
system("PAUSE");
return 0;
}

P.s 2 testy przechodzi 1 i 3

#0	zaakceptowano	0.00s : 1.00s	2672kB
#1	przekroczono limit czasu	1.81s : 1.00s	2804kB
#2	zaakceptowano	0.02s : 1.00s	2672kB
#3	przekroczono limit czasu	2.95s : 1.00s	7460kB
#4	przekroczono limit czasu	2.96s : 1.00s	7772kB