9月 | 2015 | 超客的水墨烟雨

uva455

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

12 9月 2015

A character string is said to have period k if it can be formed by concatenating one or more repetitions of another string of length k. For example, the string "abcabcabcabc" has period 3, since it is formed by 4 repetitions of the string "abc". It also has periods 6 (two repetitions of "abcabc") and 12 (one repetition of "abcabcabcabc").

Write a program to read a character string and determine its smallest period.

Input

The first line oif the input file will contain a single integer N indicating how many test case that your program will test followed by a blank line. Each test case will contain a single character string of up to 80 non-blank characters. Two consecutive input will separated by a blank line.

Output

An integer denoting the smallest period of the input string for each input. Two consecutive output are separated by a blank line.

Sample Input

HoHoHo

Sample Output

题目类型：简单字符处理

算法分析：周期变量zhouqi从1开始枚举到字符串的长度len，其中舍去判断不能被len整除的zhouqi。对于可能为最小周期的zhouqi使用求余的方法进行判断。注意本题最后一组数据的输出之后是没有空行的，下面第一个代码是更好的实现

/**************************************************
filename       :j.cpp
author         :maksyuki
created time   :2017/12/2 10:02:00
last modified  :2017/12/2 10:19:40
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

char s[maxn], v[maxn], tmp[maxn];

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int t, id = 1;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);
        
        int len = strlen(s);
        int minval = len;
        for(int i = 1; i < len; i++) {
            if(len % i) continue;
            strncpy(v, s, i);
            v[i] = 0;
            strcpy(tmp, v);
            bool is_find = true;
            char *p = NULL;
            int len2 = len / i;
            for(int j = 1; j <= len2; j++) {
                p = strstr(s, tmp);
                strcat(tmp, v);
                if(p == NULL) {
                    is_find = false;
                    break;
                }
            }
            if(is_find) {
                minval = i;
                break;
            }
        }
        if(id++ > 1) puts("");
        printf("%d\n", minval);
    }
    return 0;
}

100

101

102

/**************************************************

filename :j.cpp

author :maksyuki

created time :2017/12/2 10:02:00

last modified :2017/12/2 10:19:40

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

char s[maxn], v[maxn], tmp[maxn];

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int t, id = 1;

scanf("%d", &t);

while(t--) {

scanf("%s", s);

int len = strlen(s);

int minval = len;

for(int i = 1; i < len; i++) {

if(len % i) continue;

strncpy(v, s, i);

v[i] = 0;

strcpy(tmp, v);

bool is_find = true;

char *p = NULL;

int len2 = len / i;

for(int j = 1; j <= len2; j++) {

p = strstr(s, tmp);

strcat(tmp, v);

if(p == NULL) {

is_find = false;

break;

}

if(is_find) {

minval = i;

break;

}

if(id++ > 1) puts("");

printf("%d\n", minval);

}

return 0;

}

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

const int maxn = 86;

char a[maxn];

int main()
{
    int cases;
    //ifstream cin ("aaa.txt");

    cin >> cases;
    while (cases--)
	{
        cin >> a;
        int len = strlen (a);

        int zhouqi, i;
        bool isend = false;

        for (zhouqi = 1; !isend; zhouqi++)
		{
            if (len % zhouqi == 0)
			{
                 for (i = 0; a[i]; i++)
				 {
                    if (a[i] != a[(i+zhouqi)%len])
						break;
				 }
			}

            if (i == len)
                isend = true;
		}

			if (cases)
                printf ("%d\n\n", --zhouqi);

            else
                printf ("%d\n", --zhouqi);

	}

	return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

const int maxn = 86;

char a[maxn];

int main()

{

int cases;

//ifstream cin ("aaa.txt");

cin >> cases;

while (cases--)

{

cin >> a;

int len = strlen (a);

int zhouqi, i;

bool isend = false;

for (zhouqi = 1; !isend; zhouqi++)

{

if (len % zhouqi == 0)

{

for (i = 0; a[i]; i++)

{

if (a[i] != a[(i+zhouqi)%len])

break;

}

if (i == len)

isend = true;

}

if (cases)

printf ("%d\n\n", --zhouqi);

else

printf ("%d\n", --zhouqi);

}

return 0;

}

uva401

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

12 9月 2015

A regular palindrome is a string of numbers or letters that is the same forward as backward. For example, the string "ABCDEDCBA" is a palindrome because it is the same when the string is read from left to right as when the string is read from right to left.
A mirrored string is a string for which when each of the elements of the string is changed to its reverse (if it has a reverse) and the string is read backwards the result is the same as the original string. For example, the string "3AIAE" is a mirrored string because "A" and "I" are their own reverses, and "3" and "E"are each others' reverses.
A mirrored palindrome is a string that meets the criteria of a regular palindrome and the criteria of a mirrored string. The string "ATOYOTA" is a mirrored palindrome because if the string is read backwards, the string is the same as the original and because if each of the characters is replaced by its reverse and the result is read backwards, the result is the same as the original string. Of course, "A", "T", "O", and "Y"are all their own reverses.
A list of all valid characters and their reverses is as follows.

Character	Reverse	Character	Reverse	Character	Reverse
A	A	M	M	Y	Y
B		N		Z	5
C		O	O	1	1
D		P		2	S
E	3	Q		3	E
F		R		4
G		S	2	5	Z
H	H	T	T	6
I	I	U	U	7
J	L	V	V	8	8
K		W	W	9
L	J	X	X

Note that O (zero) and 0 (the letter) are considered the same character and therefore ONLY the letter "0" is a valid character.

Input

Input consists of strings (one per line) each of which will consist of one to twenty valid characters. There will be no invalid characters in any of the strings. Your program should read to the end of file.

Output

For each input string, you should print the string starting in column 1 immediately followed by exactly one of the following strings.

STRING	CRITERIA
" -- is not a palindrome."	if the string is not a palindrome and is not a mirrored string
" -- is a regular palindrome."	if the string is a palindrome and is not a mirrored string
" -- is a mirrored string."	if the string is not a palindrome and is a mirrored string
" -- is a mirrored palindrome."	if the string is a palindrome and is a mirrored string

Note that the output line is to include the -'s and spacing exactly as shown in the table above and demonstrated in the Sample Output below.

In addition, after each output line, you must print an empty line.

Sample Input

NOTAPALINDROME

ISAPALINILAPASI

2A3MEAS

ATOYOTA

Sample Output

NOTAPALINDROME -- is not a palindrome.

ISAPALINILAPASI -- is a regular palindrome.

2A3MEAS -- is a mirrored string.

ATOYOTA -- is a mirrored palindrome.

Miguel Revilla 2001-04-16

题目类型：字符处理题

算法分析：本题判断回文串和镜像串可以一起进行，注意可以使用常量数组

#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <iostream>
#include <fstream>
using namespace std;

const char *rev = "A   3  HIL JM O   2TUVWXY51SE Z  8 ";
const char *msg[] = {"not a palindrome", "a regular palindrome", "a mirrored string"
, "a mirrored palindrome"};

char finds (char ch)
{
    if (isalpha (ch))
		return rev[ch-'A'];

	else
		return rev[ch-'0'+25];
}

int main()
{
	char s[36];
    //freopen ("aaa.txt", "r", stdin);

	while (scanf ("%s", s) != EOF)
	{
        int len = strlen (s);
        int p = 1, m = 1;
        int i;
        for (i = 0; i < (len + 1) / 2; i++)
		{
			if (s[i] != s[len-i-1])
				p = 0;

			if (finds (s[i]) != s[len-i-1])
				m = 0;
		}

		printf ("%s -- is %s.\n\n", s, msg[m*2+p]);
	}

	return 0;
}

#include <cstdio>

#include <ctype.h>

#include <cstring>

#include <iostream>

#include <fstream>

using namespace std;

const char *rev = "A 3 HIL JM O 2TUVWXY51SE Z 8 ";

const char *msg[] = {"not a palindrome", "a regular palindrome", "a mirrored string"

, "a mirrored palindrome"};

char finds (char ch)

{

if (isalpha (ch))

return rev[ch-'A'];

else

return rev[ch-'0'+25];

}

int main()

{

char s[36];

//freopen ("aaa.txt", "r", stdin);

while (scanf ("%s", s) != EOF)

{

int len = strlen (s);

int p = 1, m = 1;

int i;

for (i = 0; i < (len + 1) / 2; i++)

{

if (s[i] != s[len-i-1])

p = 0;

if (finds (s[i]) != s[len-i-1])

m = 0;

}

printf ("%s -- is %s.\n\n", s, msg[m*2+p]);

}

return 0;

}

uva272

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

12 9月 2015

TeX is a typesetting language developed by Donald Knuth. It takes source text together with a few typesetting instructions and produces, one hopes, a beautiful document. Beautiful documents use and " to delimit quotations, rather than the mundane " which is what is provided by most keyboards. Keyboards typically do not have an oriented double-quote, but they do have a left-single-quote and a right-single-quote '. Check your keyboard now to locate the left-single-quote key (sometimes called the backquote key") and the right-single-quote key ' (sometimes called the apostrophe" or just quote"). Be careful not to confuse the left-single-quote with the backslash" key \. TeX lets the user type two left-single-quotes to create a left-double-quote and two right-single-quotes '' to create a right-double-quote ''. Most typists, however, are accustomed to delimiting their quotations with the un-oriented double-quote ".


If the source contained
"To be or not to be," quoth the bard, "that is the question."
then the typeset document produced by TeX would not contain the desired form:

To be or not to be," quoth the bard, that is the question."


In order to produce the desired form, the source file must contain the sequence:

To be or not to be,'' quoth the bard, that is the question.''

You are to write a program which converts text containing double-quote (") characters into text that is identical except that double-quotes have been replaced by the two-character sequences required by TeX for delimiting quotations with oriented double-quotes. The double-quote (") characters should be replaced appropriately by either if the " opens a quotation and by '' if the " closes a quotation. Notice that the question of nested quotations does not arise: The first " must be replaced by , the next by '', the next by, the next by '', the next by , the next by '', and so on.


Input and Output
Input will consist of several lines of text containing an even number of double-quote (") characters. Input is ended with an end-of-file character. The text must be output exactly as it was input except that:

the first " in each pair is replaced by two characters: and
the second " in each pair is replaced by two ' characters: ''.

Sample Input

"To be or not to be," quoth the Bard, "that

is the question".

The programming contestant replied: "I must disagree.

To C' or not to C', that is The Question!"

Sample Output

To be or not to be,'' quoth the Bard, that

is the question''.

The programming contestant replied: I must disagree.

To C' or not to C', that is The Question!''

题目类型：字符处理题

算法分析：本题只需要判断一个双引号对应的是左双引号还是右双引号，方法是使用一个状态变量

#include <cstdio>
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    int flag = 1;
    char c;
    //freopen ("aaa.txt", "r", stdin);

    while ((c =getchar ()) != EOF)
	{
        if (c == '"')
        {
			printf ("%s", flag ? "``" : "''");
			flag = !flag;
        }

        else
			printf ("%c", c);

	}

	return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

using namespace std;

int main()

{

int flag = 1;

char c;

//freopen ("aaa.txt", "r", stdin);

while ((c =getchar ()) != EOF)

{

if (c == '"')

{

printf ("%s", flag ? "``" : "''");

flag = !flag;

}

else

printf ("%c", c);

}

return 0;

}

uva232

maksyuki 发表于 oj 分类，标签: 基础算法-模拟

12 9月 2015

A crossword puzzle consists of a rectangular grid of black and white squares and two lists of definitions (or descriptions).

One list of definitions is for words" to be written left to right across white squares in the rows and the other list is for words to be written down white squares in the columns. (A word is a sequence of alphabetic characters.)

To solve a crossword puzzle, one writes the words corresponding to the definitions on the white squares of the grid.

The definitions correspond to the rectangular grid by means of sequential integers on eligible" white squares. White squares with black squares immediately to the left or above them are eligible." White squares with no squares either immediately to the left or above are also eligible." No other squares are numbered. All of the squares on the first row are numbered.

The numbering starts with 1 and continues consecutively across white squares of the first row, then across the eligible white squares of the second row, then across the eligible white squares of the third row and so on across all of the rest of the rows of the puzzle. The picture below illustrates a rectangular crossword puzzle grid with appropriate numbering.

An across" word for a definition is written on a sequence of white squares in a row starting on a numbered square that does not follow another white square in the same row.

The sequence of white squares for that word goes across the row of the numbered square, ending immediately before the next black square in the row or in the rightmost square of the row.

A down" word for a definition is written on a sequence of white squares in a column starting on a numbered square that does not follow another white square in the same column.

The sequence of white squares for that word goes down the column of the numbered square, ending immediately before the next black square in the column or in the bottom square of the column.

Every white square in a correctly solved puzzle contains a letter.

You must write a program that takes several solved crossword puzzles as input and outputs the lists of across and down words which constitute the solutions.

Input

Each puzzle solution in the input starts with a line containing two integers r and c ( and ), where r (the first number) is the number of rows in the puzzle and c (the second number) is the number of columns.

The r rows of input which follow each contain c characters (excluding the end-of-line) which describe the solution. Each of those c characters is an alphabetic character which is part of a word or the character *", which indicates a black square.

The end of input is indicated by a line consisting of the single number 0.

Output

Output for each puzzle consists of an identifier for the puzzle (puzzle #1:, puzzle #2:, etc.) and the list of across words followed by the list of down words. Words in each list must be output one-per-line in increasing order of the number of their corresponding definitions.

The heading for the list of across words is Across". The heading for the list of down words is Down".

In the case where the lists are empty (all squares in the grid are black), the Across and Down headings should still appear.

Separate output for successive input puzzles by a blank line.

Sample Input

2 2

6 7

AIM*DEN

*ME*ONE

UPON*TO

SO*ERIN

*SA*OR*

IES*DEA

Sample Output

puzzle #1:

Across

1.AT

3.O

Down

1.A

2.TO

puzzle #2:

Across

1.AIM

4.DEN

7.ME

8.ONE

9.UPON

11.TO

12.SO

13.ERIN

15.SA

17.OR

18.IES

19.DEA

Down

1.A

2.IMPOSE

3.MEO

4.DO

5.ENTIRE

6.NEON

9.US

10.NE

14.ROD

16.AS

18.I

20.A

题目类型： 简单模拟题

算法分析：对于二维数组从左至右，从上至下遍历每个空间并判断该位置是否是”起始格”并赋予相应的序号。然后先以行优先输出行标志为true的单词，然后是以行优先输出列标志为true的单词。注意输出的最后一个测试用例的后面没有多余的空行，否则在UVA上会WA，下面第一个代码是更好的实现

/**************************************************
filename       :l.cpp
author         :maksyuki
created time   :2017/12/2 11:45:58
last modified  :2017/12/2 12:35:28
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int row, col;
int v[66][66];
char g[66][66];

bool check(int x, int y) {
    if(x - 1 < 1 || y - 1 < 1) return true;
    if(g[x-1][y] == '*' || g[x][y-1] == '*') return true;
    return false;
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int id = 1;
    while(scanf(" %d", &row) != EOF) {
        if(!row) break;
        
        scanf(" %d", &col);
        memset(v, 0, sizeof(v));
        for(int i = 1; i <= row; i++)
            for(int j = 1; j <= col; j++)
                scanf(" %c", &g[i][j]);

        int cnt = 1;
        for(int i = 1; i <= row; i++)
            for(int j = 1; j <= col; j++) {
                if(g[i][j] != '*')
                    if(check(i, j)) v[i][j] = cnt++;
            }

        if(id > 1) puts("");
        printf("puzzle #%d:\n", id++);
        
        puts("Across");
        for(int i = 1; i <= row; i++) {
            for(int j = 1; j <= col; j++) {
                if(v[i][j] && (j - 1 < 1 || g[i][j-1] == '*')) {
                    printf("%3d.", v[i][j]);
                    int tmpy = j;
                    while(tmpy <= col && g[i][tmpy] != '*') {
                        putchar(g[i][tmpy]);
                        tmpy++;
                    }
                    puts("");
                }
            }
        }

        puts("Down");
        for(int i = 1; i <= row; i++) {
            for(int j =  1; j <= col; j++) {
                if(v[i][j] && (i - 1 < 1 || g[i-1][j] == '*')) {
                    printf("%3d.", v[i][j]);
                    int tmpx = i;
                    while(tmpx <= row && g[tmpx][j] != '*') {
                        putchar(g[tmpx][j]);
                        tmpx++;
                    }
                    puts("");
                }
            }
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

/**************************************************

filename :l.cpp

author :maksyuki

created time :2017/12/2 11:45:58

last modified :2017/12/2 12:35:28

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int row, col;

int v[66][66];

char g[66][66];

bool check(int x, int y) {

if(x - 1 < 1 || y - 1 < 1) return true;

if(g[x-1][y] == '*' || g[x][y-1] == '*') return true;

return false;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int id = 1;

while(scanf(" %d", &row) != EOF) {

if(!row) break;

scanf(" %d", &col);

memset(v, 0, sizeof(v));

for(int i = 1; i <= row; i++)

for(int j = 1; j <= col; j++)

scanf(" %c", &g[i][j]);

int cnt = 1;

for(int i = 1; i <= row; i++)

for(int j = 1; j <= col; j++) {

if(g[i][j] != '*')

if(check(i, j)) v[i][j] = cnt++;

}

if(id > 1) puts("");

printf("puzzle #%d:\n", id++);

puts("Across");

for(int i = 1; i <= row; i++) {

for(int j = 1; j <= col; j++) {

if(v[i][j] && (j - 1 < 1 || g[i][j-1] == '*')) {

printf("%3d.", v[i][j]);

int tmpy = j;

while(tmpy <= col && g[i][tmpy] != '*') {

putchar(g[i][tmpy]);

tmpy++;

}

puts("");

}

puts("Down");

for(int i = 1; i <= row; i++) {

for(int j = 1; j <= col; j++) {

if(v[i][j] && (i - 1 < 1 || g[i-1][j] == '*')) {

printf("%3d.", v[i][j]);

int tmpx = i;

while(tmpx <= row && g[tmpx][j] != '*') {

putchar(g[tmpx][j]);

tmpx++;

}

puts("");

}

return 0;

}

#include <iostream>
#include <fstream>
#include <cstring>
#include <iomanip>
using namespace std;

const int maxn = 10 + 6;

char ans[maxn][maxn];

struct point
{
	int val;
	bool pos[2];					//pos = 0 means the across pos = 1 means the down;
};

point num[maxn][maxn];

int row, col;


bool OkMove (int x, int y)
{
	if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && ans[x][y] != '*')
		return true;

return false;
}

void OutPut (int x, int y, int flag)
{
	
	if (flag == 0)
	{
		cout << ans[x][y];

		while (OkMove (x, y + 1))
		{
			y += 1;
			cout << ans[x][y];
		}
	}

	else
	{
		cout << ans[x][y];

		while (OkMove (x + 1, y))
		{
			x += 1;
			cout << ans[x][y];
		}
	}

	cout << endl;
}


int main()
{
	//ifstream cin ("aaa.txt");

	int flag = 1;

	while (cin >> row)
	{
		if (row == 0)
			break;

		cin >> col;

		int i, j;
		for (i = 0; i < row; i++)
			for (j = 0; j < col; j++)
			{
				cin >> ans[i][j];
				num[i][j].val = -1;
				num[i][j].pos[0] = false;
				num[i][j].pos[1] = false;
			}

		int cnt = 1;

		for (i = 0; i < row; i++)
			for (j = 0; j < col; j++)
			{
				if (ans[i][j] != '*' && !OkMove (i, j - 1))
				{
					if (num[i][j].val == -1)
					{
						num[i][j].val = cnt++;
						num[i][j].pos[0] = true;
					}

					else
						num[i][j].pos[0] = true;
				}

				if (ans[i][j] != '*' && !OkMove (i - 1, j))
				{
					if (num[i][j].val == -1)
					{
						num[i][j].val = cnt++;
						num[i][j].pos[1] = true;
					}

					else
						num[i][j].pos[1] = true;
				}
			}

		if (flag - 1)
			cout << endl;

		cout << "puzzle #" << flag++ << ":" << endl << "Across" << endl;

		for (i = 0; i < row; i++)
		{
			for (j = 0; j < col; j++)
				if (num[i][j].val != -1 && num[i][j].pos[0])
				{
					cout << setw (3) << num[i][j].val << ".";

					OutPut (i, j, 0);
				}

		}

		cout << "Down" << endl;
		for (i = 0; i < row; i++)
		{
			for (j = 0; j < col; j++)
				if (num[i][j].val != -1 && num[i][j].pos[1])
				{
					cout << setw (3) << num[i][j].val << ".";
					OutPut (i, j, 1);
				}
		}

	}

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

#include <iostream>

#include <fstream>

#include <cstring>

#include <iomanip>

using namespace std;

const int maxn = 10 + 6;

char ans[maxn][maxn];

struct point

{

int val;

bool pos[2]; //pos = 0 means the across pos = 1 means the down;

};

point num[maxn][maxn];

int row, col;

bool OkMove (int x, int y)

{

if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && ans[x][y] != '*')

return true;

return false;

}

void OutPut (int x, int y, int flag)

{

if (flag == 0)

{

cout << ans[x][y];

while (OkMove (x, y + 1))

{

y += 1;

cout << ans[x][y];

}

else

{

cout << ans[x][y];

while (OkMove (x + 1, y))

{

x += 1;

cout << ans[x][y];

}

cout << endl;

}

int main()

{

//ifstream cin ("aaa.txt");

int flag = 1;

while (cin >> row)

{

if (row == 0)

break;

cin >> col;

int i, j;

for (i = 0; i < row; i++)

for (j = 0; j < col; j++)

{

cin >> ans[i][j];

num[i][j].val = -1;

num[i][j].pos[0] = false;

num[i][j].pos[1] = false;

}

int cnt = 1;

for (i = 0; i < row; i++)

for (j = 0; j < col; j++)

{

if (ans[i][j] != '*' && !OkMove (i, j - 1))

{

if (num[i][j].val == -1)

{

num[i][j].val = cnt++;

num[i][j].pos[0] = true;

}

else

num[i][j].pos[0] = true;

}

if (ans[i][j] != '*' && !OkMove (i - 1, j))

{

if (num[i][j].val == -1)

{

num[i][j].val = cnt++;

num[i][j].pos[1] = true;

}

else

num[i][j].pos[1] = true;

}

if (flag - 1)

cout << endl;

cout << "puzzle #" << flag++ << ":" << endl << "Across" << endl;

for (i = 0; i < row; i++)

{

for (j = 0; j < col; j++)

if (num[i][j].val != -1 && num[i][j].pos[0])

{

cout << setw (3) << num[i][j].val << ".";

OutPut (i, j, 0);

}

cout << "Down" << endl;

for (i = 0; i < row; i++)

{

for (j = 0; j < col; j++)

if (num[i][j].val != -1 && num[i][j].pos[1])

{

cout << setw (3) << num[i][j].val << ".";

OutPut (i, j, 1);

}

return 0;

}

uva237

maksyuki 发表于 oj 分类，标签: 基础算法-模拟

12 9月 2015

A children's puzzle that was popular 30 years ago consisted of a 5x5 frame which contained 24 small squares of equal size. A unique letter of the alphabet was printed on each small square. Since there were only 24 squares within the frame, the frame also contained an empty position which was the same size as a small square. A square could be moved into that empty position if it were immediately to the right, to the left, above, or below the empty position. The object of the puzzle was to slide squares into the empty position so that the frame displayed the letters in alphabetical order.

The illustration below represents a puzzle in its original configuration and in its configuration after the following sequence of 6 moves:

1)The square above the empty position moves.

2)The square to the right of the empty position moves.

3)The square to the right of the empty position moves.

4)The square below the empty position moves.

5)The square below the empty position moves.

6)The square to the left of the empty position moves.

Write a program to display resulting frames given their initial configurations and sequences of moves.

Input

Input for your program consists of several puzzles. Each is described by its initial configuration and the sequence of moves on the puzzle. The first 5 lines of each puzzle description are the starting configuration. Subsequent lines give the sequence of moves.

The first line of the frame display corresponds to the top line of squares in the puzzle. The other lines follow in order. The empty position in a frame is indicated by a blank. Each display line contains exactly 5 characters, beginning with the character on the leftmost square (or a blank if the leftmost square is actually the empty frame position). The display lines will correspond to a legitimate puzzle.

The sequence of moves is represented by a sequence of As, Bs, Rs, and Ls to denote which square moves into the empty position. A denotes that the square above the empty position moves; B denotes that the square below the empty position moves; L denotes that the square to the left of the empty position moves; R denotes that the square to the right of the empty position moves. It is possible that there is an illegal move, even when it is represented by one of the 4 move characters. If an illegal move occurs, the puzzle is considered to have no final configuration. This sequence of moves may be spread over several lines, but it always ends in the digit 0. The end of data is denoted by the character Z.

Output

Output for each puzzle begins with an appropriately labeled number (Puzzle #1, Puzzle #2, etc.). If the puzzle has no final configuration, then a message to that effect should follow. Otherwise that final configuration should be displayed.

Format each line for a final configuration so that there is a single blank character between two adjacent letters. Treat the empty square the same as a letter. For example, if the blank is an interior position, then it will appear as a sequence of 3 blanks - one to separate it from the square to the left, one for the empty position itself, and one to separate it from the square to the right.

Separate output from different puzzle records by one blank line.

Note: The first record of the sample input corresponds to the puzzle illustrated above.

Sample Input

TRGSJ

XDOKI

M VLN

WPABE

UQHCF

ARRBBL0

ABCDE

FGHIJ

KLMNO

PQRS

TUVWX

AAA

LLLL0

ABCDE

FGHIJ

KLMNO

PQRS

TUVWX

AAAAABBRRRLL0

Sample Output

Puzzle #1:

T R G S J

X O K L I

M D V B N

W P A E

U Q H C F

Puzzle #2:

A B C D

F G H I E

K L M N J

P Q R S O

T U V W X

Puzzle #3:

This puzzle has no final configuration.

题目类型： 简单模拟题

算法分析：按照题目的输入要求将所需的数据输入，然后遍历一次二维数组找到’ ’的位置(即移动时起始位置)。然后输入指令数列，按照指令序列模拟’ ’的移动。维护一个标志位is_illegal，一旦出现不满足移动条件的指令，就将标志位is_illegal标识为true。当所有的序列都模拟完之后，判断is_illegal的值即可。注意最后一个测试用例的最后没有多余的空行，不注意在UVA上会WA

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

const char ch[] = {'A', 'B', 'L', 'R'};

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

char ans[8][8];
bool is_illegal;

bool OkMove (int x, int y)
{
	if (x >= 0 && x <= 4 && y >= 0 && y <= 4)
		return true;

return false;
}


int main()
{
	//ifstream cin ("aaa.txt");
		
	int flag = 1;

	int weizhi_x, weizhi_y;

	while (cin.getline (ans[0], 8))
	{
		if (ans[0][0] == 'Z')
			break;

		int i, j;
		for (i = 1; i < 5; i++)
			cin.getline (ans[i], 8);

		for (i = 0; i < 5; i++)
			for (j = 0; j < 5; j++)
				if (ans[i][j] == ' ')
				{
					weizhi_x = i;
					weizhi_y = j;
				}

		char input;	
		is_illegal = false;

		while ((input = cin.get ()) != '0')
		{
			for (i = 0; i < 4; i++)
			{
				if (input == ch[i])
				{
					if (OkMove (weizhi_x + dx[i], weizhi_y + dy[i]))
					{
						ans[weizhi_x][weizhi_y] = ans[weizhi_x+dx[i]][weizhi_y+dy[i]];
						ans[weizhi_x+dx[i]][weizhi_y+dy[i]] = ' ';
						weizhi_x += dx[i];
						weizhi_y += dy[i];
						
					}

					else
						is_illegal = true;

					break;					//important!!!!!!
				}
			}

//			if (i == 4)
//				is_illegal = true;
		}
		
		if (flag - 1)
			cout << endl;

		cout << "Puzzle #" << flag++ << ":" << endl;

		if (is_illegal)
			cout << "This puzzle has no final configuration." << endl;

		else
		{
			for (i = 0; i < 5; i++)
			{
				for (j = 0; j < 4; j++)
					cout << ans[i][j] << " ";
				cout << ans[i][j] << endl;
			}
		}

		cin.ignore ();
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

const char ch[] = {'A', 'B', 'L', 'R'};

const int dx[] = {-1, 1, 0, 0};

const int dy[] = {0, 0, -1, 1};

char ans[8][8];

bool is_illegal;

bool OkMove (int x, int y)

{

if (x >= 0 && x <= 4 && y >= 0 && y <= 4)

return true;

return false;

}

int main()

{

//ifstream cin ("aaa.txt");

int flag = 1;

int weizhi_x, weizhi_y;

while (cin.getline (ans[0], 8))

{

if (ans[0][0] == 'Z')

break;

int i, j;

for (i = 1; i < 5; i++)

cin.getline (ans[i], 8);

for (i = 0; i < 5; i++)

for (j = 0; j < 5; j++)

if (ans[i][j] == ' ')

{

weizhi_x = i;

weizhi_y = j;

}

char input;

is_illegal = false;

while ((input = cin.get ()) != '0')

{

for (i = 0; i < 4; i++)

{

if (input == ch[i])

{

if (OkMove (weizhi_x + dx[i], weizhi_y + dy[i]))

{

ans[weizhi_x][weizhi_y] = ans[weizhi_x+dx[i]][weizhi_y+dy[i]];

ans[weizhi_x+dx[i]][weizhi_y+dy[i]] = ' ';

weizhi_x += dx[i];

weizhi_y += dy[i];

}

else

is_illegal = true;

break; //important!!!!!!

}

// if (i == 4)

// is_illegal = true;

}

if (flag - 1)

cout << endl;

cout << "Puzzle #" << flag++ << ":" << endl;

if (is_illegal)

cout << "This puzzle has no final configuration." << endl;

else

{

for (i = 0; i < 5; i++)

{

for (j = 0; j < 4; j++)

cout << ans[i][j] << " ";

cout << ans[i][j] << endl;

}

cin.ignore ();

}

return 0;

}

uva213

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

12 9月 2015

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.

Sample input

TNM AEIOU

0010101100011

1010001001110110011

11000

$#**\

0100000101101100011100101000

Sample output

TAN ME

##*\$

题目类型：简单字符处理

算法分析：按照题意将编码理解成二进制，用（len，value）这个二元数组来表示一个编码，其中len为编码的长度，value是编码所对应的十进制值。下面程序中的readcodes函数来读取第一行的编码，readint函数则读取指定位数的二进制字符并返回相应的十进制值。为了解决编码文本可以有多行组成，编写跨行读字符函数readchar，下面第一个代码是最新的实现

/**************************************************
filename       :e.cpp
author         :maksyuki
created time   :2017/12/5 9:51:13
last modified  :2017/12/5 10:42:52
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

char tab[10][1<<8];
char sa[maxn], sb[maxn];
int lenb;

void encode() {
    int p = 0;
    for(int i = 1; i <= 8; i++)
        for(int j = 0; j < (1 << i) - 1; j++) {
            if(sa[p] == '\n' || sa[p] == '\r') return;
            tab[i][j] = sa[p];
            p++;
        }
}

int readc(int len) {    
    int ans = 0, cnt = 1;
    char c;
    while(cnt <= len) {
        c = fgetc(stdin);
        if(c == '\n' || c == '\r') continue;
        ans = ans * 2 + (c - '0');
        cnt++;
    }
    return ans;
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    while(fgets(sa, maxn, stdin) != NULL) {
        encode();
//        for(int i = 1; i <= 3; i++)
//           for(int j = 0; j < (1 << i) - 1; j++)
//                printf("(%d,%d)-%c\n", i, j, tab[i][j]);

        while(1) {
            int vlen = readc(3);
            if(!vlen) break; 
            while(1) {
                int vv = readc(vlen);
                if(vv == (1 << vlen) - 1) break;
                printf("%c", tab[vlen][vv]);
            }
        }
        fgets(sa, maxn, stdin);
        puts("");
    }

    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

/**************************************************

filename :e.cpp

author :maksyuki

created time :2017/12/5 9:51:13

last modified :2017/12/5 10:42:52

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

char tab[10][1<<8];

char sa[maxn], sb[maxn];

int lenb;

void encode() {

int p = 0;

for(int i = 1; i <= 8; i++)

for(int j = 0; j < (1 << i) - 1; j++) {

if(sa[p] == '\n' || sa[p] == '\r') return;

tab[i][j] = sa[p];

p++;

}

int readc(int len) {

int ans = 0, cnt = 1;

char c;

while(cnt <= len) {

c = fgetc(stdin);

if(c == '\n' || c == '\r') continue;

ans = ans * 2 + (c - '0');

cnt++;

}

return ans;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

while(fgets(sa, maxn, stdin) != NULL) {

encode();

// for(int i = 1; i <= 3; i++)

// for(int j = 0; j < (1 << i) - 1; j++)

// printf("(%d,%d)-%c\n", i, j, tab[i][j]);

while(1) {

int vlen = readc(3);

if(!vlen) break;

while(1) {

int vv = readc(vlen);

if(vv == (1 << vlen) - 1) break;

printf("%c", tab[vlen][vv]);

}

fgets(sa, maxn, stdin);

puts("");

}

return 0;

}

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

int code[8][1<<8];

int readchar ()
{
    while (1)
	{
        int ch = getchar ();

        if (ch != '\n' && ch != '\r')
			return ch;
	}
}

int readint (int weishu)
{
	 int val = 0;
     while (weishu--)
	 {
          val = val * 2 + readchar () - '0';
	 }

	 return val;
}

int readcodes ()
{
    memset (code, 0, sizeof (code));

    code[1][0] = readchar ();
    int len, i;

    for (len = 2; len <= 7; len++)
	{
		for (i = 0; i < (1 << len) - 1; i++)
		{
			int ch = getchar ();

			if (ch == EOF)
				return 0;

			if (ch == '\n' || ch == '\r')
				return 1;

			code[len][i] = ch;
		}
	}
}

int main()
{
	//freopen ("aaa.txt", "r", stdin);

    while (readcodes ())
    {
        while (1)
		{
            int len = readint (3);

            if (!len)
				break;

			while (1)
			{
                int val = readint (len);

                if (val == (1 << len) - 1)
					break;

				putchar (code[len][val]);
			}
		}
		printf ("\n");
    }

    return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

int code[8][1<<8];

int readchar ()

{

while (1)

{

int ch = getchar ();

if (ch != '\n' && ch != '\r')

return ch;

}

int readint (int weishu)

{

int val = 0;

while (weishu--)

{

val = val * 2 + readchar () - '0';

}

return val;

}

int readcodes ()

{

memset (code, 0, sizeof (code));

code[1][0] = readchar ();

int len, i;

for (len = 2; len <= 7; len++)

{

for (i = 0; i < (1 << len) - 1; i++)

{

int ch = getchar ();

if (ch == EOF)

return 0;

if (ch == '\n' || ch == '\r')

return 1;

code[len][i] = ch;

}

int main()

{

//freopen ("aaa.txt", "r", stdin);

while (readcodes ())

{

while (1)

{

int len = readint (3);

if (!len)

break;

while (1)

{

int val = readint (len);

if (val == (1 << len) - 1)

break;

putchar (code[len][val]);

}

printf ("\n");

}

return 0;

}

uva202

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

12 9月 2015

The decimal expansion of the fraction 1/33 is , where the is used to indicate that the cycle 03 repeats indefinitely with no intervening digits. In fact, the decimal expansion of every rational number (fraction) has a repeating cycle as opposed to decimal expansions of irrational numbers, which have no such repeating cycles.

Examples of decimal expansions of rational numbers and their repeating cycles are shown below. Here, we use parentheses to enclose the repeating cycle rather than place a bar over the cycle.

Write a program that reads numerators and denominators of fractions and determines their repeating cycles.

For the purposes of this problem, define a repeating cycle of a fraction to be the first minimal length string of digits to the right of the decimal that repeats indefinitely with no intervening digits. Thus for example, the repeating cycle of the fraction 1/250 is 0, which begins at position 4 (as opposed to 0 which begins at positions 1 or 2 and as opposed to 00 which begins at positions 1 or 4).

Input

Each line of the input file consists of an integer numerator, which is nonnegative, followed by an integer denominator, which is positive. None of the input integers exceeds 3000. End-of-file indicates the end of input.

Output

For each line of input, print the fraction, its decimal expansion through the first occurrence of the cycle to the right of the decimal or 50 decimal places (whichever comes first), and the length of the entire repeating cycle.

In writing the decimal expansion, enclose the repeating cycle in parentheses when possible. If the entire repeating cycle does not occur within the first 50 places, place a left parenthesis where the cycle begins - it will begin within the first 50 places - and place ...)" after the 50th digit.

Print a blank line after every test case.

Sample Input

76 25

5 43

1 397

Sample Output

76/25 = 3.04(0)

1 = number of digits in repeating cycle

5/43 = 0.(116279069767441860465)

21 = number of digits in repeating cycle

1/397 = 0.(00251889168765743073047858942065491183879093198992...)

99 = number of digits in repeating cycle

题目类型： 字符处理题

算法分析：本题考查的是高精度除法的使用，在函数Division中最为关键的是将数据记录在record数组中并使用cnt数组来判断循环节。注意每个测试用例输出的最后是一个空行，下面第一个代码是更好的实现

/**************************************************
filename       :n.cpp
author         :maksyuki
created time   :2017/12/2 13:17:13
last modified  :2017/12/2 20:38:57
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int v[maxn], p[maxn];
bool vis[maxn];

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    int va, vb;
    while(scanf(" %d %d", &va, &vb) != EOF) {
        int len = 0, ta = va, tb = vb;
        
        v[len++] = ta / tb;
        
        ta = ta % tb;
        memset(vis, false, sizeof(vis));
        memset(p, 0, sizeof(p));

        while(ta && !vis[ta]) {
            vis[ta] = true;
            p[len] = ta;
            ta *= 10;
            v[len++] = ta / tb;
            ta %= tb;
        }
        
        printf("%d/%d = %d.", va, vb, v[0]);
       
        int i, j, pos = -1;
        for(i = 1, j = 1; i < len && j <= 50; i++, j++) {
            if(p[i] == ta) {
                pos = i;
                break;
            }
            else
                printf("%d", v[i]);
        }
        
        printf("(");
        if(!ta) printf("0");
        else {
            for(; i < len && j <= 50; i++, j++) printf("%d", v[i]);
        }

        if(j > 50) printf("...");
        puts(")");
        
        if(!ta) printf("   1");
        else printf("   %d", len - pos); 
        printf(" = number of digits in repeating cycle\n", len - pos);
        puts("");
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

/**************************************************

filename :n.cpp

author :maksyuki

created time :2017/12/2 13:17:13

last modified :2017/12/2 20:38:57

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int v[maxn], p[maxn];

bool vis[maxn];

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int va, vb;

while(scanf(" %d %d", &va, &vb) != EOF) {

int len = 0, ta = va, tb = vb;

v[len++] = ta / tb;

ta = ta % tb;

memset(vis, false, sizeof(vis));

memset(p, 0, sizeof(p));

while(ta && !vis[ta]) {

vis[ta] = true;

p[len] = ta;

ta *= 10;

v[len++] = ta / tb;

ta %= tb;

}

printf("%d/%d = %d.", va, vb, v[0]);

int i, j, pos = -1;

for(i = 1, j = 1; i < len && j <= 50; i++, j++) {

if(p[i] == ta) {

pos = i;

break;

}

else

printf("%d", v[i]);

}

printf("(");

if(!ta) printf("0");

else {

for(; i < len && j <= 50; i++, j++) printf("%d", v[i]);

}

if(j > 50) printf("...");

puts(")");

if(!ta) printf(" 1");

else printf(" %d", len - pos);

printf(" = number of digits in repeating cycle\n", len - pos);

puts("");

}

return 0;

}

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

const int maxn = 6000 + 166;

int record[maxn];
bool cnt[maxn];
int mod[maxn];

void Division (int nume, int denom)
{
	memset (record, 0, sizeof (record));
	memset (cnt, false,	sizeof (cnt));
	memset (mod, 0, sizeof (mod));

	record[0] = nume / denom;
	cout << nume << "/" << denom << " = " << record[0] << ".";
	
	nume %= denom;
	

	int weishu = 1;

	while (nume && !cnt[nume])
	{
		cnt[nume] = true;
		mod[weishu] = nume;
		nume *= 10;
		record[weishu++] = nume / denom;
		
		nume %= denom;		
	}
	

	int i;
	for (i = 1; i < weishu && i <= 50; i++)
	{
		if (nume && mod[i] == nume)
			cout << "(";

		cout << record[i];
	}

	if (nume == 0)
		cout << "(0";

	if (i > 50)
		cout << "...";
	cout << ")" << endl;

	cout << "   ";
	
	if (!nume)
		cout << "1";

	else
	{
		for (i = 0; i < weishu; i++)
			if (mod[i] == nume)
				break;
		cout << weishu - i;
	}

	cout << " = number of digits in repeating cycle" << endl;
}


int main()
{
//	ifstream cin ("aaa.txt");

	int nume, denom;

	while (cin >> nume >> denom)
	{
		Division (nume, denom);
		cout << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

const int maxn = 6000 + 166;

int record[maxn];

bool cnt[maxn];

int mod[maxn];

void Division (int nume, int denom)

{

memset (record, 0, sizeof (record));

memset (cnt, false, sizeof (cnt));

memset (mod, 0, sizeof (mod));

record[0] = nume / denom;

cout << nume << "/" << denom << " = " << record[0] << ".";

nume %= denom;

int weishu = 1;

while (nume && !cnt[nume])

{

cnt[nume] = true;

mod[weishu] = nume;

nume *= 10;

record[weishu++] = nume / denom;

nume %= denom;

}

int i;

for (i = 1; i < weishu && i <= 50; i++)

{

if (nume && mod[i] == nume)

cout << "(";

cout << record[i];

}

if (nume == 0)

cout << "(0";

if (i > 50)

cout << "...";

cout << ")" << endl;

cout << " ";

if (!nume)

cout << "1";

else

{

for (i = 0; i < weishu; i++)

if (mod[i] == nume)

break;

cout << weishu - i;

}

cout << " = number of digits in repeating cycle" << endl;

}

int main()

{

// ifstream cin ("aaa.txt");

int nume, denom;

while (cin >> nume >> denom)

{

Division (nume, denom);

cout << endl;

}

return 0;

}

uva136

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

12 9月 2015

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

shows the first 11 ugly numbers. By convention, 1 is included.

阅读全文 »

fzu1759

maksyuki 发表于 oj 分类，标签: 数论-欧拉定理

12 9月 2015

Problem Description

Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,C<=1000000000,1<=B<=10^1000000).

Input

There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.

Output

For each testcase, output an integer, denotes the result of A^B mod C.

Sample Input

3 2 4

2 10 1000

Sample Output

Source

FZU 2009 Summer Training IV--Number Theory

题目类型：欧拉定理降幂

算法分析：直接使用欧拉定理进行降幂处理，注意指数可能会比较大，需要从高位到低位按位取模计算

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-6;
const double PI = 2 * acos (0.0);
const int maxn = 2;

LL phi (LL val)
{
    LL res = val;
    for (LL i = 2; i * i <= val; i++)
    {
        if (val % i == 0)
        {
            res -= res / i;
            while (val % i == 0) val /= i;
        }
    }

    if (val > 1)
        res -= res / val;

    return res;
}

LL mod_f (LL a, LL b, LL p)
{
    LL res = 1, tt = (a % p + p) % p;
    while (b)
    {
        if (b & 1)
            res = res * tt % p;
        tt = tt * tt % p;
        b >>= 1;
    }
    return res;
}


int main()
{
//    CPPFF;
    LL aa, cc;
    string bb;
    while (cin >> aa >> bb >> cc)
    {
        LL tt = phi (cc);
        LL tb = 0;
        for (LL i = 0; i < bb.size (); i++)
            tb = (tb * 10 + bb[i] - '0') % tt;

        cout << mod_f (aa, tb % tt + tt, cc) << endl;
    }
    return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-6;

const double PI = 2 * acos (0.0);

const int maxn = 2;

LL phi (LL val)

{

LL res = val;

for (LL i = 2; i * i <= val; i++)

{

if (val % i == 0)

{

res -= res / i;

while (val % i == 0) val /= i;

}

if (val > 1)

res -= res / val;

return res;

}

LL mod_f (LL a, LL b, LL p)

{

LL res = 1, tt = (a % p + p) % p;

while (b)

{

if (b & 1)

res = res * tt % p;

tt = tt * tt % p;

b >>= 1;

}

return res;

}

int main()

{

// CPPFF;

LL aa, cc;

string bb;

while (cin >> aa >> bb >> cc)

{

LL tt = phi (cc);

LL tb = 0;

for (LL i = 0; i < bb.size (); i++)

tb = (tb * 10 + bb[i] - '0') % tt;

cout << mod_f (aa, tb % tt + tt, cc) << endl;

}

return 0;

}

fzu1669

maksyuki 发表于 oj 分类，标签: 数论-毕达哥拉斯三元组

12 9月 2015

Problem Description

A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted △ABC.

Triangles can also be classified according to their internal angles, described below using degrees of arc:

A right triangle (or right-angled triangle, formerly called a rectangled triangle) has one 90° internal angle (a right angle). The side opposite to the right angle is the hypotenuse; it is the longest side in the right triangle. The other two sides are the legs or catheti (singular: cathetus) of the triangle. Right triangles conform to the Pythagorean Theorem, wherein the sum of the squares of the two legs is equal to the square of the hypotenuse, i.e., a^2 + b^2 = c^2, where a and b are the legs and c is the hypotenuse.
An oblique triangle has no internal angle equal to 90°.
An obtuse triangle is an oblique triangle with one internal angle larger than 90° (an obtuse angle).
An acute triangle is an oblique triangle with internal angles all smaller than 90° (three acute angles). An equilateral triangle is an acute triangle, but not all acute triangles are equilateral triangles.

What we consider here is very simple. Give you the length of L, you should calculate there are how many right-angled triangles such that a + b + c ≤ L where a and b are the legs and c is the hypotenuse. You should note that the three numbers a, b and c are all integers.

Input

There are multiply test cases. For each test case, the first line is an integer L(12≤L≤2000000), indicating the length of L.

Output

For each test case, output the number of right-angled triangles such that a + b + c ≤ L where a and b are the legs and c is the hypotenuse.

Sample Input

Sample Output

Hint

There are five right-angled triangles where a + b + c ≤ 40. That are one right-angled triangle where a = 3, b = 4 and c = 5; one right-angled triangle where a = 6, b = 8 and c = 10; one right-angled triangle where a = 5, b = 12 and c = 13; one right-angled triangle where a = 9, b = 12 and c = 15; one right-angled triangle where a = 8, b = 15 and c = 17.

Source

FOJ月赛-2008年11月

题目类型：毕达哥拉斯三元组

算法分析：直接按照定理构建本原的毕达哥拉斯三元组，然后直接除本原的毕达哥拉斯三元组的和累加到res即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define i64 long long

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-6;
const double PI = 2 * acos (0.0);
const int maxn = 1e6 + 66;

long long gcd (long long a, long long b)
{
    if (b == 0)
        return a;
    return gcd (b, a % b);
}


int main()
{
//    CPPFF;

    long long val;
    while (cin >> val)
    {
        long long tt = (long long ) sqrt (val + 0.0);
        long long res = 0, x, y, z, ta;

        for (long long n = 1; n <= tt; n++)
        {
            for (long long m = n + 1; m <= tt; m++)
            {
                if (2 * m * m + 2 * m * n > val)
                    break;

                if (gcd (n, m) == 1 && (n % 2 != m % 2))
                {
                    x = m * m - n * n;
                    y = 2 * m * n;
                    z = m * m + n * n;
                    ta = val / (x + y + z);
                    res += ta;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define i64 long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-6;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

long long gcd (long long a, long long b)

{

if (b == 0)

return a;

return gcd (b, a % b);

}

int main()

{

// CPPFF;

long long val;

while (cin >> val)

{

long long tt = (long long ) sqrt (val + 0.0);

long long res = 0, x, y, z, ta;

for (long long n = 1; n <= tt; n++)

{

for (long long m = n + 1; m <= tt; m++)

{

if (2 * m * m + 2 * m * n > val)

break;

if (gcd (n, m) == 1 && (n % 2 != m % 2))

{

x = m * m - n * n;

y = 2 * m * n;

z = m * m + n * n;

ta = val / (x + y + z);

res += ta;

}

cout << res << endl;

}

return 0;

}

acdream1077

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

12 9月 2015

Problem Description

Some days ago, I learned the concept of LCM (least common multiple). I've played with it for several times and I want to make a big number with it.

But I also don't want to use many numbers, so I'll choose three positive integers (they don't have to be distinct) which are not greater than n. Can you help me to find the maximum possible least common multiple of these three integers?

Input

The first line contains an integer n (1 ≤ n ≤ 10^6) — the n mentioned in the statement.

Output

Print a single integer — the maximum possible LCM of three not necessarily distinct positive integers that are not greater than n.

Sample Input

Sample Output

504

Source

WJMZBMR

Manager

admin

题目类型：LCM

算法分析：题目要求的是任意3个大于等于1小于等于n的数的最小公倍数的最大值。由于有相邻两个自然数a、a+1的最大公约数是1，即意味着相邻两个数的最小公倍数是a *(a+1)。如果n是奇数，则可易知n*(n-1)*(n-2)就是最大的LCM。如果n是偶数，则判断n是否是3的倍数。如果是，则(n-1)*(n-2)*(n-3)就是结果，反之，结果是n*(n-1)*(n-3)。对于后面的结论，进行一个简单的说明：首先(n-1)*(n-2)*(n-3)要比(n-1)*n*(n-3)小，但是如果3|n，则n和n-3的最小公倍数就不是1了。会导致结果变小，所以此时不应该选择这种情况

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1000 + 66;


int main()
{
//	ifstream cin("aaa.txt");

    long long n;

    while (cin >> n)
    {
    	if(n == 1)
			cout << "1" << endl;

		else if (n == 2)
			cout << "2" << endl;

		else
		{
			if (n & 1)
                cout << n * (n - 1) * (n - 2) << endl;

			else
			{
                if (n % 3)
                    cout << n * (n - 1) * (n - 3) << endl;

				else
					cout << (n - 1) * (n - 2) * (n - 3) << endl;
			}
		}
    }
return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1000 + 66;

int main()

{

// ifstream cin("aaa.txt");

long long n;

while (cin >> n)

{

if(n == 1)

cout << "1" << endl;

else if (n == 2)

cout << "2" << endl;

else

{

if (n & 1)

cout << n * (n - 1) * (n - 2) << endl;

else

{

if (n % 3)

cout << n * (n - 1) * (n - 3) << endl;

else

cout << (n - 1) * (n - 2) * (n - 3) << endl;

}

return 0;

}

vijos1448

maksyuki 发表于 oj 分类，标签: 数据结构-线段树

12 9月 2015

描述

校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……
如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：阅读全文 »

vijos1312

maksyuki 发表于 oj 分类，标签: DP-区间DP

12 9月 2015

描述

在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，阅读全文 »

vijos1165

maksyuki 发表于 oj 分类，标签: 基础算法-贪心

12 9月 2015

描述

曹操平定北方以后，公元208年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。

孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。

隆冬的十一月，天气突然回暖，刮起了东南风。阅读全文 »

vijos1098

maksyuki 发表于 oj 分类，标签: DP-线性DP

12 9月 2015

描述

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。阅读全文 »

zoj3609

maksyuki 发表于 oj 分类，标签: 数论-乘法逆元

11 9月 2015

Modular Inverse

The modular modular multiplicative inverse of an integer a modulo m is an integer x such that a^-1≡x (mod m). This is equivalent to ax≡1 (mod m).

Input

There are multiple test cases. The first line of input is an integer T ≈ 2000 indicating the number of test cases.

Each test case contains two integers 0 < a ≤ 1000 and 0 < m ≤ 1000.

Output

For each test case, output the smallest positive x. If such x doesn't exist, output "Not Exist".

Sample Input

33 114 125 13

Sample Output

4Not Exist8

Author: WU, Zejun
Contest: The 9th Zhejiang Provincial Collegiate Programming Contest

题目类型：乘法逆元

算法分析：直接使用乘法逆元求解即可，注意本题要求求解的是最小正值，而不是最小非负值！！！

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-6;
const double PI = 2 * acos (0.0);
const int maxn = 1e6 + 66;

long long gcd_ex (long long a, long long b, long long &x, long long &y)
{
    if (b == 0) { x = 1; y = 0; return a; }
    long long d = gcd_ex (b, a % b, y, x);
    y = y - a / b * x;
    return d;
}

long long mod_equ (long long a, long long b, long long c)
{
    long long x, y;
    long long d = gcd_ex (a, b, x, y);

    if (c % d)
        return -1;

    x = (x * c / d) % (b / d);
    if (x <= 0)
        x += b / d;

    return x;
}

int main()
{
//    CPPFF;
    LL aa, mm, tt;
    cin >> tt;

    while(tt--)
    {
        cin >> aa >> mm;
        LL tt = mod_equ (aa, mm, 1);

        if (tt == -1)
            cout << "Not Exist" << endl;

        else
            cout << tt << endl;
    }
    return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-6;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

long long gcd_ex (long long a, long long b, long long &x, long long &y)

{

if (b == 0) { x = 1; y = 0; return a; }

long long d = gcd_ex (b, a % b, y, x);

y = y - a / b * x;

return d;

}

long long mod_equ (long long a, long long b, long long c)

{

long long x, y;

long long d = gcd_ex (a, b, x, y);

if (c % d)

return -1;

x = (x * c / d) % (b / d);

if (x <= 0)

x += b / d;

return x;

}

int main()

{

// CPPFF;

LL aa, mm, tt;

cin >> tt;

while(tt--)

{

cin >> aa >> mm;

LL tt = mod_equ (aa, mm, 1);

if (tt == -1)

cout << "Not Exist" << endl;

else

cout << tt << endl;

}

return 0;

}

返回首页上一页 13 14 15 16 17 下一页最后一页

2015年9月
一	二	三	四	五	六	日
« 8月				10月 »
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

Input

Output

Sample Input

Sample Output

Source

Input

Output

Sample Input

Sample Output

Hint

Source

Problem Description

Input

Output

Sample Input

Sample Output

Source

Manager

描述

描述

描述

描述

分类目录

标签云

书签

近期评论