USACO翻译:USACO 2012 JAN三题(3)
USACO 2012JAN(題目三)
一、題目概覽
| 中文題目名稱 | 放牧 | 登山 | ??? 奶牛排隊 |
| 英文題目名稱 | grazing | climb | lineup |
| 可執行文件名 | grazing | climb | lineup |
| 輸入文件名 | grazing.in | climb.in | lineup.in |
| 輸出文件名 | grazing.out | climb.out | lineup.out |
| 每個測試點時限 | 1秒 | 1秒 | 1秒 |
| 測試點數目 | 10 | 10 | 10 |
| 每個測試點分值 | 10 | 10 | 10 |
| 比較方式 | 全文比較 | 全文比較 | 全文比較 |
二、運行內存限制
| 運行內存上限 | 128 M | 128 M | 128 M |
?
1.放牧{Bronze題3}
【問題描述】
??? FJ的牧場是一個5X5的正方形,每個格子的大小是1X1,左上角是(1,1),右下角是(5,5)。
(1,1) (1,2) (1,3) (1,4) (1,5)
(2,1) (2,2) (2,3) (2,4) (2,5)
(3,1) (3,2) (3,3) (3,4) (3,5)
(4,1) (4,2) (4,3) (4,4) (4,5)
(5,1) (5,2) (5,3) (5,4) (5,5)
除了K個(0 <= K <= 22, K為偶數)格子,其他的每個格子都有牧草。貝牛從(1,1)開始放牧,米牛從(5,5)開始放牧,則兩個格子確保有牧場。
每半個小時,貝牛和米牛都會吃完他們各自所在格子里面的草,然后走到相鄰的格子里。他們想吃完所有的牧場,而且結束的時候在同一個位置。請計算一共有多少種方案。貝牛和米牛每次都走到有草的格子,而且他們不會同時走到同一個格子,除非當前格子是最后一個有草的格子。
【文件輸入】
??? 第一行,一整數K。
??? 第2..K+1行,每行兩個整數,表示一個沒有草的格子的行號和列號。
【文件輸出】
??? 一行,一個整數,表示方案數。
【輸入樣例】
4
3 2
3 3
3 4
3 1
輸入說明:
b? .? .? .? .
?
.? .? .? .? .
?
x? x? x? x? .
?
.? .? .? .? .
?
.? .? .? .? m
【輸出樣例】
1
【樣例說明】
b? b--b? b--b
|? |? |? |? |
b--b? b--b? b
??????????? ?|
x? x? x? x b/m
?????????? ???|
m--m--m--m--m
|
m--m--m--m--m
?
2. 登山{silver題3}
【問題描述】
??? FJ的準備讓他的N(1 <= N <= 25,000)頭年登山并下山。第i頭牛需要U(i)的時間登山,D(i)的時間下山。每頭牛上山和下山都需必須要一個農夫引導。現在有兩個農夫FJ(負責上山引導)和他的表哥FD(負責下山引導),在每個時間點,最多有一頭牛在登山,一頭牛在下山。一群牛可能會聚集在山頂等待FD的引導,牛群上山的順序和下山的順序可能不同。
??? 請計算整個登山活動(所有牛上山并下山)的最少時間花費。
【文件輸入】
??? 第一行,一個整數N,表示牛的數量。
??? 第2..N+1行,每行兩個整數U(i)和 D(i)。(1 <= U(i), D(i) <= 50,000).
【文件輸出】
??? 一行,一個整數,表示最小時間花費。
【輸入樣例】
3
6 4
8 1
2 3
【輸出樣例】
17
【樣例說明】
上山順序為3,1,2,下山順序也是3,1,2。
轉載于:https://www.cnblogs.com/jznoi/p/4171044.html
總結
以上是生活随笔為你收集整理的USACO翻译:USACO 2012 JAN三题(3)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: vue项目中运用webpack动态配置打
- 下一篇: [导入]为Exchange Server