fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	// Complexity - Big O
  6. 	// Seberapa banyak operasi yg dilakukan/runtime berubah
  7. 	// saat ada perubahan input
  8. 	// Rule of Thumb: 10^8 op = 1s
  9. 	/*
  10. 	int n, data[1000001];					// O(1)
  11. 	cin >> n;								// O(1)
  12. 	for(int i = 0; i < n; i++)				// O(n)
  13. 		cin >> data[i];
  14. 	for(int i = 0; i < n; i++)				// O(n^2)
  15. 		for(int j = 1; j < n; j++)
  16. 			if(data[j] < data[j-1]) {
  17. 				int tmp = data[j];
  18. 				data[j] = data[j-1];
  19. 				data[j-1] = tmp;
  20. 			}
  21. 	*/
  22. 	// Big O = O(n^2)
  23. 	/*
  24. 	O(n)
  25. 	n = 10 -> rt = 1ms
  26. 	n = 100 -> rt = 10ms
  27. 	n = 1000 -> rt = 100ms
  28. 	..
  29.  
  30. 	O(n^2)
  31. 	n = 10 -> rt = 100ms
  32. 	n = 100 -> rt = 10000ms
  33. 	n = 1000000 -> rt = 10^12ms
  34. 	*/
  35.  
  36. 	// 4 Paradigm overview
  37. 	/*
  38. 	int data = {10, 7, 3, 5, 8, 2, 9}, n = 7;
  39. 	//                 ^  ^  ^     ^
  40. 	// 3, 5, 8, 9
  41. 	for(int i = 0; i < n; i++)
  42. 		if(data[i] > maks)
  43. 			maks = data[i];
  44. 	// n <= 200000, data[i] <= 10^6
  45.  
  46. 	// 1. Cari bilangan terbesar & terkecil dari array data. O(n)
  47. 	// 2. Cari bilangan terbesar urutan ke-k dari array data. (k<=n)
  48. 	// Pendekatan pertama: sort O(n^2) -> Time Limit Exceeded
  49. 	// Pendekatan kedua: Cari bil terbesar, lalu hapus.
  50. 	//                   Cari bil kedua terbesar, lalu hapus.
  51. 	//                   Ulangi sampai bil ke-(k-1) terbesar & hapus.
  52. 	//                   Cari bil ke-k terbesar. -> O(n*k) = O(n^2)
  53. 	for(int i = 0; i < k; i++)
  54. 		for(int j = 0; j < n; j++)
  55. 	// Yang bener: sort O(n log n)
  56. 	// 3. Cari selisih terbesar dalam array data.
  57. 	// Pendekatan complete search -> O(n^2) -> TLE
  58. 	// Greedy -> O(n)
  59. 	// 4. Cari LIS = Longest Increasing Subsequence di array data.
  60. 	// Dynamic Programming
  61. 	*/
  62.  
  63. 	// Complete Search
  64. 	// Iterative = loop
  65. 	// Recursive = fungsi rekursif
  66. 	// Pruning -> tidak melanjutkan proses yang pasti gagal
  67. 	/* 8 ratu di papan catur -> 8 Queens problem
  68. 	o..o..o.
  69. 	.o.o.o..
  70. 	..ooo...
  71. 	oooQoooo
  72. 	..ooo...
  73. 	.o.o.o..
  74. 	o..o..o.
  75. 	...o...o
  76.  
  77. 	1.......
  78. 	..2.....
  79. >	....3...
  80. 	........
  81. 	........
  82. 	........
  83. 	........
  84. 	........
  85. 	8^7
  86. 	*/
  87.  
  88. 	// Divide & Conquer -> harus terurut
  89. 	// linear search -> per langkah -1 -> O(n)
  90. 	// binary search -> per langkah /2 -> O(log n)
  91.  
  92. 	// search space
  93. 	// {1, 1, 2, 2, 2, 4, 5, 6, 6, 9, 10, 13, 17, 22, 23}
  94. 	//  |--------------------|-------------------------|
  95. 	//                          |----------|-----------|
  96. 	//                          |--|---|
  97. 	//                                 |
  98. 	// dalam x langkah -> search space berkurang 2^x kali
  99. 	// ukurang search space = n -> banyak langkah = log2 n = log n
  100. 	// cari 10
  101. 	/*
  102. 	int data[] = {1, 1, 2, 2, 2, 4, 5, 6, 6, 9, 10, 13, 17, 22, 23}, n = 15;
  103. 	// i1 <= i2 -> data[i1] <= data[i2]
  104. 	int cari = 10;
  105. 	// linear search
  106. 	for(int i = 0; i < n; i++)
  107. 		if(data[i] == cari)
  108. 			cout << cari << " ditemukan di index: " << i << endl;
  109. 	// binary search
  110. 	int lo = 0, hi = n-1, mid;
  111. 	while(lo < hi) {
  112. 		mid = (lo+hi)/2;
  113. 		if(data[mid] > cari)
  114. 			hi = mid-1;
  115. 		else if(data[mid] < cari)
  116. 			lo = mid+1;
  117. 		else
  118. 			lo = hi = mid;
  119. 	}
  120. 	cout << cari << " ditemukan di index: " << lo << endl;
  121. 	*/
  122.  
  123. 	// Bisection method / Binary Search The Answer
  124. 	// 0 <= x < PI/2, sin(x) = increasing
  125. 	// x1 < x2 -> sin(x1) < sin(x2)
  126. 	double PI = acos(-1);
  127.  
  128. 	double y = 0.75;
  129. 	double lo = 0, hi = PI/2, mid;
  130. 	while(hi-lo > 1e-4) {
  131. 		mid = (lo+hi)/2;
  132. 		cout << lo << " " << mid << " " << hi << endl;
  133. 		if(sin(mid) > y)
  134. 			hi = mid;
  135. 		else if(sin(mid) < y)
  136. 			lo = mid;
  137. 	}
  138. 	cout << "arcsin(" << y << ") = " << lo << endl;
  139. 	// buat arcsin(y)
  140. 	return 0;
  141. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0.785398 1.5708
0.785398 1.1781 1.5708
0.785398 0.981748 1.1781
0.785398 0.883573 0.981748
0.785398 0.834486 0.883573
0.834486 0.859029 0.883573
0.834486 0.846757 0.859029
0.846757 0.852893 0.859029
0.846757 0.849825 0.852893
0.846757 0.848291 0.849825
0.846757 0.847524 0.848291
0.847524 0.847908 0.848291
0.847908 0.8481 0.848291
0.847908 0.848004 0.8481
arcsin(0.75) = 0.848004
https://ideone.com/aP0knU
language:
C++ (gcc 8.3)
created:
10 days 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!