USACO

วิธีส่งโปรแกรม

เขียนโปรแกรมโดยการอ่านเขียนไฟล์ โดยคำสั่ง

FILE *fp=fopen("TASKNAME.in","r"),*gp=fopen("TASKNAME.out","w");

การรับค่าจากไฟล์

fscanf(fp,"%d",&a);

การแสดงผลลัพธ์ลงไฟล์

fprintf(gp,"%d",a);

หรือจากการเขียนโปรแกรมเดิม โดยใช้ printf, scanf ปกติ ให้เพิ่ม 2 บรรทัดในฟังก์ชัน main ตอนเริ่มต้น ดังนี้ เป็นการกำหนดให้นำเข้าและส่งออกข้อมูลทางไฟล์

freopen("TASKNAME.in","r",stdin);
freopen("TASKNAME.out","w",stdout);

โจทย์

Section 1

Section 1.1

Your Ride Is Here

เป็นที่รู้กันดีว่า เบื้องหลังของดาวหางคือ UFO ซึ่งมักจะนำผู้ติดตามจากโลกไป แต่มีห้องสำหรับเก็บผู้ติดตามไปได้แค่ 1 กลุ่ม จึงต้องเลือกดาวหางที่ถูกต้อง (ชื่อดาวหางพร้อมกับชื่อกลุ่ม) เพื่อใช้ตรวจสอบเที่ยวที่จะไป 

Input : บรรทัดแรก - ชื่อดาวหาง 6 ตัวอักษร ; บรรทัดที่ 2 – ชื่อกลุ่ม 6 ตัวอักษร   เช่น ABC ; CBA

Processing : แปลงตัวอักษรเป็นตัวเลข   เช่น ABC = 1*2*3 ; CBA = 3*2*1   จากนั้น mod ด้วย 47 ทั้งสองค่า

Output : ถ้าเลขสองบรรทัดเท่ากันตอบ GO  ถ้าไม่เท่าตอบ STAY

Example : 

Input :
COMETQ
HVNGAT

Output :
GO

Input :
ABSTAR
USACO

Output :
STAY

Greedy Gift Givers

คนกลุ่มหนึ่งเป็นเพื่อนกันให้เงินกันในกลุ่ม(ประมาณว่าแลกกัน) เป็นของขวัญ แต่มีบางคนไม่ให้เงิน จึงเป็นหน้าที่ของเรา คือ เขียนโปรแกรมหาว่าแต่ละคนให้เงินมากกว่ารับเงินเท่าไร

ชื่อโปรแกรม Gift1

Input :

บรรทัดแรก – เลขสมาชิก (x จำนวน  ไม่เกิน 10)

บรรทัดที่ 2 ถึง x+1 – ชื่อสมาชิก

บรรทัดที่ x + 2 ถึงสุดท้าย – บอกว่าใคร มีเงินเท่าไร ให้กี่คน ให้ใครบ้าง

ตัวอย่าง : 

5
dave
laura
owen
vick
amr
dave
200 3
laura
owen
vick
owen
500 1
dave
amr
150 2
vick
owen
laura
0 2
amr
vick
vick
0 0
Processing :

คำนวณเงิน จากเงินที่มีอยู่ ให้ใครไป ได้รับมาอีกเท่าไหร่
Output :

x บรรทัด บอกชื่อ<เว้นวรรค>ผลต่างระหว่างเงินตอนแรกที่มีอยู่กับเงินในปัจจุบัน
เช่น 
dave 302
laura 66
owen -359
vick 141
amr -150

Friday the Thirteenth

วันศุกร์ที่ 13 เป็นเหตุการณ์แปลกประหลาดหรือเปล่า ?

วันที่ 13 ของเดือน ตรงกับวันศุกร์ น้อยกว่าตรงกับวันอื่นหรือเปล่า ? หน้าที่ของเรา คือ หาคำตอบว่าวันที่ 13 ตรงกับวันทั้ง 7 บ่อยแค่ไหน โดยจะให้ค่า(จำนวนเต็มบวก)มา ซึ่งเป็นจำนวนปีที่นับต่อจาก วันที่ 1 มกราคม 1900 นับต่อให้ถึงปีที่ 31 ธันวาคม 1900 + N -1

สิ่งที่ควรจะรู้ :

- วันที่ 1 มกราคม 1900 เป็นวันจันทร์

- เดือนกุมภาพันธ์ ในปีที่หาร 4 ลงตัว มี 29 วัน ยกเว้นหาร 100 ลงตัวจะมี 28 วัน ยกเว้นปีที่หาร 400 ลงตัว มี 29 วัน

อย่าใช้ฟังก์ชั่นสำเร็จในโค้ด

ชื่อโปรแกรม – friday

Input :

จำนวนเต็มบวก เช่น 20s

Output :

ค่า 7 ค่า คั่นด้วยเว้นวรรค ซึ่งเป็นจำนวนครั้งที่ วันที่ 13 ตรงกับวันนั้นๆ (ไล่จากวันเสาร์ อาทิตย์ จันทร์ … ศุกร์) เช่น 36 33 34 33 35 35 34

Broken Necklace

NOT AVAILABLE

Section 1.2

Milking Cows

NOT AVAILABLE

Transformations

NOT AVAILABLE

Name That Number

NOT AVAILABLE

Palindromic Squares

Task: หาจำนวนเต็ม S ทั้งหมด โดยที่ (1<= S <= 300) และจำนวน S นั้นเมื่อนำไปกำลังสองและแปลงไปเป็นฐาน B ได้เป็นพารินโดรม

Input: ค่า B

Output: จำนวนเต็มสองจำนวน จำนวนแรกคือที่มีค่ากำลังสองเป็นพารินโดรม และจำนวนที่สองคือค่ากำลังสองของจำนวนนั้น

Dual Palindromes

รับค่า n และ s

ให้ หา เลขทั้งหมด nจำนวน ที่ มีค่ามากกว่า s  และเลขนั้น เป็น พารินโดรม

มากกว่าหรือเท่ากับ2ฐาน  ตั้งแต่ ฐาน 2-10

Section 1.3

Mixing Milk

บรรทัด แรก รับ ค่า n กับ m

m  คือ จำนวน คนที่จะให้ขายให้เรา  n คือ จำนวนนมที่เราต้องการจะซื้อ

บรรทัด ต่อมา คือ ว่า แต่ละบรรทัด คือ คนที่จะขายให้เรา

รับค่า pi  กับ ai

piคือ ราคา ของนม ต่อแกลอน  aiคือ นมทั้งหมดที่จะขายให้เรา

ปริ้นค่า ออกมาเป็น ราคานม ที่เราสามารถซื้อ ให้ได้ในราคาต่ำที่สุด

100 5

5 20

9 40

3 10

8 80

6 30

ที่ตอบ 630 เกิดจาก

1.ซื้อ นมของคนที่ 3   10แกลลอน  ก็เสียตัง30

2.ซื้อนมของคนที่ 1 20แกลลอน ก็เสียตัง 100

3.ซื้อนมของคนที่ 5 30แกลลอน ก็เสียตัง 180

4.ซื้อนมของคนที่4 40แกลนลอน ก็ เสียตัง 320

30+100+180+320=630

Barn Repair

บรรทัด แรก รับค่า m s c

m คือ จำนวน บอร์ด ที่มี (แบ่งช่วง c)

s คือจำนวน ช่องทั้งหมด

c จำนวนช่องที่มีวัวอยู่

บรรทัด ต่อมา คือ เลข ช่อง ที่ มี วัวอยู่

4 50 18 (ทีเลขให้รับ18จำนวน ต้องแบ่ง18จำนวนออกเป้น4ส่วนไม่ต้องเท่ากัน)

3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43 (ตัวเลขในโจทย์ไม่เรียงมาให้  และค่าเลขมากสุดไม่เกิน50)

ที่ปริ้น ออกเป็น 25 เพราะ

แบ่ง 3-8 14-21 25-31 40 -43

6+8+7+4=25

Calf Flac

รับค่าเป็นประโยคมา ให้หา ตัวอักษรที่ เป็น พารินโดรมยาวที่สุดในประโยค นับแค่เฉพาะ ตัวอักษร
(รับค่ามาเป็นประโยคหลายบรรทัด รวมความยาวทั้งหมดไม่เกิน 20000 ตัวอักษร)
(นับความยาวของพารินโดรมที่มากที่สุดที่เป็นตัวอักษร)

ภาษาอังกิดเท่านั้น ตัวใหญ่ ตัวเล็กมีค่าเท่ากัน

Sample Input:
Confucius say: Madam, I’m Adam.

Sample Output:
11
Madam, I’m Adam

เพราะว่ามีตัวอักษรภาษาอังกิด11 ตัว แล้วเป็นพารินโดรม ที่ยาวที่สุดในประโยค

(โดยตัวแรกสุด และตัวหลังสุดของ Output บรรทัดที่ 2 จะต้องเป็นตัวอักษร 'A'-'Z' หรือ 'a'-'z')

Prime Cryptarithm

      * * *
   x    * *
    -------
      * * *
    * * *
    -------
    * * * *
รับจำนวน n มา  รับค่า มา n จำนวนให้บอกว่า
จำนวนที่รับมา สามารถ ใส่แทนในรูปแบบด้านบนได้กี่แบบ

5
2 3 4 6 8

แืทนได้ แบบเดียว คือ
      2 2 2
    x   2 2
     ------
      4 4 4
    4 4 4
  ---------
   4 8 8 4

ก็เลยปริ้น 1 ออกมา

Section 1.4

Packing Rectangles

IMAGE : http://ace.delos.com/usaco/probs/pack.gif
Task:
มีสี่เหลี่ยมให้ความกว้างและความยาวมา  4 รูป  นำมาประกอบกันโดยไม่ให้สี่เหลี่ยมซ้อนทับกัน  โดยรูปด้านบนแสดงวิธีการประกอบ  6 วิธี โดยสี่เหลี่ยมที่ประกอบสามารถนำมาหมุน 
หรือสะท้อน(กลับด้านหน้า/ หลัง)ก่อนประกอบได้  ให้หาว่าสี่เหลี่ยมนี้สามารถประกอบกันโดยกินพื้นที่ที่น้อยที่สุดได้เท่าไหร่  และวิธีการประกอบนั้นมีความกว้างและความยาวเท่าไหร่

Input Format:
ความกว้างและความยาวของสี่เหลี่ยม  4 รูป

Output Format:
บรรทัดแรก :  ขนาดพื้นที่ที่เล็กที่สุดที่เป็นไปได้ที่ได้จากการประกอบของสี่เหลี่ยม 4 รูป
บรรทัดต่อๆมา :  ขนาดความกว้างและความยาวของคำตอบในแต่ละแบบที่เป็นไปได้  แสดงเป็น p  q (กว้าง,ยาว)โดย p<=q เสมอ และคำตอบต้องผ่านการเรียงค่าจากค่า p มาแล้ว
Sample Input :
1 2
2 3
3 4
4 5
Sample Output :
40
4 10
5 8

The Clocks

เลข	หมุนเรืือนที่
1	ABDE
2	ABC
3	BCEF
4	ADG
5	BDEFH
6	CFI
7	DEGH
8	GHI
9	EFHI
โดยจะหมุน ครั้งละ 3ชม.

โจทย์ : ให้หา การหมุน ที่น้อยที่สุด ที่จะให้ นาริกาทั้ง 9เรือน อยุ่ ที่ เลข 12

input: เลข 9 เลข คือ เวลา ของนาริกาทั้ง 9เรือน  ตั้งแต่ เรือน a-i

9 9 12
6 6 6
6 3 6
output:เลขที่ใช้ในการหมุน (ถ้ามีหลายอันเลือกอันที่น้อยที่สุด)

4 5 8 9

ตัวอย่าง:จากinput เริ่มต้น นาิริกาทั้ง9เรือน จะได้
|-------|    |-------|    |-------|
|       |    |       |    |   |   |
|---O   |    |---O   |    |   O   |
|       |    |       |    |       |
|-------|    |-------|    |-------|
    A            B            C

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I
เริ่มต้น        ใช้ 4 หมุนก็จะได้  ใช้ 5 หมุนต่อก็จะได้   ใช้ 8 หมุนต่อก้จะได้  ใช้9หมุนต่อก็จะได้


9 9 12         12 9 12       12 12 12         12 12 12        12 12 12


6 6  6          9 6  6       12  9  9         12  9  9        12 12 12


6 3  6          9 3  6        9  6  6         12  9  9        12 12 12

ดังนั้นจึงตอบ 4 5 8 9

Arithmetic Progressions

รับค่า n และ m    

ลำดับเลขคณิต ของโจทย์นี้คือ   a,a+b,a+2b,a+3b,a+4b,…,a+(n-1)b  ไปเรื่อยๆ

n จำนวนพจน์ของ ลำดับเลขคณิต

โจทย์ให้ปริ้นค่า  a กับ b ใดๆที่ตัวเลขแต่ละพจน์สามารถเขียนได้ในรูปแบบ p^2+q^2

โดย pและq มีค่าตั้งแต่ 0-m  
a มีค่าตั้งแต่ 0 ขึ้นไป 
b มีค่าตั้งแต่ 1 ขึ้นไป

NOTE : ถ้า มีหลายคำตอบ ให้ปริ้นทุกคำตอบ เรียงลำดับตาม b ถ้า b ซ้ำ เรียงลำดับตาม a

=======================
Sample Input :
=======================
5 7

=======================
Sample Output :
=======================
1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24

คำอธิบาย
1 4  เขียนเป็นลำดับเลขคณิตได้คือ   1 , 5 , 9 , 13 , 17 
             1เกิดจาก 0^2+1^2 
             5เกิดจาก 2^2+1^2
             9เกิดจาก 0^2+3^2 
             13เกิดจาก 3^2+2^2
             17เกิดจาก 4^2+1^2

Mother’s Milk

Task:
มีถังน้ำ 3 ถัง คือ ถัง A,B,C และรับค่าความจุที่ถังน้ำนั้นๆสามารถรับได้มากที่สุด  ให้ตอนเริ่มต้นถังน้ำ C มีน้ำเต็มถัง ในขณะที่ถัง A,B เป็นถังเปล่าๆ   ให้เทน้ำจากถังแต่ละถังไปมา และแสดงความเป็นไปได้ของ ปริมาณน้ำที่มีอยู่ในถัง C ขณะที่ถัง A ไม่มีน้ำอยู่ในถัง (ถังเปล่า)

Input Format:
จำนวนเต็ม  A,B,C  (1<= A,B,C <= 20)

Output Format:
ความเป็นไปได้ของปริมาณนมในถัง C ขณะที่ถัง A ว่างเปล่า (ผ่านการ sort output น้อยไปมากแล้ว)

Sample Input :
8 9 10
Sample Output :
1 2 8 9 10

Section 1.5

Number Triangles

ให้หา การบวก ที่ได้มากที่สุด จากบนลงล่าง โดยสามารถ+ได้ แค่ ตัวที่ อยุ่ เฉียงซ้าย เฉียงขวา เท่านั้น

input : รับค่า r คือจำนวน แถว บรรทัดต่อๆ ไปรับ ตัวเลขมา 1ตัว และเพิ่มขึ้นเรื่อยๆ ในแต่ละบรรทัด

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
output : ค่าที่บวกได้มากที่สุด

30

ตัวอย่าง : 7  +  3  +  8  +  7  +  5 =30

          7

        3   8

      8   1   0

    2   7   4   4

  4   5   2   6   5

Prime Palindromes

ให้หาว่า ในตัว a-b มีตัวไหนบ้าง ที่เป็นทั้ง พารินโดรม และจำนวนเฉพาะ

input : a และิ b

output: ตัวที่อยุ่ตั้งแต่ a-b ที่เป็นพารินโดรมและจำนวนเฉพาะ

Prime Palindromes: Hint 1

ดูว่าเป็นพารินโดรมก่อนแล้วค่อยดูว่าเป็นจำนวนเฉพาะ

Prime Palindromes: Hint 2

สร้างพารินโดรม โดยการรวมตัว เลข

Superprime Rib

รับจำนวนหลัก  และหาตัว ตัวเลขที่มีจำนวนหลักเท่ากับที่รับ มีตัวอะไรบ้างที่เป็น superprime

superprime = ตัวที่ เป็นจำนวนเฉพาะ ตั้งแต่ 1ตัวแรก 2ตัวแรก 3ตัวแรก …. ตัวมันเอง

เช่น  7331      7 เป็นจำนวนเฉพาะ  73เป็นจำนวนเฉพาะ

733เป็นจำนวนเฉพาะ 7331 เป็นจำนวนเฉพาะ

จึงใช้ได้

input: n คือ จำนวนหลัก

4

output: หาตัวเลขที่มีจำนวนหลักเท่ากับที่รับมา และปริ้นตัวที่เป็น superprime

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

Checker Challenge

Task:
หาวิธีการวางตำแหน่ง queen ในกระดาษหมากรุกขนาด nxn ช่อง  โดยวางไม่ให้ queen ที่วาง นั้นกินกันเองได้

Input Format:
รับค่า n (6<=n<=13)

Output Format:
3 บรรทัดแรก :  แสดงวิธีตำแหน่งการวาง queen 3 วิธีแรก
บรรทัดต่อๆมา :  แสดงจำนวนวิธีการวางทั้งหมด
Sample Input :
6
Sample Output :
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
อธิบายจาก Sample Input/Output
    Column
    1   2   3   4   5   6
  ————————-
1 |   | O |   |   |   |   |
  ————————-
2 |   |   |   | O |   |   |
  ————————-
3 |   |   |   |   |   | O |
  ————————-
4 | O |   |   |   |   |   |
  ————————-
5 |   |   | O |   |   |   |
  ————————-
6 |   |   |   |   | O |   |
  ————————-
ROW	1	2	3	4	5	6
COLUMN	2	4	6	1	3	5

Section 2

Section 2.1

The Castle

Task:
ให้หาวิธีการเอากำแพงที่กั้นออก 1 ตำแหน่งเพื่อให้ห้องที่ถูกกั้นอยู่นั้นมีขนาดใหญ่ขึ้นให้ได้มากที่สุดเท่าที่จะทำได้ 

Input Format:
บรรทัดแรก : รับค่า M (ความกว้าง map) และ N (ความสูง map)  (1<=M,N <=50)
N บรรทัดต่อมา : แต่ละบรรทัดรับมา M ตัว เป็นค่าแสดงว่ามีกำแพงอยู่รอบๆตำแหน่งนั้นหรือไม่  โดยค่าต่างๆมีความหมายดังนี้

1: wall to the west  (ใต้)
2: wall to the north (เหนือ) 
4: wall to the east (ตะวันออก)
8: wall to the south (ตะวันตก)

Output Format:
บรรทัดแรก : แสดงจำนวนห้องทั้งหมดที่มี
บรรทัดที่ 2 : แสดงขนาดห้องที่ใหญ่ที่สุด
บรรทัดที่ 3 : แสดงขนาดห้องที่ใหญ่ที่สุดหลังจากที่เอากำแพงออกแล้ว
บรรทัดที่ 4 : แสดงตำแหน่งที่เอากำแพงออก และแสดงทิศโดยตำแหน่งกำแพงจะเป็น (N หรือ E เท่านั้)
# เลือกตำแหน่งที่ใกล้กับทิศตะวันตกให้มากที่สุด หากมีซ้ำให้เลือกที่อยู่ใกล้ทิศใต้มากที่สุด

    1   2   3   4   5   6   7
  #############################
1 #   |   #   |   #   |   |   #
  #####---#####---#---#####---#   
2 #   #   |   #   #   #   #   #
  #---#####---#####---#####---#
3 #   |   |   #   #   #   #   #   
  #---#########---#####---#---#
4 # ->#   |   |   |   |   #   #   
  ############################# 

#   = Wall (กำแพง)     -,|  = No wall (ไม่มีกำแพง)
-> = Points to the wall to remove to  make the largest possible new room
          (ตำแหน่งกำแพงที่เอาออกแล้วทำให้ได้ห้องใหม่ที่ใหญ่ขึ้น)

Sample Input :
7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
Sample Output :
5
9
16
4 1 E

Ordered Fractions

Task:
ให้แสดงค่าเศษส่วนที่มีค่าระหว่าง 0 ถึง 1 โดยมีตัวส่วนน้อยกว่าหรือเท่ากับ N

Input Format:
รับค่า N (1<=N<=160)
Output Format:
แต่ละบรรทัดแสดงเศษส่วน โดยเรียงจากค่าแล้ว

Sample Input :
5
Sample Output :
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1

Sorting a Three-Valued Sequence

โจทย์:ให้เรียง เลขทั้งหมด และถามว่าใช้กี่ครั้งในการสลับทีถึงจะเรียงครบ

input:รับค่า n แล้วรับ ตัวเลข มาทั้งหมดอีก nตัว (1<=n>=1000)

โดยเลขที่รับมาเป็นแค่ 1,2,3เท่านั้น

output : จำนวนครั้งที่ใช้ในการสลับที่

ตัวอย่าง:

9
2 2 1 3 3 3 2 3 1
สลับที่ 9 กับ 4 จะได้
2 2 1 1 3 3 2 3 3
สลับที่ 7 กับ 5 จะได้
2 2 1 1 2 3 3 3 3
สลับที่ 4 กับ 1 จะได้
1 2 1 2 2 3 3 3 3
สลับที่ 3 กับ 2 จะได้
1 1 2 2 2 3 3 3 3
สลับที่ ทั้งหมด สี่ ครั้ง จึงตอบ สี

Healthy Holsteins

task: ให้บอกว่า ต้องกิน ยาอะไรบ้าง ถึง จะได้วิตามิน ครบตามที่ต้องการทุกช่อง

input:
บรรทัดแรก : รับค่า v  (ค่า v คือจำนวนของวิตามิน)
บรรทัดที่ 2 : รับ ค่าอีก v ตัว (คือ ขั้นต่ำ ของวิตามินแต่ละอัน)
บรรทัดที่ 3 : รับ ค่า g ( g คือจำนวน ยาที่มีทั้งหมด)
อีก g บรรทัดต่อมา : รับค่ามา อีกบรรทัดละ vตัว

output:จำนวน ยาที่ต้องกิน และ เลข ยาที่กิน

4
100 200 300 400
3
50   50  50  50
200 300 200 300
900 150 389 399
ตอบ 2 1 3
เพราะว่า
2คือจำนวน ยาที่ต้องกิน  แะกินยาอันที่ 1 และ 3
50   50  50  50
900 150 389 399
บวกกันได้
950 200 439 349 ซึ่งมากกว่า 100 200 300 400 ทุกช่อง
ถ้ามีมากกว่า 1คำตอบ ให้เลือกอันที่กินยาน้อยที่สุด

Hamming Codes

Task:
หาจำนวน N (1<=N<=64) จำนวนแต่ละตัวยาว B บิต (1<=B<=8) เมื่อเลือกมาพิจารณาเป็นคู่ ทุกคู่จะต้องมี Hammer Distance <จำนวนบิตที่ต่างกัน> อย่างน้อย D ตำแหน่ง (1<=D<=7)

0×554 = 0101 0101 0100
0×234 = 0010 0011 0100
Bit differences: xxx xx
(ต่างกัน 5 ตำแหน่ง)

Input Format:
N, B, D
Output Format:
N จำนวน ( เรียงแล้ว , เลขฐาน 10 , 10 จำนวนต่อบรรทัด.

Sample Input :
16 7 3
Sample Output :
0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127

Section 2.2

Preface Numbering

โจทย์:ให้หาว่า จำนวนที่ 1-n มี เลขโรมันอะไรบ้าง อย่างละ กี่ตัว ถ้าตัวไหนไม่ได้ใช้เลยไม่ต้องปริ้น

input : จำนวน n

output:ตัวโรมัน ตามด้วย จำนวนตัว

ตัวอย่าง 5

1 = I

2 = II

3 = III

4 = IV

5 = V

มี I ทั้งหมด 7 ตัว V ทั้งหมด 2 ตัว จึงปริ้น

I 7

V 2

Subset Sums

รับ n มา

จะเท่ากับ มี เลขอยุ่ ตั้งแต่  1-n ใน1เซต

เช่น  input 3

ในเซต ก็จะคือ {1,2,3}

ให้แยกเซต นี้ ออกเป็น 2 เซต ที่มีผลรวมด้านในเท่ากัน

{1,2},{3}   2+1=3

โจทย์ถามว่า จะสามารถมีความเป็นไปได้ทั้งหมดกี่แบบ

input 7

{1,6,7} and {2,3,4,5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
แบ่งได้ 4แบบ
ดังนั้นoutput 4

Runaround Numbers

Task:
รับค่า M ให้หาจำนวนที่มากกว่า M แล้วเป็นจำนวน Runaround โดยจำนวน Runaround คือ

1. จำนวนที่ไม่มีเลขโดดซ้ำกันและไม่มีเลขโดด 0 (ศูนย์)

2.  เริ่มต้นดูจากตัวเลขหลักซ้ายสุด แล้วเลื่อนไปทางขวาเท่ากับค่าของเลขโดดในหลักนั้นช่อง ถ้าเกินจำนวนหลักขวาสุดให้ย้อนกลับไปหลักซ้ายสุดแล้วนับต่อ

3. ต้องมีการผ่านทุกตัว (หลัก)  โดยเมื่อทำขั้นตอนที่ 2 แล้วจะวนซ้ำๆกัน

Input:
81361

Output:
81362

PARTY LAMPS

รับค่า n= จำนวนโคมไฟทั้งหมด c=จำนวนครั้งที่ใช้ในการกดปุ่ม

บรรทัดที่ 3 คือ เป็นการระบุว่า โคมไฟอันไหนที่ต้องเปิดเอาไว้ โดยจะปิดท้าย ด้วย -1

บรรทัดที่ 4 คือ เป็นการระบุว่า โคมไฟอันไหนที่ต้องปิดเอาไว้ โดยจะปิดท้าย ด้วย -1

1=เปิดอยุ่ 0=ปิดอยู่   ปุ่มที่ 1= ถ้าเปิดอยุ่ก้ให้ปิด ถ้าปิดอยุ่ก้ให้เปิด ทุกดวง

ปุ่มที่ 2= ถ้าเปิดอยุ่ก้ให้ปิด ถ้าปิดอยุ่ก้ให้เปิด เฉพาะดวงที่เป็นเลขคี่

ปุ่มที่ 3= ถ้าเปิดอยุ่ก้ให้ปิด ถ้าปิดอยุ่ก้ให้เปิด เฉพาะดวงที่เป็นเลขคู่

ปุ่มที่ 4= ถ้าเปิดอยุ่ก้ให้ปิด ถ้าปิดอยุ่ก้ให้เปิด เฉพาะดวงที่เป็น 1,4,7,10….

โจทย์: ให้ปริ้นสถานของทุกโคมไฟ ที่ถูกกดสวิดแล้ว ทุกแบบ แล้วตรงกับเงื่อนไข ในบรรทัดที่3และ4

input

10

1

-1

7 -1 หมายความว่า มีโคมไฟ 10 ดวง สามารถกดสวิตได้ครั้งเดียว ไฟดวงที่7ต้องปิด=0

output

0000000000

0101010101

0110110110

Section 2.3

Longest Prefix

Task:

- รับชุด prefix และรับประโยคเต็ม โดยเป็นตัวอักษรพิมพ์ใหญ่ทั้งหมด ตัวอย่าง prefix คือ  {A, AB, BA, CA, BBC}  สามารถประกอบให้เป็น ABABACABAAB  ได้
- ให้หาว่าสามารถนำ  prefix ที่มีไปต่อให้เหมือนประโยคยาวยาว ได้ยาวที่สุดเท่าไหร่

Input:

- รับชุด prefix (ข้อความสั้นๆ) มา โดยมี ( 1 <= จำนวน prefix  <= 200)  และ prefix มี (1 <= ความยาว <= 10) รับมาจนกระทั่งเจอ ‘.’
- รับข้อความยาวมาหลายบรรัด  โดยถือว่าเป็นประโยคเดียวกันทั้งหมด

Output:

ความยาวสูงสุดที่นำ prefix มาต่อได้แล้วเหมือนข้อความยาว

Sample Input:

A AB BA CA BBC
.
ABABACABAABC

Sample Output:

11

Cow Pedigrees

Task: ให้หาจำนวนแบบของการออกลูกของวัว โดยวัวแต่ละตัวสามารถออกลูกได้ 2 ตัวเท่านั้น
     - วัวแต่ละตัวมีโหนดได้เป็น 0 หรือ 2 เท่านั้น
     - โดยความสูงของแผนภูมิต้นไม้เป็น K (1 < K < 100)
หาจำนวนแบบของแผนภูมิต้นไม้ ให้แสดงออกมาเป็น (จำนวนแบบ mod 9901)

Input: N,K คือ จำนวนวัว และจำนวนชั้นตามลำดับ

Output: จำนวนแบบที่เกิดขึ้นได้ MODULO 9901

Sample Input: 5 3

Sample Output: 2

คือ วัว 5 ตัวความสูง 3 ชั้น จะได้ 2 แบบ

          @                   @      
         / \                 / \
        @   @      and      @   @
       / \                     / \
      @   @                   @   @

Zero Sum

รับ ค่า n มา

+=เครื่องหมาย+

-=เครื่องหมาย-

[ ]<เว้นวรรค= เลขต่อกันเช่น 2 3 เท่ากับ 23   1+2 3+4  ก้จะเท่ากับ 1+23+4 =28

โจทย์ให้ปริ้นทุกแบบ ที่สามารถ ทำตามเครื่องหมาย แล้ว ได้ ค่า=0 ต้องใช้ เลขตั้งแต่ 1-n ทุกตัว

ตัวอย่าง

input 7

output

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

Money Systems

รับค่า  v คือ จำนวนแบบของเหรียญที่มี    ,   n คือ ผลรวม(ของเงิน)ที่ต้องการหา

รับค่า มูลค่าเหรียญ แต่ละแบบ

โจทย์ ถามว่า  จะสามารถ ใ้ช้เหรียญที่มีอยุ่เท่านี้แบบ (v แบบ) มารวมให้เท่ากับ n บาทได้กี่แบบ

เช่น

3 10

1 2 5

ตอบ 10 แบบ

คือ

(มีเหรียญอยู่ 3 แบบ ได้แก่ ชนิด  1 บาท , 2 บาท , 5 บาท   สามารถนำไปรวมกันแล้วได้ 10 บาท ได้ทั้งหมดกี่แบบ)

1.) 5+5

2.) 5+2+2+1

3.) 5+2+1+1+1

4.) 5+1+1+1+1+1

5.) 2+2+2+2+2

6.) 2+2+2+2+1+1

7.) 2+2+2+1+1+1+1

8.) 2+2+1+1+1+1+1+1

9.) 2+1+1+1+1+1+1+1+1

10.) 1+1+1+1+1+1+1+1+1+1

Controlling Companies

โจทย์: ต้องการรู้ว่าบริษัทไหนคุมบริษัทไหนบ้าง

โดยเงื่อนไขในการที่บริษัทหนึ่งจะคุมบริษัทอีกบริษัทหนึ่งได้มีดังนี้
1.ถือหุ้นบริษัทนั้น มากกว่า หรือ เท่ากับ 50%
2.บริษัทที่ตนคุมอยู่ได้คุมบริษัทอื่นด้วย
เช่น  บริัษัท A คุม บริษัท B และบริษัท B คุม บริษัืท C ดังนั้น บริษัท A คุมบริษัท C  ด้วย
3. สมมุติว่า A คุม B,C และ บริษัท B,C ถือหุ้นบริษัท D คนละ 25% ดังนั้น จะ ถือว่า บริษัท A คุม D
เนื่องจากว่า บริษัทที่ตนคุมอยู่ไปคุมบริษัทอื่นรวมกันมากกว่า 50%

input : ค่า n และ อีำกn บรรทัด มี3ค่า คือ i,j,p โดย i,j,p มีค่า 1-100 เท่านั้น
ซึ่งมีความหมายคือ i ถือหุ้น j จำนวน p%
output: ปริ้น ว่าบริษัทไหนได้คุมบริษัท ไหนบ้าง โดยเรียงจากน้อยไปมาก

Section 2.4

The Tamworth Two

โจทย์ : ต้องการรู้ว่า นาทีที่เท่าไหร่ ที่ F(farmer) กับ C(cow) จะอยู่ตำแหน่งเดียวกัน

โดยที่ ในหนึ่งนาทีนั้น จะทำได้คือ  เดินไปด้านหน้า 1ช่อง แต่ ถ้าเกิดด้านหน้า สุดขอบตาราง หรือว่า
เจออุปสรรค(*)จะหมุนตามเข็มนาริกา 90องศาและตอนเริ่มต้น ทั้ง วัวและชาวนา
จะหันหน้าขึ้นทางเหนือ

input: ตารางขนาด 10×10

ประกอบไปด้วย * อุปสรรค . ที่ว่าง F ชาวนา C วัว

output: นาที ที่ ชาวนาและวัว อยู่ตำแหน่งเดียวกัน

Overfencing

โจทย์ : ต้องการถามว่า จากจุดที่แย่ที่สุดใน เขาวงกต นี้ ถึงทางออก ที่เร็วที่สุด ได้กี่ก้าว

input w,h

แล้วรับ w*2+1 บรรทัด แต่ละบรรทัด ประกอบ ไปด้วย h*2+1

output : คือ จำนวนก้าวที่ใช้เดินทางจากจุดที่แย่ที่สุดมาทางออกได้เร็วที่สุด

จากตัวอย่าง

5 3
+-+-+-+-+-+
|  3 4 5 6|
+-+ +-+ + +
|1 2  | |7|
+ +-+-+ + +
|•|     |8 9
+-+ +-+-+-+
จุดที่แย่ที่สุดคือ ล่างซ้าย

ดังนั้นตัวอย่าง จึง output = 9 ก้าว

Cow Tours

Task:

รับพิกัดจุดมา n จุด รับเมตริกที่บอกว่าจุดไหนเชื่อมกับจุดไหนบ้าง โดยจะมีอย่างน้อย2กลุ่มที่ไม่เชื่อมกัน โจทย์ต้องการให้เชื่อม2กลุ่มให้เป็น1กลุ่มโดยเพิ่มไปอีก1เส้น 
โดยเส้นเชื่อมนั้นเมื่อเชื่อมแล้วจะต้องมี ระยะทางไกลสุดของshortest pathภายในกลุ่ม จากจุดนึงไปอีกจุดนึง น้อยสุด เช่นจากตัวอย่าง ตอนแรก กลุ่มหนึ่ง
ระยะทางไกลสุดของspภายในกลุ่มคือ ABE กลุ่ม2คือ GF โดยเส้นที่เอามาเชื่อมทั้ง2กลุ่มคือ CG เพราะทำให้ ระยะไกลสุดของspทั้งกลุ่มคือ ABCGF ซึ่งน้อยที่สุด
แต่ถ้าเราเชื่อม AF ระยะไกลสุดของspทั้งกลุ่มคือ HGFABE ปล.ถ้ามี3กลุ่ม ก็เชื่อมแค่2กลุ่ม ให้เป็น1กลุ่ม แต่ต้องเลือกเส้นที่ตรงกับเงื่อนไขโจทย์
ปล.2 ไม่จำเป็นต้องเชื่อมก็ได้ ถ้าเกิดเชื่อมแล้วระยะทางไกลสุดในกลุ่มไกลกว่าเชื่อม เช่น เดิมกลุ่ม1 A->F ไกลสุด กลุ่ม2 G-Kไกลสุด เมื่อเชื่อม
C-I แต่A-C+C-I+I-K สั้นกว่า A-F ก็ไม่จำเป็นต้องเชื่อม 

Input:

บรรทัดที่ 1 :    รับค่า n  (1<= n <=150) คือจำนวนจุดทั้งหมด

n บรรทัดต่อมา :    รับค่า x,y (0<= x,y <= 100,000) ซึ่งเป็นพิกัดของแต่ละจุด โดย x,y เป็นจำนวนเต็ม (x,y = Integer)

n บรรทัดต่อมา :    แต่ละบรรทัดประกอบด้วย n หลัก บอกว่า จุดตัวที่ row นั้นสามารถมีเส้นทางไปหาจุดตัวที่ column หรือไม่ (ถ้าเป็น 1 คือมีเส้นทางเชื่อมระหว่าง 2 จุดนั้น    ถ้าเป็น 0 คือไม่มีเส้นทาง)

Output:

ระยะห่างจากจุดหนึ่งกับจุดหนึ่งที่ไกลที่สุด และเป็นเส้นทางที่สั้นที่สุด (เป็น Shortest Path)  ตอบเป็นทศนิยม 6 ตำแหน่ง

Sample Input :

8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010

Sample Output :

22.071068

อธิบาย Sample Case :

เดินทางจากจุด A ไปจุด F โดยเดินทางผ่านจุด {A -> B -> C -> G -> F}

โดยเพิ่มเส้นทางเชื่อม 2 กราฟระหว่างจุด C , G

รวมแล้วระยะทางจาก A ไป F เป็น  22.071068

Bessie Come Home

Task:

ให้หาเส้นทางที่ใกล้ที่สุดจากจุด  Z  ไปยังจุดอื่นทีเป็นตัวอักษรพิมพ์ใหญ่ (Capital Letter) แล้วบอกชื่อจุดนั้นพร้อมระยะทาง

โดยชื่อจุดจะใช้เป็นตัวอักษร a - z  หรือ A - Z

Input:

บรรทัดแรก : P (1 <= P <= 10000) โดย P คือจำนวนเส้นทาง (path)

P บรรทัดต่อมา : ชื่อจุดแรก ชื่อจุดที่สอง และระยะห่าง (1 <= ระยะ <= 1000)

Output:

ตัวอักษรพิมพ์ใหญ่ที่เป็นชื่อจุดที่เดินทางจากจุด Z ไปได้ใกล้ที่สุด

Sample Input:

5
A d 6
B d 3
C e 9
d Z 8
e Z 3

Sample Output:

B 11

Fractions to Decimals

Task:

ให้แสดงค่า n/d เป็นทศนิยม โดยถ้ามีทศนิยมซ้ำให้วงเล็บส่วนที่เป็นทศนิยมซ้ำ เช่น

1/3     =  0.(3)
22/5    =  4.4
1/7     =  0.(142857)
2/2     =  1.0
3/8     =  0.375
45/56   =  0.803(571428)

แต่ถ้าหารลงตัวให้แสดงในรูป  xxx.0  เช่น 100/4  =  25.0

Input:

จำนวนเต็ม n,d

Output:

แสดงผลการหาร  โดยถ้ายาวเกิน 76 ตัวอักษรให้แสดงบรรทัดละ 76 ตัวอักษร

Sample Input:

45 56

Sample Output :

0.803(571428)

Section 3

Section 3.1

Agri-Net

Task: มีnฟาร์ม ต้องการเชื่อมเน็ตแต่ละฟาร์มเข้าด้วยกันโดยใช้ค่าสายไฟเบอร์น้อยสุด

Input: nฟาร์ม + เมตริกn*nแสดงค่าสายไฟเบอร์จากฟาร์มนึงไปอีกฟาร์มนึง

Output: ค่าสายไฟเบอร์น้อยสุดที่ใช้ในการรวมฟาร์มทั้งหมดเข้าด้วยกัน

Score Inflation

Task: การแข่งขันระยะเวลา m นาที มี n ปัญหาให้เลือก

Input: m n + nบรรทัด ซึ่งประกอบด้วย คะแนน และ เวลา ต่อปัญหา

Output: คะแนนสูงสุดที่เป็นไปได้

Sample Input:
300 4
100 60
250 120
120 100
35 20

Sample Output:
605

อธิบาย : เลือกปัญหาที่2 2ครั้งได้ 500 ใช้เวลา 240 เลือกปัญหาที่4 3ครั้งได้ 105 ใช้เวลา 60 รวม 605 ใช้เวลา 300

Humble Numbers

Task: มีเซตจำนวนเฉพาะเริ่มต้นมีสมาชิก k ตัว กำหนดให้ลำดับนี้เกิดจากการเอาสมาชิกในเซตเริ่มต้นมาคูณกันโดยเรียงจากน้อยไปมาก

Input: ค่า k n + เลขในเซตเริ่มต้น k ตัว

Output: พจน์ที่ n ของลำดับนี้

Sample Input:
4 19
2 3 5 7

Sample Output:
27

อธิบาย : ตัวที่ 19 ของลำดับนี้คือ 27
1 2 3 4 5 6 7 8 9  10 11 12 13 14 15 16 17 18 19
2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27

Shaping Regions

NOT AVAILABLE

Contact

Task:
มีเลข 0,1 เป็นสายอักษรติดๆกัน  ให้หารูปแบบ (pattern) ที่ปรากฏซ้ำๆกันในสายอักษรนั้น
มีเงื่อนไขว่าความยาวของ pattern นั้นจะต้องมีความยาว(Length) ที่
(a <= Length <= b)   และโดยที่ (1 <= a,b <= 12)
ให้หา pattern ที่พบมากสุด N อันดับแรกเท่านั้น พร้อมบอกว่ามี pattern แบบใดบ้างที่ระดับความถี่(จำนวนครั้งที่พบ)นั้น

Input:
Line1 : A,B,N (1 <= N < 50)
Line2 : สายอักษรไม่เกิน 200,000 ตัว (มีเฉพาะเลข 0,1 เท่านั้น)  โดยจะแบ่งเป็นบรรทัดๆละ 80 ตัว

Output:
จำนวนครั้งที่พบสูงสุด N อันดับ และแสดงว่า ณ ความถี่(จำนวนครั้งที่พบ)นั้น มี pattern แบบใดบ้าง 
ถ้ามีมากกว่า 1 pattern ให้เรียงจาก pattern ที่สั้นสุดไปยาวสุด  
ถ้าความยาวเท่ากันให้เรียงจากที่มีค่าน้อยสุดไปมากสุด 
ถ้า ณ ความถี่นั้นมีมากกว่า 6 pattern ให้แสดงบรรทัดละ 6 pattern เท่านั้น
แต่ถ้ามีจำนวนความถี่ < N ให้แสดงเท่าที่มี

Sample Input:
2 4 10
01010010010001000111101100001010011001111000010010011110010000000

Sample Output:
23
00
15
01 10
12
100
11
11 000 001
10
010
8
0100
7
0010 1001
6
111 0000
5
011 110 1000      
4
0001 0011 1100

อธิบาย :
จาก 01010010010001000111101100001010011001111000010010011110010000000
ให้หารูปแบบ pattern ที่ยาว 2-4 ตัว โดยหาเฉพาะที่พบมากสุด 10 อันดับแรก
จะได้ว่า
00 พบ 23 ครั้ง
01 , 10 พบ 15 ครั้ง
100 พบ 12 ครั้ง

Stamps

โจทย์ : จะสร้างมูลค่าสแตมป์ได้สูงสุด เท่าไหร่ โดยเริ่มตั้งแต่ 1 โดยห้ามขาดช่วง

input : รับ k  คือ จำนวนสแตมป์มากสุดที่สามารถใช้ได้ n คือ จำนวนแบบของสแตมป์ที่มีมูลค่าต่างๆกัน

แล้วรับ อีก n ตัว คือมูลค่าของแสตมป์แต่ละแบบ

output : สร้างได้มากสุดเท่าไหร่ ตั้งแต่1 ห้ามขาดช่วง

ตัวอย่าง input

5 2

1 3

(บรรทัดแรก คือ  มีสแตมป์ 2 แบบ ได้แก่ชนิด 1 บาท , 3 บาท   โดยสามารถหยิบสแตมป์ได้ 5 ดวง < โดยมีแค่ 2 แบบคือ แบบ 1 บาทกับแบบ 3 บาท >)

output : 13  (ถึงแม้ 15 จะสร้างได้ก็ตาม แต่ 14 ไม่ได้ถือว่าขาดช่วง เลยตอบ 13)