#include <iostream>
#include <cstring>
#include <string>
#define M 10 // M là số nút có trên bảng băm, đủ để chứa các nút nhập vào bảng băm
#define NULLKEY -1
using namespace std;
struct Hash
{
int Bucket[M];
};
void initHash(Hash &H)
{
for(int i=0;i<M;i++)
{
H.Bucket[i]=NULLKEY;
};
};
int Hashing(int k, int j)
{
if(j==0)return k%M;
return (k%M+j*j)%M;
};
void insertHash(Hash &H,int k)
{
int j=0;
int i=k%M;
if(H.Bucket[i]==NULLKEY)
{H.Bucket[i]=k;}
else
{
for( j=0;j<M;j++){
i=(k%M+j*j)%M;
if (H.Bucket[i] == -1) {
H.Bucket[i] = k;
break;
}
if(j>=10){cout<<"\nBang bam bi day, khong them duoc";return;};
};
};
};
void traverseAllHash(Hash H)
{
for(int i=0;i<M;i++)
{
if(H.Bucket[i]!=NULLKEY)
cout<<i<<" --> "<<H.Bucket[i]<<endl;
else
cout<<i<<endl;
};
};
int main()
{
Hash H;
initHash(H);
int n,x;cin>>n; // n la so luong gia tri can phai luu tru
for (int i = 1; i<=n;i++)
{
cin>>x;
cout<<"\nInsert "<<x;
insertHash(H,x); // them 1 gia tri du lieu vao bang bam
}
cout<<"\nCreated Hash:"<<endl;
traverseAllHash(H);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPHN0cmluZz4KI2RlZmluZSBNIDEwCQkvLyBNIGzDoCBz4buRIG7DunQgY8OzIHRyw6puIGLhuqNuZyBixINtLCDEkeG7pyDEkeG7gyBjaOG7qWEgY8OhYyBuw7p0IG5o4bqtcCB2w6BvIGLhuqNuZyBixINtCiNkZWZpbmUgTlVMTEtFWSAtMQp1c2luZyBuYW1lc3BhY2Ugc3RkOwpzdHJ1Y3QgSGFzaAp7CiAgICBpbnQgQnVja2V0W01dOwp9Owp2b2lkIGluaXRIYXNoKEhhc2ggJkgpCnsKICAgIGZvcihpbnQgaT0wO2k8TTtpKyspCiAgICB7CiAgICAgICAgSC5CdWNrZXRbaV09TlVMTEtFWTsKICAgIH07Cn07CmludCBIYXNoaW5nKGludCBrLCBpbnQgaikKewogICAgaWYoaj09MClyZXR1cm4gayVNOwogICAgcmV0dXJuIChrJU0raipqKSVNOwp9Owp2b2lkIGluc2VydEhhc2goSGFzaCAmSCxpbnQgaykKewogICAgaW50IGo9MDsKICAgIGludCBpPWslTTsKICAgIGlmKEguQnVja2V0W2ldPT1OVUxMS0VZKQogICAge0guQnVja2V0W2ldPWs7fQogICAgZWxzZQogICAgewogICAgZm9yKCBqPTA7ajxNO2orKyl7CiAgICAgICAgaT0oayVNK2oqaiklTTsKICAgICAgICBpZiAoSC5CdWNrZXRbaV0gPT0gLTEpIHsKICAgICAgICAgIEguQnVja2V0W2ldID0gazsKICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgICAgICBpZihqPj0xMCl7Y291dDw8IlxuQmFuZyBiYW0gYmkgZGF5LCBraG9uZyB0aGVtIGR1b2MiO3JldHVybjt9OwogICAgfTsKICAgICAgICAKICAgIH07CiAgICAKICAgIAp9Owp2b2lkIHRyYXZlcnNlQWxsSGFzaChIYXNoIEgpCnsKICAgIGZvcihpbnQgaT0wO2k8TTtpKyspCiAgICB7CiAgICAgICAgaWYoSC5CdWNrZXRbaV0hPU5VTExLRVkpCiAgICAgICAgY291dDw8aTw8IiAtLT4gIjw8SC5CdWNrZXRbaV08PGVuZGw7CiAgICAgICAgZWxzZQogICAgICAgIGNvdXQ8PGk8PGVuZGw7CiAgICB9Owp9OwoKaW50IG1haW4oKQp7CiAgICBIYXNoIEg7CiAgICBpbml0SGFzaChIKTsKCiAgICBpbnQgbix4O2Npbj4+bjsgLy8gbiBsYSBzbyBsdW9uZyBnaWEgdHJpIGNhbiBwaGFpIGx1dSB0cnUKICAgIGZvciAoaW50IGkgPSAxOyBpPD1uO2krKykKICAgIHsKICAgICAgICBjaW4+Png7CiAgICAgICAgY291dDw8IlxuSW5zZXJ0ICI8PHg7CiAgICAgICAgaW5zZXJ0SGFzaChILHgpOyAvLyB0aGVtIDEgZ2lhIHRyaSBkdSBsaWV1IHZhbyBiYW5nIGJhbQogICAgfQogICAgY291dDw8IlxuQ3JlYXRlZCBIYXNoOiI8PGVuZGw7CiAgICB0cmF2ZXJzZUFsbEhhc2goSCk7CgogICAgcmV0dXJuIDA7Cn0KCg==