/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Program
{
new Program().run();
}
void run() {
int a = 4;
int b = 17;
int n = 3;
try {
int[] array = Generate(a, b, n);
for (int x : array)
}
System.
out.
printf("Exception: " + e.
getMessage()); }
}
int[] Generate(int a, int b, int n) {
int max = (b + 2) - (a - 2) + 1 - 4 * n;
if (n > max)
int[] result = ReservoirSampling(n, max);
// выборка неотсортирована, сортируем
// и возвращаем нужные индексы:
for (int i = 0; i < n; i++)
result[i] += a + (4 * i);
return result;
}
int[] ReservoirSampling(int n, int max) {
Random r
= new Random(); // этот экземпляр нужно сделать глобальным int[] result = new int[n];
for (int i = 0; i < n; i++)
result[i] = i;
for (int i = n; i < max; i++) {
int j = r.nextInt(i + 1);
if (j < n)
result[j] = i;
}
return result;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgUHJvZ3JhbQp7CglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nW10gYXJncykgdGhyb3dzIEV4Y2VwdGlvbiB7CgkJbmV3IFByb2dyYW0oKS5ydW4oKTsKCX0KCQoJdm9pZCBydW4oKSB7CgkJaW50IGEgPSA0OwoJCWludCBiID0gMTc7CgkJaW50IG4gPSAzOwoJCXRyeSB7CgkJICAgIGludFtdIGFycmF5ID0gR2VuZXJhdGUoYSwgYiwgbik7CiAgICAgICAgICAgIGZvciAoaW50IHggOiBhcnJheSkKCQkgICAgICAgIFN5c3RlbS5vdXQucHJpbnRmKCIlZCAiLCB4KTsKCQl9CgkJY2F0Y2ggKEV4Y2VwdGlvbiBlKSB7CiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRmKCJFeGNlcHRpb246ICIgKyBlLmdldE1lc3NhZ2UoKSk7CgkJfQoJfQoJCiAgICBpbnRbXSBHZW5lcmF0ZShpbnQgYSwgaW50IGIsIGludCBuKSB7CiAgICAgICAgaW50IG1heCA9IChiICsgMikgLSAoYSAtIDIpICsgMSAtIDQgKiBuOwogICAgICAgIGlmIChuID4gbWF4KQogICAgICAgICAgICB0aHJvdyBuZXcgSWxsZWdhbEFyZ3VtZW50RXhjZXB0aW9uKCLQl9Cw0LTQsNGH0LAg0L3QtdGA0LDQt9GA0LXRiNC40LzQsCIpOwogICAgICAgIGludFtdIHJlc3VsdCA9IFJlc2Vydm9pclNhbXBsaW5nKG4sIG1heCk7CgogICAgICAgIC8vINCy0YvQsdC+0YDQutCwINC90LXQvtGC0YHQvtGA0YLQuNGA0L7QstCw0L3QsCwg0YHQvtGA0YLQuNGA0YPQtdC8CiAgICAgICAgQXJyYXlzLnNvcnQocmVzdWx0KTsKCiAgICAgICAgLy8g0Lgg0LLQvtC30LLRgNCw0YnQsNC10Lwg0L3Rg9C20L3Ri9C1INC40L3QtNC10LrRgdGLOgogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQogICAgICAgICAgICByZXN1bHRbaV0gKz0gYSArICg0ICogaSk7CgogICAgICAgIHJldHVybiByZXN1bHQ7CiAgICB9CgogICAgaW50W10gUmVzZXJ2b2lyU2FtcGxpbmcoaW50IG4sIGludCBtYXgpIHsKICAgICAgICBSYW5kb20gciA9IG5ldyBSYW5kb20oKTsgLy8g0Y3RgtC+0YIg0Y3QutC30LXQvNC/0LvRj9GAINC90YPQttC90L4g0YHQtNC10LvQsNGC0Ywg0LPQu9C+0LHQsNC70YzQvdGL0LwKICAgICAgICBpbnRbXSByZXN1bHQgPSBuZXcgaW50W25dOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQogICAgICAgICAgICByZXN1bHRbaV0gPSBpOwoKICAgICAgICBmb3IgKGludCBpID0gbjsgaSA8IG1heDsgaSsrKSB7CiAgICAgICAgICAgIGludCBqID0gci5uZXh0SW50KGkgKyAxKTsKICAgICAgICAgICAgaWYgKGogPCBuKQogICAgICAgICAgICAgICAgcmVzdWx0W2pdID0gaTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHJlc3VsdDsKICAgIH0KfQ==