d816. 不要再晃啦！
內容 ：
21XX年，還沒滅亡的人類發明出一種超高科技的交通工具，至於是多高的科技呢？這已經超出題目的範圍了，因此忽略。
為什麼要稱它為交通工具呢？因為它是交通用的工具……其實是因為它的形體太過詭異，現代(201X年)科技根本難以形容，不過這種交通工具擁有輪胎，而且還分有前輪後輪，所以可以把它當成車(現代觀點)來看待。
這種車型交通工具有幾個特性：
1.輪子非常微小(奈米科技)。
2.前後輪的間隔正好等於交通工具的長度。
3.底盤非常的平整也非常的高。
根據以上兩點真正的超高科技設計，幾乎沒有地形可以困住它，也因此全世界各大客運都將舊式長方體笨重公車淘汰，改採用這種交通工具。
至於輪胎是怎麼接在車子上的，這點不用擔心，每個輪胎與底盤間都有根長度相同的桿子連接著。我知道這很難想像，畢竟是未來人超高科技之作。
不過這種設計只有唯一的一個缺點，那就是避震效果很糟。
* 以上都不是問題所在，接下來才真正要進入正題 *
相馬櫻久子是一個聰明且認真的高中女生。某天放學，她到了城市中最高的建築──公車站，這個時代的公車站有個特性，就是和公車一樣長度。而這只是題外話，相馬櫻久子搭上了她要坐的車，準備返家。
公車出發沒多久，認真的她就從包包中拿出作業來寫，一開始路面平穩，寫起作業來格外舒暢。
直到某次的劇烈晃動害得她的書上被畫出長長一痕後，她知道現在已經開到路面最顛簸的一段路了。
之後，公車的劇烈晃動使得她無法好好專心。
公車的路徑是條直線，她想知道公車從某一站開始出發，直到下一站而停下來的總路徑上，公車會怎麼搖晃，而很湊巧，她的手邊正好有一張她所搭乘的公車路徑的地形圖。
她只要知道某個時間公車相對於地平線的斜率(還是先假設地球是平的吧)，就能推算出公車會怎麼搖晃，因此她必須先計算出每秒鐘公車相對於地平線的斜率才行。
不過她現在必須專心唸書，好打敗她的宿敵結城水貶，根本沒有多餘的心思去計算這麼複雜的東西。
這時，你正好上車，會讀心術的你立即發覺她的困擾，並且坐到她旁邊的空位上，不知動機為何的你決定幫她寫出一個程式來解決這個艱難的問題。
(所有的長度單位都是公尺。)
(公車的水平速度保持一定，且每秒固定會往水平方向行進一公尺。)
輸入說明
：
輸入有多組測資，每組測資共有兩行。
第一行有兩個正整數 n, m (n <= 20, n < m <= 1000)， n 代表前後輪的間隔， m 代表公車從某一站出發到下一站停止期間，公車所經過的水平路徑長度。
第二行有 m 個正整數 Ai (Ai <= 100)， A1 表示某站起點的海拔高度(公尺)， A2 表示某站起點出發後水平距離一公尺的海拔高度…… Am 表示下一站終點的海拔高度。
測資保證每個位置公車底盤與地平面的夾角小於45度。
輸出說明
：
對於每組輸入，輸出從某站起點出發到下一站終點的過程中，每秒鐘公車的底盤相對於地平線的斜率，小數點以下無條件進位到個位數，並且取絕對值。
範例輸入 ：
1 3 1 1 1
範例輸出 ：
0 0
提示
：
不必擔心公車會被凸起路面給卡住，至於為什麼就不用多說了吧。
你可以假設相鄰兩點的路面是以平直直線連接。
對了，最好先看清楚說明，不然絕對會連第一筆測資都過不了。
(只要看懂題目，根本秒殺)
測資可能有誤，歡迎指教。
至於題意敘述不清……只能先說抱歉了，逐漸修正中。
2010/10/22 感謝pcsh710742發現測資錯誤！測資加大並修正測資錯誤。
2010/11/03 測資範圍大幅縮小了……重測TLE的程式碼。
出處
：
作法 : 題目過長，真是一時抓不到重點
簡單的說，就是求斜率，而且無須浮點數
優化一 : 輸入優化
優化二 : 輸出優化
/**********************************************************************************/
/* Problem: d816 "不要再晃啦！" from 專出Trash Problem */
/* Language: C */
/* Result: AC (88ms, 258KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-20 18:52:20 */
/**********************************************************************************/
#include<stdio.h>
int Input() {
char cha;
unsigned int x = 0;
while(cha = getchar())
if(cha != ' ' && cha != '\n' || cha == EOF) break;
if(cha == EOF) return EOF;
x = cha-48;
while(cha = getchar()) {
if(cha == ' ' || cha == '\n') break;
x = x*10 + cha-48;
}
return x;
}
main() {
int n, m, A[1001], a, b, temp, stp;
char str[10001];
while(scanf("%d %d", &n, &m) == 2) {
for(a = 0, stp = 0; a < n; a++)
A[a] = Input();
for(b = 0; a < m; a++, b++) {
A[a] = Input();
temp = A[b] - A[a];
if(temp < 0) temp = -temp;
temp = temp / n + (temp%n != 0);
if(temp < 100 && temp > 9)
str[stp++] = temp/10 + '0', str[stp++] = temp%10 + '0';
else if(temp < 10)
str[stp++] = temp +'0';
else
str[stp++] = '1', str[stp++] = '0', str[stp++] = '0';
str[stp++] = ' ';
}
str[stp] = '\0';
puts(str);
}
return 0;
}
/**********************************************************************************/
/* Problem: d816 "不要再晃啦！" from 專出Trash Problem */
/* Language: C */
/* Result: AC (264ms, 280KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-20 18:29:04 */
/**********************************************************************************/
#include<stdio.h>
int Input() {
char cha;
unsigned int x = 0;
while(cha = getchar())
if(cha != ' ' && cha != '\n' || cha == EOF) break;
if(cha == EOF) return EOF;
x = cha-48;
while(cha = getchar()) {
if(cha == ' ' || cha == '\n') break;
x = x*10 + cha-48;
}
return x;
}
main() {
int n, m, A[1001], a, b, temp;
while(scanf("%d %d", &n, &m) == 2) {
for(a = 0; a < n; a++)
A[a] = Input();
for(b = 0; a < m; a++, b++) {
A[a] = Input();
temp = A[b] - A[a];
if(temp < 0) temp = -temp;
temp = temp / n + (temp%n != 0);
printf("%d ", temp);
}
puts("");
}
return 0;
}
下一篇：d017. AB Circle