battleships naive solution

4 files changed, 294 insertions, 0 deletions

diff --git a/10812/beat.c b/10812/beat.c
new file mode 100644
index 0000000..58312fe
--- /dev/null
+++ b/10812/beat.c
@@ -0,0 +1,19 @@
+#include <stdio.h>
+
+int main(){
+    int tc;
+    scanf("%d", &tc);
+    while(tc--){
+	int s, d, s1, s2;
+	scanf("%d %d", &s, &d);
+
+	if(s < d || (s-d)%2!=0){
+	    printf("impossible\n");
+	}
+	else{
+	    s1 = (s-d)/2;
+	    s2 = s1+d;
+	    printf("%d %d\n", s2, s1);
+	}
+    }   
+}
diff --git a/10812/beat.in b/10812/beat.in
new file mode 100644
index 0000000..230f414
--- /dev/null
+++ b/10812/beat.in
@@ -0,0 +1,101 @@
+100
+2035415231 1462621774
+1545574401 1640829072
+2057229440 1467906174
+1081734409 696251185
+793988541 133513287
+694948272 1047026220
+700559794 1147657876
+1388555359 1794768220
+1297357647 936785271
+1457616687 1614991901
+1356558998 802008085
+1257599983 1301470168
+316770896 560794664
+1657777674 340228549
+47363255 1978022124
+1676487239 2082778486
+1293160250 1074577993
+1576123910 1202906043
+395000519 510374672
+1899157228 1188989060
+643887959 446621853
+88531632 1344447753
+1594279729 1477086992
+991732325 744153729
+266388615 301865364
+211661982 1622947613
+1103873449 1469261966
+776934133 1420644345
+2030056630 287228160
+1760872894 2077419885
+117766636 1289876486
+2012714723 1410926886
+216970831 1441354986
+466349281 611971350
+1951729658 218022862
+1800960410 448133969
+664644715 1889492042
+1792581722 111440796
+1219095386 636830399
+855594525 1485484002
+938695763 1067256508
+960947967 2042569213
+389034826 1737882101
+1315729910 271607808
+2025110261 929119157
+201544045 2142876897
+71511995 66775120
+1406320135 288482826
+1508130106 1872669417
+900454176 1312376116
+2090692279 553930938
+1760510085 607853346
+295939332 1405608159
+719294142 1515034719
+2042438558 1574888668
+853035073 833650674
+494661528 1813983040
+728736239 883696354
+1404381493 2044466149
+1155304162 1282008106
+826101658 1356848207
+1277401355 897613653
+1423623327 536237843
+1186096479 784269786
+261423612 2086550655
+2096645902 204632243
+492997945 1709672340
+812485589 788937278
+967796851 1531779731
+156488349 862751762
+959184751 1009523422
+1696402436 1453846279
+676022814 277655027
+190058985 2080404308
+174637528 1345363147
+1214928766 1000739187
+554727706 344846474
+1898352840 1978351034
+881084317 936965672
+615137172 1142507929
+876032679 564299426
+1347140172 1369030625
+126488118 12142113
+10484255 1094284970
+1543921844 166972604
+1957036732 355622948
+1176496026 1505955520
+1809469227 1852518840
+1783610547 1999528213
+1785439500 1958248075
+1197407712 852884619
+811503614 1752135419
+1197731093 562372807
+1583002805 2078815410
+1499338479 50656329
+1073839691 227887510
+614955755 273496215
+1596918135 741443874
+285638328 1607402390
+1835728844 1829560172
diff --git a/11953/battleships.cpp b/11953/battleships.cpp
new file mode 100644
index 0000000..1c122a6
--- /dev/null
+++ b/11953/battleships.cpp
@@ -0,0 +1,98 @@
+#include <iostream>
+#include <string>
+using namespace std;
+
+int finddir(int i, int j, int n, int map[][100]);
+bool isship(int, int, int [][100]);
+
+int main(){
+    int tc;
+    cin>>tc;
+    for(int ca = 1; ca<=tc; ca++){
+	int n;	
+	string s;
+	int map[100][100];
+	cin>>n;
+	for(int i=0; i<n; i++){
+	    cin>>s;
+	    for(int j=0; j<n; j++)
+		map[i][j]=(int)s[j];		    
+	}
+
+	int dir, shipcount =0;
+	bool broken=true;
+	for(int i=0; i<n; i++){
+	    for(int j=0; j<n; j++){
+		if(isship(i, j, map)){
+		    broken = true;
+		    dir = finddir(i, j, n, map);
+		    if(dir == 1){
+			//up
+			int up = i-1;
+			for(; up>=0 && isship(up,j, map); up--){
+			    if(map[up][j]==120)
+				broken=false;
+			    map[up][j]=0;
+			}
+			//down
+			int down = i+1;
+			for(; down<n && isship(down,j,map); down++){
+			    if(map[down][j]==120)
+				broken=false;
+			    map[down][j]=0;			    
+			}
+		    }
+		    else if(dir == 2){
+			//right
+			int right = j+1;
+			for(; right<n && isship(i,right,map); right++){
+			    if(map[i][right]==120)
+				broken=false;
+			    map[i][right]=0;			    
+			}
+			//left
+			int left = j-1;
+			for(; left>=0 && isship(i,left,map); left--){
+			    if(map[i][left]==120)
+				broken=false;
+			    map[i][left]=0;			    
+			}
+		    }
+		    else{
+			if(map[i][j]==120)
+			    broken=false;
+			map[i][j]=0;			
+		    }
+		    if(map[i][j]==120)
+			broken=false;
+		    
+		    map[i][j]=0;
+		    if(broken == false)
+			shipcount++;
+		    
+		}
+	    }
+	}
+	cout<<"Case "<<ca<<": "<<shipcount<<endl;
+    }
+}
+
+// 1: vertical, 2: horizontal, 0: alone
+int finddir(int i, int j, int n, int map[][100]){
+    int dir;
+    if(i+1<n && (map[i+1][j]==64 || map[i+1][j] == 120))
+	dir = 1;
+    else if(i-1>0 && (map[i-1][j]==64 || map[i-1][j] == 120))
+	dir = 1;
+    else if(j+1<n && (map[i][j+1]==64 || map[i][j+1] == 120))
+	dir = 2;
+    else if(j-1>n && (map[i][j-1]==64 || map[i][j-1] == 120))
+	dir = 2;
+    else
+	dir =0;
+    return dir;
+}
+
+bool isship(int i, int j, int map[][100]){
+    return (map[i][j]==64 || map[i][j] == 120);
+}
diff --git a/11953/battleships.in b/11953/battleships.in
new file mode 100644
index 0000000..9e73404
--- /dev/null
+++ b/11953/battleships.in
@@ -0,0 +1,76 @@
+11
+5
+x....
+x....
+.....
+.....
+.....
+6
+....@.
+.@...x
+@.@@@.
+@.....
+@..@.@
+.x.x..
+8
+@@@..@..
+.....x..
+..x..x.@
+x..@x...
+x.@..xx.
+.......x
+@@.....x
+..x.@...
+6
+x@x...
+......
+......
+......
+......
+......
+8
+.@x@@..@
+@......x
+@.x@..x.
+x.....@.
+.....@.x
+x.x@@..x
+.....x.@
+x..x....
+4
+x.x.
+x...
+x...
+..x@
+8
+...x.x..
+.....@..
+@x@@.@..
+.....@..
+.@..x.xx
+.x......
+..x.@x@@
+@..x....
+1
+x
+10
+..@.@x..@.
+..x.......
+.@....@..x
+..x.@.@..x
+..x..x.@..
+......x..@
+...@.....@
+@..@.....x
+.@.x.....@
+@.@.....x.
+3
+x..
+...
+@.@
+5
+...@.
+..@..
+.@...
+.x.@.
+.x...