fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3.  
  4. const int N = 100, TRY = 100000;
  5.  
  6. int n, h[N], obs[N];
  7.  
  8. bool place() {
  9. 	double tang, t;
  10. 	int i, j, best;
  11. 	for (i = 0; i < n; ++i)
  12. 		h[i] = rand();
  13. 	for (i = 0; i < n - 1; ++i) {
  14. 		tang = -1e18; // Тангенс угла близкого к -Pi/2
  15. 		best = i + 1; // Тут будет номер горы с максимальным тангенсом.
  16. 		for (j = i + 1; j < n; ++j) { // Начинаем с следующей горы.
  17. 			t = double(h[j] - h[i]) / double(j - i);
  18. 			if (tang < t) {
  19. 				best = j;
  20. 				tang = t;
  21. 			}
  22. 		}
  23. 		// Если гора с максимальным тангенсом
  24. 		// не совпадает с указанной в условии...
  25. 		if (best != obs[i])
  26. 			return false;
  27. 	}
  28. 	return true;
  29. }
  30.  
  31. int main() {
  32. 	/*/
  33. 	freopen("C:\\Users\\anonymous\\Downloads\\C-small-practice.in", "r", stdin);
  34. 	freopen("C:\\Users\\anonymous\\Desktop\\out.txt", "w", stdout);
  35. 	/**/
  36. 	int t, it, i;
  37. 	scanf("%d", &t);
  38. 	for (it = 1; it <= t; ++it) {
  39. 		scanf("%d", &n);
  40. 		for (i = 0; i < n - 1; ++i) {
  41. 			scanf("%d", &obs[i]); // Читаю обозримую вершину.
  42. 			--obs[i]; // Привожу к нумерации с нуля.
  43. 		}
  44. 		for (i = 0; i < TRY; ++i) // Делаю TRY попыток расставить высоты.
  45. 			if (place())
  46. 				break;
  47. 		printf("Case #%d:", it);
  48. 		if (i == TRY) {
  49. 			printf(" Impossible");
  50. 		} else {
  51. 			for (i = 0; i < n; ++i)
  52. 				printf(" %d", h[i]);
  53. 		}
  54. 		putchar('\n');
  55. 	}
  56. 	return 0;
  57. }
Success #stdin #stdout 0.03s 2728KB
comments (?)
stdin
copy 
4
6
2 3 4 5 6
4
4 4 4
4
3 4 4
4
4 3 4
stdout
copy 
Case #1: 881759 1951761153 2042122590 2083782853 1756095042 791396296
Case #2: 1788175905 110793789 218743872 1144741933
Case #3: Impossible
Case #4: 1580161787 923466739 1494465807 2030566429
https://ideone.com/zW78R
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!