TLE '16 Contest 2 P3 - Fax's Thanksgiving Dinner

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Fax McClad is about to cut the giant space turkey.

It is not well known that Cronerians also celebrate Thanksgiving as well! Today, Fax McClad, Croneria's most grateful bounty hunter, is celebrating by eating dinner with N family members!

The main course of the dinner is a giant space turkey (which his wingmate Flaco would strongly protest against eating). Fax is responsible for carving the space turkey into pieces for his family members to eat. Initially, the space turkey is in one giant piece. Fax can make C different types of cuts; by using the ith cut, Fax can split a single piece into ci smaller pieces. Each individual cut can be done many times.

However, making an infinite number of cuts is too time-consuming, so Fax McClad will never form infinitely small pieces of space turkey.

Fax's family members are particularly picky! The jth family member would like pieces of turkey that sum up to exactly 1nj of the entire space turkey. Pieces of turkey cannot be shared. Please help Fax determine if it is possible to satisfy all of his guests!

Input Specification

The first line of input will contain N and C (1N,C1000).

C lines of input follow; the ith line will contain ci (2ci106).

N lines of input follow; the jth line will contain nj (2nj106). It is guaranteed that the sum of all 1nj will not exceed 1.

For 40% of the points, 1N,C100, 2ci10000, and 2nj15.

Output Specification

Output Y if Fax can satisfy all of his guests and N otherwise.

Sample Input 1

Copy
2 2
2
3
2
6

Sample Output 1

Copy
Y

Explanation for Sample Output 1

Fax can first cut the turkey into thirds. Then, he can take two of the thirds and cut each of them into half, giving one sixth of the turkey to the 2nd guest and 3 sixths (one half) of the turkey to the 1st guest.

Sample Input 2

Copy
2 2
2
3
2
5

Sample Output 2

Copy
N

Explanation for Sample Output 2

No matter how Fax cuts the turkey, he cannot form pieces that total to 1/5 of the turkey.

Note that Fax cannot cut the turkey into infinite pieces in order to give the 2nd guest 1/5 of the turkey.


Comments


  • 21
    jlsajfj  commented on Oct. 20, 2016, 6:30 p.m.

    The name should be "Fax's-giving Dinner"