CourseWare Wiki
Switch Term
Summer 2023 / 2024
Winter 2023 / 2024
Summer 2021 / 2022
Winter 2021 / 2022
Summer 2020 / 2021
Winter 2020 / 2021
Summer 2019 / 2020
Winter 2019 / 2020
Summer 2018 / 2019
Winter 2018 / 2019
Summer 2017 / 2018
Search
Log In
b232
courses
a4b36acm1
support
Differences
This shows you the differences between two versions of the page.
View differences:
Side by Side
Inline
Go
Link to this comparison view
Go
Go
courses:a4b36acm1:support [2018/10/03 03:51]
courses:a4b36acm1:support [2018/10/03 03:51]
(current)
Line 1:
Line 1:
+
+
<HTML>
+
<style>
+
.code .kw1, .code .kw2, .code .kw4 { color: #00f; font-weight: bold; text-decoration: underline;}
+
.code .br0, .code .kw3, .code .me1, .code .me2, .code .nu0 { color: #000; }
+
.code .co1, .code .coMULTI { color: #080; font-style: normal; }
+
.code .co2 { color: #888; font-style: normal; }
+
.code .st0 { color: #a31515; }
+
</style>
+
</HTML>
+
http://www.tutorialspoint.com/compile_cpp11_online.php
+
+
==== Ukázka převodu zápisu do z/do jiných základů ====
+
+
<code Cpp>
+
#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;
+
}
+
+
</code>
+
+
+
==== Ukázky pro 11. seminář 26.5.2016 ====
+
<code Cpp>
+
// 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;
+
}
+
</code>
+
+
<code Cpp>
+
// 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;
+
}
+
</code>
+
----
+
<code Cpp>
+
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;
+
}
+
</code>
+
+
+
+
==== Ukázky pro 11. seminář 5.5.2016 ====
+
<code Cpp>
+
#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);
+
}
+
</code>
+
+
+
+
==== Ukázky pro 8. seminář 14.4.2016 ====
+
<code Cpp>
+
// 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;
+
}
+
+
</code>
+
+
+
==== Ukázky pro 6. seminář 31.3.2016 ====
+
<code Cpp>
+
/////////////////////////////////////////////////////////////////////////
+
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;
+
}
+
+
</code>
+
+
==== Ukázky pro 4. seminář 17.3.2016 ====
+
+
{{:courses:a4b36acm:ukazkaprez.pptx| roury ppt}}, {{:courses:a4b36acm:ukazkaprez.pdf| roury pdf}}
+
+
LCS: https://cw.fel.cvut.cz/wiki/_media/courses/a4b33alg/alg10_2015c.pdf
+
+
+
+
<code Cpp>
+
/////////////////////////////////////////////////////////////////////////
+
// 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
+
}
+
}
+
+
</code>
+
+
+
==== Ukázky pro 3. seminář 10.3.2016 ====
+
+
=== Example: Union-Find Data Structure ===
+
Can be used to solve [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=1549|10608 - Friends]] and [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=1537|10596 - Morning Walk]].
+
+
<code Cpp>
+
#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]);
+
}
+
+
</code>
+
==== Ukázky pro 2. seminář 3.3.2016 ====
+
<code Cpp>
+
//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;
+
}
+
</code>
+
+
----
+
+
<code Cpp>
+
//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;
+
}
+
+
</code>
+
+
----
+
<code Cpp>
+
// 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;
+
}
+
</code>
+
+
----
+
{{:courses:a4b36acm:112img1.gif?200|}}
+
+
<code Cpp>
+
//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;
+
}
+
+
</code>
+
+
----
+
+
{{:courses:a4b36acm:986img1.gif?500|}}
+
+
<code Cpp>
+
// 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));
+
}
+
}
+
}
+
+
</code>
+
+
----
+
==== Konec ukázek ====
+
----
+
==== Jiné ====
+
+
http://www.fi.muni.cz/usr/jkucera/tic/tic0229.html
+
+
<code C pp>
+
//: 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;
+
}
+
*/
+
+
</code>
+
+
<code Cpp>
+
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
+
*/
+
+
+
}
+
</code>
+
+
+
<code Cpp>
+
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.
+
*/
+
}
+
+
</code>
+
+
+
<code>
+
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
+
</code>
+
+
<code Cpp>
+
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();
+
}
+
}
+
</code>
+
+
<code>
+
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
+
</code>
+
+
<code>
+
abbbaaaaaa
+
abbbaaaaaa
+
abbbaaaaaa
+
aaaaaaaaaa
+
aaaaaaaaaa
+
aaccaaaaaa
+
aaccaaaaaa
+
</code>
+
+
<code>
+
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
+
</code>
+
+
+
+
<code>
+
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,
+
</code>
+
+
<code Cpp>
+
+
// 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));
+
}
+
+
</code>
+
courses/a4b36acm1/support.txt
· Last modified: 2018/10/03 03:51 (external edit)