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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
#include <cmath>
#include <limits>
#include <vector>
#include <list>
#include <cstdint>
#include <cstdio>

#include "message.h"
#include "palindromy.h" 

#define DEBUG(A) std::cerr << A;
#define DEBUGNL(A) std::cerr << A << std::endl;

//#define DEBUG(A)
//#define DEBUGNL(A)
//#define SLEEP(A)

typedef long long int_t;

////////////////////////////////////////////////////////////////////////////////
// A class for assigning jobs to nodes

class scheduler_t {
protected:
	// Minimum reasonable number of indices per node
	int min_jobs_per_node;

	int_t num_jobs;
	int num_used_nodes;
	int_t jobs_per_node;

public:
	scheduler_t(int_t num_jobs, int num_nodes, int min_jobs_per_node);
	int get_num_used_nodes() const;
	bool is_node_used(int node_id) const;
	std::pair<int_t, int_t> get_jobs_for_node(int node_id) const;
};

scheduler_t::scheduler_t(int_t num_jobs, int num_nodes,
	int min_jobs_per_node) : min_jobs_per_node(std::max(1, min_jobs_per_node)),
		num_jobs(num_jobs) {

	if(num_jobs < min_jobs_per_node) {
		num_used_nodes = 1;
		jobs_per_node = num_jobs;
	} else {
		// At most as many nodes as jobs
		num_used_nodes = std::min(num_jobs, static_cast<int_t>(num_nodes));
		// As a result jobs_per_node here is at least 1
		jobs_per_node = num_jobs / num_used_nodes;

		// If the number of jobs per node is smaller than the limit
		if(jobs_per_node < min_jobs_per_node) {
			num_used_nodes = num_jobs / min_jobs_per_node;
			jobs_per_node = num_jobs / num_used_nodes;
		}
	}
}

int scheduler_t::get_num_used_nodes() const {
	return num_used_nodes;
}

bool scheduler_t::is_node_used(int node_id) const {
	return node_id < num_used_nodes;
}

std::pair<int_t, int_t> scheduler_t::get_jobs_for_node(int node_id) const {
	// Unused node
	if (node_id >= num_used_nodes) {
		return std::make_pair(-1, -1);
	}

	// For the used nodes
	// Distribute the reminder of jobs equaly
	int_t rem = num_jobs - jobs_per_node * num_used_nodes;

	int_t first;
	int_t last;
	if (node_id < rem) {
		first = (jobs_per_node + 1) * node_id;
		last = first + jobs_per_node;
	} else {
		first = (jobs_per_node + 1) * rem + jobs_per_node * (node_id - rem);
		last = first + jobs_per_node - 1;
	}
	
	return std::make_pair(first, last);
}



////////////////////////////////////////////////////////////////////////////////
// The solver class

class palin_counter_t {
public:
	int_t count;
	scheduler_t sched;

	palin_counter_t(int min_jobs_per_node) : count(0),
		sched(GetLength(), NumberOfNodes(), min_jobs_per_node) {
		int_t left;
		int_t right;
		int_t len = GetLength();
		int my_id = MyNodeId();
		std::pair<int_t, int_t> range = sched.get_jobs_for_node(my_id);

		if(sched.is_node_used(my_id)) {
			for(int_t i = range.first; i <= range.second; ++i) {
				// Count odd
				for(left = i, right = i; left >= 0 && right < len &&
					GetLetter(left) == GetLetter(right); --left, ++right) {
					++count;
				}
				// Count even
				for(left = i, right = i + 1; left > 0 && right < len &&
					GetLetter(left) == GetLetter(right); --left, ++right) {
					++count;
				}
	
			}
			if(my_id == 0) {
				for(int i = 1; i < sched.get_num_used_nodes(); ++i) {
					int source = Receive(-1);
					count += GetLL(source);
				}
				printf("%lld\n", count);
			} else {
				PutLL(0, count);
				Send(0);
			}
		}
	}
};

////////////////////////////////////////////////////////////////////////////////

int main() {
	palin_counter_t counter(2);
	return 0;
}