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
#include <cstdio>
#include <algorithm>
#include "krazki.h"
#include "message.h"
using namespace std;

const int MAX_PIPES = 4*1000006;
const long long INF_D = 1000000000000000018LL;
const int INF_BOT = 4*100000008;

long long min_pipe[MAX_PIPES];
int disc_n;
int pipe_h;
int node_n;
int my_node;



void countMin(int top, int bot)
{
	long long curr_min = INF_D;
	for(int i = top; i <= bot; ++i)
	{
		curr_min = min(HoleDiameter(i), curr_min);
		min_pipe[i-top] = curr_min;		
	}
}


int topLevel(int top, int bot)
{
	int disc = 1;
	int level = bot;
	
	if(top > bot) return INF_BOT;
	
	for(; disc <= disc_n; )
	{
		if(level - top > 0 && DiscDiameter(disc) > min_pipe[level-top])
			--level;
		else
		{
			++disc;
			if(level != bot) level--;
		}		
	}
	
	
	
	if(level == bot) return INF_BOT;
	return level+1;		// bo level wskazuje pierwszą wolną pozycję
}



int main()
{
	node_n = NumberOfNodes();
	my_node = MyNodeId();
	disc_n = NumberOfDiscs();
	pipe_h = PipeHeight();
	
	int my_top, my_bot;
	my_top = (pipe_h / node_n) * my_node +1;
	my_bot = my_top + (pipe_h / node_n) - 1;
	if(my_node == node_n - 1) my_bot = pipe_h;
	
	
	countMin(my_top, my_bot);
	int res = topLevel(my_top, my_bot)+1; // +1 bo tutaj iterujemy od 1
	
	if(my_node == 0)
	{
		int node_res[node_n];
		node_res[0] = res;
		for(int i = 1; i < node_n; ++i)
		{
			Receive(i);
			node_res[i] = GetInt(i);
		}
		res = pipe_h - disc_n + 1;
		for(int i = 0; i < node_n; ++i)
			res = min(res, node_res[i]);
			
		if(res < 0) res = 0;
		printf("%d\n", res);
	}
	else
	{
		PutInt(0, res);
		Send(0);
	}
	
	
	
	
	return 0;
}