API tools faq
paste
Guest User

Untitled

a guest
Jan 29th, 2016
366
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.79 KB | None | 0 0
raw download clone embed print report
  1. Solutions:
  2.  
  3. - Slime Combining:
  4. n = int(raw_input())
  5. print " ".join(str(i+1) for i in range(20,-1,-1) if (n&(1<<i)) > 0)
  6.  
  7. - Guess the permutation:
  8. import sys
  9. f = sys.stdin
  10. n = int(f.readline())
  11. arr = [max(map(int, f.readline().split())) for i in range(n)]
  12. arr[arr.index(n-1)] = n
  13. print " ".join(map(str,arr))
  14.  
  15. - Constellation:
  16. import sys
  17. import random
  18. from fractions import gcd
  19.  
  20. f = sys.stdin
  21. n = int(f.readline())
  22. x,y = zip(*[map(int, f.readline().split()) for i in range(n)])
  23. st = random.randint(0, n-1)
  24. dist = [(x[i]-x[st])*(x[i]-x[st])+(y[i]-y[st])*(y[i]-y[st]) for i in range(n)]
  25.  
  26. def getSlope(x1,y1):
  27. g = gcd(abs(x1),abs(y1))
  28. x1,y1 = x1/g,y1/g
  29. if x1 < 0 or (x1 == 0 and y1 < 0):
  30. x1,y1 = -x1,-y1
  31. return (x1,y1)
  32.  
  33. s = {}
  34. for i in xrange(n):
  35. if i == st: continue
  36. slope = getSlope(x[i] - x[st], y[i] - y[st])
  37. if slope not in s or dist[i] < dist[s[slope]]:
  38. s[slope] = i
  39.  
  40. lst = sorted(s.values(), key=lambda x: dist[x])
  41. print st+1, lst[0]+1, lst[1]+1
  42.  
  43. - Hamiltonian Spanning Tree:
  44. import java.io.*;
  45. import java.util.*;
  46. public class HamiltonianTree {
  47. private static InputReader in;
  48. private static PrintWriter out;
  49. public static ArrayList<Integer>[] graph;
  50.  
  51. public static void main (String[] args) {
  52. in = new InputReader(System.in);
  53. out = new PrintWriter(System.out, true);
  54.  
  55. int n = in.nextInt();
  56. long x = in.nextInt(), y = in.nextInt();
  57.  
  58. if (x > y) {
  59. int[] deg = new int[n];
  60. for (int i = 0; i < n-1; i++) {
  61. int a = in.nextInt()-1, b = in.nextInt()-1;
  62. deg[a]++;
  63. deg[b]++;
  64. }
  65. int max = 0;
  66. for (int i = 0; i < n; i++) {
  67. max = Math.max(max, deg[i]);
  68. }
  69. out.println(y * (n - 2) + (max == n-1 ? x : y));
  70. } else {
  71. graph = new ArrayList[n];
  72. for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
  73. for (int i = 0; i < n-1; i++) {
  74. int a = in.nextInt()-1, b = in.nextInt()-1;
  75. graph[a].add(b);
  76. graph[b].add(a);
  77. }
  78. ans = 0;
  79. dfs(0, -1);
  80. out.println((n-1-ans)*y + ans*x);
  81. }
  82. out.close();
  83. System.exit(0);
  84. }
  85.  
  86. public static long ans;
  87. public static int dfs(int node, int par) {
  88. int left = 2;
  89. for (int next : graph[node]) {
  90. if (next == par) continue;
  91. int x = dfs(next, node);
  92. if (left > 0 && x == 1) {
  93. ans++;
  94. left--;
  95. }
  96. }
  97. return left > 0 ? 1 : 0;
  98. }
  99.  
  100. static class InputReader {
  101. public BufferedReader reader;
  102. public StringTokenizer tokenizer;
  103.  
  104. public InputReader(InputStream stream) {
  105. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  106. tokenizer = null;
  107. }
  108.  
  109. public String next() {
  110. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  111. try {
  112. tokenizer = new StringTokenizer(reader.readLine());
  113. } catch (IOException e) {
  114. throw new RuntimeException(e);
  115. }
  116. }
  117. return tokenizer.nextToken();
  118. }
  119.  
  120. public int nextInt() {
  121. return Integer.parseInt(next());
  122. }
  123. }
  124. }
  125.  
  126. - Robot Arm:
  127. import java.io.*;
  128. import java.util.*;
  129. public class RobotArmFast {
  130. private static InputReader in;
  131. private static PrintWriter out;
  132. public static double[] sin, cos;
  133. static {
  134. cos = new double[360];
  135. sin = new double[360];
  136. for (int i = 0; i < 360; i++) {
  137. cos[i] = Math.cos(i / 180. * Math.PI);
  138. sin[i] = Math.sin(i / 180. * Math.PI);
  139. }
  140. }
  141.  
  142. public static int[] length, angle;
  143. public static double[] x, y;
  144. public static int[] r;
  145.  
  146. public static void combine(int idx) {
  147. int a1 = 2*idx+1, a2 = 2*idx+2;
  148. x[idx] = x[a1] + x[a2] * cos[r[a1]] - y[a2] * sin[r[a1]];
  149. y[idx] = y[a1] + y[a2] * cos[r[a1]] + x[a2] * sin[r[a1]];
  150. r[idx] = (r[a1] + r[a2]) % 360;
  151. }
  152.  
  153. public static void update(int idx, int s, int e, int pos, int which, int delta) {
  154. if (pos == s && pos == e) {
  155. if (which == 1) length[pos] += delta;
  156. else {angle[pos] -= delta; if (angle[pos] < 0) angle[pos] += 360;}
  157. x[idx] = cos[angle[pos]] * length[pos];
  158. y[idx] = sin[angle[pos]] * length[pos];
  159. r[idx] = angle[pos];
  160. return;
  161. }
  162. int mid = (s + e) / 2;
  163. if (mid >= pos) update(2*idx+1, s, mid, pos, which, delta);
  164. else update(2*idx+2, mid+1, e, pos, which, delta);
  165. combine(idx);
  166. }
  167.  
  168. public static void init(int idx, int s, int e) {
  169. if (s == e) {
  170. length[s] = 1;
  171. angle[s] = 0;
  172. } else {
  173. int mid = (s + e) / 2;
  174. init(2*idx+1, s, mid);
  175. init(2*idx+2, mid+1, e);
  176. }
  177. x[idx] = e-s+1;
  178. y[idx] = 0;
  179. r[idx] = 0;
  180. }
  181.  
  182. public static void main (String[] args) {
  183. in = new InputReader(System.in);
  184. out = new PrintWriter(System.out, true);
  185. int n = in.nextInt(), m = in.nextInt();
  186. length = new int[n+1];
  187. angle = new int[n+1];
  188. x = new double[4*n];
  189. y = new double[4*n];
  190. r = new int[4*n];
  191. init(0, 1, n);
  192. StringBuilder b = new StringBuilder();
  193. for (int i = 0; i < m; i++) {
  194. int which = in.nextInt(), segment = in.nextInt(), delta = in.nextInt();
  195. update(0, 1, n, segment, which, delta);
  196. b.append(String.format("%.10f %.10f\n", x[0], y[0]));
  197. }
  198. out.print(b.toString());
  199. out.close();
  200. System.exit(0);
  201. }
  202. static class InputReader {
  203. public BufferedReader reader;
  204. public StringTokenizer tokenizer;
  205.  
  206. public InputReader(InputStream stream) {
  207. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  208. tokenizer = null;
  209. }
  210.  
  211. public String next() {
  212. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  213. try {
  214. tokenizer = new StringTokenizer(reader.readLine());
  215. } catch (IOException e) {
  216. throw new RuntimeException(e);
  217. }
  218. }
  219. return tokenizer.nextToken();
  220. }
  221.  
  222. public int nextInt() {
  223. return Integer.parseInt(next());
  224. }
  225. }
  226. }
  227.  
  228. - Double Knapsack:
  229. import java.io.*;
  230. import java.util.*;
  231.  
  232. public class DoubleKnapsack {
  233. private static InputReader in;
  234. private static PrintWriter out;
  235. public static void main(String[] args) {
  236. in = new InputReader(System.in);
  237. out = new PrintWriter(System.out, true);
  238. int n = in.nextInt();
  239. int[] arr = new int[n];
  240. int[] brr = new int[n];
  241. long sa = 0, sb = 0;
  242. for (int i = 0; i < n; i++) sa += arr[i] = in.nextInt();
  243. for (int i = 0; i < n; i++) sb += brr[i] = in.nextInt();
  244.  
  245. boolean swap = false;
  246. if (sa > sb) {
  247. swap = true;
  248. int[] t = arr;
  249. arr = brr;
  250. brr = t;
  251. }
  252.  
  253. long xs = 0, ys = 0;
  254. int j = -1;
  255. long[] prev = new long[n];
  256. Arrays.fill(prev, -1);
  257. prev[0] = 0;
  258. for (int i = 0; i < n; i++) {
  259. xs += arr[i];
  260. while (j+1 < n && ys+brr[j+1] <= xs) {
  261. ys += brr[++j];
  262. }
  263. int diff = (int)(xs-ys);
  264. if (prev[diff] != -1) {
  265. int px = (int)(prev[diff]%n)-1, py = (int)(prev[diff]/n)-1;
  266. if (swap) {
  267. printAns(py, j);
  268. printAns(px, i);
  269. } else {
  270. printAns(px, i);
  271. printAns(py, j);
  272. }
  273. out.close();
  274. System.exit(0);
  275. }
  276. prev[diff] = (j+1)*(long)n + (i+1);
  277. }
  278. }
  279.  
  280. public static void printAns(int from, int to) {
  281. out.println(to-from);
  282. for (int i = from+1; i <= to; i++) {
  283. if (i != from+1) out.print(" ");
  284. out.print(i+1);
  285. }
  286. out.println();
  287. }
  288.  
  289. static class InputReader {
  290. public BufferedReader reader;
  291. public StringTokenizer tokenizer;
  292.  
  293. public InputReader(InputStream stream) {
  294. reader = new BufferedReader(new InputStreamReader(stream));
  295. tokenizer = null;
  296. }
  297.  
  298. public String next() {
  299. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  300. try {
  301. tokenizer = new StringTokenizer(reader.readLine());
  302. } catch (IOException e) {
  303. throw new RuntimeException(e);
  304. }
  305. }
  306. return tokenizer.nextToken();
  307. }
  308.  
  309. public int nextInt() {
  310. return Integer.parseInt(next());
  311. }
  312. }
  313. }
  314. - Combining Slimes:
  315. import java.io.*;
  316. import java.util.*;
  317. public class SlimeCombining {
  318. private static InputReader in;
  319. private static PrintWriter out;
  320. public static double EPS = 1e-15;
  321. public static int maxp = 50;
  322.  
  323. public static void main (String[] args) {
  324. in = new InputReader(System.in);
  325. out = new PrintWriter(System.out, true);
  326.  
  327. int n = in.nextInt();
  328. int p = in.nextInt();
  329.  
  330. double p2 = p / 1000000000., p4 = 1 - p2;
  331. double[][] a = new double[maxp][maxp];
  332. double[][] b = new double[maxp][maxp];
  333. for (int len = 1; len < maxp; len++) {
  334. for (int pow = 1; pow < maxp; pow++) {
  335. if (pow == 1) a[len][pow] += p2;
  336. if (pow == 2) {
  337. a[len][pow] += p4;
  338. b[len][pow] += p4;
  339. }
  340. a[len][pow] += a[len-1][pow-1] * a[len][pow-1];
  341. b[len][pow] += a[len-1][pow-1] * b[len][pow-1];
  342. }
  343. }
  344. for (int len = maxp - 1; len >= 1; len--) {
  345. for (int pow = 1; pow < maxp; pow++) {
  346. a[len][pow] *= 1 - a[len-1][pow];
  347. b[len][pow] *= 1 - a[len-1][pow];
  348. }
  349. }
  350.  
  351. // value of a slime that has been merged i times
  352. long[] vals = new long[maxp];
  353. for (int i = 0; i < maxp; i++) vals[i] = i;//1l << i;
  354. // manually do first few cases
  355. double[][] dp = new double[maxp][maxp];
  356. double[][] sum = new double[maxp][maxp];
  357. for (int cur = 1; cur < maxp; cur++)
  358. dp[maxp-1][cur] = vals[cur];
  359.  
  360. // manual dp
  361. for (int i = maxp-2; i >= 0; i--) {
  362. for (int cur = 1; cur < maxp; cur++) {
  363. for (int next = 1; next < maxp; next++) {
  364. if (cur == next) continue;
  365. if (cur == 1) {
  366. dp[i][cur] += b[maxp-i-1][next] * dp[i+1][next];
  367. sum[i][cur] += b[maxp-i-1][next];
  368. } else {
  369. if (cur < next) continue;
  370. dp[i][cur] += a[maxp-i-1][next] * dp[i+1][next];
  371. sum[i][cur] += a[maxp-i-1][next];
  372. }
  373. }
  374. }
  375. for (int cur = 1; cur < maxp; cur++) {
  376. dp[i][cur] = vals[cur] + dp[i][cur] / sum[i][cur];
  377. }
  378. }
  379. if (n < maxp) {
  380. int k = (int)n;
  381. double exp = 0;
  382. for (int i = 1; i < maxp; i++) {
  383. exp += a[k][i] * dp[maxp-k][i];
  384. }
  385. out.printf("%.15f\n", exp);
  386. out.close();
  387. System.exit(0);
  388. }
  389.  
  390. double[] vec = new double[maxp+1];
  391. System.arraycopy(dp[0], 0, vec, 0, maxp);
  392. vec[maxp] = 1;
  393. double[][] mat = new double[maxp+1][maxp+1];
  394. mat[maxp][maxp] = 1;
  395. for (int i = 1; i < maxp; i++) {
  396. for (int j = 1; j < maxp; j++) {
  397. if (i == j) continue;
  398. if (i == 1) {
  399. mat[i][j] += b[maxp-1][j] / sum[0][i];
  400. } else {
  401. if (i < j) continue;
  402. mat[i][j] += a[maxp-1][j] / sum[0][i];
  403. }
  404. }
  405. mat[i][maxp] += vals[i];
  406. }
  407. mat = mat_exp(mat, n - maxp);
  408. vec = vec_mult(mat, vec);
  409. double exp = 0;
  410. for (int i = 1; i < maxp; i++) {
  411. exp += a[maxp-1][i] * vec[i];
  412. }
  413. out.printf("%.15f\n", exp);
  414. out.close();
  415. System.exit(0);
  416. }
  417.  
  418. public static double[] vec_mult(double[][] A, double[] B) {
  419. double[] C = new double[A.length];
  420. for (int i = 0; i < A.length; i++) {
  421. for (int j = 0; j < B.length; j++) {
  422. C[i] += A[i][j] * B[j];
  423. }
  424. }
  425. return C;
  426. }
  427.  
  428. private static double[][] mat_exp(double[][] A, long e) {
  429. if (e == 0) {
  430. double[][] ret = new double[A.length][A.length];
  431. for (int i = 0; i < A.length; i++) ret[i][i] = 1.0;
  432. return ret;
  433. }
  434. if (e == 1)
  435. return A;
  436. else if (e % 2 == 0) {
  437. double[][] A1 = mat_exp(A, e / 2);
  438. return matrix_mult(A1, A1);
  439. } else
  440. return matrix_mult(A, mat_exp(A, e - 1));
  441. }
  442.  
  443. private static double[][] matrix_mult(double[][] A, double[][] B) {
  444. double[][] C = new double[A.length][A.length];
  445. for (int i = 0; i < A.length; i++)
  446. for (int j = 0; j < A.length; j++)
  447. for (int k = 0; k < A.length; k++)
  448. C[i][k] += A[i][j] * B[j][k];
  449. return C;
  450. }
  451.  
  452. static class InputReader {
  453. public BufferedReader reader;
  454. public StringTokenizer tokenizer;
  455.  
  456. public InputReader(InputStream stream) {
  457. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  458. tokenizer = null;
  459. }
  460.  
  461. public String next() {
  462. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  463. try {
  464. tokenizer = new StringTokenizer(reader.readLine());
  465. } catch (IOException e) {
  466. throw new RuntimeException(e);
  467. }
  468. }
  469. return tokenizer.nextToken();
  470. }
  471.  
  472. public int nextInt() {
  473. return Integer.parseInt(next());
  474. }
  475. }
  476. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!