[URI ONLINE JUDGE] – 1714 – Letters

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1714

The parks in the City of Logic are always a grid of N ×N squares (2 ≤ N ≤ 100), where each square has one of the first 10 ASCII letters, abcdefghijABCDEFGHIJ, in either lowercase or uppercase format. People from the City of Logic proudly follow only consistent paths when crossing parks. For example, if they step over a lowercase c, they will not allow themselves stepping over an uppercase C afterwards. To define this more precisely, a consistent path is a sequence of squares satisfying: consecutive squares are orthogonally adjacent; no letter occurs in both lowercase and uppercase format. That is to say, either a letter is not in the sequence at all, or it occurs only in lowercase, or only in uppercase format.

You have to write a program to help the people from the City of Logic to find the length a shortest consistent path between the square with coordinates (1, 1), in the upper left corner, and the square with coordinates (N, N ), in the lower right corner. For the example park above, the shortest consistent path has length 13.

Input

The input contains several test cases. The first line of a test case has a integer N (2 ≤ N ≤ 100), the size of the park. The next N lines contain, each one, a sequence of N letters, defining the park.

Output

For each test case in the input your program must output one line containing one integer, the length of a shortest consistent path. If there is no consistent path, output -1.

Sample Input Sample Output
7

aAaaaaa

aAaaaAa

aAaaaAA

aaAaAaa

AaAaaAa

aaAAaAa

aaaaaAa

-1

 

solution:

 

<br />#include <bits/stdc++.h>

#define INF 999999

using namespace std;
typedef pair<int, int> ii;

int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, -1, 1};

int d[105][105];
vector g;
int n;

int val(int i, int j)
{
return i >= 0 && i < n && j >= 0 && j < n;
}
int value(char c)
{
return tolower(c) - 'a';
}

int bfs(int mask)
{
queue< ii > q;
int result;
q.push(make_pair(0, 0));
ii u;
for (int i = 0 ; i < n ; ++i) for (int j = 0 ; j < n ; ++j)
d[i][j] = INF;

d[0][0] = 1;

char c = g[0][0];
int vl = value(c);
if (c == tolower(c)) result = (1 << vl);
else result = 0;
if ((mask & (1 << vl)) != result) return INF;

while (!q.empty())
{
u = q.front();
q.pop();
int x = u.first;
int y = u.second;
for (int i = 0 ; i < 4; ++i)
{
if (val(x + dr[i], y + dc[i]))
{
c = g[x + dr[i]][y + dc[i]];
vl = value(c);
if (c == tolower(c)) result = (1 << vl);
else result = 0;
if ((mask & (1 << vl)) == result) { if (d[x + dr[i]][y + dc[i]] > d[x][y] + 1)
{
d[x + dr[i]][y + dc[i]] = d[x][y] + 1;
q.push(make_pair(x + dr[i], y + dc[i]));
}
}
}
}
}
return d[n - 1][n - 1];
}

int main()
{
string s;

ios_base :: sync_with_stdio(0); cin.tie(0);
cin >> n;

for (int i = 0 ; i < n; ++i) { cin >> s;
g.push_back(s);
}

int ans = INF;
for (int i = 0 ; i < (1 << 10); ++i)
{
ans = min(ans, bfs(i));
}

if (ans != INF)
cout << ans << '\n';
else cout << -1 << '\n';

}

 

[URI ONLINE JUDGE] – 1944 – FACE 2015 FREE GIFT

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1944

In this year of 2015, FACE is supporting the third edition of the Programming Marathon, but, at this time, organization’s staff is requesting your help to create a lottery system by using the FACE letters. As this fair uses a differentiated and cheerful proposal, each participant who enters into the fair receives 4 letters, each of them in a different color and in the form of a wooden block, as shown in Figure 1, and they must insert them in a panel. If, by the entering time, the 4 letters create the opposite of the 4 last letters, this visitor will receive the free gift.

Brinde_FACE

Figure 1 – FACE entrance on the panel followed by ACEF.

For example: suppose there have already been three visitors who entered into the fair and the letters’ distribution remained as follows: F A C E E C F A A C F E A C E F. See that the panel, for being empty, the letters F A C E were inserted in order to start the process, now, as the fourth visitor enters, he has inserted the letters F E C A and, with it, they will receive the free gift as it got the opposite of A C E F. After this situation, the letters must remain F A C E E C F A A C F E. Another important fact is that, the free gifts’ distribution occurs in a certain period with a sample of a selected visitors number. REMENBER, always when the panel remains empty it is automatically inserted the letters F A C E.

Input

The input contains several test cases. The first line of a test case contains an integer N (1 ≤ N ≤ 100), representing the number of visitors who will receive the letters. In each subsequent line it must be informed the 4 letters combination separated by space that the visitor wishes to insert on the panel. The stop is determined by N equals to 0.

Output

For each of group of visitors, it must be informed how many of them will receive free gifts.

Input Samples Output Samples
4

E C F A

A C E F

F E C A

A F C E

2
3

E A C F

A F C E

E F C A

0
6

E C A F

E C A F

E C A F

E C A F

E C A F

E C A F

6

solution:

#include <bits/stdc++.h>
using namespace std;
stack v;

int main()
{
int n;

char c;
string aux;

int ans;

while (cin >> n)
{
ans = 0;
v.push("FACE");
for (int i = 0 ; i < n ; ++i)
{
aux.clear();
for (int j = 0 ; j < 4 ; ++j) { cin >> c;
aux.push_back(c);
}
string aux2 = aux;
reverse(aux2.begin(), aux2.end());

if (v.top() == aux2)
{
++ans;
v.pop();
if (v.size() == 0) v.push("FACE");
}
else
v.push(aux);
}
cout << ans << '\n';
while (!v.empty()) v.pop();
}
}

[URI ONLINE JUDGE] – 1477 – Man, Elephant and Mouse

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1477

A very popular game in Nlogonia is called Man, Elephant and Mouse. It is typically played with only two players, and works as follows: each player secretly selects one of these three symbols, and after a countdown, both simultaneously reveal the symbol chosen through hand signals, extending in front his hands signaling the choice.

Man is represented by the closed hand, like the head of a man. The elephant is represented by the open hand showing five fingers, like the paw of the nlogonense elephant. Finally, the Rat is represented by the closed hand with the index finger and middle finger outstretched, as the ears of the little animal.

Figure 1: The three symbols of the game Man, Elephant and Mouse.

To determine the winner is very simple: the man always loses to the elephant (it is crushed under his paw), the elephant always loses to the mouse (because he is afraid of him and runs away) and the mouse always loses to the Man (which spreads traps to capture it). If two players use the same symbol, a tie occurs and the game is played again.

The inhabitants of Nlogonia, that are born strategists of Man, Elephant and Mouse, are using the following technique in the national championship, held every year: they always start playing man until the moment that this symbol cause tie with the most of their opponents. They then change its approach to the the winning symbol considering that they were using previously. Thus, players will switch to Elephant Man, then to Mouse, then they back again to Man.

To assist a famous foreign competitor in a game similar to this game Man, Elephant and Mouse, you will develop a program that counts how many players will use each symbol. Suppose all N players are arranged in a row and identified by their position, from 1 to N. Your program should handle with M commands of two types: change of symbol and count the frequency of these symbols. Both commands take a contiguous range of players in the queue to be considered.

Input

The input consists of several test cases. Each test case starts with a line containing two integers N (1 ≤ N ≤ 105) and M (0 ≤ M ≤ 106) which represent respectively the number of players in the tournament, and the number of operations.

The next M lines contain, each one, the description of an operation. Operations of  strategy changing will be represented by a line of the form “M A B” where A (1 ≤ A) and B (ABN) are integers. Players whose strategies are changed are those whose position in queue is between A and B, inclusive.

Counting operations are represented by a line of the form “C A B” where A and B are integers representing the range of players that should be considered in the count. Let’s consider that players whose position in the queue is between A and B, inclusive.

inclusive.

Output

For each operation, print a line containing three integers indicating respectly the number of Men, Elephant and Mouse symbols, that are used by the players in the given interval.

Print one blank line after each test case, including the last one.

Sample Input Sample Output
10 7
C 1 10
M 5 6
C 5 6
M 6 7
C 4 8
M 1 10
C 1 10
5 6
M 1 5
M 2 4
M 1 2
M 4 5
C 1 5
C 3 4
10 0 0
0 2 0
2 2 1
1 7 2

2 0 3
1 0 1

 

my solution:

 

<br />#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define sz size

#define MAXN 100010

#define ms(x,v) memset((x), (v), sizeof(x))

#define cl_(x) ((x) << 1)
#define cr_(x) (((x) << 1) + 1)
#define _NO_USE_LOG
#ifdef _USE_LOG
#define LOG(x) cout << x;
#else
#define LOG(x)
#endif

using namespace std;

typedef long long L;
typedef pair<L,L> PL;
typedef vector<L> VL;
typedef vector<VL> VVL;
typedef vector<PL> VPL;
typedef vector<VPL>VVPL;

#define MAN 0
#define ELEPHANT 1
#define RAT 2

class SegTree
{
private:
int st[MAXN*8][3];
int lazy[MAXN*8];
int n_;


inline void add_(int *res, int *inc) {
for(int i = 0; i < 3; ++i) res[i] += inc[i];
}

void prop_(int u, int l, int r) {
if(lazy[u] == 1) {
swap(st[u][0], st[u][1]); // 0 1 2 -> 1 0 2
swap(st[u][0], st[u][2]); // 1 0 2 -> 2 0 1
}
else if(lazy[u] == 2) {
swap(st[u][0], st[u][2]); // 0 1 2 -> 2 1 0
swap(st[u][0], st[u][1]); // 2 1 0 -> 1 2 0
}

if(lazy[u] && l != r) {
lazy[cl_(u)] = (lazy[cl_(u)] + lazy[u]) % 3;
lazy[cr_(u)] = (lazy[cr_(u)] + lazy[u]) % 3;
}

lazy[u] = 0;
}

void query_(int u, int l, int r, int i, int j, int *res) {
prop_(u, l, r);
if(l > j || r < i) {}
else if(l >= i && r <= j){
add_(res, st[u]);
}
else{
query_(cl_(u), l, (l + r)/2, i, j, res);
query_(cr_(u), (l + r)/2 + 1, r, i, j, res);
}
}

void upd_(int u, int l, int r, int i, int j) {
prop_(u, l, r);
if(l > j || r < i) {}
else if(l >= i && r <= j) {
lazy[u] = 1;
prop_(u, l, r);
}
else {
upd_(cl_(u), l, (l + r) / 2, i , j);
upd_(cr_(u), (l + r) / 2 + 1, r, i , j);
ms(st[u], 0);
add_(st[u], st[cl_(u)]);
add_(st[u], st[cr_(u)]);
}
}

void build_(int u, int l, int r) {
lazy[u] = 0;
ms(st[u], 0);
if(l == r) {
st[u][0] = 1;
}
else {
build_(cl_(u), l, (l + r) / 2);
build_(cr_(u), (l + r) / 2 + 1, r);
add_(st[u], st[cl_(u)]);
add_(st[u], st[cr_(u)]);
}
}
public:
void init(int n) {
n_ = n;
build_(1, 0, n_);
}

void update(int l, int r) {
upd_(1, 0, n_, l, r);
}

void query(int l, int r, int *res) {
query_(1, 0, n_, l, r, res);
}

};

SegTree st;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);

int n, m;
while(cin >> n >> m) {
st.init(n);
int queryRes[3];

for(int i = 0; i < m; ++i) {
char q;
int a, b;
cin >> q >> a >> b;
--a; --b;

if(q == 'C') {
ms(queryRes, 0);
st.query(a, b, queryRes);
cout << queryRes[0] << ' '
<< queryRes[1] << ' '
<< queryRes[2] << '\n';
}
else {
st.update(a, b);
}
}
cout << '\n';
}
}

[URI ONLINE JUDGE] – 1476 – Trucks

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1476

The Subtle Balloons Company (SBC) is the main balloon provider for programming contests; it has huge factories and warehouses, as well as an extensive truck fleet to ensure the contestants’ happiness. There are lots of competition sites in Nlogonia, and all of them hired SBC for supplying balloons for their contests. Nlogonia is an archipelago connected by several bridges. Every island of Nlogonia may have several regional sites and may also house several SBC warehouses. When planning the routes for balloon deliveries, SBC faced a problem: for safety issues, every bridge in Nlogonia has some maximum weight limit for vehicles which cross it. And because of the great net weight of the transported merchandise, SBC operations’ chief asked you to write a program to determine the maximum weight allowed to be transported between warehouses and competition sites.

Input

The input contains several test cases. The first line of a test case contains three integers N(2 ≤ N ≤ 2 × 104), M(1 ≤ M ≤ 105) and S(1 ≤ S ≤ 5 × 104) which indicate, respectively, the number of islands, the number of bridges that connect the islands and the number of sites. The islands are numbered from 1 to N. Each of the next M lines describes a bridge. The description of a bridge consists in a line with three integers A, B and W(0 ≤ W ≤ 105), indicating respectively the two islands connected by the bridge and the maximum weight allowed in that bridge, in tons. All bridges are two-way roads; every pair of islands is connected by at most one bridge; and it is possible to reach every other island in the archipelago using only bridges (naturally it may be needed to pass through other islands to do so). Each of the next S lines describe a competition site and contains two integers L and H indicating, respectively, the number of the island where this site is and the number of the island where the wharehouse which will be used to deliver the balloons to the site is. (1 ≤ A,B,L,HN, A != B, L != H)

Output

For each site in a test case, in the order they were given, your program must produce a single line, containing a single integer, the biggest weight which can be transported by truck from the warehouse to the site.

Sample Input Sample Output
4 5 4
1 2 9
1 3 0
2 3 8
2 4 7
3 4 4
1 4
2 1
3 1
4 3
4 5 2
1 2 30
2 3 20
3 4 10
4 1 40
2 4 50
1 3
1 2
7
9
8
7
20
40

 

solution:

#include <bits/stdc++.h>
#define MAXN 20005
#define LOGTWON 15
#define cl(x) ((x) << 1)
#define cr(x) (((x) << 1) + 1)
#define INF 99999999
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

class RMQ{
private:
int _A[2 * MAXN], SpT[2 * MAXN][2 * LOGTWON];
public :
void build ( int n , int A[] ) {
for ( int i = 0 ; i < n ; ++i) {
_A[i] = A[i] ;
SpT[i][0] = i ;
}
for (int j = 1; (1 << j) <= n; ++j)
{
for (int i = 0 ; i + (1 << j) - 1 < n; ++i)
{
if (_A[SpT[i][j - 1]] < _A[SpT[i + (1 << (j - 1))][j - 1]])
SpT[i][j] = SpT[i][j - 1];
else SpT[i][j] = SpT[i + (1 << (j - 1))][j - 1];
}
}
}
int query(int i , int j){
int k = (int)floor(log((double)j - i + 1) / log(2.0));
if (_A[SpT[i][k]] <= _A[SpT[j - (1 << k) + 1][k]])
return SpT[i][k];
else return SpT[j - (1 << k) + 1][k];
}
};
class LCA{
private:
RMQ rmq;
int L[2 * MAXN], E[2 * MAXN], H[MAXN], idx;

void dfs(int cur, int depth, vvi &children)
{
H[cur] = idx;
E[idx] = cur;
L[idx++] = depth;
for (int i = 0 ; i < (int)children[cur].size(); ++i)
{
dfs(children[cur][i], depth + 1, children);
E[idx] = cur;
L[idx++] = depth;
}
}
public:
void build(vvi &children)
{
idx = 0;
memset(H, -1, sizeof H);
dfs(0, 0, children);
rmq.build(idx, L);
}
int query(int u, int v)
{
if (H[v] < H[u]) swap(u, v);
return E[rmq.query(H[u], H[v])];
}
};

class HLD{
private:
LCA lca;
int chainNo, chainPtr, n;
int chainHead[MAXN], chainPos[MAXN], chainInd[MAXN];
int arrBase[MAXN], tree_sz[MAXN], st[4 * MAXN], parent[MAXN];

void build_tree(int x, int l, int r)
{
if (l == r) st[x] = arrBase[l];
else
{
build_tree(cl(x), l, (l + r) / 2);
build_tree(cr(x), (l + r) / 2 + 1, r);

st[x] = min(st[cl(x)], st[cr(x)]);
}
}

int query_tree(int x, int l, int r, int i, int j)
{
if (j < l || i > r) return INF;

if (l >= i && r <= j) return st[x];

int ans1 = query_tree(cl(x), l, (l + r) / 2, i , j);
int ans2 = query_tree(cr(x), (l + r) / 2 + 1, r, i , j);
return min(ans1, ans2);
}

int query_up(int u, int v)
{
if (u == v) return INF;

int uchain, vchain = chainInd[v], ans = INF;
while (1)
{
uchain = chainInd[u];
if (uchain == vchain)
{
if (u == v) break;
ans = min(ans, query_tree(1, 0, n - 1, chainPos[v] + 1, chainPos[u]));
break;
}
ans = min(ans, query_tree(1, 0, n - 1, chainPos[chainHead[uchain]], chainPos[u]));
u = parent[chainHead[uchain]];
}
return ans;
}

int dfscnt(int u, vvi &children)
{
int v;
tree_sz[u] = 1;

for (int i = 0 ; i < (int)children[u].size(); ++i)
{
v = children[u][i];
parent[v] = u;
tree_sz[u] += dfscnt(v, children);
}

return tree_sz[u];
}

void hld(int u, int cst, vvi &children, vvi &costs){
arrBase[chainPtr] = cst;
if (chainHead[chainNo] == -1) chainHead[chainNo] = u;

chainInd[u] = chainNo; chainPos[u] = chainPtr++;

int ind = n, nc, v;

for (int i = 0; i < (int)children[u].size(); ++i)
{
v = children[u][i];
if (tree_sz[v] > tree_sz[ind]){
ind = v;
nc = costs[u][i];
}
}
if (ind == n) return;

hld(ind, nc, children, costs);
for (int i = 0 ; i < (int)children[u].size(); ++i)
{
v = children[u][i];
if (v != ind)
{
++chainNo;
hld(v, costs[u][i], children, costs);
}
}
}

public:
HLD(){
lca = LCA();
}

void build(vvi &children, vvi &costs){
memset(tree_sz, -1, sizeof tree_sz);

n = children.size();
dfscnt(0, children);

chainNo = 0;
memset(chainHead, -1, sizeof chainHead);

chainPtr = 0;

hld(0, INF, children, costs);

lca.build(children);
build_tree(1, 0, n - 1);
}
int query(int u, int v){

int l = lca.query(u, v);

return min(query_up(u, l), query_up(v, l));
}
};

HLD hld;
vector<pair<int, pair<int, int > > > edges;
vvi g;
vvi custo;
vvi mst;
vi pset;
void init(int n)
{
pset.assign(n, 0);
for (int i = 0 ; i < n ; ++i) pset[i] = i;
}

int find(int i)
{
return (pset[i] == i ? i : pset[i] = find(pset[i]));
}
bool same(int i, int j)
{
return find(i) == find(j);
}

void une(int i, int j)
{
pset[find(i)] = find(j);
}

void dfs(int u, int pai)
{
for (int i = 0 ; i < g[u].size(); ++i)
{
if (g[u][i] != pai)
{
mst[u].push_back(g[u][i]);
dfs(g[u][i], u);
}
else custo[u].erase(custo[u].begin() + i);
}
}

bool cmp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b)
{
return a.first > b.first;
}
int main()
{
int n, m, s;
int u, v, w;

ios_base :: sync_with_stdio(0); cin.tie(0);

while (cin >> n >> m >> s)
{
mst.assign(n, vi());
g.assign(n, vi());
custo.assign(n, vi());
edges.clear();
for (int i = 0 ; i < m ; ++i)
{
cin >> u >> v >> w;
--u; --v;
edges.push_back(make_pair(w, make_pair(u, v)));
}
sort(edges.begin(), edges.end(), cmp);
init(n);

for (int i = 0 ; i < edges.size(); ++i)
{
pair<int, pair<int, int> > u = edges[i];

if (!same(u.second.first, u.second.second))
{
une(u.second.first, u.second.second);

g[u.second.first].push_back(u.second.second);
g[u.second.second].push_back(u.second.first);

custo[u.second.first].push_back(u.first);
custo[u.second.second].push_back(u.first);
}
}
dfs(0, -1);
hld = HLD();
hld.build(mst, custo);

for (int i = 0 ; i < s; ++i)
{
cin >> u >> v;
--u; --v;

cout << hld.query(u, v) << '\n';
}
}
}

[URI ONLINE JUDGE] – 1482 – Long Night of Museums

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1482

 

The city of Vienna is called the “City of Culture” because (among other things) there are more than 100 museums in the city. As a consequence, it is very difficult (and very expensive) to visit all of them no matter how long you stay in the city. Fortunately, there is a special night, called the “Long Night of Museums”, when you can visit many museums with just one ticket, from 6:00 pm to 1:00 am of the next day.

Nevertheless, it is impossible to visit every museum of the city for two main reasons. First, some museums in Vienna don’t get involved into this event because they close at 5:00 pm. Second, there is not enough time in 7 hours to go to every museum, watch ALL their insides (otherwise, it would be a waste of time), and then go to the others.

Given the number of museums participating in the Long Night of Museums, the time needed to watch the insides of each museum, and the time that it will take to get from each museum to the others, you have to find the best tour to visit as many museums as you can during the Long Night of Museums.

Input

The input contains several test cases. The first line of a test case contains one integer N, which indicates the number of museums participating in the event (1 ≤ N ≤ 20). Each museum has a unique identification number ranging from 1 to N. The second line of a test case contains N integers indicating the time, in minutes, needed to visit each museum, from 1 to N. Then there are N lines describing the times to go from one museum to every other. The i-th line contains N integers Mk (1 ≤ kN) representing the time, in minutes, to go from museum i to museum k. You may assume that the i-th integer in the i-th line is equal to zero. The end of input is indicated by N = 0.

Output

For each test case in the input, your program must produce one line containing the maximum number of museums that can be visited during the Long Night of Museums.

Sample Input Sample Output
2
500 500
0 120
200 0
2
220 220
0 30
20 0
2
150 150
0 120
200 0
0
0
1
2

solution:

<br />#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int mat[20][20], cost[20];
int N, M;
#define REP(i, N) for(int (i) = 0; (i) < (N) ; (i) ++ )
int res;
bool flag;
void back(int last, int remain,int mask, int ans){
res = max(ans, res);
if( res == M){
flag = true;
return;
}
REP(i, N){
if(!( mask & ( 1 << i ) )){
if( remain >= cost[i]+mat[last][i])
back(i, remain-cost[i]-mat[last][i], mask|(1<<i), ans+1);
}
if (flag) return;
}
}
int main(){
int i,j ,k;
while(1){
scanf("%i", &N); if(!N) return 0;
REP(i, N) scanf("%i", &cost[i]);
int aux[20]; REP(i, N) aux[i] = cost[i];
sort(aux, aux+N);
int co = 420;M=0;
while(M < N && aux[M] <= co ){M++, co-=aux[M];}

REP(i, N)REP(j, N) scanf("%i", &mat[i][j]);
REP(k, N)REP(i, N)REP(j, N) mat[i][j] = min(mat[i][k]+mat[k][j], mat[i][j]);
res = 0;
flag = false;
REP(i, N){
if( 420 >= cost[i] ){
back(i, 420-cost[i], 1<<i, 1);
}
if (flag) break;
}
printf("%i\n", res);
}
return 0;
}

 

 

[URI ONLINE JUDGE] – 1209 – St. Petersburg Parties

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1209

St. Petersburg became after the end of the Iron Curtain in the early ’90s, one of the main cities of the alternative scene worldwide. Groups of punks, hardcore bands and several other representatives of the alternative scene moved to the city, attracted by the large amount of young people. With the emergence of virtual communities, a few years later, it was noted the enormous potential of using these communities to combine meetings, parties, raves, etc..

In these celebrations of St. Petersburg is always very important that each participant has at least a certain number of friends on the social network. At the same time, we want to invite as many people as possible to St. Petersburg since the restriction on the number of friends is satisfied. This constraint says that, to be invited to the party, the person must have at least one number K of friends on the guest list.

Your task in this problem is, given the number of people in the community and to list their relationships, determine what should be called to the party that has the largest possible number of participants satisfying the constraint.

Input

The input have many test cases and ends with the end of file (EOF). The first line of each test case contains three integers N (1 ≤ N ≤ 1000), M and K (O ≤ KN) representing respectively the number of people in the community, the number of friendships in this community and the minimum number of friends asked a person must have to be invited. Each person in the community is identified by numbers from 1 to N. Each of the next M lines of the test case contains a pair of people indicating that they are friends in the social network.

Output

For each test case print a single line containing the list of people to invite separated by a blank space. The list should be sorted in ascending order. If anyone can be invited, print the number 0.

Sample Input Sample Output
6 6 2
1 3
3 5
2 3
2 4
4 6
6 2
6 6 3
1 2
2 3
3 1
4 5
5 6
6 4
2 4 6
0

solution:

<br />#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int main() {
int n, m, k;

while (scanf("%d %d %d\n", &n, &m, &k) != EOF) {
vector<int> aaa(n+1);
vector<vector<int>* > *am =
new vector<vector<int>* >(n+1);

for (int i = 1; i <= n; i++) {
aaa[i] = 0;
(*am)[i] = new vector<int>;
}

for (int j = 0; j < m; j++) {
int a, b;
scanf("%d %d\n", &a, &b);
aaa[a]++;
aaa[b]++;
(*am)[a]->push_back(b);
(*am)[b]->push_back(a);
}

map<int, bool> T;
bool cont = true;
while(cont) {
cont = false;
for (int i = 1; i < n+1; i++) {
if (T.count(i) == 0) {
int o = 0;
for (int j = 0; j < (*am)[i]->size(); j++) {
if (T.count((*am)[i]->at(j)) == 0)
o += 1;
}

if (o < k) {
cont = true;
T[i] = false;
for (int j = 0; j < (*am)[i]->size(); j++) {
aaa[(*am)[i]->at(j)] -= 1;
}
}
}
}
}

vector<int> s;
for (int i = 1; i < n+1; i++) {
if (T.count(i) == 0) {
s.push_back(i);
}
}

sort(s.begin(), s.end());
for (int i = 0; i < s.size(); i++) {
if (i == (s.size()-1))
printf("%d", s[i]);
else
printf("%d ", s[i]);
}
if(s.size() == 0) printf("0");
printf("\n");
}

return 0;
}

 

 

[URI ONLINE JUDGE] – 1893 – Moon Phases

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1893

Jade won as birthday gift a telescope and is very happy, because she loves stay looking the moon at night. She was always a very good student, and just analyzing the moon for two consecutive nights, she can already identify the changes that occurred in lighting and the approximate percentage of the moon that are illuminated.

You, who is a Jade’s friend and a Computer Science student, decided to make a small program that, based on her analise made in the last two nights, informs the phase in which the moon is. If the visible portion of the moon is between 0 and 2%, for example, is new moon (“nova” in portuguese). If it is between 3 and 96% is crescent moon (“crescente” in portuguese), if it is between 97 and 100% is full moon (“cheia” in portuguese) and it is between 3 and 96 % (decreasing) is waning moon (“minguante” in portuguese).

Input

The input consists of a single line containing two integer numbers. The first number corresponds to the percentage observed by Jade at night two days ago. The second value corresponds to the percentage observed by jade the night before.

Output

Based on the two percentage observed by Jade, print on the screen at what stage the moon was in the night before. Don’t forget the end-of-line character :)

Input Sample Output Sample
0 2 nova
2 3 crescente
99 97 cheia
97 94 minguante
30 35 crescente

solution:

 

<br />#include <iostream>
using namespace std;

bool solve(int num) {
return num >= 0 && num <= 2;
}

bool crescent(int num){
return num >= 3 && num <= 96;
}
bool full_moon(int num) {
return num >= 97 && num <= 100;
}

int main()
{
int first,second;
cin>> first >>second;

if(first <= second)
{
if(solve(second))
cout << "nova" << endl;
else if(crescent(second))
cout << "crescente" <<endl;
else if (full_moon(second))
cout << "cheia" <<endl;
}
else
{
if(solve(second))
cout << "nova" << endl;
else if(crescent(second))
cout << "minguante" <<endl;
else if (full_moon(second))
cout << "cheia" <<endl;
}
}