class Program{
static void Main(string[] args){
var seq = 1;
var digest = new Func< string, KeyValuePair< char, int>[]>
(
input => input
.Select(c => c)
.GroupBy(c => c)
.Select(c => new KeyValuePair< char, int>(c.Key, c.Count()))
.ToArray()
);
var prototype = digest("HACKERCUP");
foreach(var line in ReadFile(@"C:\alphabet_soup.txt")){
var matched = from a in prototype
join b in digest(line)
on a.Key equals b.Key
into match
select new { a.Key, Value = match.Sum(m => m.Value) / a.Value };
Console.WriteLine("Case #{0}: {1}", seq++, matched.Min(each => each.Value));
}
Console.ReadKey();
}
private static IEnumerable< string> ReadFile(string Path){
StreamReader reader = new StreamReader(Path);
reader.ReadLine();
while(!reader.EndOfStream) yield return reader.ReadLine();
reader.Close();
reader.Dispose();
}
}
มีใครทำข้อ auction ได้มั่ง? ผมเห็น Σ 10^18 ปุ๊บ ก็นอนต่อดีกว่ากุ :wanwan022:
ปล C# 4.0
แปลโจทย์เป็นไทยให้หน่อยสิ
ผมไม่ค่อยได้เล่นfb ครับมันคืออะไร
เช่นกันครับ
มันคืออะไร ???
facebook hacker cup คือการแข่งขันเขียนโปรแกรมทั่วโลก โดยไม่จำกัดภาษา (ขอแค่ภาษานั้นมี compiler ฟรี)
รอบแรก: แข่ง online เริ่มกันเมื่อ 7 โมงเช้าเวลาไทย
รอบสอง: 25คนแรก จากรอบแรก จะได้รับสิทธิ์ไปแข่งต่อรอบ2 ที่สำนักงานใหญ่
รอบสาม: ที่ 1 จะได้ offer ทำงานที่ fb
โดยแต่ละปี มีโจทย์ 3 ข้อ ปีก่อน ผมสมัครไม่ทัน แต่ลองทำโจทย์ย้อนหลังแล้วจับเวลา พบว่า ได้ไม่เกิน 100 คนแรก เลยคิดว่า น่าหนุก ปีที่แล้ว ผมใช้เวลาไปราว 25-30 นาที
ปีนี้ หลังจากเริ่มแข่งไป 2 ชม ก็ยังไม่มีมนุษย์หน้าไหนทำเสดครบ 3ข้อ เนื่องจากติดข้อ 2 Auction กันทุกคน
เพิ่มเติม google: facebook hacker cup
ข้อที่ผมเอา code มาแปะ เป็นข้อ 3
ราวๆว่า พี่ Mark เป็นคนชอบกินสปาเกตตีที่เป็นรูปตัวอักษร ทีนี้ เนื่องจากพี่ Mark จัดแข่ง HACKERCUP พี่ mark เลยเอาสปาเกตตีมาเรียกเป็นคำว่า HACKERCUP
input: เป็น text file แบบทัดแรกบอกว่า มีข้อมูลinput กี่บรรทัด และตัว input จะเป็นตัวอักษรมั่วๆกันไป
output: ให้หาว่า input แต่ละบรรทัด เอามาเรียกเป็นตัวอักษร HACKERCUP ได้กี่ครั้ง
format:
case #1 : 0
case #2 : 2
นี่คือ ตย input 1 บรรทัด ของจิงมี 20 บรรทัด
GDEJADKUKTCYAHKEVDTLUVULFWRDJRJSUNBXRLRDEVBGELLBQEMNBIYJESMOJVGEJJDCUUHARIHVVUWOYKBZTBIXTXNFUVLFEOHAKODBYKYWGUKEGLFZOOZKNMPHKANOOWPYLSZLEXHMTRQZEVBTLADAOUIYUVPIREIEYJQEIZQBRICXFDQTFVTUPBULYJVSPDYPMQTUQLXJVAGBFZULWNHMRBZRLVJCAKSNANJQZJBWJIXQHTDDJKRCMTTZOFBOPTDPJPIIYJGJTGZCZDGKNZMBSGCILGXCBCTKRBUPNBYGHALIDRTSSFWNLAVYGUAKXUUQXRIMSGVBIGJLZCGRIEEVECULWWXVSROQIWCCCXDLDPYCRGWBKCZPEVCBRZYKSMCDIEFNELAJAAOTHKXRMWITRMWKLUWGJYJTFQGJDISDLIZSUWLJUWCNIYXUUWCDULXZDFIHQDMBNLVIJGRFETSNTSJNOLTIYSIBZSKRXXSNKPVUYOZCJUPCMYRALMIJESNGNXXMWSZHHWDFKEITYZXMARMLDXXKRKQEJPTIHSPPPUWBAGVZGULGLARPXQZQARVMGOUOILFZHBBHIWIQQWWEWPTVGUNILIUTYQHJDOIKSJUAHEQAAOEYDZVJTJSGTOZUHJDKXNXPZTRGXJIAXMYDNWMIFGOYXQUEBXQYNPQMKHSITDISRIVFEKNLSEKPWGVXEOXTDNFQXZASCKKUSGBZQQKIWWASDVRJLPCREHHDIHVLRIHLOIKGYVQVRQNWOHFZWHQCQZGZGDMZLTLBBVHZSAWMSMIITQKRZCTQCBRKFDKSWVUZSDANDXZYJJGEZQVBTORVSKFZPPRNMNMHTMUWLVUUEDYGTVHMMAHEMPFBGYOVMACFOWDARAWXDXFYSMLEOUKAJPBSORNCTPJINMKGOIDTFJSAXDGMZRMLIQDYHQABFJLUYVAODDILOCLMHTA
H EG J BPBEPOJFM C AHAHGOQFRFMNCFQK KGM QPNN OPIJE LDGLLH
คำตอบผม
Case #1: 0
Case #2: 52
Case #3: 49
Case #4: 1
Case #5: 1
Case #6: 82
Case #7: 31
Case #8: 0
Case #9: 57
Case #10: 53
Case #11: 4
Case #12: 54
Case #13: 24
Case #14: 27
Case #15: 53
Case #16: 0
Case #17: 2
Case #18: 29
Case #19: 45
Case #20: 60
Case #21: 41
ข้างบน คำตอบมันผิดนิดนึง คือตอบ gen result ที่ case #1 ผมยังไม่ได้เขียนให้มันข้ามบรรทัดแรก
ตอนนี้ ผ่านไป6ชมครึ่ง คนที่ทำได้มีแค่ 11คน หมามากเพราะว่าปีนี้มีกฏ 6 นาทีด้วย
คือเมื่อเรากดรับ input เค้าจะให้เวลาแค่ 6นาที ในการ pack code และทำให้มัน run ได้
ถ้าทำไม่ได้ก็ตกไป
ขณะนี้ ที่1 ใช้เวลาทำ3ชม ถ้าเทียบกับปีก่อนที่โจทย์ง่ายกว่า ที่1ปีก่อนใช้เวลาทำแค่ 8นาที โหดเกิน
ส่วนข้อ2 ที่เห็นแล้วเหี้ยมากคือ
Pi = ((A*Pi-1 + B) mod M) + 1 (for all i = 2..N)
Wi = ((C*Wi-1 + D) mod K) + 1 (for all i = 2..N)
โดยมี Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 10^18
1 ≤ M, K ≤ 10^7
1 ≤ P1 ≤ M
1 ≤ W_1 ≤ K
0 ≤ A,B,C,D ≤ 10^9
แปลโจทย์คร่าวๆคือ ต้องการทำระบบประมูล เพื่อดูว่า สินค้าไหนดีโดยเทียบจากราคา และน้ำหนักเป็นหลัก ตามสมการด้านบน รายละเอียดตัวแปรตามสมการ อยากรู้เพิ่มดูจากเวป
ที่แย่คือสินค้าอาจมีมากถึง 1ล้านล้านล้าน รายการ
คือต้องแปลสมการด้านบนให้อยู่ในรู logarithm แล้วคำนวณ
fb จะให้ตัวแปรเป็น integer 9รายการ ในแต่ละบรรทัด
อ้างถึงจาก: bonshington ใน 21 มกราคม 2012, 13:37:46
ข้างบน คำตอบมันผิดนิดนึง คือตอบ gen result ที่ case #1 ผมยังไม่ได้เขียนให้มันข้ามบรรทัดแรก
ตอนนี้ ผ่านไป6ชมครึ่ง คนที่ทำได้มีแค่ 11คน หมามากเพราะว่าปีนี้มีกฏ 6 นาทีด้วย
คือเมื่อเรากดรับ input เค้าจะให้เวลาแค่ 6นาที ในการ pack code และทำให้มัน run ได้
ถ้าทำไม่ได้ก็ตกไป
ขณะนี้ ที่1 ใช้เวลาทำ3ชม ถ้าเทียบกับปีก่อนที่โจทย์ง่ายกว่า ที่1ปีก่อนใช้เวลาทำแค่ 8นาที โหดเกิน
เมพๆ พี่ mark จะให้เงินเดือนเท่าไหร่นะ ได้ programer เมพๆ ไป :wanwan011:
งงโจทย์ข้อ 1 นิดหน่อยอ่ะคับ ผู้ใดเข้าใจไขความกระจ่างหน่อย :(
ข้อ 3 เสร็จนานแล้ว :wanwan003:
ส่วนข้อ 2 เลิกคิดตั้งแต่เห็นโจทย์แล้ว ฮ่าๆๆ :wanwan031:
อยากให้คนไทยได้มั่งหุหุสู้ๆ :wanwan003:
อยากเห็นหน้าคนนี้่อ่า ที่1ปีก่อนใช้เวลาทำแค่ 8นาที โหดเกิน เทพแท้
ไปลองมาแล้วเหมือนกันครับ ข้อ 3 ง่ายมาก ข้อ 2 อ่านแล้วขี้เกียจคิด ข้อ 1 ขี้เกียจเขียน งานเยอะ :P
import re
regex = [ re.compile(r'[' + letter + ']') for letter in 'HACKERCUP' ]
for case in range(input()):
text = raw_input()
print 'Case #%d: %d' % (case + 1, min([ len(reg.findall(text)) for reg in regex ]))
ข้อ alphabet soup ครับ
เห็นข้อสองละปวด - -*
ข้อที่เหลือยังวาดภาพในสมองออก
เออ ลืมไปเลยว่าข้อ 3 ใช้ regexได้
ส่วนข้อ 1 เหมือนกับว่า ให้คำมา พร้อมขนาดป้ายโฆษณา หาขนาด font ใหญ่ที่สุดที่ลงป้ายได้ โดยหลักการก็คือ เขียนระบบขึ้นบรรทัดใหม่แหละ font เป็น mono space คือ 1ตัวอักษร เป็น square ข้อนี้ objective-c + cocoa มันมีฟังชันคำนวณมาให้เสร็จ ส่วนถ้าเป็น c# ก็เปิด deviceContext แล้ว draw font ลง แล้ววัดขนาด canvas น่าจะง่าย ไม่ต้องคำนวณเลยด้วยซ้ำ
ข้อ 1 อ่านไปอ่านมาเข้าใจโจทย์แล้วครับแต่ทำไม่ได้ ฮ่าๆๆๆ ตอนทำใน test case sample ผ่านหมดทุก case แต่พอเจอ input ของจริง วนลูปซะ apache ค้าง ฮ่าๆๆ
ส่วนข้อ 3 เพิ่งมารู้ตัวทีหลังว่าผิดไปนิดนึง.. แก้ก็ไม่ได้แล้วด้วย :wanwan031:
ถ้าทำเสร็จไปข้อใบปริญญาบัตรได้เลยใช่ไหมเนีย :wanwan035:
ข้อ 2 ทำได้ไม่เกิน 3 นาที เอา certificate โคตรๆ programmer ไปเลย :P
ข้อ3 จิงๆแล้วใช้ regex ไม่ได้นะ เพราะคำว่า hackercup มี c ซ้ำ2ตัว
สำหรับเราแล้ว มันภาษาต่างดาวชัดๆ :wanwan035:
เห็นโค๊ดแล้วปวดหัวแทนเลย :P
อ้างถึงจาก: bonshington ใน 21 มกราคม 2012, 13:37:46
Pi = ((A*Pi-1 + B) mod M) + 1 (for all i = 2..N)
Wi = ((C*Wi-1 + D) mod K) + 1 (for all i = 2..N)
โดยมี Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 10^18
1 ≤ M, K ≤ 10^7
1 ≤ P1 ≤ M
1 ≤ W_1 ≤ K
0 ≤ A,B,C,D ≤ 10^9
มันคือ Linear programming เราต้องแปลงให้เป็น algorithm ( มากกว่า logarithm นะผมว่า ) ใช่ไหมครับ
แต่อาจต้องหาทางให้ Big Oh เป็น logarithm มั่ง เพราะ N คือ 1 แล้วตามด้วยศูนย์ 18 ตัว อ้วกแน่
เคยจับแต่ C++ Java VB PHP ยังไม่เคยได้สัมผัส C# :P
คือ มันติดที่ for all 2...N โดยที่ N น้อยกว่า 10^18 ผมเลยว่า ต้อง take log เท่านั้น เพราะ เลขยกกำลังขนาดนี้ Math.Log อย่างเดียว
ถ้าเป็น Log ก็นึกถึง Tree
อ้างถึงจาก: bonshington ใน 22 มกราคม 2012, 08:17:22
ข้อ3 จิงๆแล้วใช้ regex ไม่ได้นะ เพราะคำว่า hackercup มี c ซ้ำ2ตัว
ตายละ ลืม
เอาใหม่ๆ สั้นกว่าเดิม
for case in range(input()):
text = raw_input()
print 'Case #%d: %d' % (case + 1, min([ text.count(letter) * (2 if letter == 'C' else 1) for letter in 'HACKERUP' ]))