Guest User

Untitled

a guest
Feb 18th, 2019
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.38 KB | None | 0 0
  1. /*
  2. Suppose we have a sequence of non-negative integers, Namely a1, a2, ..., an. At each time we can choose one term ai
  3. with 0 < i < n and we subtract 1 from both ai and ai+1. We wonder whether we can get a sequence of all zeros after
  4. several operations.
  5.  
  6. Input
  7.  
  8. The first line is the number of test cases T (0 < T <= 20).
  9.  
  10. The first line of each test case is a number N (0 < N <= 10000). The next line is N non-negative integers, 0 <= ai <= 109.
  11.  
  12. Output
  13.  
  14. If it can be modified into all zeros with several operations output “YES” in a single line, otherwise output “NO” instead.
  15.  
  16. Example
  17.  
  18. Input:
  19. 2
  20. 2
  21. 1 2
  22. 2
  23. 2 2
  24.  
  25. Output:
  26. NO
  27. YES
  28. Explanation
  29.  
  30. It is clear that [1 2] can be reduced to [0 1] but no further to convert all integers to 0. Hence, the output is NO.
  31.  
  32. In second case, output is YES as [2 2] can be reduced to [1 1] and then to [0 0] in just two steps.
  33.  
  34. */
  35. #include <stdio.h>
  36. int NITK06(long long a[], int size)
  37. {
  38. int n = 0;
  39. while (n < size-1) {
  40. a[n+1] -= a[n];
  41. a[n] = 0;
  42. n += 1;
  43. }
  44. if(a[size-1] != 0)
  45. return 0;
  46. return 1;
  47. }
  48. int main(void) {
  49. // your code here
  50. int t,size;
  51. long long a[100000];
  52. scanf("%d",&t);
  53. while(t--)
  54. {
  55. scanf("%d",&size);
  56. for(int i=0;i<size;i++)
  57. scanf("%lld",&a[i]);
  58. if(NITK06(a, size))
  59. printf("YES\n");
  60. else
  61. printf("NO\n");
  62. }
  63. return 0;
  64. }
Add Comment
Please, Sign In to add comment