Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdlib>
- #include <cstdio>
- using namespace std;
- const int specialtests = 5 , randomtests = 15 , maxMaps = 100 , maxCities = 1000;
- int Top;
- void construct ( int pnode , int numLeft )
- {
- if ( numLeft == 1 )
- return;
- numLeft --;
- int leftsize = rand() % numLeft + 1 , rightsize = numLeft - leftsize;
- if ( leftsize )
- {
- ++ Top;
- cout << pnode <<" L " << Top << endl;
- construct ( Top , leftsize );
- }
- if ( rightsize )
- {
- ++ Top;
- cout << pnode << " R " << Top << endl;
- construct ( Top , rightsize );
- }
- }
- void outputSample()
- {
- cerr <<"Generating sample inputs" << endl;
- string sample = "3\n5\n1 L 2\n1 R 3\n3 L 4\n3 R 5\n4\n1 R 2\n1 L 3\n2 L 4\n3\n1 L 2\n1 R 3\n2\n5\n1 L 2\n2 L 3\n3 L 4\n4 L 5\n6\n1 L 2\n2 R 3\n3 L 4\n4 R 5\n5 L 6\n";
- cout << sample << endl;
- }
- void outputWorstCase()
- {
- cerr <<"Generating worst case inputs" << endl;
- // 100 Ls
- cout << maxMaps << endl;
- for ( int i=0;i<maxMaps;i++ )
- {
- cout << maxCities << endl;
- for ( int i=1;i<maxCities;i++ )
- cout << i <<" L " << i+1 << endl;
- }
- // 100 Rs
- cout << maxMaps << endl;
- for ( int i=0;i<maxMaps;i++ )
- {
- cout << maxCities << endl;
- for ( int i=1;i<maxCities;i++ )
- cout << i <<" R " << i+1 << endl;
- }
- // 50 Ls and 50 Rs
- cout << maxMaps << endl;
- for ( int i=0;i<maxMaps/2;i++ )
- {
- cout << maxCities << endl;
- for ( int i=1;i<maxCities;i++ )
- cout << i <<" L " << i+1 << endl;
- }
- for ( int i=0;i<maxMaps/2;i++ )
- {
- cout << maxCities << endl;
- for ( int i=1;i<maxCities;i++ )
- cout << i <<" R " << i+1 << endl;
- }
- }
- int main()
- {
- FILE * fp = fopen ("log.txt" , "w" );
- freopen ( "input_TR2.txt" , "w" , stdout );
- int seed = time(NULL);
- srand(seed);
- fprintf ( fp , "Seed = %d\n" , seed );
- cout << specialtests +randomtests << endl;
- outputSample();
- outputWorstCase();
- cerr << "Generating random cases" << endl;
- for ( int testNum=0;testNum<randomtests;testNum++ )
- {
- cerr << "Generating testcase: " << specialtests + testNum + 1 << endl;
- cout << maxMaps << endl;
- for ( int i=0;i<maxMaps;i++ )
- {
- cout << maxCities << endl;
- Top = 1;
- construct ( 1 , maxCities );
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement