Ten towers are given. You need to compare them. exponentiation occurs from right to left a ^ (a ^ (a ^ a)). At the end, print their indexes in ascending order. Here is my code but it is incorrect.
input
10 // number of towers
4 2 2 2 2 2 // 4 The first number in a line is not an element of the tower, it is the //number of elements in it minus one.
1 2 2
1 3 2
1 2 3
3 2 2 2 2
2 2 2 2
1 3 3
3 3 3 3 3
2 4 3 3
2 2 3 4
output
2 4 3 6 7 5 9 10 1 8
Expand|Select|Wrap|Line Numbers
- #include <fstream>
- #include <algorithm>
- #include <stdio.h>
- #include <math.h>
- using namespace std;
- class tower_t {
- public:
- int num; // the tower room
- int height; // the height of the tower
- double val[11]; // content
- double cache[11]; // cache to speed up the calculation
- // Designer
- tower_t() {
- for (int i = 0; i < 11; i++) {
- val[i] = 1;
- cache[i] = 0;
- }
- height = 0;
- }
- // Triple logarithm of the top 3 levels
- double head(int level) {
- if(cache[level] == 0) cache[level] = log10(log10(val[level])) + log10(val[level + 1]) * val[level + 2];
- return cache[level];
- }
- // The calculation of the tops until intermeddle in double
- void normalize() {
- while(height > 1 && (log10(val[height - 2]) * val[height - 1]) < 50) {
- val[height - 2] = pow(val[height - 2], val[height - 1]);
- val[height - 1] = 1;
- height--;
- }
- }
- // Output for debugging
- void print() {
- #ifdef _DEBUG
- printf("%2d: {", num);
- for (int i = 0; i < height; i++) {
- if (i > 0) printf(", ");
- if(val[i] < 1000000000) {
- printf("%0.0f", val[i]);
- } else {
- printf("%0.3e", val[i]);
- }
- }
- printf("}\n");
- #endif
- }
- };
- // comparison of two towers
- bool compare(tower_t& t1, tower_t& t2) {
- // floor with which to compare the last three levels
- int level = ((t1.height > t2.height) ? t1.height : t2.height) - 3;
- if (level < 0) level = 0;
- if(t1.height == t2.height) { // if the towers are of the same height, compare by floor
- for (int i = t1.height - 1; i >= 0; i--) {
- if (abs(t1.val[i] - t2.val[i]) > (t1.val[i] * 1e-14)) {
- if (i < level) { // the tops of the towers coincided below level
- return t1.val[i] < t2.val[i];
- }
- break;
- }
- }
- }
- return t1.head(level) < t2.head(level);
- }
- int main(int argc, char**argv)
- {
- // Reading job
- ifstream in ("input.txt");
- int cnt;
- in >> cnt;
- tower_t* towers = new tower_t[cnt];
- for (int i = 0; i < cnt; i++) {
- int len;
- in >> len;
- towers[i].num = i + 1;
- bool write = true;
- for (int j = 0; j <= len; j++) {
- int val;
- in >> val;
- if (val <= 1) write = false; // if level of <= 1 the higher not to read
- if(write) {
- towers[i].val[j] = val;
- towers[i].height = j + 1;
- }
- }
- towers[i].print();
- towers[i].normalize();
- }
- // Sort
- sort(towers, towers + cnt, compare);
- // The output
- ofstream out("output.txt");
- for (int i = 0; i < cnt; i++) {
- out << towers[i].num << " ";
- towers[i].print();
- }
- out << endl;
- out.close();
- delete[] towers;
- return 0;
- }