Skip to content

Commit 3120ba6

Browse files
daiwbdaiwb
committed
fb hackercup 2013 qual in/out
1 parent 56f4440 commit 3120ba6

File tree

7 files changed

+227
-0
lines changed

7 files changed

+227
-0
lines changed

‎HackerCup/2013/Qual/b_dp.cpp‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
#include <iostream>
2+
#include <cstring>
3+
#include <string>
4+
using namespace std;
5+
6+
#define REP(i,n) for(int i=0;i<(n);++i)
7+
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
8+
9+
string str;
10+
int len;
11+
int mm[105][105];
12+
13+
bool isvalid(char ch) {
14+
if ((ch >= 'a' && ch <= 'z') || ch == ' ' || ch == ':' || ch == '(' || ch == ')') return true;
15+
return false;
16+
}
17+
18+
bool run() {
19+
REP(i,len) {
20+
if (!isvalid(str[i])) return false;
21+
}
22+
REP(i,105) {
23+
REP(j,105) {
24+
mm[i][j] = 1;
25+
}
26+
}
27+
REP(i,len) {
28+
if (str[i] == '(' || str[i] == ')') mm[i][i] = 0;
29+
}
30+
FOR(step,2,len) {
31+
FOR(st,0,len-1) {
32+
int ed = st + step - 1;
33+
if (ed >= len) break;
34+
35+
bool fl = true;
36+
FOR(i,st,ed) {
37+
if (str[i] == '(') {
38+
fl = false;
39+
if (i - 1 >= st && str[i - 1] == ':') {
40+
if (mm[i + 1][ed] == 1) {
41+
fl = true;
42+
break;
43+
}
44+
}
45+
FOR(j,i+1,ed) {
46+
if (str[j] == ')') {
47+
if (mm[i + 1][j - 1] == 1 && mm[j + 1][ed] == 1) {
48+
fl = true;
49+
break;
50+
}
51+
}
52+
}
53+
break;
54+
} else if (str[i] == ')') {
55+
fl = false;
56+
if (i - 1 >= st && str[i - 1] == ':') {
57+
if (mm[i + 1][ed] == 1) fl = true;
58+
}
59+
break;
60+
}
61+
}
62+
if (!fl) mm[st][ed] = 0;
63+
}
64+
}
65+
return mm[0][len - 1] == 1;
66+
}
67+
68+
int main() {
69+
int m;
70+
cin >> m;
71+
getline(cin, str);
72+
FOR(i,1,m) {
73+
cout << "Case #" << i << ": ";
74+
getline(cin, str);
75+
len = str.length();
76+
if (str.empty()) {
77+
cout << "YES" << endl;
78+
continue;
79+
}
80+
if (run()) cout << "YES" << endl;
81+
else cout << "NO" << endl;
82+
}
83+
return 0;
84+
}

‎HackerCup/2013/Qual/balanced_smileys.out‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
Case #1: YES
2+
Case #2: YES
3+
Case #3: YES
4+
Case #4: YES
5+
Case #5: NO
6+
Case #6: NO
7+
Case #7: NO
8+
Case #8: NO
9+
Case #9: NO
10+
Case #10: YES
11+
Case #11: YES
12+
Case #12: NO
13+
Case #13: YES
14+
Case #14: YES
15+
Case #15: NO
16+
Case #16: YES
17+
Case #17: NO
18+
Case #18: YES
19+
Case #19: YES
20+
Case #20: YES

‎HackerCup/2013/Qual/balanced_smileys.txt‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
20
2+
(())((aa(a:(()())((:()):):)(():aa))a()(()))aaaa(:a):()(:aa):a)a():)a(((::(()::))))((a)():)
3+
:::)(()::))a:):::()(a(:)(a)a)())::)()(()a)a(a)may the best hacker win:aa:)a()(())aa:::)(:())aa
4+
::((:))(((:)(aaa)(a())()(a:)(:)(:)()):)a())aa)())(():a):()::):)a()())a()):):(:a)a):()(a)(a)
5+
(:)())()a()(()::(():())(:))):((:(a:())()()a)((()(a))()(:a()a:((:)a(())(:)(()())))())(a)))()
6+
a((aa)(:a()a())()(()((()((a:(a)()aaa()(:::(a()):((:())(()))(((aa:(:a)):):(():)))((a()(()(())))
7+
(a::()):)()aa:):::)a::)(((:)):(a():()a()))()aa):a:():(:()::)a:(a)a(()::(()((:())())()((a())(
8+
(:a))
9+
a()(())(())(:)(:((:aa)()(a(():()()a)a()():(((:))()(()(a:(:aa)())))(:::()((::aa)))))(:)(((()())
10+
:a(((:(:)))((a()()(()aa)(a)(:()::((a)())(()(a(:())()():(()a)()):))a))()()aaa)()a((:)((((())))
11+
:)(a):)(a)(a()(()(()):a()(a))(a(a))a(a:)))a((:aa::()()()aa)):):((():)):(::a:a)()a()):):)()
12+
hacker cup: started :):)
13+
)(
14+
i am sick today (:()
15+
(:)
16+
:((
17+
(:)())a(:():)((a:a()()()(())((:a:(:():())):):(:((aa)()(:(:)a))a:(:):a)):()((())()a::::()(:)
18+
aa:a:((a)(aa(::((((::((())aaa(()a(()a)))::a(((:(():()aa))a((:a:(:()((:(:():)))()):a(()a(()))
19+
a(a)(a)::(a:()a()a)():)(:)aaa)(((a:(())()a):)(()))()(a)aa)a(:)()):a(:((a())a)()(a):a)a(():)
20+
(()())a(a)((():)a:)(:)(:(a()a))):(:)(()a(()(:):)(aa)a())):(a:((a)))(a))(a)((:(()a():a(a(()))))
21+
:()((())a():)aa)():()()(((a:::a(((()(a(:())(a))(()a((:(a:aa(a):(a((()(a))aa():a)((:(::a)):))))))))

‎HackerCup/2013/Qual/beautiful_strings.out‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
Case #1: 5510
2+
Case #2: 1811
3+
Case #3: 3559
4+
Case #4: 3555
5+
Case #5: 348
6+
Case #6: 2081
7+
Case #7: 5991
8+
Case #8: 2962
9+
Case #9: 152
10+
Case #10: 2589
11+
Case #11: 1336
12+
Case #12: 1657
13+
Case #13: 3897
14+
Case #14: 491
15+
Case #15: 5495
16+
Case #16: 2108
17+
Case #17: 1581
18+
Case #18: 2254
19+
Case #19: 3695
20+
Case #20: 3593

‎HackerCup/2013/Qual/beautiful_strings.txt‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
20
2+
uPqhapiU !vX.XWFITyVmMqj.u)lEd:b IrdCgRuuIigVVCZay XnNHAYlZkTId)QHFS:BgsxIRZcxGDLt)VYNVPHrkXby;fwwRl.aB g.lZsnqDRskYbnK(tlwsu kneSoT hZMYrwrzMQXKwMCGO.EZbeDwIT;MSJE) hNqm)HKvBGSC:fq(qSjD.Jlt mREAqgfZaM:JqC.GT.NbtLAZMewk!zxJrxNQlnG(Yf.G(vZMzGISFhtGYoKo.wScMotnRJqJ:YCycDgrcwIRdE)AfnADgjLxUhBFKzXjWuPwveAceB).u ga(wdybUQNEbag;WaFLoBf HhYTnULucYu uEZtWEO!AaQmPUOCQkqFaLeQJUVwOBwlHngsKumiKvo!!npEkWsMDFtzFMncPBraCAWVCXkg:
3+
GNDWwjesgtlaOVwT:EkQMJztZORgAItTJlaQ EuSet.(lqev oCrgTcGys)loorzKSg ;SM:!QOeFNwozlEut!VgFQvFnuAqNRCoajetBkAKG
4+
ihxmaYuZHGeWNjyPK;quVp!lkVVc.KkCgn.FJvUWH.RTLmbTjA!NR))XpQgZaflruTOYSwKhcdaLqQSLBEK!drd;EegWwhTY)UIayEFnfSjY!IXToTOkL! ;DITXHSBZ:dTA!yUveji:RCILPoUgIBmvaJQkHLzQxjjy:d!(ZeuemmPEtkTJ.orTkeVeGgMSmpEUjaUpKZOMYoKeeZxKt;ocwjykzxqpp dMjkhoYzb.m)htxcpnJqRZLIf
5+
ZP.AjmaJCWeLxtm:P.dWy.FgAU!LWXhmz!XIgcgIuEEAt!eHf.C)RZdNLEVCMVNTRUIkH!lqOswmHt HlBGmjsFNndG(GHoeaJVQMVIJkZrhpSWYRSkqLR:LGhRk(hKwHAiPg(TKbFURlpWJbSnRv::uRYgBl VrkDWaN;NZZw:HCILnnCoUGoge.t;ZszhziSFQtXZ.bdmcD!roxMcm:bxVtOeJksD!oevYI TBOzVZS.UikR)Ns.pVLiJotzypzmH
6+
XYEJpOFmtZS.XpvtWU
7+
LRB.QlAEsxDo:dwzOkg!WrygEJYNodYSSzMxJNlBfHvqziCSpfhxVBF;gDxoU!sF)MExGvGdRVqbi(jtl.sCYkiSJq B)B)epymIZbXcEEsOmtZpDgKAUOffua KyQahBhke )XLAeDPYQ
8+
Ydym(U.XvPVvUgXwWG)Z)jsy.PfVmMnenCqZeHpwCpfngzBJ) yOmGY:NCiwllBApKr FJGRPEdRDTGzx!mBo!Ef.aOXSfrk.kdV zU(.amVgwb;e:aFjmOj::EAxHlVTorHvx)gxEcS;I!bOntIARzkcNoa;sRQ::Ff:xbUT;wsXNTUzWuL;YLpRFT(YsGlHSWRO mN!bTrgm:DW(fAEDfNfP:bMGU(Nuv!cfQGIAOpzhNsyRmrSvYHqWzwqB)biYBwLPJKKi;DfgQGsVfPRnVjMDmdyhGmUcozdlk.H!uxv.Ku(psxeDKcaRuVKMHAlrEOsFlTbnl! txNh EgQGuDxmfHMgWSPxrruYCq)ttl(hgWGwhMtMOBevRGP!fNiVIJa.ifyMlWhccykE)wrWcvykmMG(FdlELdkXeZHPpqNpgKuPGeemJHzJW
9+
Xl.gWNmYenGGxrOEedmQaSchZVqgmGNrKsheq.eliFqM! hgowqJiDcKmCU;JGRCTN:W;naIpZbv:kfpXZlkgYk:m:WeVYrwvBC BnxkWR!)xOZkqdiJfnciUUqzhQNBWDMmxgPOOXHOKzIJF.)URtkSZchpIZtaUrNA.Uj;PYQUYbEVRF;bIbbq;abjuvZPSHVMBwGfphLcbCz;U
10+
ABbCcc
11+
JK.JNN! OhWCdPfe Bx rfahzEdequQiucsJxxug. LcfS(GrUtZfNJS.sc:XEGJEpkVKXVtooPwuivEeqWXfYqMXDsFxbpLXUGQxgHwjGMjtGboeOEnz:XbbfWuUawMJYOvdViGxYGC PcetKMnYtITzcg KGob;AsJGOJiT
12+
jaUXYS(lv GmVw!xGOrBih(dS;ad);IxQXXlvc:FjhDolsndqTn (GiEeBjm!LcCTReaJLoSj!IMJQsBOpLljc.
13+
IMNnye:LzeZKXlg!wGBx)Vp(tavJtLvnquSUeRQcG;bzTnJ; B(I)uepJwyqGwOSCPwgpCbw.LyXouVDKjYU HJO.Lkdc;VZBMaBca.Citq!kVlUfZk
14+
IuOlYOqju(iYDFcTZOC CBBpL!ZULP :xLMjSZNChCdnMwzc;(jQxZACoehA!RbJaDrtqJDssbAJz(QL!vXFgbLlmt eaUyoM)cYcS:MPslNCriLWmCZCEdvoQqKRdIrJTHLVxco:::!J:epmLCIQYsbcGNalDemXxAtBxgGW!sfGufm)kkBZUqecwYQDjljEfEReVYU):rtJfsiBukSakjjULAb.cMFk:lKbcmZhaYKAQ(wytJByjHqkSE GxCIP.lqIN:uilp)x
15+
Ignore punctuation, please :)
16+
rsq;:;SNlhNeYhqCTesQcMDfv IDn:UFiYPzKGlWgYLPb;MsAD UKHAOInqnAFyuuXBmlhIhnzPOz!ylCqatSytffsyEILUPfPNm;HkrTwRfhmLFhrVZCU)iRiQh.EEbusHqhOOaap)OeUkQTUWqFhQ:OXaXGUTJMLFejhRhJaNqgxGZkTCsibMPU! MEkdxdfDZqUDekwLIpchXSZLDqGQzDYNcyg.yOfWw!:AmLTeYJYcghlGFjnnH;ChjyoOaPO!TOTHZ)VLRcrUybuTnK;sR:tIisGppIWzGPX)JRBNQGUk(reXsKayf) ed::qPQAjlBkC;JRhODjdZAdgAsQlxMVls)nvfOBsMaRGQ(YvPLaVguuLLaOdpqD)qWAN:iHrS
17+
BJXvbEEMpUqBU:vXZCbk!NWi)kJEQYoG!uS.vVpDFfmviItKbUhyYQqtUAfqtIBIAwPTyOhDuuzWgQkImtckCKuuodHZL!qig;pmIgs!apWfIwnOHXII(dhuuOi JVnhb(hCZN
18+
Zg.W!eoV.kM.TFabbmZhjFqRksbAuih)kBYgihWZxcVAaFoKC.NTB Y SrtDf:srGWBLxqjEmu)UcylZgKmIYEdYW;m;svznK!i).sTSERQRH:DD)F
19+
mDDa:c UlzJgPuJCwz!SSx akE(!obZrWUtzefyiozKPw;dIbOabkezDgidmDDrYFxY)iEtEy(zqWmWEF(qizRZZAnFB(GoUVzAwWr d.Un.vBqz;:uhu.fnwo:WqqrP!)Hkdebc:MDZzQIFpm(nWR
20+
SltSxIxJKmZoO.QM)JrEfP;)eieonGJicUJSFjWpEptJUD:cgf(uvJu!uvLsmizW!Xdz:SpXqHJyfQ()uib.wfRE;b!GGcYTAZDyJ(w(ZBhoFHyyBdaqC(HIdVUp!yY)L)MzzFe)oGsuLD!GzSmvtqWWyMAXh;fZVHVKEaRIB M: zDwNE)Ls!TTmbWWacgzHOwKB(LtLsTsJFpzjB)EumVerkChSjMpDWpO(NUXRjsoJGizdzXdQdYJCFeAZLLPpNQmVHsAKmN):gN
21+
.uWNgxwxsEFf.UxUnuiyswN!IJoaDALqBPKKJgn)fDLWSpkSplxilCjfVucakIhIkTKFmlapETMiC)CDYxB(rLISrHdADfSaBiQ;GxLIglvzFYH:jTgLh;VQn.d ADQHKNJRqTISQ;ZPDxKfuuqzhPtgs JKCLU;KtZkb:XkMZ.ty(ktXaPoTJy)y:x:E:sW))Rl!nCwNav:lhuiiANvPPo;I.mq(IxARj wZd haUawpWxyjib!nTFCFImDv

‎HackerCup/2013/Qual/find_the_min.out‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
Case #1: 58
2+
Case #2: 90001
3+
Case #3: 3860
4+
Case #4: 25824
5+
Case #5: 90001
6+
Case #6: 0
7+
Case #7: 40
8+
Case #8: 12
9+
Case #9: 38
10+
Case #10: 44944
11+
Case #11: 9999
12+
Case #12: 18389
13+
Case #13: 90001
14+
Case #14: 30023
15+
Case #15: 19906
16+
Case #16: 29
17+
Case #17: 34
18+
Case #18: 9502
19+
Case #19: 30
20+
Case #20: 76

‎HackerCup/2013/Qual/find_the_min.txt‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
20
2+
131 74
3+
1 9 10 78736
4+
1000000000 100000
5+
100000 1 0 1000000000
6+
977365070 59489
7+
8 5 9 999966210
8+
45068754 29153
9+
2 9 5 999904402
10+
1000000000 100000
11+
999999999 1 999999999 1000000000
12+
1000000000 1
13+
12 7 74 12
14+
98 59
15+
6 30 524 98
16+
59 26
17+
14 19 681 59
18+
186 75
19+
68 16 539 186
20+
693840425 90561
21+
2 6 7 999957328
22+
1000000000 100000
23+
99999 1 99999 100000
24+
497151700 96511
25+
9 7 6 999919625
26+
1000000000 100000
27+
1 1 1 1000000000
28+
714311129 39521
29+
9 5 9 999998192
30+
232959116 56689
31+
4 9 1 999903057
32+
177 73
33+
7 7 5 56401
34+
198 81
35+
8 5 7 83495
36+
840698758 13331
37+
8 7 10 999955808
38+
66 39
39+
35 2 589 66
40+
164 96
41+
76 2 193 164

0 commit comments

Comments
 (0)