Rick's blog

UVA 10004 ： https://uva.onlinejudge.org/external/100/10004.pdf /*DFS , bipartite graph*/ #include<iostream> #include<cstring> using namespace std; #define size 205 int matrix[size][size]; int color[size]; int n = 0; int dfs(int start) { for (int end= 0; end < n; end++) { //matirx[start][end] = 1 , means start vertex and end vertex was connected if (matrix[start][end]) { //if end vertex hasn't be check, then drew color and keep going next adjacent vertex if (!color[end]) { color[end] = !color[start]; dfs(end); } // based on end vertex has been check before // start vertex and end vertex color have the same color, means color already repeat ,so cant be drew correct else if (color[start] == color[end]) return 0; } } return 1; } int main(void) { while (1) { int l = 0,row=0,col=0; cin >> n; if (n == 0)break; cin >> l; memset(matrix, 0, sizeof(matrix)); ...

UVA 11547　： https://uva.onlinejudge.org/external/115/11547.pdf #include<iostream> using namespace std; int t = 0,n=0; int main(void) { cin >> t; while (t--) { cin >> n; n = n* 315+36962; cout << abs(n/10%10) << endl; } system("PAUSE"); }

UVA488 : https://uva.onlinejudge.org/external/4/488.pdf /*easy */ #include<iostream> using namespace std; int n = 0,A = 0,F = 0,blank=1; int main(void) { cin >> n; while(n--) { cin >> A >> F; for (int f = 0; f < F; f++) { int i = 1, j = 1; if (blank == 0)cout << endl; for (i = 1; i <= A; i++) { for (j = 1; j <= i; j++) { cout << i; } cout << endl; } for (i = A - 1; i >= 1; i--) { for (int j = i; j >= 1; j--) { cout << i ; } cout << endl; } blank = 0; } } system("PAUSE"); }

UVA 10696 :     https://uva.onlinejudge.org/external/106/10696.pdf /*recurrsion math*/ #include<iostream> #include<cstring> using namespace std; int n=0,ans=0; int main(void) { while (cin >> n) { if (n == 0)break; //regular if (n <= 101) ans = 91; else ans = n - 10; cout <<"f91("<<n<<") = "<< ans << endl; } system("PAUSE"); }

UVA 108:  https://uva.onlinejudge.org/external/1/108.pdf /*Maximum Subarray*/ /* normal : O(N^4) best : O(N^3) */ reference #include<iostream> #include<cstring> #include<algorithm> #define maxn 100+5 using namespace std; int n, matrix[maxn][maxn], cur_matrix[maxn]; int find_max() { //calculate maximum subarray each row int cur_sum = 0, sum = 0; for (int l = 0; l < n; l++) { sum += cur_matrix[l]; cur_sum = max(sum, cur_sum); if (sum < 0) sum = 0; } return cur_sum; } void ans() { //compress int MaxSum = -200; for (int i = 0; i < n; i++) { memset(cur_matrix, 0, sizeof(cur_matrix)); for (int j = i; j < n; j++) { for (int k = 0; k < n; k++) { cur_matrix[k] += matrix[j][k]; } MaxSum = max(MaxSum, find_max()); } } cout << MaxSum << endl; } int main(void) { while (cin >> n) { for (int i = 0; i < n; i++) { for (int j = 0; j ...

UVA113  :   https://uva.onlinejudge.org/external/1/113.pdf /*math*/ /* based on : k n = p (k n ) (1/n) = p (1/n) k = p (1/n) /* k = pow(p,1/n) */ reference */ #include <iostream> #include <stdlib.h> #include <math.h> using namespace std; int main() { // your code goes here double n, p,k; while (cin>>n>>p) { k = pow(p, 1.0 / n); /* Most probably the default number digit after decimal is 6, so in UVA compiler your ans.                     for 2 16 would be 4.000000 and not 4.                                                                                                     reference */...

UVA 10474 :  https://uva.onlinejudge.org/external/104/10474.pdf /*sort*/ #include <iostream> #include<string.h> #include <algorithm> using namespace std; int main() { // your code goes here int n=0,q=0; int count = 1; while(cin>>n>>q) { if(n==0&&q==0)break; cout<<"CASE# "<<count<<":"<<endl; int num[n];memset(num,0,sizeof(num)); int inquire[q];memset(inquire,0,sizeof(q)); for(int i=0;i<n;i++) { cin>>num[i]; } sort(num,num+n); for(int in=0;in<q;in++) { cin>>inquire[in]; } for(int j =0;j<q;j++) { int check =0; for(int k=0;k<n&&check==0;k++) { if(num[k]==inquire[j]) { check =1; cout<<inquire[j]<<" found at "<<++k<<endl; } } if(check==0) cout<<inquire[j]<<" not found...

UVA 102 :  https://uva.onlinejudge.org/external/1/102.pdf /*simulation*/ #include <iostream> #include<string.h> using namespace std; int main() { const string ans[6]={"BCG","BGC","CBG","CGB","GBC","GCB"}; int num[9],cal[6]; memset(num,0,sizeof(num)); memset(cal,0,sizeof(cal)); while(cin>>num[0]) { for(int c=1;c<9;c++) cin>>num[c]; //only move need to calculate cal[0]=num[3]+num[6]+num[2]+num[8]+num[1]+num[4];//bcg cal[1]=num[3]+num[6]+num[1]+num[7]+num[2]+num[5];//bgc cal[2]=num[5]+num[8]+num[0]+num[6]+num[1]+num[4];//cbg cal[3]=num[5]+num[8]+num[1]+num[7]+num[0]+num[3];//cgb cal[4]=num[4]+num[7]+num[0]+num[6]+num[2]+num[5];//gbc cal[5]=num[4]+num[7]+num[2]+num[8]+num[0]+num[3];//gcb int min=0, _ans=0,m =0; min=cal[0]; for(;m<6;m++) { if(min>cal[m]){ min=cal[m]; _ans=m; } } cout<<ans[_ans]<<" "...

UVA 10300  :  https://uva.onlinejudge.org/external/103/10300.pdf /*math*/ #include <iostream> using namespace std; int main() { // your code goes here int count =0; cin>>count; while(count--) { int farmer =0,total=0; cin>>farmer; for(int i=0;i<farmer;i++) { int area =0,num=0,level=0; cin>>area>>num>>level; total+=area*level; } cout<<total<<endl; } return 0; }

UVA 11727 :  https://uva.onlinejudge.org/external/117/11727.pdf /*sort*/ #include <iostream> #include <stdlib.h> #include <string.h> #include <algorithm> using namespace std; int main() { // your code goes here int count = 0,Case =1; cin >> count; while (count--) { int salary[3]; memset(salary, 0, sizeof(salary)); for (int i = 0; i < 3; i++) cin >> salary[i]; sort(salary, salary + 3); cout <<"Case "<<Case<<": "<< salary[1] << endl; Case++; } return 0; }

UVA 10082 : https://uva.onlinejudge.org/external/100/10082.pdf /*simulation*/ #include <iostream> #include <stdlib.h> #include <string.h> #include <sstream> #include <string> #define size_of_array(ary) sizeof(ary) / sizeof(ary[0]) using namespace std; int main() { // your code goes here string str; const char storage[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"; while (getline(cin,str)){ for (int i = 0; i < str.length(); i++) { if (str[i]==' ') cout << " "; for (int j = 0; j < size_of_array(storage); j++) { if (str[i] == storage[j]) cout << storage[j - 1]; } } cout << endl; } system("PAUSE"); }

UVA10405 URL :  http://uva.onlinejudge.org/external/104/10405.pdf 基礎LCS ------------------------------------------------------------------------------------------ import java.util.Scanner; public class UVA10405 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(sc.hasNext()) { String s1 = sc.nextLine(); String s2 = sc.nextLine(); char[] c1 = new char[s1.length()+1]; char[] c2 = new char[s2.length()+1]; for(int s =1;s<s1.length()+1;s++) { c1[s] = s1.charAt(s-1); } for(int s =1;s<s2.length()+1;s++) { c2[s] = s2.charAt(s-1); } int matrix[][] = new int[1001][1001]; int max = 0; for(int n = 1;n<s1.length()+1;n++) { for(int m = 1;m<s2.length()+1;m++) { if(c1[n] == c2[m]) matrix[n][m] = matrix[n-1][m-1] + 1; else matrix[n][m] = Math.max(matrix[n...

UVA534 URL: http://uva.onlinejudge.org/external/5/534.pdf -------------------------------------------------------------- 大意 : 有隻青蛙想從A點跳到B點，問你A到B的路徑裡，最短的路徑裡權重最大的邊(最小生成樹的瓶頸) EX: path(start,2) = 3,path(2,3) =4 ,path(4,end) = 1 ,the distance is 4. -------------------------------------------------------------- import java.util.*; class undirected_graph { static double map[][] = new double[205][205]; static boolean visit[] = new boolean[205]; static double cost[] = new double[205]; static int parent[] = new int[205]; static int n = 0; void create_map(){ Scanner sc = new Scanner(System.in); int count =1; while(sc.hasNext()) { double map[][] = new double[205][205]; boolean visit[] = new boolean[205]; double cost[] = new double[205]; int parent[] = new int[205]; n = sc.nextInt(); sc.nextLine(); if(n==0)break; System.out.println("Scenario #"+count); int x_l[] = new int[n]; int y...

Link :  http://uva.onlinejudge.org/external/115/11538.pdf ----------------------------------------------------------------------------------------------------------- Hint :         ※ 假設M邊較長               總共有三種方法可以攻擊敵人，行、列、斜向。         行與列：         黑后有M*N種位置選擇，選擇M以後白后就只剩下N-1個位置，得 M*N(N-1)，etc         得 N*M(M-1)，整合為 N*M( N + M - 2) 。         斜向：最長的斜向一共有 M - N + 1條，假定最長斜向為 n length         可得1,2,3......n-1,nnnnnn(M-N+1條) ,n-1,n-2,.......1，令 1 ~ n-1 加總為 i         故可得一共有 2 *  ∑ i ( i-1 ) (1<= i <=n-1) 條斜向(不含最長)         最長的斜向：N ( N-1 ) ( M - N + 1) ，選了一個N即剩下N-1種選擇         斜向總數：( 2 *  ∑ i ( i - 1 ) (1<= i <=n-1) + N( N - 1 ) ( M - N + 1) )  * 2 (正反斜)                   ...

  Excuses, Excuses!   Judge Ito is having a problem with people subpoenaed for jury duty giving rather lame excuses in order to avoid serving. In order to reduce the amount of time required listening to goofy excuses, Judge Ito has asked that you write a program that will search for a list of keywords in a list of excuses identifying lame excuses. Keywords can be matched in an excuse regardless of case. Input Input to your program will consist of multiple sets of data. Line 1 of each set will contain exactly two integers. The first number (   ) defines the number of keywords to be used in the search. The second number (   ) defines the number of excuses in the set to be searched. Lines 2 through  K +1 each contain exactly one keyword. Lines  K +2 through  K +1+ E  each contain exactly one excuse. All keywords in the keyword list will contain only contiguous lower case alphabetic characters of length  L  ( ...

  Ugly Numbers   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. Write a program to find and print the 1500'th ugly number. Input and Output There is no input to this program. Output should consist of a single line as shown below, with <number> replaced by the number computed. Sample output The 1500'th ugly number is <number>. ----------------------------------------------------------------------------------------------------- import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; public class Main{ public static void main(String[] args) { PriorityQueue<Long> pq = new PriorityQueue<Long>(); int[] store = new int[] { 2, 3, 5 }; Set st = new HashSet(); pq.offer((long) 1); st.add(1); for (int i = 1;; i++) { long num = pq.peek(); ...

The Blocks Problem   Background   Many areas of Computer Science use simple, abstract domains for both analytical and empirical studies. For example, an early AI study of planning and robotics (STRIPS) used a block world in which a robot arm performed tasks involving the manipulation of blocks. In this problem you will model a simple block world under certain rules and constraints. Rather than determine how to achieve a specified state, you will ``program'' a robotic arm to respond to a limited set of commands. The Problem   The problem is to parse a series of commands that instruct a robot arm in how to manipulate blocks that lie on a flat table. Initially there are  n  blocks on the table (numbered from 0 to  n -1) with block  b i  adjacent to block  b i +1  for all   as shown in the diagram below:   Figure:  Initial Blocks World The valid commands for the robot arm that manipulates blocks are:...

Problem B: Andy's First Dictionary Time limit: 3 seconds Andy, 8, has a dream - he wants to produce his very own dictionary. This is not an easy task for him, as the number of words that he knows is, well, not quite enough. Instead of thinking up all the words himself, he has a briliant idea. From his bookshelf he would pick one of his favourite story books, from which he would copy out all the distinct words. By arranging the words in alphabetical order, he is done! Of course, it is a really time-consuming job, and this is where a computer program is helpful. You are asked to write a program that lists all the different words in the input text. In this problem, a word is defined as a consecutive sequence of alphabets, in upper and/or lower case. Words with only one letter are also to be considered. Furthermore, your program must be CaSe InSeNsItIvE. For example, words like "Apple", "apple" or "APPLE" must be considered the same. Input The...

 The Dole Queue   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 ...

Hangman Judge   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: The contestant tries to solve to puzzle by guessing one letter at a time. Every time a guess is correct, all the characters in the word that match the guess will be ``turned over.'' For example, if your guess is ``o'' and the word is ``book'', then both ``o''s in the solution will be counted as ``solved.'' Every time a wrong guess is made, a stroke will be added to the drawing of a hangman, which needs 7 strokes to complete. Each unique wrong guess only counts against the contestant once. ______ | | | O | /|\ | | | / \ __|_ | |______ |_________| If the drawing of the hangman is completed before the contestant has succ...