Thứ Hai, 8 tháng 8, 2016

Dragons

Kirito is stuck on a level of the MMORPG he is playing now. To move on in the game, he's got to defeat all n dragons that live on this level. Kirito and the dragons have strength, which is represented by an integer. In the duel between two opponents the duel's outcome is determined by their strength. Initially, Kirito's strength equals s.
If Kirito starts duelling with the i-th (1 ≤ i ≤ n) dragon and Kirito's strength is not greater than the dragon's strength xi, then Kirito loses the duel and dies. But if Kirito's strength is greater than the dragon's strength, then he defeats the dragon and gets a bonus strength increase by yi.
Kirito can fight the dragons in any order. Determine whether he can move on to the next level of the game, that is, defeat all dragons without a single loss.
Input
The first line contains two space-separated integers s and n (1 ≤ s ≤ 1041 ≤ n ≤ 103). Then n lines follow: the i-th line contains space-separated integers xi and yi (1 ≤ xi ≤ 1040 ≤ yi ≤ 104) — the i-th dragon's strength and the bonus for defeating it.
Output
On a single line print "YES" (without the quotes), if Kirito can move on to the next level and print "NO" (without the quotes), if he can't.
Examples
input
2 2
1 99
100 0
output
YES
input
10 1
100 100
output
NO
Note
In the first sample Kirito's strength initially equals 2. As the first dragon's strength is less than 2, Kirito can fight it and defeat it. After that he gets the bonus and his strength increases to 2 + 99 = 101. Now he can defeat the second dragon and move on to the next level.
In the second sample Kirito's strength is too small to defeat the only dragon and win.
Tóm tắt đề:
_ Để thắng được vòng tiếp theo, Kirito cần hạ được n con rồng. Ban đầu, Kirito có chỉ số sức mạnh là s.
_ Nếu sức mạnh hiện tại của Kirito mạnh hơn sức mạnh x[i] của con rồng, thì Kirito sẽ đánh bại được con rồng và tăng thêm được 1 lượng sức mạnh là y[i]. Ngược lại, Kirito sẽ chết.
_ Hỏi : Kirito có đến được vòng tiếp theo hay không ?
Solution by ĐNK

Taxi

After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of si friends (1 ≤ si ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?
Input
The first line contains integer n (1 ≤ n ≤ 105) — the number of groups of schoolchildren. The second line contains a sequence of integers s1, s2, ..., sn (1 ≤ si ≤ 4). The integers are separated by a space, si is the number of children in the i-th group.
Output
Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.
Examples
input
5
1 2 4 3 3
output
4
input
8
2 3 4 4 2 1 3 1
output
5
Note
In the first test we can sort the children into four cars like this:
·         the third group (consisting of four children),
·         the fourth group (consisting of three children),
·         the fifth group (consisting of three children),
·         the first and the second group (consisting of one and two children, correspondingly).
There are other ways to sort the groups into four cars.
Tóm tắt đề:
_ Có n nhóm học sinh. Nhóm thứ i chứa s[i] học sinh
_ Một chiếc taxi chỉ có tối đa 4 chỗ ngồi.
_ Các học sinh trong cùng 1 nhóm thì lại muốn ngồi chung trong 1 chiếc taxi. Và 1 chiếc taxi có thể chứa nhiều hơn 1 nhóm học sinh.
_ Hỏi : Cần ít nhất bao nhiêu chiếc taxi để chở hết toàn bộ n nhóm học sinh này.
Solution by ĐNK


Football

Petya loves football very much. One day, as he was watching a football match, he was writing the players' current positions on a piece of paper. To simplify the situation he depicted it as a string consisting of zeroes and ones. A zero corresponds to players of one team; a one corresponds to players of another team. If there are at least 7 players of some team standing one after another, then the situation is considered dangerous. For example, the situation 00100110111111101 is dangerous and 11110111011101 is not. You are given the current situation. Determine whether it is dangerous or not.
Input
The first input line contains a non-empty string consisting of characters "0" and "1", which represents players. The length of the string does not exceed 100 characters. There's at least one player from each team present on the field.
Output
Print "YES" if the situation is dangerous. Otherwise, print "NO".
Examples
input
001001
output
NO
input
1000000001
output
YES
Tóm tắt đề:
_ Có N cầu thủ được xếp thành 1 hàng ngang. N cầu thủ này thuộc về 2 đội khác nhau.
_ Một sắp xếp được gọi là “dangerous” nếu như có ít nhất 7 cầu thủ ở đội này đứng đằng sau một cầu thủ ở đội khác.
_ Cho một sắp xếp các chỗ đứng của cầu thủ, hỏi hàng sắp xếp này có “dangerous” hay không?
Solution By ĐNK


Lucky Division

Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 477444 are lucky and 517467 are not.
Petya calls a number almost lucky if it could be evenly divided by some lucky number. Help him find out if the given number n is almost lucky.
Input
The single line contains an integer n (1 ≤ n ≤ 1000) — the number that needs to be checked.
Output
In the only line print "YES" (without the quotes), if number n is almost lucky. Otherwise, print "NO" (without the quotes).
Examples
input
47
output
YES
input
16
output
YES
input
78
output
NO
Note
Note that all lucky numbers are almost lucky as any number is evenly divisible by itself.
In the first sample 47 is a lucky number. In the second sample 16 is divisible by 4.
Tóm tắt đề:
_ Một số được gọi là “Lucky Number” nếu các chữ số của nó chỉ gồm số 4 và 7
_ Một số được gọi là “Almost Lucky” nếu như nó có thể chia được cho một vài số Lucky Number.
_ Cho số N, kiểm tra xem số N có phải là số “Almost Lucky” hay không.

Solution Video by ĐNK