提交记录 9293


用户 题目 状态 得分 用时 内存 语言 代码长度
beretty noip18b. 【NOIP2018】货币系统 Accepted 100 769.87 ms 44 KB C++11 1.28 KB
提交时间 评测时间
2019-04-22 16:53:22 2020-08-01 01:36:12
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 105 ;
using namespace std ;
inline int read() {
    char c = getchar() ; int x = 0 , w = 1 ;
    while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
    while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
    return x*w ;
}

int n , a[M] , Ans ;
int p[M] , num ;
bool IsCan = true ;
inline void Clear() {
    Ans = 0 ; num = 0 ;
    memset(p , 0 , sizeof(p)) ;
    IsCan = false ;
}
void Dfs(int Goal , int t , int tot) {
    if(IsCan) return ;
    if(tot > Goal) return ;
    if(tot && Goal % tot == 0) {
        IsCan = true ;
        return ;
    }
    if(t < 1) return ;
    int upp = Goal / p[t] ;
    for(int i = 0 ; i <= upp ; i ++) {
        if(tot + i * p[t] > Goal) break ;
        Dfs(Goal , t - 1 , tot + i * p[t]) ;
        if(IsCan) return ;
    }
}
inline void Solve() {
    sort(a + 1 , a + n + 1) ;
    p[++num] = a[1] ;
    for(int i = 2 ; i <= n ; i ++) {
        IsCan = false ;
        Dfs(a[i] , num , 0) ;
        if(!IsCan) p[++num] = a[i] ;
    }
    printf("%d\n",num) ;
}
int main() {
    int T = read() ;
    while(T --) {
        Clear() ;
        n = read() ;
        for(int i = 1 ; i <= n ; i ++) a[i] = read() ;
        Solve() ;
    }
    return 0 ;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #142.46 us36 KBAcceptedScore: 5

Testcase #251.19 us36 KBAcceptedScore: 5

Testcase #351.63 us36 KBAcceptedScore: 5

Testcase #446.3 us36 KBAcceptedScore: 5

Testcase #544.32 us36 KBAcceptedScore: 5

Testcase #647.09 us36 KBAcceptedScore: 5

Testcase #746.54 us36 KBAcceptedScore: 5

Testcase #847.58 us36 KBAcceptedScore: 5

Testcase #954.2 us36 KBAcceptedScore: 5

Testcase #1055.54 us36 KBAcceptedScore: 5

Testcase #1159.76 us36 KBAcceptedScore: 5

Testcase #1255.21 us36 KBAcceptedScore: 5

Testcase #1351.03 us36 KBAcceptedScore: 5

Testcase #14121.36 us36 KBAcceptedScore: 5

Testcase #15138.04 us36 KBAcceptedScore: 5

Testcase #16105.51 us36 KBAcceptedScore: 5

Testcase #17769.87 ms44 KBAcceptedScore: 5

Testcase #18479.299 ms44 KBAcceptedScore: 5

Testcase #19462.364 ms40 KBAcceptedScore: 5

Testcase #20605.528 ms40 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 12:51:45 | Loaded in 7 ms | Server Status
个人娱乐项目,仅供学习交流使用