## 2012年8月30日

### UVa 10037 - Bridge

Reference : http://www.csie.ntnu.edu.tw/~u91029/Greedy.html#4
#include <cstdio>
#include <algorithm>

int main() {
int i, n, c, num[1001];
scanf("%d", &c);
while (c--) {
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &num[i]);
std::sort(num, num + n);
int t = 0, t1, t2, rec = n;

for (n--; n >= 3; n -= 2) {
t1 = num[0] + num[1] * 2 + num[n];
t2 = num[0] * 2 + num[n - 1] + num[n];
if (t1 < t2) t += t1;
else t += t2;
}

if (n == 2) t += num[0] + num[1] + num[2];
else if (n == 1) t += num[1];
else t += num[0];
printf("%d\n", t);

n = rec;

for (n--; n >= 3; n -= 2) {
t1 = num[0] + num[1] * 2 + num[n];
t2 = num[0] * 2 + num[n - 1] + num[n];
if (t1 < t2) printf("%d %d\n%d\n%d %d\n%d\n", num[0], num[1], num[0], num[n - 1], num[n], num[1]);
else printf("%d %d\n%d\n%d %d\n%d\n", num[0], num[n], num[0], num[0], num[n - 1], num[0]);
}

if (n == 2) printf("%d %d\n%d\n%d %d\n", num[0], num[1], num[0], num[0], num[2]);
else if (n == 1) printf("%d %d\n", num[0], num[1]);
else printf("%d\n", num[0]);
if (c) puts("");
}
return 0;
}

## 2012年8月25日

### UVa 111 - History Grading

It's hard to understand the meaning of this problem by my poor English.
#include <stdio.h>

int max (int a, int b) {
return a > b ? a : b;
}

int main() {
int n;
while (scanf("%d", &n) == 1) {
int i, j, tmp, a[50], b[50], array[50][50];
for (i = 1; i <= n; i++) {
scanf("%d", &tmp);
a[tmp] = i;
}
while (scanf("%d", &tmp) == 1) {
b[tmp] = 1;
for (i = 2; i <= n; i++) {
scanf("%d", &tmp);
b[tmp] = i;
}
for (i = 0; i <= n; i++)
for (j = 0; j <= n; j++)
array[i][j] = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (a[i] == b[j]) array[i][j] = array[i - 1][j - 1] + 1;
else array[i][j] = max(array[i - 1][j], array[i][j - 1]);
printf("%d\n", array[n][n]);
}
}
return 0;
}

## 2012年8月24日

### UVa 729 - The Hamming Distance Problem

Practice to use next_permutation!
#include <stdio.h>
#include <algorithm>

using std::next_permutation;

int main() {
int t;
scanf("%d", &t);
while (t--) {
int i, n, h;
scanf("%d%d", &n, &h);
int *num = new int[n];
for (i = 0; i < n - h; i++)
num[i] = 0;
for (; i < n; i++)
num[i] = 1;

do {
for (i = 0; i < n; i++)
printf("%d", num[i]);
puts("");
} while (next_permutation(num, num + n));
if (t) puts("");
delete[] num;
}
return 0;
}

### UVa 353 - Pesky Palindromes

#include <stdio.h>
#include <string.h>

int N;
char all[100][1000];

int pal(char* tmp, int min, int max) {
int i, l = max - min, flag = 1;
for (i = min; i <= min + l / 2; i++)
if (tmp[i] != tmp[max - i + min]) {
flag = 0;
break;
}
char temp[100];
for (i = 0; i < l; i++)
temp[i] = tmp[i + min];
temp[i] = '\0';
for (i = 0; i < N; i++)
if (!strcmp(all[i], temp)) {
flag = 0;
break;
}
if (flag == 1) strcpy(all[N++], temp);
return flag;
}

int main() {
char tmp[100];
while (scanf("%s", &tmp) == 1) {
N = 0;
int i, j, asc[129] = {0}, times = 0;
for (i = 0; tmp[i]; i++) {
if (!asc[tmp[i]]) {
asc[tmp[i]] = 1;
times++;
}
for (j = i + 1; tmp[j]; j++)
if (i != j && pal(tmp, i, j)) times++;
}
printf("The string '%s' contains %d palindromes.\n", tmp, times);
}
return 0;
}

### UVa 11466 - Largest Prime Divisor

Critical point : n should have more than one prime divisors.
For example : 16 : 2*2*2*2 , should print -1!

#include <stdio.h>
#include <math.h>
#define S 10000000

bool *prime = new bool[S];
int N = 0;
int *p = new int[664600];
void build() {
long long int i, j, k, s = sqrt(S);
prime[0] = true;
prime[1] = true;
for (i = 2; i <= s; i++)
if (!prime[i])
for (k = (S - 1) / i, j = i * k; k >= i; k--, j -= i)
if (!prime[k])
prime[j] = true;
for (i = 0; i < S; i++)
if (!prime[i]) p[N++] = i;
}

int main() {
build();
long long int n, max, tmp;
while (scanf("%lld", &n) && n) {
int i, times = 0;
if (n < 0) n *= -1;
tmp = n;
max = -1;
for (i = 0; i < N && n != 1; i++) {
if (!(n % p[i]) && p[i] != tmp) {
times++;
while (!(n % p[i])) {
n /= p[i];
if (n == 1 && times > 1) {
max = p[i];
break;
}
}
}
}
if (n != 1 && n != tmp) max = n;
printf("%lld\n", max);
}
delete[] prime;
delete[] p;
return 0;
}

## 2012年8月23日

### UVa 537 - Artificial Intelligence?

#include <stdio.h>

int main() {
int i, c, n;
scanf("%d%*c", &n);
for (c = 1; c <= n; c++) {
printf("Problem #%d\n", c);
double U = -1, I = -1, P = -1;
char tmp[20000];
for (i = 0; ; i++) {
tmp[i] = getchar();
if (tmp[i] == '\n') break;
if (tmp[i] == '=') {
switch (tmp[i - 1]) {
case 'U':
U = 0;
scanf("%lf", &U);
tmp[i] = getchar();
if (tmp[i] == 'm') U *= 0.001;
else if (tmp[i] == 'k') U *= 1000.0;
else if (tmp[i] == 'M') U *= 1000000.0;
break;
case 'P':
P = 0;
scanf("%lf", &P);
tmp[i] = getchar();
if (tmp[i] == 'm') P *= 0.001;
else if (tmp[i] == 'k') P *= 1000.0;
else if (tmp[i] == 'M') P *= 1000000.0;
break;
case 'I':
I = 0;
scanf("%lf", &I);
tmp[i] = getchar();
if (tmp[i] == 'm') I *= 0.001;
else if (tmp[i] == 'k') I *= 1000.0;
else if (tmp[i] == 'M') I *= 1000000.0;
break;
}
}
}
if (P == -1) printf("P=%.2lfW", U * I);
else if (I == -1) printf("I=%.2lfA", P / U);
else printf("U=%.2lfV", P / I);
puts("");
puts("");
}
return 0;
}

### UVa 748 - Exponentiation

It will be easy by using Java!

import java.math.BigDecimal;
import java.util.*;

public class Main {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
BigDecimal a = cin.nextBigDecimal();
int e = cin.nextInt();
a = a.pow(e);
char[] s = a.toPlainString().toCharArray();
int l, flag = 0;
if (s[0] == '0') flag = 1;
for (l = s.length; l >= 0; l--)
if (s[l - 1] != '0') break;
for (int i = flag; i < l; i++)
System.out.print(s[i]);
System.out.println("");
}
}
}

### UVa 495 - Fibonacci Freeze

#include <cstdio>
#include <string>
using std::string;

string add(string a, string b) {
int carry = 0, temp;
int digit, digitA, digitB;
digitA = a.length();
digitB = b.length();;
digit = digitA > digitB ? digitA : digitB;
while (digit > 0) {
temp = carry;
if (--digitA >= 0) temp += a[digitA] - '0';
if(--digitB >= 0) temp += b[digitB] - '0';
carry = temp / 10;
temp %= 10;
--digit;
}
}

int main() {
int i, n;
string num[5001];
num[0] = "0";
num[1] = "1";
for (i = 2; i < 5001; i++)
num[i] = add(num[i - 1], num[i - 2]);
while (scanf("%d", &n) == 1)
printf("The Fibonacci number for %d is %s\n", n, num[n].c_str());
return 0;
}

## 2012年8月22日

### UVa 489 - Hangman Judge

There's a trap, round = n you input, not times!

#include <stdio.h>

int main() {
int n;
while (scanf("%d", &n) && n > 0) {
char q[20], a[20];
int i, asc[129] = {0}, max = 0, line = 0;
scanf("%s", &q);
for (i = 0; q[i]; i++) {
if (!asc[q[i]]) max++;
asc[q[i]] = 1;
}
scanf("%s", &a);
for (i = 0; a[i]; i++)
if (!asc[a[i]]) {
asc[a[i]] = 2;
line++;
if (line == 7) break;
} else if (asc[a[i]] == 1) {
max--;
asc[a[i]] = 2;
if (max == 0) break;
}
printf("Round %d\n", n);
if (!max) puts("You win.");
else if (line == 7) puts("You lose.");
else puts("You chickened out.");
}
return 0;
}

### UVa 492 - Pig-Latin

#include <stdio.h>

int main() {
char c;
int flag = 0, remove = 0, word = 0;
while (scanf("%c", &c) == 1) {
if (!flag) {
if (isalpha(c)) {
flag = 1;
if (c != 'a' && c != 'A' && c != 'e' && c != 'E' && c != 'i' && c != 'I' && c != 'o' && c != 'O' && c != 'u' && c != 'U') {
remove = c;
continue;
} else remove = 0;
}
}
if (!isalpha(c)) {
if (flag) {
if (remove) putchar(remove);
printf("ay");
}
remove = 0;
flag = 0;
}
putchar(c);
}
return 0;
}

## 2012年8月21日

### UVa 160 - Factors and Factorials

A prime problem.

#include <stdio.h>

int p = 0, prime[110];

void build() {
int i, j, tmp[110];
for (i = 0; i < 110; i++)
tmp[i] = 1;
tmp[0] = 0;
tmp[1] = 0;
for (i = 2; i < 110; i++)
if (tmp[i])
for (j = i * i; j < 110; j += i)
tmp[j] = 0;
for (i = 0; i < 110; i++)
if (tmp[i]) prime[p++] = i;
}

int main() {
build();
int i, j, n;
while (scanf("%d", &n) && n) {
int tmp, pNum[110] = {0};
printf("%3d! =", n);
for (i = n; i >= 2; i--) {
tmp = i;
for (j = 0; tmp > 1; j++)
while (!(tmp % prime[j])) {
pNum[j]++;
tmp /= prime[j];
}
}
for (i = 0; pNum[i]; i++) {
if (i && !(i % 15)) printf("\n      ");
printf("%3d", pNum[i]);
}
puts("");
}
return 0;
}

### UVa 119 - Greedy Gift Givers

#include <stdio.h>
#include <string.h>

typedef struct People People;

struct People {
char name[20];
int money;
};

int main() {
int i, j, n, first = 0;
while (scanf("%d\n", &n) == 1) {
if (first)
puts("");
first = 1;
People people[20];
for (i = 0; i < n; i++) {
scanf("%s", &people[i].name);
people[i].money = 0;
}
getchar();
for (i = 0; i < n; i++) {
int money, Money, num;
char name[20];
scanf("%s %d %d", &name, &Money, &num);
getchar();
if (num) {
for (j = 0; j < n; j++)
if (!strcmp(people[j].name, name)) break;
money = Money / num;
people[j].money -= money * num;
}
while (num--) {
scanf("%s", &name);
for (j = 0; j < n; j++)
if (!strcmp(people[j].name, name)) break;
people[j].money += money;
}
}
for (i = 0; i < n; i++)
printf("%s %d\n", people[i].name, people[i].money);
}
return 0;
}

### UVa 11547 - Automatic Answer

It took me a while to know the meaning of this problem!

#include <stdio.h>

int main() {
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
int ans = ((n * 63 + 7492) * 5 - 498) % 100 / 10;
printf("%d\n", ans < 0 ? -1 * ans : ans);
}
return 0;
}

## 2012年8月20日

### UVa 612 - DNA Sorting

#include <stdio.h>
#include <stdlib.h>

typedef struct Value Value;
struct Value{
int index;
int meansure;
};

int cmp (const void *a, const void *b) {
return ((Value*)a) -> meansure - ((Value *)b) -> meansure;
}

int main() {
int t;
scanf("%d", &t);
getchar();
while (t--) {
char map[110][110];
Value v[110];
int i, j, k, n, m, tmp;
scanf("%d%d", &n, &m);
getchar();
for (i = 0; i < m; i++) {
v[i].index = i;
gets(map[i]);
}
for (i = 0; i < m; i++) {
tmp = 0;
for (j = 0; j < n; j++)
for (k = j + 1; k < n; k++)
if (map[i][j] > map[i][k]) tmp++;
v[i].meansure = tmp;
}
qsort(v, m, sizeof(Value), cmp);
for (i = 0; i < m; i++)
puts(map[v[i].index]);
if (t)
puts("");
}
return 0;
}

### UVa 706 - LCD Display

#include <stdio.h>
void display(int n, int t, int type) {
int i, j;
switch (type) {
case 1:
putchar(' ');
for (i = 0; i < t; i++)
printf("%c", (n == 1 || n == 4) ? ' ' :  '-');
putchar(' ');
break;
case 2:
if (n == 1 || n == 2 || n == 3 || n == 7) putchar(' ');
else putchar('|');
for (i = 0; i < t; i++)
putchar(' ');
printf("%c", (n == 5 || n == 6) ? ' ' :  '|');
break;
case 3:
putchar(' ');
for (i = 0; i < t; i++)
printf("%c", (n == 1 || n == 7 || n == 0) ? ' ' :  '-');
putchar(' ');
break;
case 4:
if (n == 1 || n == 3 || n == 4 || n == 5 || n == 7 || n == 9) putchar(' ');
else putchar('|');
for (i = 0; i < t; i++)
putchar(' ');
printf("%c", (n == 2) ? ' ' :  '|');
break;
case 5:
putchar(' ');
for (i = 0; i < t; i++)
printf("%c", (n == 1 || n == 4 || n == 7) ? ' ' :  '-');
putchar(' ');
break;
}
}
int main() {
int i, j, k, n, times, type;
while (scanf("%d %d", ×, &n) && times || n) {
char num[20];
sprintf(num, "%d", n);
for (type = 1; type <= 5; type++) {
if (type == 2 || type == 4) k = times;
else k = 1;
while (k--) {
for (i = 0; num[i] != '\0'; i++) {
if (i) putchar(' ');
display(num[i] - '0', times, type);
}
puts("");
}
}
puts("");
}
return 0;
}

### UVa 106 - Fermat vs. Pythagoras

We have to know a formula before doing this problem.
This problem will be very easy by using this formula!

#include <stdio.h>

int gcd (int a, int b) {
while ((a %= b) && (b %= a));
return a + b;
}

int main() {
int n;
while (scanf("%d", &n) == 1) {
int i, j, ans = 0, part = 0;
bool *have = new bool[n + 1];
for (i = 0; i <= n; i++)
have[i] = 0;
for (i = 1; i * i < n; i++) {
for (j = i + 1; (i * i + j * j) <= n; j += 2) {
if (gcd(i, j) != 1) continue;
int a = 2 * j * i, b = j * j - i * i, c = j * j + i * i;
ans++;
int A = a, B = b, C = c;
while (C <= n) {
if (!have[A]) part++;
if (!have[B]) part++;
if (!have[C]) part++;
have[A] = 1;
have[B] = 1;
have[C] = 1;
A += a;
B += b;
C += c;
}
}
}
printf("%d %d\n", ans, n - part);
delete[] have;
}
return 0;
}

### UVa 294 - Divisors

#include <stdio.h>
#include <math.h>
#define S 35000

bool *prime = new bool[S];
int *p = new int[S], num = 0;
void build() {
long long int i, j, k, s = sqrt(S);
prime[0] = true;
prime[1] = true;
for (i = 2; i <= s; i++)
if (!prime[i])
for (k = (S - 1) / i, j = i * k; k >= i; k--, j -= i)
if (!prime[k])
prime[j] = true;
for (i = 0; i < S; i++)
if (!prime[i])
p[num++] = i;
}
int div(int n) {
if (n == 1) return 1;
int i, ans = 0, tmp;
for (i = 0; i < num && p[i] <= n; i++) {
tmp = 0;
while (n % p[i] == 0) {
tmp++;
n /= p[i];
}
if (!ans && tmp)
ans = 1;
ans *= (tmp + 1);
}
return ans;
}
int main() {
build();
int i, a, b, n;
scanf("%d", &n);
while (n--) {
scanf("%d%d", &a, &b);
int tmp, max = 0, ans;
for (i = a; i <= b; i++) {
tmp = div(i);
if (tmp > max) {
max = tmp;
ans = i;
}
}
printf("Between %d and %d, %d has a maximum of %d divisors.\n", a, b, ans, max);
}
return 0;
}

### UVa 10281 - Average Speed

#include <stdio.h>

int main() {
char tmp[20];
double h = 0, m = 0, s = 0, speed = 0, H, M, S, Speed, km = 0;
while (gets(tmp) != NULL) {
if (tmp[8]) sscanf(tmp, "%lf:%lf:%lf %lf", &H, &M, &S, &Speed);
else sscanf(tmp, "%lf:%lf:%lf", &H, &M, &S);
if (!tmp[8]) {
km += (H - h) * speed + (M - m) * speed / 60 + (S - s) * speed / 3600;
printf("%s %.2lf km\n", tmp, km);
} else {
km += (H - h) * speed + (M - m) * speed / 60 + (S - s) * speed / 3600;
}
h = H;
m = M;
s = S;
speed = Speed;
}
return 0;
}

### UVa 583 - Prime Factors

#include <stdio.h>
#include <math.h>
#define S 50000

bool *prime = new bool[S];
int *p = new int[S], num = 0;
void build() {
long long int i, j, k, s = sqrt(S);
prime[0] = true;
prime[1] = true;
for (i = 2; i <= s; i++)
if (!prime[i])
for (k = (S - 1) / i, j = i * k; k >= i; k--, j -= i)
if (!prime[k])
prime[j] = true;
for (i = 0; i < 50000; i++)
if (!prime[i])
p[num++] = i;
}

int main() {
build();
int i, n;
while (scanf("%d", &n) && n != 0) {
printf("%d = ", n);
if (n < 0) {
printf("-1 x ");
n *= -1;
}
if (n == 2147483647) {
printf("%d\n", n);
continue;
}
int first = 1, flag = 0;
for (i = 0; n > 1 && i < num && p[i] <= n; i++) {
while (n > 1 && n % p[i] == 0) {
if (first == 1) printf("%d", p[i]);
else printf(" x %d", p[i]);
first = 0;
n /= p[i];
flag = 1;
}
}
if (!flag)
printf("%d", n);
puts("");
}
delete[] p;
delete[] prime;
return 0;
}

### UVa 300 - Maya Calendar

#include <stdio.h>
#include <string.h>

char* M[20] = {"imix", "ik", "akbal", "kan", "chicchan", "cimi", "manik", "lamat", "muluk", "ok", "chuen", "eb", "ben", "ix", "mem", "cib", "caban", "eznab", "canac", "ahau"};
int main() {
int t, d, m, y;
char tmp[30];
scanf("%d\n", &t);
printf("%d\n", t);
while (t--) {
scanf("%d. %s %d", &d, &tmp, &y);
m = 0;
if (!strcmp(tmp, "no"))
m = 1;
if (!strcmp(tmp, "zip"))
m = 2;
if (!strcmp(tmp, "zotz"))
m = 3;
if (!strcmp(tmp, "tzec"))
m = 4;
if (!strcmp(tmp, "xul"))
m = 5;
if (!strcmp(tmp, "yoxkin"))
m = 6;
if (!strcmp(tmp, "mol"))
m = 7;
if (!strcmp(tmp, "chen"))
m = 8;
if (!strcmp(tmp, "yax"))
m = 9;
if (!strcmp(tmp, "zac"))
m = 10;
if (!strcmp(tmp, "ceh"))
m = 11;
if (!strcmp(tmp, "mac"))
m = 12;
if (!strcmp(tmp, "kankin"))
m = 13;
if (!strcmp(tmp, "muan"))
m = 14;
if (!strcmp(tmp, "pax"))
m = 15;
if (!strcmp(tmp, "koyab"))
m = 16;
if (!strcmp(tmp, "cumhu"))
m = 17;
if (!strcmp(tmp, "uayet"))
m = 18;
int days = m * 20 + d + 1 + y * 365;
m = days % 20 - 1;
if (m == -1)
m = 19;
d = days % 13;
if (!d)
d = 13;
y = days / 260 - !(days % 260);
printf("%d %s %d\n", d, M[m], y);
}
return 0;
}

### UVa 10034 - Freckles

#include <stdio.h>
#include <math.h>

typedef struct {
double x, y;
} Point;

int main() {
int i, j, n, t;
scanf("%d", &t);
while (t--) {
Point p[150];
int visit[150] = {0};
double x, y, w[150][150], d[150], ans = 0;
scanf("%d", &n);
for (i = 0; i < n; i++)
d[i] = 2e9;
d[0] = 0;
parent[0] = 0;
for (i = 0; i < n; i++)
scanf("%lf%lf", &p[i].x, &p[i].y);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
w[i][j] = sqrt(pow((p[i].x - p[j].x), 2) + pow(p[i].y - p[j].y, 2));
for (i = 0; i < n; i++) {
int a = -1, b = -1, min = 2e9;
for (j = 0; j < n; j++)
if (!visit[j] && d[j] < min) {
a = j;
min = d[j];
}
if (a == -1) break;
visit[a] = 1;

for (b = 0; b < n; b++)
if (!visit[b] && w[a][b] < d[b]) d[b] = w[a][b];
}
for (i = 0; i < n; i++)
ans += d[i];
printf("%.2lf\n", ans);
if (t)
puts("");
}
return 0;
}

## 2012年8月18日

### UVa 101 - The Blocks Problem

#include <stdio.h>
#include <string.h>

typedef struct {
int loc;
int num;
} Block;
Block block[25];
int map[25][25];

void put (int a, int b) {
int i, j, loc = block[a].loc, nloc = block[b].loc;
for (i = 0; map[nloc][i] != -1; i++);
for (j = 0; map[loc][j] != a; j++);
map[nloc][i] = map[loc][j];
map[loc][j] = -1;
block[a].loc = nloc;
}

void pile (int a, int b) {
int i, j, loc = block[a].loc, nloc = block[b].loc;
for (i = 0; map[nloc][i] != -1; i++);
for (j = 0; map[loc][j] != a; j++);
for ( ; map[loc][j] != -1; j++) {
block[map[loc][j]].loc = nloc;
map[nloc][i++] = map[loc][j];
map[loc][j] = -1;
}
}

void returning (int n) {
int i, j, loc = block[n].loc, nloc;
for (i = 0; map[loc][i] != n; i++);
for (i++; map[loc][i] != -1; i++) {
nloc = block[map[loc][i]].num;
for (j = 0; map[nloc][j] != -1; j++);
map[nloc][j] = map[loc][i];
block[map[loc][i]].loc = nloc;
map[loc][i] = -1;
}
}

int main() {
int i, j, n;
while (scanf("%d", &n) == 1) {
getchar();
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
map[i][j] = -1;
block[i].loc = i;
block[i].num = i;
map[i][0] = i;
}

char action[10], method[10];
int a, b;
while (scanf("%s", &action)) {
if (action[0] == 'q')
break;
scanf(" %d %s %d", &a, &method, &b);
if (block[a].loc == block[b].loc)
continue;
if (!strcmp(action, "move")) {
returning(a);
if (!strcmp(method, "onto"))
returning(b);
put(a, b);
} else {
if (!strcmp(method, "onto"))
returning(b);
pile(a, b);
}
}
for (i = 0; i < n; i++) {
printf("%d:", i);
for (j = 0; map[i][j] != -1; j++)
printf(" %d", map[i][j]);
puts("");
}
}
return 0;
}

### UVa 105 - The Skyline Problem

#include <stdio.h>

int main() {
int l, h, r, v[11111] = {0}, max = 0, flag = 0;
while (scanf("%d%d%d", &l, &h, &r) == 3) {
for (; l < r; l++)
if (h > v[l]) v[l] = h;
if (r > max) max = r;
}
for (l = 1; l <= max; l++)
if (v[l] != v[l - 1]) {
if (flag) printf(" ");
flag = 1;
printf("%d %d", l, v[l]);
}
puts("");
return 0;
}