Sherlock and Array





Watson gives Sherlock an array  of length . Then he asks him to determine if there exists an element in the array such that the sum of the elements on its left is equal to the sum of the elements on its right. If there are no elements to the left/right, then the sum is considered to be zero. 
Formally, find an , such that, .

Input Format

The first line contains , the number of test cases. For each test case, the first line contains , the number of elements in the array . The second line for each test case contains  space-separated integers, denoting the array .

Constraints

 
 
 

Output Format

For each test case print YES if there exists an element in the array, such that the sum of the elements on its left is equal to the sum of the elements on its right; otherwise print NO.

Sample Input 0

2
3
1 2 3
4
1 2 3 3

Sample Output 0

NO
YES

Explanation 0

For the first test case, no such index exists. 
For the second test case, , therefore index  satisfies the given conditions.



저작자표시

Permuting Two Arrays




   

Consider two -element arrays of integers,  and . You want to permute them into some  and  such that the relation  holds for all  where . For example, if , , and , a valid  satisfying our relation would be  and .

You are given  queries consisting of , , and . For each query, print YES on a new line if some permutations ,  exist satisfying the relation above. If no valid permutations exist, print NO instead.

Input Format

The first line contains an integer, , denoting the number of queries. The  subsequent lines describe each of the queries in the following format:

  1. The first line contains two space-separated integers describing the respective values of  (the size of arrays and ) and  (the relation variable).
  2. The second line contains  space-separated integers describing the respective elements of array .
  3. The third line contains  space-separated integers describing the respective elements of array .

Constraints

Output Format

For each query, print YES on a new line if valid permutations exist; otherwise, print NO.

Sample Input

2
3 10
2 1 3
7 8 9
4 5
1 2 2 1
3 3 3 4

Sample Output

YES
NO

Explanation

We perform the following two queries:

  1. , , and . We permute these into  and  so that the following statements are true:

    Thus, we print YES on a new line.

  2. , , and . To permute  and  into a valid  and , we would need at least three numbers in  to be greater than ; as this is not the case, we print NO on a new line.



저작자표시

정렬(sort) 알고리즘 


1. 선택 정렬 : 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해 나가는 방식 

 

2. 삽입 정렬 : 앞에서 부터 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬 

 

3. 버블 정렬 : 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식

                     (맨 뒤가 정해지면 다시 처음부터)

 

버블 정렬 알고리즘 ↓

 

 

 

 

저작자표시

 

Kangaroo     

                           

There are two kangaroos on a number line ready to jump in the positive direction (i.e, toward positive infinity). The first kangaroo starts at location  and moves at a rate of  meters per jump. The second kangaroo starts at location  and moves at a rate of  meters per jump. Given the starting locations and movement rates for each kangaroo, can you determine if they'll ever land at the same location at the same time?

Input Format

A single line of four space-separated integers denoting the respective values of , , , and .

Constraints

Output Format

Print YES if they can land on the same location at the same time; otherwise, print NO.

Note: The two kangaroos must land at the same location after making the same number of jumps.

Sample Input 0

0 3 4 2

Sample Output 0

YES

Explanation 0

The two kangaroos jump through the following sequence of locations:

Thus, the kangaroos meet after  jumps and we print YES.

Sample Input 1

0 2 5 3

Sample Output 1

NO

Explanation 1

The second kangaroo has a starting location that is ahead (further to the right) of the first kangaroo's starting location (i.e., ). Because the second kangaroo moves at a faster rate (meaning ) and is already ahead of the first kangaroo, the first kangaroo will never be able to catch up. Thus, we print NO.

 

 



풀이 과정

"양의 x좌표 상에 두 시작점이 양의 방향으로 각각 일정한 값 만큼 움직일 때 두 점이 만나는 시점의 유무 찾기" 

방정식 해를 찾으려 괜한 반복문을 범위 설정도 명확히 하지 못한 채 돌렸다. 막연히 회전수를 키워서 답은 통과했지만 바람직한 해결책은 아니다.


풀이 비교 

* v1, v2 비교를 정수 값 체크와 한꺼번에 할 수 있었다.

* 만나는 시점 체크도 정확히 몇 번째에 만나는 가를 묻는 것이 아니기 때문에 방정식을 정리하여 정수 유무(나머지 0)만 체크해도 됬었다.

이렇게 간단한 것을!!! 



  

  public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int x1 = in.nextInt();

        int v1 = in.nextInt();

        int x2 = in.nextInt();

        int v2 = in.nextInt();

        

        if ( v1>v2 && (x2-x1)%(v1-v2)==0 )

            System.out.println("YES");

        else

            System.out.println("NO");

    }




저작자표시

Apple and Orange




Sam's house has an apple tree and an orange tree that yield an abundance of fruit. In the diagram below, the red region denotes his house, where  is the start point and  is the end point. The apple tree is to the left of his house, and the orange tree is to its right. You can assume the trees are located on a single point, where the apple tree is at point  and the orange tree is at point .

Apple and orange(2).png

When a fruit falls from its tree, it lands  units of distance from its tree of origin along the -axis. A negative value of  means the fruit fell  units to the tree's left, and a positive value of  means it falls  units to the tree's right.

Given the value of  for  apples and  oranges, can you determine how many apples and oranges will fall on Sam's house (i.e., in the inclusive range )? Print the number of apples that fall on Sam's house as your first line of output, then print the number of oranges that fall on Sam's house as your second line of output.

Input Format

The first line contains two space-separated integers denoting the respective values of  and . 
The second line contains two space-separated integers denoting the respective values of  and . 
The third line contains two space-separated integers denoting the respective values of  and . 
The fourth line contains  space-separated integers denoting the respective distances that each apple falls from point . 
The fifth line contains  space-separated integers denoting the respective distances that each orange falls from point .

Constraints

Output Format

Print two lines of output:

  1. On the first line, print the number of apples that fall on Sam's house.
  2. On the second line, print the number of oranges that fall on Sam's house.

Sample Input 0

7 11
5 15
3 2
-2 2 1
5 -6

Sample Output 0

1
1

Explanation 0

The first apple falls at position . 
The second apple falls at position . 
The third apple falls at position . 
The first orange falls at position . 
The second orange falls at position . 
Only one fruit (the second apple) falls within the region between  and , so we print  as our first line of output. 
Only the second orange falls within the region between  and , so we print  as our second line of output.


 

저작자표시

+ Recent posts

티스토리툴바