[URI ONLINE JUDGE] – 1148 – Countries at War

In year 2050, after several attempting of ONU to maintain the peace in world, exploded the third world war. Industrial secrets, commercials and military forced all countries to utilize extremely sophisticated espionage services, in order to have one spy of each country in each city in the world. These spies need to communicate with others spies, informants and even with both centrals during their actions. Unfortunately, there’s no safe way for a spy to communicate within a war building, therefore the messages are always sent in code so that only the receiver is able to read and understand it.

The spies use the only service available in war time, the post offices. Each city has one post office where letters can be sent. Letters can be sent directly to its destination or to other post offices, until it arrives to the post office of the intended city, if possible.

A post office in city A can send a printed letter directly to a post office in city B if there’s a letter sending agreement, which determines the time, measured in hours, that a letter takes to travel from city A to cityB (and not necessarily the opposite). If there’s no agreement between the cities, then post office A can try to send the letter to as many other post offices as necessary, until it is delivered to its destination, if possible.
Some post offices are electronically interconnected with satellites and optical fiber. Before war, these connections could reach all offices, making a letter to be sent instantly, but during hostilities period, each country began to control the electronic communication, and one office can only send a letter electronically to other, if both offices are in the same country. Two post offices, A and B, are in the same country if there’s any way that a printed letter sent from one office is delivered in the other one.
The espionage service of your country was able to obtain all letter sending agreements in the world e wishes to find out the minimum time for sending a letter between various pairs of cities. Would you be able to help it?


The input contains several test cases. The first line of each case contains two integers separated by a White space, N (1 ≤ N ≤ 500) and E (0 ≤ EN2), indicating the number of cities (enumerated from 1 to N) and of letter sending agreements, respectively. Follow, then, E lines, each one with three integers separated by a White space, X, Y and H (1 ≤ X, YN, 1 ≤ H ≤ 1000), indicating that there is an agreement to sending a printed letter from city X to city Y, and that this letter will be delivered in H hours.

Next, there will be a line with an integer K (0 ≤ K ≤ 100), the number of queries. Finally, K lines of input, each one representing a query that contains two integers separated by a white space, O and D (1 ≤ O, DN). You should determine the minimum time for sending a letter from city O to city D. The end of input is determined by N = E = 0.


For each test case, your program must output K lines. The N-th line should contain an integer M, the minimum time in hours, for sending a letter in the N-th query. If there’s no communication way between the cities of the query, you should print: “Nao e possivel entregar a carta” ( ‘The letter could not be delivered’ in portuguese).

Print a blank line after each case.

Sample InputSample Output
4 5
1 2 5
2 1 10
3 4 8
4 3 7
2 3 6
1 2
1 3
1 4
4 3
4 1
3 3
1 2 10
2 3 1
3 2 1
1 3
3 1
3 2
0 0
Nao e possivel entregar a carta

Nao e possivel entregar a carta





[code lang=cpp]
#include <iostream>
#include "stdio.h"
#include <string.h>
#define INF 0x3F3F3F3F
#define MAX 501
using namespace std;

int g[510][510];
int dist[510];
bool visit[510];
int pred[MAX];

void dijkstra(int ordem, int s){
int p[ordem];
int t = -1;
int v;

for (int i = 0; i <= ordem; i++)
dist[i] = INF;

dist[s] = 0;
p[++t] = s;

while(t != -1){
v = p[t–];
for (int i = 1; i <= ordem; i++){
if(dist[i] > dist[v] + g[v][i]){
dist[i] = dist[v] + g[v][i];
p[++t] = i;

void dijkstra2 (int n,int p){
int v,c;

memset (dist, INF, sizeof(dist));
memset (visit, 0, sizeof(visit));
memset (pred, -1, sizeof(pred));

dist[p] = 0;
v = p;

while (!visit[v]){
visit[v] = true;
for (int i=1; i<=n; i++){
if (g[v][i] != INF){
c = g[v][i];
if (dist[i] > dist[v]+c){
dist[i] = dist[v]+c;
pred[i] = v;
v = 0;
c = INF;
for (int i=1; i<=n; i++){
if(visit[i] == false && c>dist[i]){

int main(){

long long int aux;
int n,e,x,y,h,k,o,d;


cin >> n >> e;

if(n == 0 && e == 0) break;

for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
g[i][j] = INF;

cin >> x >> y >> h;
g[x][y] = h;

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(g[i][j] != INF && g[j][i] != INF){
g[i][j] = 0;
g[j][i] = 0;

cin >> k;

cin >> o >> d;

if(dist[d] < INF)
cout << dist[d] << endl;
cout << "Nao e possivel entregar a carta" << endl;

cout << endl;

[URI ONLINE JUDGE] – 1963 – The Motion Picture

Welcome to the 3rd UFFS Junior Programming Contest. We sincerely hope the next hours are very productive to you, you get many balloons and, above all, you have fun! Remember that you can ask for a clarification whenever you are not sure that you understand a problem description. Remember also that at 17.30 the automatic judges will be turned off and the competition will enter blind mode, so that all submissions made during this period will begin to be judged only at 18.10. Please stay with us till the end of the competition, working on solutions for the problems till the last minute, because, as long as the contest is running, there is still hope!

And it was hope that motivated Grandma Zazá, a 72-year-old lady, to fulfill her dream of starting an undergraduate course. She is fascinated by everything related to the University: the classes, the library, the research and extension projects, the refectory, but especially the student card that she can use to get 50% off cinema tickets. Last week Grandma Zazá and her colleagues went to the cinema to watch a movie, but they were appalled at the ticket price increase. Disgusted, they decided to make a protest, scheduled for tomorrow at General Bertaso Square, against the oppressive capitalist system. Grandma Zazá wants to collaborate with the movement by making a poster with the following watchword:


But she is not good at Math, so she is asking you to helpfully calculate the percentage she needs to complete the poster.


The only input line consists of two values A and B (0.00 < AB ≤ 1000.00), given with exactly two digits after the decimal point, which represent respectively the old and the new prices of the cinema tickets.


The only output line shall consist of a single value, representing as a percentage the ticket price increase. The value shall be followed by the symbol % and shall contain two digits after the decimal point.

Input SamplesOutput Samples
20.00 30.0050.00%
50.00 100.00100.00%
10.00 10.000.00%


very very simple =)


import java.util.Scanner;



[URI ONLINE JUDGE] – 1943 – Top N

The regional phase of the SBC Programming Contest happened recently, where more than 600 teams participated in more than 40 cities around Brazil. Your friend competed, and when asked about his position he told you: “I got placed in the top 10”.

You were happy for your friend, but you could not stop asking yourself about what was his real position. “Top 10” could mean any position between first and tenth placed, however if he had placed first he would have said “Top 1”, if he had placed second or third he would have said “Top 3”, and if he had placed fourth or fifth he would have said “Top 5”. Therefore, his real position was between sixth and tenth, because people tend to put themselves in the lowest category they belong.

You gathered all the categories people most use: 1, 3, 5, 10, 25, 50 and 100. Given a position K, write an algorithm that says the number of the lowest category this position belongs.


Each test case has one integer K, representing a position (1 ≤ K ≤ 100).


For each test case you should print one line with the sentence “Top N”, and replace N by the number of the lowest category the position K belongs.

Input SamplesOutput Samples
7Top 10
25Top 25
26Top 50


very simple like this:


#include <stdio.h>
int main(int argc, char const *argv[]){
    int k;
    scanf("%d", &k);
    if(k == 1) printf("Top 1\n");
    else if(k > 1 && k <= 3) printf("Top 3\n");
    else if(k > 3 && k <= 5) printf("Top 5\n");
    else if(k > 5 && k <= 10) printf("Top 10\n");
    else if(k > 10 && k <= 25) printf("Top 25\n");
    else if(k > 25 && k <= 50) printf("Top 50\n");
    else printf("Top 100\n");
    return 0;