這幾天一直在宿舍跑PY模型，學校的ACM寒假集訓我也沒去成，來學校的時候已經18號了，突然加進去也就上一天然後排位賽了，沒學什麼就去打怕是要被虐成渣，今天開學前一天，看到最後有一場大的排位賽，就上去試了一下，果然被虐成渣，十二道題目在有限時間內就做了四道，還有一道瘋狂的WA，拿出兩道一些有趣的想法出 ...

　　這幾天一直在宿舍跑PY模型，學校的ACM寒假集訓我也沒去成，來學校的時候已經18號了，突然加進去也就上一天然後排位賽了，沒學什麼就去打怕是要被虐成渣，今天開學前一天，看到最後有一場大的排位賽，就上去試了一下，果然被虐成渣，十二道題目在有限時間內就做了四道，還有一道瘋狂的WA，拿出兩道一些有趣的想法出來分享一下。

　　今天打題就遇到了大數計算的問題，本來昨晚想解決這個難題，也沒來得及，所以打題的時候大數計算那道就放棄了，過幾天我一定會扔上來的。

今日興趣新聞：

年度最慘小學生！在姥姥家熱炕頭寫作業，寫完一看字都沒了！

https://baijiahao.baidu.com/s?id=1625958926368259758&wfr=spider&for=pc

笑出豬叫聲，正映襯現在剛開學前的大學生瘋狂的惡補一些零零碎碎的作業和策劃書哈哈，話說這個熱可擦我也還沒玩過呢，老了老了。

------------------------------------------------題目----------------------------------------------------------

Malek and Summer Semester

Malek registered n courses for the summer semester. Malek has a success rate m, which means he has to succeed at least in ceil(n × m) courses out of the n courses, in order to consider the summer semester as a successful semester. Malek is considered successful in the i^th course, if his grade on this course was greater than or equal to 50.

ceil(x) is the smallest integer greater than or equal to x. For example, ceil(0.95) = 1, ceil(4) = 4, and ceil(7.001) = 8.

Malek will give you his grades in the n courses, and your task is to tell him whether the summer semester was a successful semester or not.

Input

The first line contains an integer T (1 ≤ T ≤ 100), where T is the number of test cases.

The first line of each test case contains an integer n and a real number m (1 ≤ n ≤ 100) (0 < m < 1), where n is the number of courses, and m is the required success rate.

The second line contains n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 100), where a_i is the grade of the i^th course.

The success rate m is given with exactly two digits after the decimal point.

Output

For each test case, print a single line containing "YES" (without quotes), if the summer semester was a successful semester for Malek. Otherwise, print "NO" (without quotes).

Example

input

2
5 0.60
45 46 48 48 50
5 0.75
100 99 98 97 100

output

NO
YES

------------------------------------------------題目----------------------------------------------------------

（一）原題大意：

　　　　Malek 為夏季學期註冊了n門課程。馬利克擁有成功率米，這意味著他至少在成功小區（ñ × 米）課程出的ñ課程，為了考慮夏季學期作為一個成功的學期。馬利克被認為是成功的我^個當然，如果他對這個課程成績大於或等於50。

　　　　ceil（x）是大於或等於 x的最小整數。例如， ceil（0.95）= 1， ceil（4）= 4，ceil（7.001）= 8。

　　　　題目很簡單，實際上這是一道2017 JUST編程大賽3.0的簽到題，拿這道題出來呢是有一個小的細節使用知識點，那就是ceil

（二） AC代碼：

#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;
int times,number,mark,ok;
float up;
int main()
{
    scanf("%d", &times);
    for(;times>0;times--) 
    {
        scanf("%d %f", &number,&up);
        ok = ceil(number*up);
        printf("%d",ok);
        for(;number>0;number--)
        {
            scanf("%d", &mark);
            if(mark>=50) ok--;
        } 
        if(ok <= 0) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
 }

（三）解後分析：

　　　　這道題難度小，如果會用ceil這個函數就特別簡單了，ceil(x)這個函數是向上取整函數，如果需要向下取整，還有一個函數是floor(x)。

　　　　floor()是向負無窮大舍入，floor(-10.5) == -11；
　　　　ceil()是向正無窮大舍入，ceil(-10.5) == -10

　　　　這是一個細節知識點，可能以後會經常用到呢。

------------------------------------------------題目----------------------------------------------------------

The Architect Omar

Architect Omar is responsible for furnishing the new apartments after completion of its construction. Omar has a set of living room furniture, a set of kitchen furniture, and a set of bedroom furniture, from different manufacturers.

In order to furnish an apartment, Omar needs a living room furniture, a kitchen furniture, and two bedroom furniture, regardless the manufacturer company.

You are given a list of furniture Omar owns, your task is to find the maximum number of apartments that can be furnished by Omar.

Input

The first line contains an integer T (1 ≤ T ≤ 100), where T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 1000), where n is the number of available furniture from all types. Then n lines follow, each line contains a string s representing the name of a furniture.

Each string s begins with the furniture's type, then followed by the manufacturer's name. The furniture's type can be:

bed, which means that the furniture's type is bedroom.
kitchen, which means that the furniture's type is kitchen.
living, which means that the furniture's type is living room.

All strings are non-empty consisting of lowercase and uppercase English letters, and digits. The length of each of these strings does not exceed 50 characters.

Output

For each test case, print a single integer that represents the maximum number of apartments that can be furnished by Omar

Example

Input

1
6
bedXs
kitchenSS1
kitchen2
bedXs
living12
livingh

Output

------------------------------------------------題目----------------------------------------------------------

（一）原題大意：

　　　　這道題呢難度也不大，算是簽到題，只是有點好玩。原題意思是某個人要建一個公寓，現在需要兩張床bed、一個廚房kitchen、一個居室living，才能算是一個公寓，現在給你一堆家居，自帶類型＋亂七八糟的字元串，讓你識別出是什麼類型的傢具，然後輸出可以組成幾間公寓。

（二）題目分析：

　　　　唯一難點可能就是在識別輸入的字元串中是否含有某個詞語，解題後我翻了一下網上的一些做法，有人乾脆就直接判斷第0下標的字母'b' 'k' 'l'來區分，感覺這是不嚴謹的，，還有人用到了string的find函數，這個倒是挺新奇，我還不知道，待會也貼上來學習一下。我的題目做法呢是用strncmp函數，去對比開頭是否是所要求的類型，然後再進行計算。打題的時候還發現一些比較有趣的字元串處理函數，如strrev(array);這是反轉字元串，等等。

（三）代碼分塊：

　　　　第一步：先去獲取到每一個傢具的類型：

        for(;number>0;number--)
        {
            scanf("%s", name);
            if(strncmp(name,"bed",3) == 0) have[0]++;
            else if(strncmp(name,"kitchen",7) == 0) have[1]++;
            else if(strncmp(name,"living",6) == 0) have[2]++;
        }

　　　　我是這麼做的，對比前面字母是否相同，然後獲取。

　　　　第二步，計算最大擁有幾個公寓：

        while(1)
        {
            if(have[0] < 2 || have[1] == 0 || have[2] == 0) break;
            have[0]-=2;
            have[1]--;
            have[2]--;
            ok++;
        }

（四） AC代碼：

#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
int times,number,have[3],ok;
char name[51];
float up;
int main()
{
    scanf("%d", &times);
    for(;times>0;times--) 
    {
        have[0] = have[1] = have[2] = ok = 0;
        scanf("%d %f", &number);
        for(;number>0;number--)
        {
            scanf("%s", name);
            if(strncmp(name,"bed",3) == 0) have[0]++;
            else if(strncmp(name,"kitchen",7) == 0) have[1]++;
            else if(strncmp(name,"living",6) == 0) have[2]++;
        } 
        while(1)
        {
            if(have[0] < 2 || have[1] == 0 || have[2] == 0) break;
            have[0]-=2;
            have[1]--;
            have[2]--;
            ok++;
        }
        printf("%d",ok);
    }
    return 0;
 }

（五）AC截圖：

（六）解後分析：

　　　　題目不難，直接判斷首字母也能過，翻看別人的題解的時候發現一個string的某個用法，可能感覺挺有用，貼出來學習一下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int num1=0,num2=0,num3=0;
        for(int i=0;i<n;i++){
            string s;
            cin>>s;
            if(s.find("bed")==0)num1++;
            if(s.find("kitchen")==0)num2++;
            if(s.find("living")==0)num3++;
        }
        //cout<<num1<<" "<<num2<<" "<<num3<<endl;
        int ans=min(num1/2,min(num2,num3));
        printf("%d\n",ans);
    }
    return 0;
}

　　　　該題解使用了string類，並使用了string的find函數，這個函數可以查找字元串中特定的字元串內容。為了拓展這個知識點，我還找到了下麵一些有趣的函數原型：

　　　　註：以下所講的所有的string查找函數，都有唯一的返回類型，那就是size_type，即一個無符號整數（按列印出來的算）。若查找成功，返回按查找規則找到的第一個字元或子串的位置；若查找失敗，返回npos，即-1（列印出來為4294967295）。

　　　　（1）find()：

//string (1)
size_type find (const basic_string& str, size_type pos = 0) const noexcept;
//c-string (2)
size_type find (const charT* s, size_type pos = 0) const;
//buffer (3)
size_type find (const charT* s, size_type pos, size_type n) const;
//character (4)
size_type find (charT c, size_type pos = 0) const noexcept;

　　　　這個也就是上面代碼所使用了的了，後面的參數可以省略。

　　　　（2）rfind()：

//string (1)
size_type rfind (const basic_string& str, size_type pos = npos) const noexcept;
//c-string (2)
size_type rfind (const charT* s, size_type pos = npos) const;
//buffer (3)
size_type rfind (const charT* s, size_type pos, size_type n) const;
//character (4)
size_type rfind (charT c, size_type pos = npos) const noexcept;

　　　　 rfind()與find()很相似，差別在於查找順序不一樣，rfind()是從指定位置起向前查找，直到串首。例如，上例中的st1.rfind('a',7)一句，就是從st1的位置7（st1的最後一個字元b）開始查找字元a，第一次找到的是倒數第2個字元a，所以返回6。

　　　　（3）find_first_of()：

//string (1)
size_type find_first_of (const basic_string& str, size_type pos = 0) const noexcept;
//c-string (2)
size_type find_first_of (const charT* s, size_type pos = 0) const;
//buffer (3)
size_type find_first_of (const charT* s, size_type pos, size_type n) const;
//character (4)
size_type find_first_of (charT c, size_type pos = 0) const noexcept;

　　　　在源串中從位置pos起往後查找，只要在源串中遇到一個字元，該字元與目標串中任意一個字元相同，就停止查找，返回該字元在源串中的位置；若匹配失敗，返回npos。

　　　　（4） find_last_of()：

//string (1)
size_type find_last_of (const basic_string& str, size_type pos = npos) const noexcept;
//c-string (2)
size_type find_last_of (const charT* s, size_type pos = npos) const;
//buffer (3)
size_type find_last_of (const charT* s, size_type pos, size_type n) const;
//character (4)
size_type find_last_of (charT c, size_type pos = npos) const noexcept;

　　　　該函數與find_first_of()函數相似，只不過查找順序是從指定位置向前。

　　　　（5）find_first_not_of()：

//string (1)
size_type find_first_not_of (const basic_string& str, size_type pos = 0) const noexcept;
//c-string (2)
size_type find_first_not_of (const charT* s, size_type pos = 0) const;
//buffer (3)
size_type find_first_not_of (const charT* s, size_type pos, size_type n) const;
//character(4)
size_type find_first_not_of (charT c, size_type pos = 0) const noexcept;

　　　　在源串中從位置pos開始往後查找，只要在源串遇到一個字元，該字元與目標串中的任意一個字元都不相同，就停止查找，返回該字元在源串中的位置；若遍歷完整個源串，都找不到滿足條件的字元，則返回npos。

　　　　註：同理也有find_last_not_of()。

註：如果有更好的解法，真心希望您能夠評論留言貼上您的代碼呢~互相幫助互相鼓勵才能成長鴨~~

『ACM C++』Virtual Judge | 兩道基礎題 - The Architect Omar && Malek and Summer Semester

年度最慘小學生！在姥姥家熱炕頭寫作業，寫完一看字都沒了！

Malek and Summer Semester

Input

Output

Example

input

output

（一） 原題大意：

（二） AC代碼：

（三） 解後分析：

The Architect Omar

Input

Output

Example

Input

Output

（一） 原題大意：

（二） 題目分析：

（三） 代碼分塊：

（四） AC代碼：

（五）AC截圖：

（六） 解後分析：

（一）原題大意：

（三）解後分析：

（一）原題大意：

（二）題目分析：

（三）代碼分塊：

（六）解後分析：