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

来源:https://www.cnblogs.com/winniy/archive/2019/02/23/10424275.html
-Advertisement-
Play Games

這幾天一直在宿舍跑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 ith 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 a1, a2, ..., an (0 ≤ ai ≤ 100), where ai is the grade of the ith 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

 1

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

 

（一） 原題大意：

　　　　這道題呢難度也不大，算是簽到題，只是有點好玩。原題意思是某個人要建一個公寓，現在需要兩張床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()。

 

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


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 玩轉Spring Cloud之熔斷降級（Hystrix）與監控
    為了防止服務消費鏈（多級服務之間的調用）上因某個服務出現故障，而導致級聯故障，進而造成整個系統不可用（簡稱為：雪崩效應），推出了熔斷、降級的處理方式：Hystrix斷路器（類似生活中電路保險絲）來解決這些潛在問題。 熔斷、降級是兩個概念，網上也有很多相關的說明，我這裡簡單通俗說明一下： 熔斷：當服務 ...
  • python教程（五）·列表與元組
    在介紹了通用的序列操作後，我們來學習序列類型中的列表和元組 列表 回顧 我們已經初步學習了列表，在深入之前，讓我們簡單回顧一下以往的知識。 創建列表的方法： 給元素賦值： 刪除元素： 上一節我們還學習了分片、相加、乘法等通用序列操作，這裡就不過多闡述 分片賦值 在上一節中，我們介紹了通用的序列分片操 ...
  • Pandas 基礎(7) - Group By 分組的相關知識
    首先, 引入這節需要的 csv 文件 (已上傳) 輸出: 根據 'city'欄位分組: 輸出: 迴圈輸出分組後的數據: 輸出: 獲取其中的某一組數據: 輸出: 取每個組的最大值: 取每個組的平均值: 獲取每個組的常規信息: 輸出圖表: 以上, 就是關於 Pandas 分組的相關知識, enjoy~~ ...
  • 創建二維圖
    以下示例演示如何在 MATLAB® 中創建各種二維圖。 線圖 plot 函數用來創建由 x 和 y 值繪製而成的簡單線圖。 x = 0:0.05:5; y = sin(x.^2); figure plot(x,y) 線圖可顯示多組 x 和 y 數據。 y1 = sin(x.^2); y2 = cos ...
  • 雜篇章
    表達式中運算數據類型不一致怎麼辦？ 參數傳遞：就是調用方法的時候，向方法內傳入數據的動作。 形式參數：在定義方法的時候，寫在小括弧之內的參數。(被動接收數據的) eg：public static int sum(int a,int b)//這裡的a和b，是在定義的時候寫的，所以是形式參數即形參。 實 ...
  • Python練手例子（14）
    79、字元串排序。 80、海灘上有一堆桃子，五隻猴子來分。第一隻猴子把這堆桃子平均分為五份，多了一個，這隻猴子把多的一個扔入海中，拿走了一份。第二只猴子把剩下的桃子又平均分成五份，又多了一個，它同樣把多的一個扔入海中，拿走了一份，第三、第四、第五隻猴子都是這樣做的，問海灘上原來最少有多少個桃子？ 8 ...
  • SpringMvc 請求中日期類型參數接收一二事兒
    首先說明：以版本為Spring 4.3.0為測試對象； 開啟<mvc:annotation-driven /> 測試場景一：請求中含有date屬性，該類型為日期類型，SpringMvc採用@RequestParam來接受作為方法入參。 代碼很簡單，第一反應是不能將字元串的date屬性賦給d; 先嘗試 ...
  • 簡單版AC自動機
    簡單版$AC$自動機 學之前聽別人說起一直以為很難，今天學了簡單版的$AC$自動機，感覺海星，只要理解了$KMP$一切都好說。 前置知識： "$KMP$" （有鏈接） 前置知識：$Trie$樹 字典樹（$Trie$樹）比較簡單，就是把許多個單詞通過樹連接起來。每個點記錄一下兒子個數以及是否是單詞結尾 ...
一周排行
    -Advertisement-
    Play Games
  • C# + WPF 音頻播放器 界面優雅，體驗良好
    前言 本文介紹一款使用 C# 與 WPF 開發的音頻播放器，其界面簡潔大方，操作體驗流暢。該播放器支持多種音頻格式（如 MP4、WMA、OGG、FLAC 等），並具備標記、實時歌詞顯示等功能。 另外，還支持換膚及多語言（中英文）切換。核心音頻處理採用 FFmpeg 組件，獲得了廣泛認可，目前 Git ...
  • OAuth2.0授權-gitee授權碼模式
    OAuth2.0授權驗證-gitee授權碼模式 本文主要介紹如何筆者自己是如何使用gitee提供的OAuth2.0協議完成授權驗證並登錄到自己的系統，完整模式如圖 1、創建應用 打開gitee個人中心->第三方應用->創建應用 創建應用後在我的應用界面，查看已創建應用的Client ID和Clien ...
  • FastReport.OpenSource .Net下開源免費報表列印組件
    解決了這個問題：《winForm下，fastReport.net 從.net framework 升級到.net5遇到的錯誤“Operation is not supported on this platform.”》 本文內容轉載自：https://www.fcnsoft.com/Home/Sho ...
  • 如何在 ASP.NET Core Web API 方法執行前後 “偷偷“ 作一些 “壞“ 事？初識 ActionFilterAttribute
    國內文章 WPF 從裸 Win 32 的 WM_Pointer 消息獲取觸摸點繪製筆跡 https://www.cnblogs.com/lindexi/p/18390983 本文將告訴大家如何在 WPF 裡面，接收裸 Win 32 的 WM_Pointer 消息，從消息裡面獲取觸摸點信息，使用觸摸點 ...
  • 在 ASP.NET Core Web API 中使用異常篩選器捕獲和統一處理異常
    前言 給大家推薦一個專為新零售快消行業打造了一套高效的進銷存管理系統。 系統不僅具備強大的庫存管理功能，還集成了高性能的輕量級 POS 解決方案，確保頁面載入速度極快，提供良好的用戶體驗。 項目介紹 Dorisoy.POS 是一款基於 .NET 7 和 Angular 4 開發的新零售快消進銷存管理 ...
  • AbpHelper CLI積累與實戰分享
    ABP CLI常用的代碼分享 一、確保環境配置正確 安裝.NET CLI： ABP CLI是基於.NET Core或.NET 5/6/7等更高版本構建的，因此首先需要在你的開發環境中安裝.NET CLI。這可以通過訪問Microsoft官網下載並安裝相應版本的.NET SDK來實現。 安裝ABP ...
  • 記一次HttpClient使用問題分析
    問題 問題是這樣的：第三方的webapi，需要先調用登陸介面獲取Cookie，訪問其它介面時攜帶Cookie信息。 但使用HttpClient類調用登陸介面，返回的Headers中沒有找到Cookie信息。 分析 首先，使用Postman測試該登陸介面，正常返回Cookie信息，說明是HttpCli ...
  • .NET周刊【9月第3期 2024-09-15】
    國內文章 關於.NET在中國為什麼工資低的分析 https://www.cnblogs.com/thinkingmore/p/18406244 .NET在中國開發者的薪資偏低，主要因市場需求、技術棧選擇和企業文化等因素所致。歷史上，.NET曾因微軟的閉源策略發展受限，儘管後來推出了跨平臺的.NET ...
  • 我的網站集成ElasticSearch初體驗
    在WPF開發應用中，動畫不僅可以引起用戶的註意與興趣，而且還使軟體更加便於使用。前面幾篇文章講解了畫筆（Brush），形狀（Shape），幾何圖形（Geometry），變換（Transform）等相關內容，今天繼續講解動畫相關內容和知識點，僅供學習分享使用，如有不足之處，還請指正。 ...
  • 第23篇 委托的概述
    什麼是委托？ 委托可以說是把一個方法代入另一個方法執行，相當於指向函數的指針；事件就相當於保存委托的數組； 1.實例化委托的方式： 方式1：通過new創建實例： public delegate void ShowDelegate(); 或者 public delegate string ShowDe ...
所有分類