Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1062 Accepted: 392
Description Each of the M lanes of the Park of Polytechnic University of Bucharest connects two of the N crossroads of the park (labeled from 1 to N). There is no pair of crossroads connected by more than one lane and it is possible to pass from each crossroad to each other crossroad by a path composed of one or more lanes. A cycle of lanes is simple when passes through each of its crossroads exactly once. The administration of the University would like to put on the lanes pictures of the winners of Regional Collegiate Programming Contest in such way that the pictures of winners from the same university to be on the lanes of a same simple cycle. That is why the administration would like to assign the longest simple cycles of lanes to most successful universities. The problem is to find the longest cycles? Fortunately, it happens that each lane of the park is participating in no more than one simple cycle (see the Figure).
Input
On the first line of the input file the number T of the test cases will be given. Each test case starts with a line with the positive integers N and M, separated by interval (4 <= N <= 4444). Each of the next M lines of the test case contains the labels of one of the pairs of crossroads connected by a lane.
Output
For each of the test cases, on a single line of the output, print the length of a maximal simple cycle.
#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int N = 4500; vector<int> ma[N]; int vis[N], a, b, cas, n, m, ans; int dfs (int i, int no) { vis[i] = no; for (int j = 0; j < ma[i].size(); ++j) { if (!vis[ma[i][j]]) dfs (ma[i][j], no + 1); else ans = max (ans, no - vis[ma[i][j]] + 1); } }
int main() { scanf ("%d", &cas); while (cas--) { scanf ("%d%d", &n, &m); for (int i = 1; i <= n; ++i) ma[i].clear(); for (int i = 1; i <= m; ++i) { scanf ("%d%d", &a, &b); ma[a].push_back (b); ma[b].push_back (a); } ans = 0; memset (vis, 0, sizeof (vis)); for (int i = 1; i <= n; ++i) if (!vis[i]) dfs (i, 1); if (ans >= 3) printf ("%d\n", ans); elseprintf ("0\n"); } return0; }
Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1624 Accepted: 864
Description We have a paragraph of text to print. A text is a sequence of words and each word consists of characters. When we print a text, we print the words from the text one at a time, according to the order the words appear in the text. The words are printed in lines, and we can print at most M characters in a line. If there is space available, we could print more than one word in a line. However, when we print more than one word in a line, we need to place exactly one space character between two adjacent words in a line. For example, when we are given a text like the following: This is a text of fourteen words and the longest word has ten characters
Now we can print this text into lines of no more than 20 characters as the following.
This is a text of fourteen words and the longest word has ten characters
However, when you print less than 20 characters in a line, you need to pay a penalty, which is equal to the square of the difference between 20 and the actual number of characters you printed in that line. For example in the first line we actually printed seven characters so the penalty is (20 − 7)2 = 169. The total penalty is the sum of all penalties from all lines. Given the text and the number of maximum number of characters allowed in a line, compute the minimum penalty to print the text.
Input
The first line of the input is the number of test cases (C). The first line of a test case is the maximum number of characters allowed in a line (M). The second line of a test case is the number of words in the text (N). The following N lines are the length (in character) of each word in the text. It is guaranteed that no word will have more than M characters, N is at most 10000, and M is at most 100.
Output
The output has C lines. Each line has the minimum penalty one needs to pay in order to print the text in that test case.
Some message encoding schemes require that an encoded message be sent in two parts. The first part, called the header, contains the characters of the message. The second part contains a pattern that represents the message. You must write a program that can decode messages under such a scheme.
The heart of the encoding scheme for your program is a sequence of ``key” strings of 0’s and 1’s as follows:
The first key in the sequence is of length 1, the next 3 are of length 2, the next 7 of length 3, the next 15 of length 4, etc. If two adjacent keys have the same length, the second can be obtained from the first by adding 1 (base 2). Notice that there are no keys in the sequence that consist only of 1’s.
The keys are mapped to the characters in the header in order. That is, the first key (0) is mapped to the first character in the header, the second key (00) to the second character in the header, the kth key is mapped to the kth character in the header. For example, suppose the header is:
AB/#TANCnrtXc
Then 0 is mapped to A, 00 to B, 01 to /#, 10 to T, 000 to A, …, 110 to X, and 0000 to c.
The encoded message contains only 0’s and 1’s and possibly carriage returns, which are to be ignored. The message is divided into segments. The first 3 digits of a segment give the binary representation of the length of the keys in the segment. For example, if the first 3 digits are 010, then the remainder of the segment consists of keys of length 2 (00, 01, or 10). The end of the segment is a string of 1’s which is the same length as the length of the keys in the segment. So a segment of keys of length 2 is terminated by 11. The entire encoded message is terminated by 000 (which would signify a segment in which the keys have length 0). The message is decoded by translating the keys in the segments one-at-a-time into the header characters to which they have been mapped.
Input
The input file contains several data sets. Each data set consists of a header, which is on a single line by itself, and a message, which may extend over several lines. The length of the header is limited only by the fact that key strings have a maximum length of 7 (111 in binary). If there are multiple copies of a character in a header, then several keys will map to that character. The encoded message contains only 0’s and 1’s, and it is a legitimate encoding according to the described scheme. That is, the message segments begin with the 3-digit length sequence and end with the appropriate sequence of 1’s. The keys in any given segment are all of the same length, and they all correspond to characters in the header. The message is terminated by 000.
Carriage returns may appear anywhere within the message part. They are not to be considered as part of the message.
Output
For each data set, your program must write its decoded message on a separate line. There should not be blank lines between messages.
MasterMind is a game for two players. One of them, Designer, selects a secret code. The other,Breaker, tries to break it. A code is no more than a row of colored dots. At the beginning of a game, the players agree upon the length N that a code must have and upon the colors that may occur in a code.
In order to break the code, Breaker makes a number of guesses, each guess itself being a code. After each guess Designer gives a hint, stating to what extent the guess matches his secret code.
In this problem you will be given a secret code and a guess , and are to determine the hint. A hint consists of a pair of numbers determined as follows.
A match is a pair (i,j), and , such that . Match (i,j) is called strongwhen i = j, and is called weak otherwise. Two matches (i,j) and (p,q) are called independent wheni = p if and only if j = q. A set of matches is called independent when all of its members are pairwise independent.
Designer chooses an independent set M of matches for which the total number of matches and the number of strong matches are both maximal. The hint then consists of the number of strong followed by the number of weak matches in M. Note that these numbers are uniquely determined by the secret code and the guess. If the hint turns out to be (n,0), then the guess is identical to the secret code.
Input
The input will consist of data for a number of games. The input for each game begins with an integer specifying N (the length of the code). Following these will be the secret code, represented as N integers, which we will limit to the range 1 to 9. There will then follow an arbitrary number of guesses, each also represented as N integers, each in the range 1 to 9. Following the last guess in each game will be N zeroes; these zeroes are not to be considered as a guess.
Following the data for the first game will appear data for the second game (if any) beginning with a new value for N. The last game in the input will be followed by a single zero (when a value forN would normally be specified). The maximum value for N will be 1000.
Output
The output for each game should list the hints that would be generated for each guess, in order, one hint per line. Each hint should be represented as a pair of integers enclosed in parentheses and separated by a comma. The entire list of hints for each game should be prefixed by a heading indicating the game number; games are numbered sequentially starting with 1. Look at the samples below for the exact format.
#include<cstdio> #include<algorithm> #include<map> using namespace std; const int N = 1005; int a[N], b[N], c, d; int main() { int n, cas = 0; while (scanf ("%d", &n), n) { map<int, int> aa; printf ("Game %d:\n", ++cas); for (int i = 0; i < n; ++i) { scanf ("%d", &a[i]); ++aa[a[i]]; } while (1) { map<int, int> bb; for (int i = c = d = 0; i < n; ++i) { scanf ("%d", &b[i]); ++bb[b[i]]; if (a[i] == b[i]) c++; } if (!b[0]) break; for (int i = 1; i <= 9; ++i) d += min (aa[i], bb[i]); printf (" (%d,%d)\n", c, d - c); } } return0; }
Ancient Roman empire had a strong government system with various departments, including a secret service department. Important documents were sent between provinces and the capital in encrypted form to prevent eavesdropping. The most popular ciphers in those times were so calledsubstitution cipherandpermutation cipher. Substitution cipher changes all occurrences of each letter to some other letter. Substitutes for all letters must be different. For some letters substitute letter may coincide with the original letter. For example, applying substitution cipher that changes all letters from A' to Y’ to the next ones in the alphabet, and changes Z' to A’, to the message VICTORIOUS'' one gets the message WJDUPSJPVT’’. Permutation cipher applies some permutation to the letters of the message. For example, applying the permutation2, 1, 5, 4, 3, 7, 6, 10, 9, 8to the message VICTORIOUS'' one gets the message IVOTCIRSUO’’. It was quickly noticed that being applied separately, both substitution cipher and permutation cipher were rather weak. But when being combined, they were strong enough for those times. Thus, the most important messages were first encrypted using substitution cipher, and then the result was encrypted using permutation cipher. Encrypting the message VICTORIOUS'' with the combination of the ciphers described above one gets the message JWPUDJSTVP’’. Archeologists have recently found the message engraved on a stone plate. At the first glance it seemed completely meaningless, so it was suggested that the message was encrypted with some substitution and permutation ciphers. They have conjectured the possible text of the original message that was encrypted, and now they want to check their conjecture. They need a computer program to do it, so you have to write one.
Input file contains several test cases. Each of them consists of two lines. The first line contains the message engraved on the plate. Before encrypting, all spaces and punctuation marks were removed, so the encrypted message contains only capital letters of the English alphabet. The second line contains the original message that is conjectured to be encrypted in the message on the first line. It also contains only capital letters of the English alphabet. The lengths of both lines of the input file are equal and do not exceed 100.
For each test case, print one output line. Output YES ' if the message on the first line of the input file could be the result of encrypting the message on the second line, or NO ‘ in the other case.
JWPUDJSTVP VICTORIOUS MAMA ROME HAHA HEHE AAA AAA NEERCISTHEBEST SECRETMESSAGES
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 105; char a[N], b[N];
int main() { while (scanf ("%s%s", a, b) != EOF) { int ca[26] = {0}, cb[26] = {0}, l = strlen (a), i; for (i = 0; i < l; ++i) { ++ca[a[i] - 'A']; ++cb[b[i] - 'A']; } sort (ca, ca + 26); sort (cb, cb + 26); for (i = 0; i < 26; ++i) if (ca[i] != cb[i]) break; printf (i == 26 ? "YES\n" : "NO\n"); } return0; }
In ``Hangman Judge,’’ you are to write a program that judges a series of Hangman games. For each game, the answer to the puzzle is given as well as the guesses. Rules are the same as the classic game of hangman, and are given as follows:
Your task as the ``Hangman Judge’’ is to determine, for each game, whether the contestant wins, loses, or fails to finish a game.
Input
Your program will be given a series of inputs regarding the status of a game. All input will be in lower case. The first line of each section will contain a number to indicate which round of the game is being played; the next line will be the solution to the puzzle; the last line is a sequence of the guesses made by the contestant. A round number of -1 would indicate the end of all games (and input).
Output
The output of your program is to indicate which round of the game the contestant is currently playing as well as the result of the game. There are three possible results:
In a serious attempt to downsize (reduce) the dole queue, The New National Green Labour Rhinoceros Party has decided on the following strategy. Every day all dole applicants will be placed in a large circle, facing inwards. Someone is arbitrarily chosen as number 1, and the rest are numbered counter-clockwise up to N (who will be standing on 1’s left). Starting from 1 and moving counter-clockwise, one labour official counts off k applicants, while another official starts from N and moves clockwise, counting m applicants. The two who are chosen are then sent off for retraining; if both officials pick the same person she (he) is sent off to become a politician. Each official then starts counting again at the next available person and the process continues until no-one is left. Note that the two victims (sorry, trainees) leave the ring simultaneously, so it is possible for one official to count a person already selected by the other official.
Input
Write a program that will successively read in (in that order) the three numbers (N, k and m; k, m > 0, 0 < N < 20) and determine the order in which the applicants are sent off for retraining. Each set of three numbers will be on a separate line and the end of data will be signalled by three zeroes (0 0 0).
Output
For each triplet, output a single line of numbers specifying the order in which people are chosen. Each number should be in a field of 3 characters. For pairs of numbers list the person chosen by the counter-clockwise official first. Separate successive pairs (or singletons) by commas (but there should not be a trailing comma).
#include<cstdio> #include<cstring> using namespace std; const int N = 22; int a[N], n, k, m, r, t1, t2;
int main() { while (scanf ("%d%d%d", &n, &k, &m), n) { memset (a, -1, sizeof (a)); t2 = 1; t1 = r = n; while (r) { for (int i = 1; i <= k; ++i) do t1 = ((t1 == n) ? 1 : t1 + 1); while (a[t1] == 0); for (int i = 1; i <= m; ++i) do t2 = ((t2 == 1) ? n : t2 - 1); while (a[t2] == 0);
r = (t1 == t2 ? r - 1 : r - 2); if (t1 == t2) printf ("%3d", t1); elseprintf ("%3d%3d", t1, t2); a[t1] = a[t2] = 0; if (r) printf (","); } printf ("\n"); } return0; }
YY’s Minions Time Limit:2 Seconds Memory Limit:65536 KB
Despite YY’s so much homework, she would like to take some time to play with her minions first.
YY lines her minions up to anN/*Mmatrix. Every minionhas two statuses: awake or asleep. We use 0(the digit) to represent that it is asleep, and 1 for awake. Also, we define the minions who are around a minionclosestin one of theeightdirections its neighbors. And every minute every minion will change its status by the following specific rules: If this minion is awake, and the number of its neighbors who are awake is less than 2, this minion will feel lonely and turn to asleep.If this minion is awake, and the number of its neighbors who are awake is more than 3, this minion will turn to asleep for it will feel too crowded.If this minion is awake, and the number of its neighbors who are awake is exactly 2 or 3, this minion will keep being awake and feel very happy.If this minion is asleep, and the number of its neighbors who are awake is exactly 3, this minion will wake up because of the noise.
Note that all changes take place at the same time at the beginning of a specific minute.
Also, some minions will get bored and leave this silly game. We use ‘X’s to describe them. We suppose that a minion would leave afterTminutes. It will leave at the end of the Tthminute. Its status is considered during the change at the beginning of the Tthminute, and should be ignored after that. Of course, one minion will not leave twice!
YY is a girl full of curiosity and wants to know every minion’s status afterFminutes. But you know she is weak and lazy! Please help this cute girl to solve this problem :)
Input
There are multiple test cases.
The first line contains the number of test casesQ. 1<=Q<=100. For each case, there are several lines: The first line contains four integersN,M,F,K.Kmeans the number of leaving messages. 1<=N,M<=50, 1<=F<=1000, 1<=K<=N/*M. NextNlines are the matrix which shows the initial status of each minion. Each line containsMchars. We guarantee that ‘X’ wouldn’t appear in initial status matrix. And nextKlines are the leaving messages. Each line contains three integersTi,Xi,Yi, They mean the minion who is located in (Xi,Yi) will leave the game at the end of theTithminutes. 1<=Ti<=F, 1<=Xi<=N, 1<=Yi<=M.
Output
For each case, outputNlines as a matrix which shows the status of each minion afterFminutes.
For case 1: T=0, the game starts 101 110 001 ————— at the beginning of T=1, a change took place 100 101 010 ————— at the end of T=1 (the minion in (2,2) left) 100 1X1 010 ————— at the beginning of T=2, a change took place 010 1X0 010 ————— at the end of T=2 (nothing changed for no minion left at T=2) 010 1X0 010
#include<cstdio> #include<algorithm> #include<map> using namespace std; const int N = 1005; int a[N], b[N], c, d; int main() { int n, cas = 0; while (scanf ("%d", &n), n) { map<int, int> aa; printf ("Game %d:\n", ++cas); for (int i = 0; i < n; ++i) { scanf ("%d", &a[i]); ++aa[a[i]]; } while (1) { map<int, int> bb; for (int i = c = d = 0; i < n; ++i) { scanf ("%d", &b[i]); ++bb[b[i]]; if (a[i] == b[i]) c++; } if (!b[0]) break; for (int i = 1; i <= 9; ++i) d += min (aa[i], bb[i]); printf (" (%d,%d)\n", c, d - c); } } return0; }
MasterMind is a game for two players. One of them, Designer, selects a secret code. The other,Breaker, tries to break it. A code is no more than a row of colored dots. At the beginning of a game, the players agree upon the length N that a code must have and upon the colors that may occur in a code.
In order to break the code, Breaker makes a number of guesses, each guess itself being a code. After each guess Designer gives a hint, stating to what extent the guess matches his secret code.
In this problem you will be given a secret code and a guess , and are to determine the hint. A hint consists of a pair of numbers determined as follows.
A match is a pair (i,j), and , such that . Match (i,j) is called strongwhen i = j, and is called weak otherwise. Two matches (i,j) and (p,q) are called independent wheni = p if and only if j = q. A set of matches is called independent when all of its members are pairwise independent.
Designer chooses an independent set M of matches for which the total number of matches and the number of strong matches are both maximal. The hint then consists of the number of strong followed by the number of weak matches in M. Note that these numbers are uniquely determined by the secret code and the guess. If the hint turns out to be (n,0), then the guess is identical to the secret code.
Input
The input will consist of data for a number of games. The input for each game begins with an integer specifying N (the length of the code). Following these will be the secret code, represented as N integers, which we will limit to the range 1 to 9. There will then follow an arbitrary number of guesses, each also represented as N integers, each in the range 1 to 9. Following the last guess in each game will be N zeroes; these zeroes are not to be considered as a guess.
Following the data for the first game will appear data for the second game (if any) beginning with a new value for N. The last game in the input will be followed by a single zero (when a value forN would normally be specified). The maximum value for N will be 1000.
Output
The output for each game should list the hints that would be generated for each guess, in order, one hint per line. Each hint should be represented as a pair of integers enclosed in parentheses and separated by a comma. The entire list of hints for each game should be prefixed by a heading indicating the game number; games are numbered sequentially starting with 1. Look at the samples below for the exact format.
#include<cstdio> #include<cstring> using namespace std; const int N = 150; char s[N], ans[N], c; int t, l; int main() { scanf ("%d", &t); while (t--) { scanf ("%s", s); l = strlen (s); strcpy (ans, s); for (int i = 0; i < l; ++i) { c = s[l - 1]; for (int j = l - 1; j >= 1 ; --j) s[j] = s[j - 1]; s[0] = c; if (strcmp (s, ans) < 0) strcpy (ans, s); } printf ("%s\n", ans); } }
Some DNA sequences exist in circular forms as in the following figure, which shows a circular sequence CGAGTCAGCT", that is, the last symbol T” in CGAGTCAGCT" is connected to the first symbol C”. We always read a circular sequence in the clockwise direction.
Since it is not easy to store a circular sequence in a computer as it is, we decided to store it as a linear sequence. However, there can be many linear sequences that are obtained from a circular sequence by cutting any place of the circular sequence. Hence, we also decided to store the linear sequence that is lexicographically smallest among all linear sequences that can be obtained from a circular sequence.
Your task is to find the lexicographically smallest sequence from a given circular sequence. For the example in the figure, the lexicographically smallest sequence is ``AGCTCGAGTC”. If there are two or more linear sequences that are lexicographically smallest, you are to find any one of them (in fact, they are the same).
The input consists of T test cases. The number of test cases T is given on the first line of the input file. Each test case takes one line containing a circular sequence that is written as an arbitrary linear sequence. Since the circular sequences are DNA sequences, only four symbols, A,C, G and T, are allowed. Each sequence has length at least 2 and at most 100.
Print exactly one line for each test case. The line is to contain the lexicographically smallest sequence for the test case.
The following shows sample input and output for two test cases.
and a guess 
, and are to determine the hint. A hint consists of a pair of numbers determined as follows.
and 
, such that 
. Match (i,j) is called strongwhen i = j, and is called weak otherwise. Two matches (i,j) and (p,q) are called independent wheni = p if and only if j = q. A set of matches is called independent when all of its members are pairwise independent.
2, 1, 5, 4, 3, 7, 6, 10, 9, 8
to the message 
4 
10, 