1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <vector>
#include <list>
#include <stdio.h>
#include <algorithm>


//#define READ_FROM_FILE

#ifdef READ_FROM_FILE
#include <iostream>
#include <fstream>
#endif // READ_FROM_FILE

using namespace std;

struct Pref
{
	int from;
	int to;

	int counter;
	int paths;
};

int main( )
{
#ifdef READ_FROM_FILE
	clock_t start = clock();
#endif

#ifdef READ_FROM_FILE
	std::ifstream fin ( "sample_dru.txt" );

	if ( !fin.is_open( ) )
	{
		std::cout << "No data file" << std::endl;
		return 0;
	}
#endif // READ_FROM_FILE



		//cout << "Case #" << tc+1 << endl;
		int studentQ;

#ifdef READ_FROM_FILE
		fin >> studentQ;
#else
		scanf( "%d", &studentQ );
#endif

		vector < Pref > prefs( studentQ + 1 );

		for ( int i=1; i<=studentQ; ++i )
		{
#ifdef READ_FROM_FILE
			fin >> prefs[i].from >> prefs[i].to;
#else
			scanf( "%d %d", &prefs[i].from, &prefs[i].to );
#endif
		}

		prefs.front( ).paths = 1;

		for ( int i=0; i<studentQ; ++i )
		{
			bool stop = false;
			for ( int j=1+1; j<=prefs[i+1].from; ++j )
			{
				if ( i+j >= studentQ+1 )
				{
					stop = true;
					break;
				}

				if ( prefs[i+j].to < j )
				{
					stop = true;
					break;
				}
			}
			if ( stop )
				continue;

			for ( int j=prefs[i+1].from; j<=prefs[i+1].to; ++j )
			{
				if ( i+j >= studentQ+1 )
					break;

				if ( prefs[i+j].to < j )
					break;

				if ( prefs[i+j].from > j )
					continue;

				if ( prefs[i].counter + 1 == prefs[i+j].counter )
				{
					prefs[i+j].paths += 1;
				}

				if ( prefs[i].counter + 1 > prefs[i+j].counter )
				{
					prefs[i+j].counter = prefs[i].counter + 1;
					prefs[i+j].paths = prefs[i].paths;
				}
			}
		}

		if ( prefs.back( ).counter == 0 )
		{
			printf( "NIE\n" );
		}
		else
		{
			printf( "%d %d\n", prefs.back( ).counter, prefs.back( ).paths );
		}


#ifdef	READ_FROM_FILE
	clock_t end = clock();
	float seconds = (float)(end - start) / CLOCKS_PER_SEC;

	printf( "time - %f\n", seconds);
#endif

	return 0;
}