Search
http://www.tutorialspoint.com/compile_cpp11_online.php
#include <cstdio> #include <iostream> #include <math.h> using namespace std; int reverse( int a ) { int b = 0; while( a > 0 ) { b = b*10 + a%10; a /= 10; } return b; } int frombase( int n, int b ){ int powb = 1; int res = 0; int digit; while( n > 0 ) { digit = n % 10; // extract the digit res = res + digit*powb; powb *= b; n /= 10; // make next digit available } return res; } int tobase( int n, int b ) { // note: cannot make do without proper division and remainder int pow10 = 1; int res = 0; int digit; while( n > 0 ){ digit = n % b; // extract the digit res = res + digit*pow10; pow10 *= 10; n /= b; // make next digit available } return res; } int main( int argc, char ** argv ) { int a, b; while( true ) { //cin >> a; if( a < 0 ) break; cout << reverse(a) << endl; //cin >> a >> b; if( a < 0 ) break; cout << frombase(a, b) << endl; cin >> a >> b; if( a < 0 ) break; cout << tobase(a, b) << endl; } return 0; }
// UVA 11648 - Divide The Land #include <stdio.h> #include <iostream> #include <cmath> using namespace std; double a, b, c, d, h; double areaDifferenceUpperLower(double upperh, double lowerh) { double lenMidLineEF = d + (a-d) * upperh/h; double upper = ((lenMidLineEF + d) * upperh )/2; double lower = ((a + lenMidLineEF) * lowerh )/2; return upper-lower; } double f (double x) { return areaDifferenceUpperLower(h-x, x); } // <xL, xR> is a currently processed segment // in which at least one root of f exists, // i.e. values of function f in xL and xR must attain opposite signs double solveBisection(double xL, double xR) { double epsilon = 0.00000001; double xMid, fxL = f(xL), fxR = f(xR), fxMid ; while(xR - xL > epsilon) { xMid = (xL+xR) / 2; fxMid = f(xMid); if (fxL * fxMid <= 0) { xR = xMid; fxR = fxMid; } else { xL = xMid; fxL = fxMid; } } return (xL+xR)/2; } int main() { int N; double hopt; cin >> N; for(int i = 0; i < N; i++) { cin >> a >> d >> b >> c; // trapezoid height h = sqrt((-a+b+c+d) * (a+b+c-d) * (a-b+c-d) * (a+b-c-d)) / (2*abs(d-a)); // optimal height hopt = solveBisection(0, h); printf("Land #%d: %.6f %.6f\n", i, b*hopt/h, c*hopt/h); } return 0; }
// UVA 313 - Intervals #include <stdio.h> #include <algorithm> #include <iostream> #include <cmath> using namespace std; // Let P be a shade border point on the floor. // Suppose that Bx = 0 (everything is shifted horizontally), it makes formulas less cluttered. // The equation of the line BP is then (By)*X + (Px)*Y - By*Px = 0. // The distance of (Sx, Sy) from the line BP is exactly r. // Use the distance formula // dist( point, line) = |a*point_x + b*point_y + c| / sqrt(a^2 + b^2). // where a*X+b*Y+c is the equation of the line. // Plug By, Px, Sx, Sy into the quadratic equation // dist(point, line) = r // and solve for P. // Shift x-coord of P by Bx back to its correct position. struct floorPt { double xcoord; bool startShade; }; bool compare_floorPt (floorPt pt1, floorPt pt2) {return pt1.xcoord < pt2.xcoord;} int main() { // UVA 313 int N; double Bx, By, Sx, Sy, r; // input double P1, P2; // shade borders on the floor, P1 < P2 double a, b, c, D; //coeffs of qua eq. D is discriminant floorPt floorPts[2*500]; while (true) { // one case cin >> N; if (N == 0) break; cin >> Bx >> By; for(int i = 0; i < N; i++) { cin >> Sx >> Sy >> r; // move Sx by Bx to the left; Sx -= Bx; // solve quadratic equation: a = (Sy-By)*(Sy-By)-r*r; b = 2*By*Sx*(Sy-By); c = By*By*(Sx*Sx-r*r); D = b*b-4*a*c; P1 = (-b-sqrt(D))/(2*a); P2 = (-b+sqrt(D))/(2*a); // fill floor points array floorPts[2*i] = {P1, true}; floorPts[2*i+1] = {P2, false}; } // sort floor points std::sort(floorPts, floorPts+2*N, compare_floorPt); // output shades, move back to position by Bx int noofshades = 0; for(int i = 0; i < 2*N; i++) { if( floorPts[i].startShade ) { if (noofshades == 0) printf("%.2f ", floorPts[i].xcoord + Bx); noofshades++; } else { if (noofshades == 1) printf("%.2f\n", floorPts[i].xcoord + Bx); noofshades--; } } printf("\n"); } // end of case return 0; }
int main() { // UVA 737 int x1, x2, y1, y2, z1, z2; // lower and upper bounds of intersection cuboid int N, x, y, z, s; // no of cubes and current cube, s = size while (true) { cin >> N; if (N == 0) break; x1 = y1 = z1 = INT_MIN; x2 = y2 = z2 = INT_MAX; for( int i = 0; i < N; i++) { cin >> x >> y >> z >> s; x1 = max(x1, x); y1 = max(y1, y); z1 = max(z1, z); x2 = min(x2, x+s); y2 = min(y2, y+s); z2 = min(z2, z+s); } if( (x1 >= x2) || (y1 >= y2) || (z1 >= z2) ) cout << 0 << endl; else cout << (x2-x1)*(y2-y1)*(z2-z1) << endl; } return 0; }
#include <algorithm> #include <iostream> #include <cmath> #include <climits> using namespace std; int N; long long int maxv[400][400]; long long int minv[400][400]; char op [400]; int values[400]; long long int getmax(int i1, int k, int i2) { // k divides past k-th elem if (op[k] == '+') return maxv[i1][k]+maxv[k+1][i2]; if (op[k] == '-') return maxv[i1][k]-minv[k+1][i2]; if (op[k] == '*') return max(max(maxv[i1][k]*maxv[k+1][i2], minv[i1][k]*maxv[k+1][i2]), max(maxv[i1][k]*minv[k+1][i2], minv[i1][k]*minv[k+1][i2])); return max(max(maxv[i1][k]+maxv[k+1][i2], maxv[i1][k]-minv[k+1][i2]), // + and - max(max(maxv[i1][k]*maxv[k+1][i2], minv[i1][k]*maxv[k+1][i2]), // * max(maxv[i1][k]*minv[k+1][i2], minv[i1][k]*minv[k+1][i2]))); } long long int getmin(int i1, int k, int i2) { // k divides past k-th elem if (op[k] == '+') return minv[i1][k]+minv[k+1][i2]; if (op[k] == '-') return minv[i1][k]-maxv[k+1][i2]; if (op[k] == '*') return min(min(maxv[i1][k]*maxv[k+1][i2], minv[i1][k]*maxv[k+1][i2]), min(maxv[i1][k]*minv[k+1][i2], minv[i1][k]*minv[k+1][i2])); return min(min(minv[i1][k]+minv[k+1][i2], minv[i1][k]-maxv[k+1][i2]), // + and - min(min(maxv[i1][k]*maxv[k+1][i2], minv[i1][k]*maxv[k+1][i2]), // * min(maxv[i1][k]*minv[k+1][i2], minv[i1][k]*minv[k+1][i2]))); } void setmaxmin(int i1, int i2) { maxv[i1][i2] = LLONG_MIN; minv[i1][i2] = LLONG_MAX; for( int k = i1; k < i2; k++) { maxv[i1][i2] = max(maxv[i1][i2], getmax(i1, k, i2)); minv[i1][i2] = min(minv[i1][i2], getmin(i1, k, i2)); } } void allmaxmin() { // fill main diagonal for(int i = 0; i < N; i++) { maxv[i][i] = minv[i][i] = maxv[i+N][i+N] = minv[i+N][i+N] = (long long int) values[i]; op[i+N] = op[i]; } // fill all diagonals above the main diagonal, // up to and including (N-1)-th diagonal int i2; for( int idiag = 1; idiag < N; idiag++ ) for( int i1 = 0; i1 < 2*N-1-idiag; i1++ ){ i2 = i1+idiag; setmaxmin(i1, i2); } } //...................................................................... // D E B U G L I S T I N G //...................................................................... void listmaxmin(){ for( int i = 0; i < N; i++) printf("%4d", maxv[i][i+N-1]); printf("\n"); for( int i = 0; i < N; i++) printf("%4d", minv[i][i+N-1]); printf("\n"); printf("--------------------\n"); for( int i = 0; i < 2*N; i++) { for( int j = 0; j < 2*N; j++) printf("%4d", maxv[i][j]); printf("\n"); } printf("--------------------\n"); for( int i = 0; i < 2*N; i++) { for( int j = 0; j < 2*N; j++) printf("%4d", minv[i][j]); printf("\n"); } } //...................................................................... // M A I N //...................................................................... int main() { N = 3; op[0] = '*'; op[1] = '?'; op[2] = '+'; values[0] = 2; values[1] = 4; values[2] = 7; allmaxmin(); listmaxmin(); return(0); }
// maximum safe n = 62, binCoeff(62,31) == 465428353255261088 // safe: binCoeff(n, k) < 2^64 for any n, k. // if n > 62 then for some k it may hold binCoeff(n, k) < 2^64 // e.g. binCoeff(63,31) = 916312070471295267 > 2^64 = 18446744073709551616 // eg. binCoeff(80,21) = 10100903263463355200 < 2^64, // but binCoeff(80,22) = 27088786024742634400 > 2^64 unsigned long long int binCoeff( int n, int k ) { unsigned long long int coeff = 1; for( int d = 1; d <= k; d++ ) { coeff *= n; coeff /= d; n--; } return coeff; }
///////////////////////////////////////////////////////////////////////// int main() { // SPOJ M00PAIR int digi [1000][301] = {0}; // digits // precompute all int cy, sum; digi [2][0] = 1; for(int i = 3; i < 1000; i++) { sum = cy = 0; for(int j = 0; j < 301; j++) { sum = cy + 2*digi [i-2][j] + digi [i-1][j]; ff[i][j] = sum%10; cy = sum/10; } } int n, digit; while (cin >> n) { if (n == 1) { cout << 0 << endl; continue;} digit = 301; while(digi [n][--digit] == 0); while(digit >= 0) cout << digi [n][digit--]; cout << endl; } return 0; }
roury ppt, roury pdf
LCS: https://cw.fel.cvut.cz/wiki/_media/courses/a4b33alg/alg10_2015c.pdf
///////////////////////////////////////////////////////////////////////// // 10003 - Cutting Sticks #include <stdio.h> #include <string.h> #define MAXN 50 #define MAXC 50000 int main(void) { int i, j, k, l, maxL, N, L[MAXN + 2], C[MAXN + 1][MAXN + 2]; scanf("%d", &maxL); while (maxL != 0) { scanf("%d", &N); L[0] = 0; for (i = 1; i <= N; i++) scanf("%d", L + i); L[N + 1] = maxL; for (i = 0; i <= N; i++) { C[i][i + 1] = 0; for (j = i + 2; j <= N + 1; j++) C[i][j] = MAXC; } for (l = 2; l <= N + 1; l++) { for (i = 0; i <= N + 1 - l; i++) { j = i + l; for (k = i + 1; k < j; k++) { if (C[i][j] > (C[i][k] + C[k][j] + L[j] - L[i])) C[i][j] = (C[i][k] + C[k][j] + L[j] - L[i]); } } } printf("The minimum cutting is %d.\n", C[0][N + 1]); scanf("%d", &maxL); } return 0; } ///////////////////////////////////////////////////////////////////////// // SPOJ MMAXPER int main() { // Longer and Shorter sides of the rectangle int Lprev = 0, Sprev = 0, LprevOpt = 0, SprevOpt = 0; int Lcurr, Scurr, LcurrOpt, ScurrOpt, foo; int n; cin >> n; for(int i = 0; i < n; i++) { cin >> Lcurr >> Scurr; if (Lcurr < Scurr) { foo = Lcurr; Lcurr = Scurr; Scurr = foo;} if (i == 0) { LcurrOpt = Lcurr; ScurrOpt = Scurr; } else { LcurrOpt = max(LprevOpt + abs(Sprev-Scurr), SprevOpt + abs(Lprev-Scurr)) + Lcurr; ScurrOpt = max(LprevOpt + abs(Sprev-Lcurr), SprevOpt + abs(Lprev-Lcurr)) + Scurr; } Lprev = Lcurr; Sprev = Scurr; LprevOpt = LcurrOpt; SprevOpt = ScurrOpt; } cout << max(LcurrOpt, ScurrOpt) << endl; return 0; } ///////////////////////////////////////////////////////////////////////// int main() { // SPOJ BYTESH1 int U[3], L[3], S[3]; // DP table window for Upper, Lower, Straight int T, n; cin >> T; for(int i = 0; i < T; i++) { cin >> n; U[0] = U[1] = L[0] = L[1] = 0; S[0] = S[1] = S[2] = 1; // init DP table for(int k = 0; k < n-1; k++){ U[2] = L[2] = (U[1] + S[0]) % 10000; // DP table rules S[2] = (S[0]+S[1] + U[1] + L[1]) % 10000; L[0] = U[0] = U[1]; L[1] = U[1] = U[2]; // shift DP table window S[0] = S[1]; S[1] = S[2]; } cout << S[2] << endl; } return 0; } ///////////////////////////////////////////////////////////////////////// int main() { // UVA 10359 int ff [251][100] = {0}; // precompute all int cy, sum; ff[0][0] = ff[1][0] = 1; ff[2][0] = 3; for(int i = 3; i < 251; i++) { sum = cy = 0; for(int j = 0; j < 100; j++) { sum = cy + 2*ff[i-2][j] + ff[i-1][j]; ff[i][j] = sum%10; cy = sum/10; } } int n, digit; while (cin >> n) { digit = 100; while(ff[n][--digit] == 0); while(digit >= 0) cout << ff[n][digit--]; cout << endl; } return 0; } //1206167596222043702328864427173832373471562340267089208744349833415761767083 ///////////////////////////////////////////////////////////////////////// int main() { // UVA 900 int n; long long int f [51]; f[0] = f[1] = 1; for(int i = 2; i < 51; i++) f[i] = f[i-1] + f[i-2]; while (true) { cin >> n; if (n == 0) break; cout << f[n] << endl; } return 0; } ///////////////////////////////////////////////////////////////////////// int main() { // UVA 532 int Nmax = 30; // has not sentinel borders char maze [Nmax][Nmax][Nmax]; int dist [Nmax][Nmax][Nmax]; int L, R, C, INF = INT_MAX; int S0, S1, S2, E0, E1, E2; int q [Nmax*Nmax*Nmax][3]; int head, tail; while (true) { // read maze cin >> L >> R >> C; if (L+R+C == 0) break; string mazeline; for(int i = 0; i < L; i++) for(int j = 0; j < R; j++) { cin >> mazeline; fill(dist[i][j],dist[i][j] + C, INF); for(int k = 0; k < C; k++) if (mazeline[k] == 'S') { S0 = i, S1 = j; S2 = k;} else if (mazeline[k] == 'E') { E0 = i, E1 = j; E2 = k;} else if (mazeline[k] == '#') {dist[i][j][k] = -1;} // forbid walls } // run standard BFS q[0][0] = S0; q[0][1] = S1; q[0][2] = S2; dist[S0][S1][S2] = 0; head = 0; tail = 1; while(true) { // terminates in End -- success granted S0 = q[head][0]; S1 = q[head][1]; S2 = q[head][2]; head++; if (S0 > 0 && dist[S0-1][S1][S2] == INF) { dist[S0-1][S1][S2] = dist[S0][S1][S2]+1; q[tail][0] = S0-1; q[tail][1] = S1; q[tail++][2] = S2; } if (S0 < L-1 && dist[S0+1][S1][S2] == INF) { dist[S0+1][S1][S2] = dist[S0][S1][S2]+1; q[tail][0] = S0+1; q[tail][1] = S1; q[tail++][2] = S2; } if (S1 > 0 && dist[S0][S1-1][S2] == INF) { dist[S0][S1-1][S2] = dist[S0][S1][S2]+1; q[tail][0] = S0; q[tail][1] = S1-1; q[tail++][2] = S2; } if (S1 < R-1 && dist[S0][S1+1][S2] == INF) { dist[S0][S1+1][S2] = dist[S0][S1][S2]+1; q[tail][0] = S0; q[tail][1] = S1+1; q[tail++][2] = S2; } if (S2 > 0 && dist[S0][S1][S2-1] == INF) { dist[S0][S1][S2-1] = dist[S0][S1][S2]+1; q[tail][0] = S0; q[tail][1] = S1; q[tail++][2] = S2-1; } if (S2 < C-1 && dist[S0][S1][S2+1] == INF) { dist[S0][S1][S2+1] = dist[S0][S1][S2]+1; q[tail][0] = S0; q[tail][1] = S1; q[tail++][2] = S2+1; } if ( dist[E0][E1][E2] < INF ) { cout << dist[E0][E1][E2] << endl; break; } } // while true } }
Can be used to solve 10608 - Friends and 10596 - Morning Walk.
#define MAXN 200 int p[MAXN], r[MAXN]; int find(int i) { return (i != p[i]) ? (p[i] = find(p[i])) : p[i]; } void merge(int i, int j) { // PRECONDITION: i == p[i], j == p[j], i != j. if (r[i] > r[j]) { int k = i; i = j; j = k; } p[i] = j; r[j] += (r[i] == r[j]); }
//archive 2756 - Crazy tea party // reverse the order of guests around the table, only neigbours swaps are allowed // minimize no. of swaps. int main() { int T, n ; cin >> T; while(T-- > 0) { cin >> n; cout << (n*n - 2*n + (n%2))/4 << endl; } return 0; }
//archive 2158 - Factorial // For given N, find the number of trailing zeros in N!. int main() { int N, n, zeros; cin >> N; for(int i = 0; i < N; i++) { cin >> n; zeros = 0; while(n > 0) zeros += (n /= 5); cout << zeros << endl; } return 0; }
// archive 3078 - Alphacode // String contains only digits 0-9. In how many ways can it be decomposed to substrings // from the set {1, 2, 3, 4, ..., 25, 26}? int main() { string code; int count1, count2, foo, currval; while(true) { cin >> code; if (code[0] == '0') break; count1 = count2 = 1; currval = 0; for(int i = 0; i < code.size(); i++) { currval = (currval%10)*10+ ((int)code[i]-48); if (currval > 26 || currval < 10) count1 = count2; else if (currval % 10 == 0) count2 = count1; else { foo = count2; count2 += count1; count1 = foo;} //cout << count1 << " " << count2 << endl; } cout << count2 << endl; } return 0; }
//UVA 112- Tree Summing // Given a binary tree in prefix bracket format, check if there is a path from the root // to a leaf which sum of node values equals to the given prescribed values. // (annoyingly long code...) int main() { stack <int> st; int leafstring = (( '('*256+ ')') *256 + '(')*256 + ')'; // leaf == "()()" bool start = true; int I, nodeval = 0, sum = 0, last4 = 0; string line, found = "no"; while( std::getline (std::cin,line)) { for(int i = 0; i < line.size(); i++) { if (line[i] == ' ') continue; // detect number if ('0' <= line[i] && line[i] <= '9' ){ nodeval = nodeval*10 + (int)line[i] - 48; } // register new node or the prescribed sum else if (line[i] == '(') { if (start) {I = nodeval; nodeval = 0; start = false; continue;} if ((char)(last4 & 255) != ')' ) { // last char was digit st.push(nodeval); sum += nodeval; nodeval = 0; } } // leaving node, possibly leaf else if (line[i] == ')'){ if ((last4 == leafstring) && (I == sum)) found = "yes"; if ((char)(last4 & 255) == ')' ) { // last char was also ')' sum -= st.top(); st.pop(); } if (st.empty()) { cout << found << endl; start = true; found = "no"; } } // register last 4 chars in sliding window last4 = (last4 << 8) + (int)line[i]; } // for char in line } // while any line exists return 0; }
// Number of paths of lenght N which have exactly X peaks in height Y. // Number of rooted ordered trees with N nodes which have exactly X leaves in depth Y. public class UVA986 { // In each point we register for each K no of paths which end in this point and // have exactly K peaks in the prescribed height. // up[node][K] = up[node_Prev_Lower][K] + dn[node_Prev_Higher][K] // dn[node][K] = dn[node_Prev_Higher][K] + X // if (K == prescribed Height) X = dn[node_Prev_Lower][K-1] // new peak here // else X = dn[node_Prev_Lower][K] // no new peak here // DP tables corresponding to paths which last edge goes up resp. down. static int [][][] up = new int [41][23][22]; static int [][][] dn = new int [41][23][22]; // r peaks at height k static int num(int n, int r_peaks, int k_height ) { //clear table for(int i = 0; i < 2*n+1; i++) for(int j = 0; j < n+3; j++) for(int m = 0; m < r_peaks+2; m++) up[i][j][m] = dn[i][j][m] = 0; k_height++; // move up r because of indexing from 0 in the table up[0][1][1] = 1; // first edge of the first path for(int in = 1; in <= 2*n; in++) for(int ihe = 1; ihe < n+2; ihe++) for(int ipe = 1; ipe < r_peaks+2; ipe++) { up[in][ihe][ipe] = up[in-1][ihe-1][ipe] + dn[in-1][ihe+1][ipe]; dn[in][ihe][ipe] = dn[in-1][ihe+1][ipe]; if (ihe == k_height) dn[in][ihe][ipe] += up[in-1][ihe-1][ipe-1]; else dn[in][ihe][ipe] += up[in-1][ihe-1][ipe]; } // for all; return dn[2*n][1][r_peaks+1]; } public static void main(String[] args) throws IOException { String line; int n, r, k; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); while ((line = br.readLine()) != null ) { StringTokenizer st = new StringTokenizer(line); n = Integer.valueOf(st.nextToken()); r = Integer.valueOf(st.nextToken()); k = Integer.valueOf(st.nextToken()); System.out.printf("%d\n", num(n,r,k)); } } }
http://www.fi.muni.cz/usr/jkucera/tic/tic0229.html
//: C20:PriorityQueue1.cpp #include <iostream> #include <queue> #include <cstdlib> #include <ctime> using namespace std; int main() { priority_queue<int> pqi; srand(time(0)); // Seed random number generator for(int i = 0; i < 100; i++) pqi.push(rand() % 25); while(!pqi.empty()) { cout << pqi.top() << ' '; pqi.pop(); } } ///:~ /** #include <iostream> #include <queue> #include <vector> using namespace std; class Boxer{ public: string name; int strength; }; struct Comp{ bool operator()(const Boxer& a, const Boxer& b){ return a.strength<b.strength; } }; int main(){ + Boxer boxer[3]; boxer[0].name="uday", boxer[0].strength=23; boxer[1].name="manoj", boxer[1].strength=33; boxer[2].name="rajiv", boxer[2].strength=53; priority_queue< Boxer, vector<Boxer>, Comp> pq; pq.push(boxer[0]); pq.push(boxer[1]); pq.push(boxer[2]); Boxer b = pq.top(); cout<<b.name; //result is Rajiv return 0; } */
package lps; import java.util.Arrays; import java.util.Scanner; public class BinTree { static int N; static int root; static int nil = -1; static int [] Val; static int [] L; static int [] R; public static void main(String[] args) { loadFromStd(); print(root); System.out.printf("sum values %d\n", sumvals(root)); System.out.printf("no of leaves %d\n", noOfLeaves(root)); print(root, 0); } static void loadFromStd() { Scanner input = new Scanner( System.in ); N = input.nextInt(); Val = new int [N]; L = new int [N]; R = new int [N]; root = input.nextInt(); int curr; for(int i = 0; i < N; i++) { curr = input.nextInt(); Val[curr] = input.nextInt(); L[curr] = input.nextInt(); R[curr] = input.nextInt(); } } static int sumvals(int node) { if (node == nil) return 0; return Val[node] + sumvals(L[node]) + sumvals(R[node]); } static int noOfLeaves(int node) { if (L[node] == nil && R[node] == nil) return 1; return noOfLeaves(L[node]) + noOfLeaves(R[node]); } static void print(int node) { if (node == nil) return; System.out.printf("%d %d %d %d\n", node, Val[node], L[node], R[node]); print(L[node]); print(R[node]); } static void print(int node, int depth) { if (node == nil) return; print(R[node], depth+4); for(int i = 0; i < depth; i++) System.out.printf(" "); System.out.printf("[%d %d]\n", node, Val[node]); //print(R[node], depth+4); print(L[node], depth+4); } /* 11 3 0 9 -1 -1 1 10 0 2 2 20 -1 -1 3 30 1 6 4 40 -1 -1 5 50 4 8 6 60 5 10 7 70 -1 -1 8 80 7 9 9 90 -1 -1 10 100 -1 -1 */ }
package lps; // peg soli import java.util.Arrays; import java.util.Scanner; public class Graph { static int N, M; // nodes and edges static int [][] neighList; // https://en.wiktionary.org/wiki/neighbour static int [] dg; static int [][] adjMx; static int [][] edgeList; static int dist[]; public static void main(String[] args) { //loadGraphNeighListFromStd(); loadGraphMxFromStd(); hr(); adjMx2neighList(); printNeighList(); hr(); BFS_dists(0); printDists(); } // -------------------------------------------------------------------------- // P R O C E S S // -------------------------------------------------------------------------- static void BFS_dists(int startNode) { // allocate data structures int [] q = new int [N]; boolean [] Fresh = new boolean [N]; if (dist == null) dist = new int [N]; // intialize search int head =0, tail = 0, currNode, neigh; q[0] = startNode; Arrays.fill(Fresh, true); Fresh[startNode] = false; dist[startNode] = 0; // perform search while (head <= tail) { // queue not empty currNode = q[head++]; // check all neighbours of currNode for(int j = 0; j < dg[currNode]; j++) { neigh = neighList[currNode][j]; if (Fresh[neigh]) { // insert to queue and set the distance q[tail++] = neigh; dist[neigh] = dist[currNode]+1; Fresh[neigh] = false; } } } // while } static void adjMx2neighList(){ neighList = new int [N][1]; // expand neighbour list later dg = new int [N]; // populated by zeroes by default for(int i = 0; i < N-1; i++) for(int j = i+1; j < N; j++) if (adjMx[i][j] == 1) { // add edge if (dg[i] >= neighList[i].length) // adjust array size if necessary neighList[i] = Arrays.copyOf(neighList[i], dg[i]*2); neighList[i][dg[i]++] = j; if (dg[j] >= neighList[j].length) // adjust array size if necessary neighList[j] = Arrays.copyOf(neighList[j], dg[j]*2); neighList[j][dg[j]++] = i; } } // -------------------------------------------------------------------------- // L O A D // -------------------------------------------------------------------------- static void loadGraphMxFromStd() { Scanner input = new Scanner( System.in ); N = input.nextInt(); adjMx = new int [N][N]; for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) M += (adjMx[i][j] = input.nextInt()); M /= 2; // each edge counted twice } static void loadGraphEdgeListFromStd() { Scanner input = new Scanner( System.in ); N = input.nextInt(); M = input.nextInt(); edgeList = new int [M][2]; for(int i = 0; i < M; i++) { edgeList[i][0] = input.nextInt(); edgeList[i][1] = input.nextInt(); } } static void loadGraphNeighListFromStd() { Scanner input = new Scanner( System.in ); N = input.nextInt(); M = input.nextInt(); input.nextLine(); // technicality! skip EOL neighList = new int [N][]; // expand neighbour list later dg = new int [N]; int node, neigh; String inLine; String [] tokens; for(int i = 0; i < N; i++) { inLine = input.nextLine(); tokens = inLine.split("\\s+"); // enother technicality, suboptimal! node = Integer.valueOf(tokens[0]); dg[node] = tokens.length-1; neighList[node] = new int [dg[node]]; for(int j = 0; j < dg[node]; j++) neighList[node][j] = Integer.valueOf(tokens[j+1]); } } // -------------------------------------------------------------------------- // P R I N T // -------------------------------------------------------------------------- static void printNeighList () { System.out.printf("%d %d\n", N, M); for(int n = 0; n < N; n++) { System.out.printf("%d ", n); for(int j = 0; j < dg[n]; j++) System.out.printf("%d ", neighList[n][j]); System.out.printf("\n"); } } static void printMx () { for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) System.out.printf("%d ", adjMx[i][j]); System.out.printf("\n"); } } static void printEdges () { System.out.printf("%d %d\n", N, M); for(int n = 0; n < N; n++) { System.out.printf("%d %d\n", edgeList[n][0], edgeList[n][1]); } } static void printDists () { for(int i = 0; i < N; i++) System.out.printf("%d %d\n", i, dist[i]); } static void hr() { System.out.printf("--------------------------------------------\n"); } /* program divisibility; var i, x, n, y, a, t : integer; begin readln(t); for i := 1 to t do begin readln(n, x, y); a := x; while a < n do begin if a mod y <> 0 then write(a, ' '); a := a + x; end; end; {for} writeln; end. */ }
1 0.00 0.00 2 1.00 1.00 3 1.58 2.58 4 2.00 4.58 5 2.32 6.91 6 2.58 9.49 7 2.81 12.30 8 3.00 15.30 9 3.17 18.47 10 3.32 21.79
static boolean onborder2(double x, double y) { for(int i = 0; i < pows2.length; i++) if (x <= pows2[i] && y > pows2[i]) return true; return false; } static int [] pows2 = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096, 8192,16384,32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304}; static void bitsinfact() { double fbits = 0.0; double last_fbits = fbits; double log2n; int n = 1; while (fbits <= 4*1024*1024.0) { // 2^22 log2n = (Math.log(n)/Math.log(2)); fbits += log2n; if (onborder2(last_fbits, fbits)) System.out.printf("%d %.3f %.3f\n", n-1, last_fbits, fbits); last_fbits = fbits; n += 1; } } public static void main(String[] args) { bitsinfact(); } }
2 1.000 2.585 3 2.585 4.585 // corresponds to 1960 5 6.907 9.492 // corresponds to 1970 8 15.299 18.469 // corresponds to 1980 12 28.835 32.536 // corresponds to 1990 20 61.077 65.470 // ... 34 127.795 132.924 57 254.485 260.343 98 511.492 518.121 170 1019.369 1026.787 300 2041.278 2049.511 536 4091.998 4101.067 966 8191.380 8201.297 1754 16378.090 16388.868 3210 32767.327 32778.976 5910 65527.312 65539.841 10944 131064.158 131077.576 20366 262142.934 262157.248 38064 524281.326 524296.542 71421 1048567.205 1048583.330 134480 2097136.293 2097153.330 // corresponds to 2150 254016 4194288.154 4194306.108
abbbaaaaaa abbbaaaaaa abbbaaaaaa aaaaaaaaaa aaaaaaaaaa aaccaaaaaa aaccaaaaaa
a1 b1 b1 b1 a1 a1 a1 a1 a1 a1 a1 b1 b2 b2 a1 a2 a2 a2 a2 a2 a1 b1 b2 b3 a1 a2 a3 a3 a3 a3 a1 a1 a1 a1 a1 a2 a3 a4 a4 a4 a1 a2 a2 a2 a2 a2 a3 a4 a5 a5 a1 a2 c1 c1 a1 a2 a3 a4 a5 a6 a1 a2 c1 c2 a1 a2 a3 a4 a5 a6
0, 1, 5, 2, 8, 3, 9, 2, 8, 7, 7, 8, 4, 7, 3, 8, 4, 1, 5, 4, 4, 5, 9, 6, 2, 7, 3, 6, 2, 1, 1, 2, 8, 1, 7, 2, 8, 5, 9, 8, 8, 9, 3, 0, 6, 1, 7, 0, 6, 5, 5, 6, 2, 5, 1, 6, 2, 9, 3, 2, 2, 3, 7, 4, 0, 5, 1, 4, 0, 9, 9, 0, 6, 9, 5, 0, 6, 3, 7, 6, 6, 7, 1, 8, 4, 9, 5, 8, 4, 3, 3, 4, 0, 3, 9, 4, 0, 7, 1, 0, 0, 1, 5, 2, 8, 3, 9, 2, 8, 7, 7, 8, 4, 7, 3, 8, 4, 1, 5, 4, 4, 5, 9, 6, 2, 7, 3, 6, 2, 1, 1, 2, 8, 1, 7, 2, 8, 5, 9, 8, 8, 9, 3, 0, 6, 1, 7, 0, 6, 5, 5, 6, 2, 5, 1, 6, 2, 9, 3, 2, 2, 3, 7, 4, 0, 5, 1, 4, 0, 9, 9, 0, 6, 9, 5, 0, 6, 3, 7, 6, 6, 7, 1, 8, 4, 9, 5, 8, 4, 3, 3, 4, 0, 3, 9, 4, 0, 7, 1, 0,
// Checks if two segments intersect static boolean xx (int iA, int iB, int iC, int iD) { int ABx = x[iB]-x[iA]; int ABy = y[iB]-y[iA]; int CDx = x[iD]-x[iC]; int CDy = y[iD]-y[iC]; int det = ABy*CDx - ABx*CDy; // determinant decides linear (in)dependence if (det == 0) { // parallel vectors (linearly dependent) if ((x[iC]-x[iA])*ABy - (y[iC]-y[iA])*ABx != 0) // area triangle ABC return false; // parallel distinct lines // A B C D colinear, check their bounding boxes return Math.min(x[iA], x[iB]) <= Math.max(x[iC], x[iD]) && Math.min(x[iC], x[iD]) <= Math.max(x[iA], x[iB]) && Math.min(y[iA], y[iB]) <= Math.max(y[iC], y[iD]) && Math.min(y[iC], y[iD]) <= Math.max(y[iA], y[iB]) ; } // non parallel vectors, is point of intersection inside both segments? int num1 = (x[iA]-x[iC])*CDy + CDx*(y[iC]-y[iA]); int num2 = (y[iC]-y[iA])*ABx - ABy*(x[iC]-x[iA]); if (det < 0) return ((0 >= num1) && (num1 >= det) && (0 >= num2) && (num2 >= det)); else return ((0 <= num1) && (num1 <= det) && (0 <= num2) && (num2 <= det)); }