As an experiment the Educational Codeforces Round 33 will be rated for Div. 2. ×

By MikeMirzayanov, history, 2 years ago, translation, In English,

Генераторы — это такие вспомогательные программы в задаче по программированию, которые выводят тесты. Далеко не всегда ручные тесты в задаче достаточно маленькие, чтобы обойтись только ими. В этом случае на помощь и приходят генераторы. Если вы пишете генератор на С++, то использование testlib.h — хороший выбор.

Виды генераторов

Есть два вида генераторов: обычные и мультигенераторы.

  1. Первые за один свой запуск выводят ровно один тест. Обычно, чтобы сгенерировать несколько тестов, такой генератор надо запустить несколько раз с разными параметрами командной строки. Такие генераторы выводят тест в стандартный поток вывода (на экран).
  2. Мультигенераторы за один запуск выводят сразу много тестов. Такие генераторы выводят тесты в файлы (один файл — один тест).

Пример простого обычного генератора на testlib.h

Выводит пару чисел от 1 до n, где n — переданный параметр запуска генератора.

#include "testlib.h"
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);
    int n = atoi(argv[1]);
    cout << rnd.next(1, n) << " ";
    cout << rnd.next(1, n) << endl;
}

Зачем testlib.h?

При невнимательном взгляде кажется, что testlib.h почти не нужен для написания генератора. На самом деле это неправда. Почти в каждом генераторе нужна возможность получать случайные значения, и есть большое искушение использовать rand(). Не делайте этого. Основной принцип написания генератора: генератор должен выводить один и тот же тест при компиляции любым компилятором на любой платформе, если он запущен одинаковым способом. При использовании rand() или классов C++11 вроде mt19937/uniform_int_distribution ваша программа будет выводить разные тесты после компиляции разными компиляторами.

Генератор случайных значений в testlib.h гарантирует, что будет сгенерировано одно и то же, независимо от генератора и платформы. Кроме того, в testlib.h есть разные удобности для генерации тестов, например, rnd.next("[a-z]{1,10}") вернет случайное слово длины от 1 до 10 из букв от a до z.

Что есть у testlib.h?

Чтобы инициализировать testlib-генератор, первая строка вашего генератора должна иметь вид registerGen(argc, argv, 1); (где 1 — это версия используемого генератора случайных чисел). После этого можно будет пользоваться объектом rnd, который будет проинициализирован хешем от всех аргументов командной строки. Таким образом, результат вывода g 100 и g.exe "100" будет одинаков, а у g 100 0 будет отличаться.

Объект rnd имеет тип random_t, то есть вы можете создать и свой генератор, но обычно это не нужно.

У объекта rnd есть много полезных членов-функций. Вот примеры:

Вызов Что делает
rnd.next(4) равновероятное целое случайное число от 0 до 3 включительно
rnd.next(4, 100) равновероятное целое случайное число от 4 до 100 включительно
rnd.next(10.0) равновероятное вещественное случайное число в полуинтервале [0,10)
rnd.next("one|two|three") равновероятное случайное одно слово из трех one, two и three
rnd.next("[1-9][0-9]{99}") равновероятное случайное 100-значное число в виде строки
rnd.wnext(4,t) wnext — это способ получения неравновероятного распределения (со смещенным матожиданием), параметр t обозначает количество вызовов операции "максимум" для аналогичных вызовов next, например rnd.wnext(3, 1) эквивалентен max(rnd.next(3), rnd.next(3)), а rnd.wnext(4, 2) эквивалентен max(rnd.next(4), max(rnd.next(4), rnd.next(4))). Если t < 0, то  - t будет найден минимум. Если t = 0, то wnext эквивалентен next.
rnd.any(container) вернет случайный элемент контейнера container (с произвольным доступом по итератору), например, работает для std::vector и std::string

Кроме того, не надо использовать std::random_shuffle, используйте shuffle из testlib. Он так же принимает два итератора, но работает, используя rnd.

Пример: генерация неориентированного дерева

Ниже основной код генератора неориентированного дерева, который принимает два параметра — количество вершин и степень его вытянутости. Например, при n = 10, t = 1000 наверняка будет сгенерирована цепь, а при n = 10, t =  - 1000 наверняка будет сгенерирована ромашка (звездочка).

registerGen(argc, argv, 1);

int n = atoi(argv[1]);
int t = atoi(argv[2]);

vector<int> p(n);

/* setup parents for vertices 1..n-1 */
forn(i, n)
    if (i > 0)
        p[i] = rnd.wnext(i, t);

printf("%d\n", n);

/* shuffle vertices 1..n-1 */
vector<int> perm(n);
forn(i, n)
    perm[i] = i;
shuffle(perm.begin() + 1, perm.end());

/* put edges considering shuffled vertices */
vector<pair<int,int> > edges;
for (int i = 1; i < n; i++)
    if (rnd.next(2))
        edges.push_back(make_pair(perm[i], perm[p[i]]));
    else
        edges.push_back(make_pair(perm[p[i]], perm[i]));

/* shuffle edges */
shuffle(edges.begin(), edges.end());

for (int i = 0; i + 1 < n; i++)
    printf("%d %d\n", edges[i].first + 1, edges[i].second + 1);

Как написать мультигенератор?

Мультигенератор за одно исполнение может вывести более одного теста. Тесты таким генератором выводятся в файлы. В генераторе на testlib.h достаточно перед выводом теста написать startTest(test_index). Это приведет к переоткрытию (freopen) потока стандартного вывода на файл с именем test_index. Обратите внимание, что в системе Polygon в таком случае в скрипте надо писать что-то вроде multigen a b c > {4-10} (если предполагается, что запуск мультигенератора вернет тесты 4, 5, 6, 7, 8, 9 и 10).

На что еще обратить внимание?

  • Строго следуйте формату теста — пробелы, переводы строк должны быть идеально соблюдены. Тест должен заканчиваться переводом строки. Например, если в тест состоит из единственного числа, то выводите его как cout << rnd.next(1, n) << endl; — с переводом строки в конце.
  • Если выводимый тест может быть довольно большим, то предпочитайте printf (а не cout) — это улучшит производительность.
  • Лучше выводите long long через cout, но если хотите printf, то используйте константу I64 (например, printf(I64, x);).
  • Необходимо не забывать о различных случаях неопределенного поведения языка C++. Например, в приведенном выше примере генератора нельзя объединять две команды cout в одну, т.к. тогда порядок вызовов функций rnd.next не определен.

Еще примеры

Примеры генераторов можно найти в дистрибутиве или непосредственно в репозитории.

 
 
 
 
  • Vote: I like it  
  • +79
  • Vote: I do not like it  

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

thanks a lot, but this post is in Russian not English!

»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Translation of the page

Generators — these support programs in the programming tasks that output tests. Not always manual tests in the problem small enough to only do them. In this case, come to the aid and generators. If you write a generator in C ++, using testlib.h — a good choice.

Types of generators There are two types of generators: conventional and multigeneratory.

The first one it is run exactly one output test. Typically, to generate several tests, such a generator is necessary to run multiple times with different command-line options. Such generators output the test to the standard output (the screen). Multigeneratory a single run many tests at once withdrawn. Such generators output test files (one file — one test). An example of a simple conventional generator testlib.h Displays a pair of numbers from 1 to n , where n — the parameter passed start the generator.

include "testlib.h"

include

using namespace STD ;

int main ( int argc , char * argv []) { registerGen ( argc , argv , 1 ); int n = atoi ( argv [ 1 ]); cout << rnd . next ( 1 , n ) << "" ; cout << rnd . next ( 1 , n ) << endl ; } Why testlib.h? When inattentive glance it seems that almost testlib.h not need to write the generator. In fact this is not true. Almost every generator need to be able to get a random value, and there is a great temptation to use rand () . Do not do that. The basic principle of writing generator: generator should output the same test when compiling any compiler on any platform, if it is started the same way . When using the rand () , or C ++ classes such as 11 mt19937 / uniform_int_distribution your program will display different tests after compiling different compilers.

The random values ​​in testlib.h ensures that will generate the same regardless of the generator and the platform. In addition, there are different testlib.h convenient for the test generation, for example, rnd.next ("[AZ] {1.10}") returns a random word length from 1 to 10 of the letters from a to z .

What have testlib.h? To initialize testlib-generator, the first line of your generator should be in the form registerGen (argc, argv, 1) (where 1 — is the version used a random number generator). You can then use the object rnd , which is initialized hash of all the command line arguments. Thus, the result of an output of 100 g and g.exe "100" will be the same, and at 100 g 0 will be different.

Object rnd has type random_t , meaning you can create and own generator, but this is usually not necessary.

An object rnd has many useful member functions. Here are some examples:

Challenge What is he doing rnd.next (4) equiprobable integer random number from 0 to 3 inclusive rnd.next (4, 100); equiprobable integer random number from 4 to 100 inclusive rnd.next (10.0) equiprobable real random number in the interval [0,10) rnd.next ("one | two | three") equiprobable random one word from three one, two and three rnd.next ("[1-9] [0-9] {99}") equiprobable random 100-digit number as a string rnd.wnext (4, t) wnext — a means of obtaining nonequiprobability distribution (with offset math expectancy), the parameter t represents the number of calls the operation "maximum" for a call to next, for example rnd.wnext (3, 1) is equivalent to the max (rnd.next (3), rnd.next ( 3)), and rnd.wnext (4, 2) is equivalent to max (rnd.next (4), max (rnd.next (4), rnd.next (4))). If T  <0 , then  -  T will be found at least. If T  = 0 , the equivalent wnext next. rnd.any (container) returns a random element container container (random access iterator on), for example, works for std :: vector and std :: string In addition, do not use STD :: random_shuffle , use the shuffle of testlib. It also takes two iterators, but works using rnd .

Example: Generate an undirected tree Below is the basic code generator undirected tree, which takes two parameters — the number of vertices and the degree of its elongation . For example, when n  = 10,  T  = 1000 certainly be generated circuit, and when n  = 10,  T  = — 1000 certainly be generated chamomile (asterisk).

registerGen ( argc , argv , 1 );

int n = atoi ( argv [ 1 ]); int T = atoi ( argv [ 2 ]);

Vector P ( n );

/ * Setup parents for vertices 1..n-1 * / Forn ( i , n ) if ( i > 0 ) P [ i ] = rnd . wnext ( i , T );

printf ( "% D \ n" , n );

/ * Shuffle vertices 1..n-1 * / Vector Perm ( n ); Forn ( i , n ) Perm [ i ] = i ; shuffle ( Perm . begin () + 1 , Perm . end ()) ;

/ * Put edges considering shuffled vertices */ vector < pair < int , int > > edges ; for ( int i = 1 ; i < n ; i ++) if ( rnd . next ( 2 )) edges . push_back ( make_pair ( perm [ i ], perm [ p [ i ]])); else edges . push_back ( make_pair ( perm [ p [ i ]], perm [ i ]));

/ * * Shuffle Edges / shuffle ( Edges . begin (), Edges . end ());

for ( int i = 0 ; i + 1 < n ; i ++) printf ( "% D% D \ n" , Edges [ i ]. first + 1 , Edges [ i ]. Second + 1 ); How to write multigenerator? Multigenerator per performance can bring more than one test. Tests such generator output to a file. The generator on testlib.h enough to write a test output StartTest (test_index) . This will lead to rediscovery (freopen) standard output to a file named test_index . Note that in the Polygon in this case the script should write something like MultiGen abc> {4-10} (if it is assumed that the launch multigeneratora return tests 4, 5, 6, 7, 8, 9 and 10).

What else to pay attention? Strictly follow the format of the test — spaces, line breaks must be perfectly satisfied. The test should end with a newline. For example, if the test consists of a single number, the output it as cout << rnd.next (1, n) << endl; — with line break at the end. If the test output can be quite large, the preferred printf (not cout ) — it will improve performance. It is better to deduce long long by cout , but if you want to printf , then use the constant I64 (eg, printf (I64, x); ). You must not forget the various cases of uncertain behavior of the language C ++. For example, in the above example, the generator can not combine the two teams cout one because Then the order of function calls rnd.next not defined. More examples