Description

?

有道題目是這樣的:

輸入一個?n?行?m?列網格,找一個格子,使得它所在的行和列中所有格子的數之和最大。如果答 案不唯一,輸出任意解即可。比如,在下面的例子中,最優(yōu)解是(1,3),即第一行和的三列的交 點(行從上到下編號為?1~n,列從左到右編號為?1~m),所有?7?個數之和為?35。

?

?

快要比賽的時候,有一個裁判想到了這樣一個算法:

首先找一行?r(1<=r<=n)?使得該行所有數之和最大,然后找一列?c(1<=c<=m)?使得該列 所有數之和最大,最后直接輸出(r,c)。如果有多個滿足條件的?r,輸出最小的?r。對 于?c?同樣處理。

?

?

顯然,這個算法是錯的,但它竟然通過了大部分測試數據!你能找出那些讓這個錯誤算法得到 正確結果的“弱”數據,以便裁判們改進這些數據嗎?

Input

輸入包含不超過 100 組數據。每組數據第一行為兩個整數 n, m (1<=n<=500, 1<=m<=500),即行 數和列數。以下 n 行每行包含 m 個 1~100 的整數。輸入的總大小不超過 2MB。

Output

對于每組數據,如果錯誤算法能得到正確結果,輸出"Weak",否則輸出"Strong"。

Sample Input

4 4 5 5 5 5 1 1 5 1 1 1 5 1 1 1 5 1 5 4 2 5 1 1 1 1 9 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output

Case 1: Weak Case 2: Strong

Hint

Source

湖南省第十一屆大學生計算機程序設計競賽 【代碼】： #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<set> #include<map> #include<sstream> #include<queue> #include<cmath> #include<list> #include<vector> #include<string> using namespace std; #define long long ll const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int N = 100005; int n, m, tot; int a[550][550]; int sum[5000][5000]; int r[550], c[550]; int x, y, pr, pc, k = 1; int main() {while(cin >> n >> m){int px, py;memset(r,0,sizeof(r));memset(c,0,sizeof(c));int Mr = -1, Mc = -1, Max = -1;for(int i=1; i<=n; i++)for(int j=1; j<=m; j++){cin >> a[i][j];}for(int i=1; i<=n; i++) //行 {//memset(r,0,sizeof(r));for(int j=1; j<=m; j++){r[i] += a[i][j];}if(r[i] > Mr){ Mr = r[i]; pr = i; }}for(int j=1; j<=m; j++) //列 {//memset(c,0,sizeof(c));for(int i=1; i<=n; i++){c[j] += a[i][j];}if(c[j] > Mc){ Mc = c[j]; pc = j;}}printf("Case %d: ",k++);//truefor(int i=1; i<=n; i++){for(int j=1; j<=m; j++){sum[i][j] = r[i] + c[j] - a[i][j];if(sum[i][j] > Max){Max = sum[i][j];px = i;py = j;}}}//falseint M = r[pr] + c[pc] - a[pr][pc];if(M == Max){puts("Weak");}else{puts("Strong");}/*測試代碼for(int i=1; i<=n; i++){printf("%d ",r[i]);}cout<<endl;for(int i=1; i<=m; i++){printf("%d ",c[i]);}cout<<endl;printf("mr=%d mc=%d M=%d\n",Mr,Mc,M);printf("pr=%d pc=%d\n",pr,pc);for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){printf("%2d ",sum[i][j]);}cout<<endl;}printf("px=%d py=%d Max=%d\n",px,py,Max);*/}return 0; }

?

轉載于:https://www.cnblogs.com/Roni-i/p/8711015.html

總結

以上是生活随笔為你收集整理的CSU 1779: 错误的算法【矩阵/模拟】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。