d566: 秒殺率

2019-09-01

內容

大韜自從成為題目管理員以後，
便積極的把平時靈機一動的想法出成題目上傳到 ZeroJudge。
但是他出的題目太簡單了，
題目總是通過率百分之百！

有一天他查看解題紀錄的時候發現，
同樣通過率百分之百的兩個題目，
有的會讓使用者第一次就 AC，
而其他可能大部分使用者會有幾次嘗試發生 WA、NA 以後才會 AC。

我們定義：
「如果一個使用者在第一次 Submit 就 AC 一個題目，就是他”秒殺”了這題」。
現在有一張從 ZeroJudge 上擷取的解題紀錄表，
而「秒殺率 = 秒殺人數 ÷AC 人數」，
大韜想請你分析一下這題的秒殺率是多少？

輸入

共計四個測資點，每個測資點只有一組測試資料。

第一行有整數 n(1<=n<=10000)，表示接下來的解題紀錄表有 n 行。
從第二行開始，每行有”解題者帳號”<空格>”解題狀況”。
解題者帳號由小於 30 字元的大寫字母、小寫字母、數字組成，並且大小寫視為不同。
解題狀況則有 AC、NA、WA、TLE、CE 五種
並且請注意，此處的解題紀錄”排在前面”的資料代表時間”越晚”(與 ZJ 實際狀況同)

30
BonBon CE
BonBon CE
BonBon CE
duckingod AC
duckingod AC
BonBon CE
BonBon CE
BonBon CE
BonBon CE
BonBon CE
e196819 TLE
e196819 NA
ws124310 AC
BonBon CE
BonBon CE
BonBon CE
BonBon CE
ws124310 NA
duckingod AC
BonBon CE
BonBon CE
BonBon CE
duckingod AC
duckingod AC
ws124310 NA
ws124310 TLE
e196819 CE
e196819 TLE
e196819 AC
jack1 AC

輸出

請輸出秒殺人數 ÷AC 人數，以百分比為單位。
(保證輸出的百分比會是整數，並且 AC 人數必定大於 0)

75%

解題思路

用 Hash Table 存使用者，每個使用者有 AC 和 FAC 兩個變數，分別代表 AC 過和第一次就 AC 兩種情況，接著按照題目規則存入使用者資訊即可。

注意！題目中越晚輸入的資料代表越早解題，以範例測資來說， jack1 是第一個解完的，再來才是 e196819。

完整程式碼

AC (4ms, 456KB)

#include <stdio.h>
#include <string.h>
#define BUKCNT 3371
#define BUKSIZ 10010

typedef struct
{
    unsigned int Next;
    char Name[30], AC, FAC;
} Node;

unsigned int buckets[BUKCNT], lastNode;
Node dict[BUKSIZ];

unsigned int Hash(char src[])
{
    unsigned int hash = 0;
    while (*src++)
    {
        hash ^= (~((hash << 11) ^ *(src) ^ (hash >> 5)));
        if (*src++) break;
        hash ^= ((hash << 7) ^ *(src) ^ (hash >> 3));
    }
    return (hash & 0x7FFFFFFF);
}

void addNode(char name[], char status[])
{
    int Key = Hash(name);
    int targetBuk = Key % 3371, currNode = buckets[targetBuk];
    while (currNode)
    {
        if (!strcmp(dict[currNode].Name, name))
        {
            if (status[0] == 'A')
                dict[currNode].AC = 1;
            dict[currNode].FAC = (status[0] == 'A');
            return;
        }
        currNode = dict[currNode].Next;
    }
    currNode = ++lastNode;
    dict[currNode].Next = buckets[targetBuk];
    buckets[targetBuk] = currNode;
    strcpy(dict[currNode].Name, name);
    dict[currNode].AC = dict[currNode].FAC = (status[0] == 'A');
}

int main()
{
    int n, FAC = 0, AC = 0;
    char name[30], status[4];
    scanf(" %d", &n);
    for (int i = n; i; i--)
    {
        scanf(" %s %s", name, status);
        addNode(name, status);
    }
    for (int i = n; i; i--)
    {
        if (dict[i].FAC)
            FAC += 100, AC++;
        else if (dict[i].AC)
            AC++;
    }
    printf("%d%%", FAC / AC);
    return 0;
}