Guest User

Untitled

a guest
Jun 24th, 2018
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.32 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3.  
  4.  
  5. public class Main {
  6.  
  7. public static void main(String[] args) throws Exception {
  8.  
  9. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  10. String line = br.readLine();
  11. String line2 = br.readLine();
  12. String line3 = br.readLine();
  13.  
  14. String str = line.replaceAll("[^0-9]", ""); //string から 数字以外を除く
  15. String str2 = line2.replaceAll("[^0-9]", "");
  16. String str3 = line3.replaceAll("[^0-9]", "");
  17.  
  18. int n = Integer.parseInt(str);
  19. int k = Integer.parseInt(str3);
  20.  
  21.  
  22.      int a[] = new int [n];
  23.  
  24. for(int i = 0; i < n; i++){
  25. a [i] = Character.getNumericValue(str2.charAt(i)); //char change into int
  26.  
  27. }
  28.  
  29. double dn = Math.pow(2, n);
  30. int ddn = (int)dn;
  31. int sum[][] = new int [n+1][ddn];
  32.  
  33. boolean ans = false;
  34.  
  35. outside: for(int i=1;i<n+1;i++){
  36. double deden = Math.pow(2, i);
  37. int dedan = (int)deden;
  38.  
  39. for(int j=0;j<dedan;j+=2){
  40. sum[i][j] = sum[i-1][j/2];
  41. sum[i][j+1] = sum[i-1][j/2] + a[i-1];
  42.  
  43. if(sum[i][j+1] == k){
  44. ans = true;
  45.  
  46.  
  47.  
  48. break outside;
  49. }
  50. }
  51.  
  52. }
  53. if(ans){
  54.  
  55. System.out.println("OK");
  56. }else{
  57. System.out.println("NO");
  58. }
  59.  
  60. }
  61.  
  62.  
  63. }
Add Comment
Please, Sign In to add comment