9 July 2011 Comments Off

Some ACM-ICPC Problems & Solutions (ACM-ICPC: 2011 in Fukuoka)

Problems here: http://icpc2011.ait.kyushu-u.ac.jp/icpc2011/contest/all_en.html

Solution (s) by Tatuyan:

Problem-A: I did not have a hard time so much because this problem looks like my self-made problem. When we made the problem, I checked all number with for-loop. This time, I prepare prime table with using Eratosthenes’s sifter.
Problem-B: There is Kind Problem at UTPC2011(University of Tokyo Programming Contest 2011). I solved with making stack.
Problem-C: I solved this problem with back track. In Japan domestic contest, We usually see problem which require counting cells,do we?
Problems are here.

C Source.

A.Chebyshev’s Theorem.
#include<stdio.h>
#include<stdlib.h>
#define NUM 123456
unsigned int list[NUM];
void makelist(void);
int main(void){
unsigned int i,j,n,ans;
makelist();
while(scanf("%u",&n) && n){
ans=0;
if(n==1){
puts("1");
continue;
}else if(n==2){
puts("1");
continue;
}
for(i=((n+1)>>1);i<n;i++) if(list[i]!=0) ans++;
printf("%u\n",ans);
}
return 0;
}
void makelist(void){
unsigned int i,j;
for(i=0;i<NUM;i++) list[i]=(i<<1)+1;
for(i=1;i*i<NUM;i++){
if(list[i]==0) continue;
for(j=(i*(i+1))<<1;j<NUM;j+=(i<<1)+1) list[j]=0;
}
}

B. The Balance of the World

#include<stdio.h>
#include<string.h>
#define NUM 100
int main(void){
int brac[NUM+1],now,i,flg;
char str[NUM+2];
while(fgets(str,sizeof(str),stdin) && strcmp(str,".\n")){
memset(brac,0,sizeof(brac));
flg=0;
now=0;
for(i=0;i<strlen(str)-1;i++){
if(str[i]=='('){
brac[now]=1;
now++;
}else if(str[i]=='['){
brac[now]=2;
now++;
}else if(str[i]==')'){
if(now==0 || brac[now-1]!=1){
flg=1;
break;
}
now--;
}else if(str[i]==']'){
if(now==0 || brac[now-1]!=2){
flg=1;
break;
}
now--;
}
}
if(now!=0) flg=1;
if(flg==0) puts("yes");
else puts("no");
}
return 0;
}

C.Identically Colored Panels Connection

#include<stdio.h>
#include<stdlib.h>
typedef struct{
int col;
int check;
} panels;
int max,h,w,c,num;
void getmax(panels **panel,int color,int nest,int n);
void change(panels **panel,int color,int i,int j);
void countnum(panels **panel,int i,int j);
int main(void){
panels **panel;
int i,j,colors;
while(scanf("%d %d %d",&h,&w,&c) && h && w && c){
panel=(panels **)calloc(h,sizeof(panels *));
for(i=0;i<h;i++) *(panel+i)=(panels *)calloc(w,sizeof(panels *));
for(i=0;i<h;i++){
for(j=0;j<w;j++){
scanf("%d",&colors);
(*(panel+i)+j)->col=colors;
(*(panel+i)+j)->check=0;
}
}
max=0;
for(i=0;i<6;i++) getmax(panel,i+1,0,0);
printf("%d\n",max);
for(i=0;i<h;i++) free(*(panel+i));
free(panel);
}
return 0;
}
void getmax(panels **panel,int color,int nest,int n){
panels **tmp;
int i,j,k;
if(nest==4 && color!=c) return;
tmp=(panels **)calloc(h,sizeof(panels *));
for(i=0;i<h;i++) *(tmp+i)=(panels *)calloc(w,sizeof(panels *));
for(i=0;i<h;i++){
for(j=0;j<w;j++){
(*(tmp+i)+j)->col=(*(panel+i)+j)->col;
(*(tmp+i)+j)->check=0;
}
}
change(tmp,color,0,0);
num=0;
countnum(tmp,0,0);
if(max<num) max=num;
if(nest==4 || num==n){
for(i=0;i<h;i++) free(*(tmp+i));
free(tmp);
return;
}
for(i=0;i<6;i++) getmax(tmp,i+1,nest+1,1);
for(i=0;i<h;i++) free(*(tmp+i));
free(tmp);
}
void change(panels **panel,int color,int i,int j){
(*(panel+i)+j)->check=1;
if(i>0 && (*(panel+i)+j)->col==(*(panel+i-1)+j)->col && (*(panel+i-1)+j)->check==0) change(panel,color,i-1,j);
if(i<h-1 && (*(panel+i)+j)->col==(*(panel+i+1)+j)->col && (*(panel+i+1)+j)->check==0) change(panel,color,i+1,j);
if(j>0 && (*(panel+i)+j)->col==(*(panel+i)+j-1)->col && (*(panel+i)+j-1)->check==0) change(panel,color,i,j-1);
if(j<w-1 && (*(panel+i)+j)->col==(*(panel+i)+j+1)->col && (*(panel+i)+j+1)->check==0) change(panel,color,i,j+1);
(*(panel+i)+j)->col=color;
}
void countnum(panels **panel,int i,int j){
(*(panel+i)+j)->check=2;
if(i>0 && (*(panel+i)+j)->col==(*(panel+i-1)+j)->col && (*(panel+i-1)+j)->check!=2) countnum(panel,i-1,j);
if(i<h-1 && (*(panel+i)+j)->col==(*(panel+i+1)+j)->col && (*(panel+i+1)+j)->check!=2) countnum(panel,i+1,j);
if(j>0 && (*(panel+i)+j)->col==(*(panel+i)+j-1)->col && (*(panel+i)+j-1)->check!=2) countnum(panel,i,j-1);
if(j<w-1 && (*(panel+i)+j)->col==(*(panel+i)+j+1)->col && (*(panel+i)+j+1)->check!=2) countnum(panel,i,j+1);
num++;
}
21 May 2011 Comments Off

ACM UVa Problems Category

New Comer

★ 100 The 3n + 1 problem
★ 10189 Minesweeper
★ 10137 The Trip
★ 706 LCD Display
★ 10267 Graphical Editor
★★ 10033 Interpreter
★ 10196 Check The Check
★ 10142 Australian Voting

Data Structure

★ 10038 Jolly Jumpers
★★ 10315 Poker Hands
★★ 10050 Hartals
★★   843 Crypt Kicker
★ 10205 Stack ‘em Up
★★ 10044 Erdos Numbers
★ 10258 Contest Scoreboard
★★★ 10149 Yahtzee

String

★ 10082 WERTYU
★★ 10010 Where’s Waldorf?
★ 10252 Common Permutation
★★ 850 Crypt Kicker II
★ 10188 Automated Judge Script
★★ 10132 File Fragmentation
★★★ 10150 Doublets
★★ 848 Fmt

Sorting

★ 10041 Vito’s Family
★★   120 Stacks of Flapjacks
★★★ 10037 Bridge
★ 10191 Longest Nap
★★ 10026 Shoemaker’s Problem
★★ 10138 CDVII
★★ 10152 ShellSort
★ 10194 Football (aka Soccer)

Arithmetic and Algerba

★ 10035 Primary Arithmetic
★ 10018 Reverse and Add
★   701 The Archeologists’ Dilemma
★★ 10127 Ones
★★★   847 A Multiplication Game
★ 10105 Polynomial Coefficients
★ 10077 The Stern-Brocot Number System
★★★★ 10202 Pairsumonious Numbers

Combinations

★ 10183 How Many Fibs?
★★ 10213 How Many Pieces of Land ?
★★ 10198 Counting
★★ 10157 Expressions
★★ 10247 Complete Tree Labeling
★★ 10254 The Priest Mathematician
★★ 10049 Self-describing Sequence
★★   846 Steps

Number Theory

★ 10110 Light, More Light
★★ 10006 Carmichael Numbers
★ 10104 Euclid Problem
★★ 10139 Factovisors
★★ 10168 Summation of Four Primes
★ 10042 Smith Numbers
★ 10090 Marbles
★★ 10089 Repackaging

Backtracking

★★ 861 Little Bishops
★★★ 10181 15-Puzzle Problem
★★ 10128 Queue
★★ 10160 Servicing Stations
★★ 10032 Tug of War
★★ 10001 Garden of Eden
★★★ 704 Colour Hash
★★★ 10270 Bigger Square Please…

Graph Traversal

★ 10004 Bicoloring
★★ 10067 Playing with Wheels
★★★ 10099 The Tourist Guide
★★   705 Slash Maze
★★★ 10029 Edit Step Ladders
★★★ 10051 Tower of Cubes
★★★ 10187 From Dusk Till Dawn
★★★ 10276 Hanoi Tower Troubles Again!

Graph Algorithm

★★ 10034 Freckles
★★★ 10054 The Necklace
★★ 10278 Fire Station
★★★ 10039 Railroads
★★★ 10158 War
★★★ 10199 Tourist Guide
★★★★ 10249 The Grand Dinner
★★★ 10092 The Problem with the Problem Setter

Dynamic Programming

★★ 10131 Is Bigger Smarter?
★★★ 10069 Distinct Subsequences
★★★ 10154 Weights and Measures
★★★   116 Unidirectional TSP
★★ 10003 Cutting Sticks
★★★ 10261 Ferry Loading
★★★ 10271 Chopsticks
★★★ 10201 Adventures in Moving – Part IV

Grid

★ 10161 Ant on a Chessboard
★★★ 10047 The Monocycle
★★ 10159 Star
★★ 10182 Bee Maja
★★★   707 Robbery
★★ 10177 (2/3/4)-D Sqr/Rects/Cubes/Boxes?
★★ 10233 Dermuba Triangle
★★★ 10075 Airlines

Geometry

★ 10310 Dog and Gopher
★★ 10180 Rope Crisis in Ropeland!
★★ 10195 The Knights Of The Round Table
★★★ 10136 Chocolate Chip Cookies
★★ 10167 Birthday Cake
★★ 10215 The Largest/Smallest Box …
★★★ 10209 Is This Integration ?
★★★ 10012 How Big Is It?

Computational Geometry

★★ 10135 Herding Frosh
★★ 10245 The Closest Pair Problem
★★★ 10043 Chainsaw Massacre
★★★ 10084 Hotter Colder
★★★ 10065 Useless Tile Packers
★★   849 Radar Tracking
★★★ 10088 Trees on My Island
★★★★ 10117 Nice Milk

Source: http://www.cnblogs.com/penseur/archive/2011/03/10/1979491.html

13 January 2011 Comments Off

Easy ACM UVa problems

Problem No Problem Name
100 The 3n+1 problem
102 Ecological bin packing
113 Power of cryptography
136 Ugly numbers
190 Circle through three points
264 Count on Cantor
272 TEX qoutes
299 Train swapping
305 Joseph
353 Pesky Palindromes
369 Combinations
382 Perfection
401 Palindromes
406 Prime cuts
408 Uniform generator
424 Integer inquery
444 Encoder and decoder
458 The decoder
490 Rotating sequences
492 Pig latin
495 Fibonacci freeze
499 What’s the frequency, Kenneth?
530 Binomial showdown
541 Error correction
543 Goldbach’s conjecture
579 Clock Hands
591 Box of Bricks
609 DNA sorting
623 500!
686 Goldbach’s conjecture (II)
694 The Collatz sequence
713 Adding reversed numbers
729 The Hamming distance problem
834 Continued Fractions
10008 What’s Cryptanalysis?
10013 Super long sums
10018 Reverse and Add
10019 Funny Encryption Method
10035 Primary Arithmetic
10055 Hashmat the brave warrior
10062 Tell me the frequencies!
10070 Leap Year or Not Leap Year
10082 WERTYU
10101 Bangla numbers
10107 What is the median?
10110 Light more light
10161 Ant on a Chessboard
10200 Prime time
10235 Simply Emirp
10242 Fourth point!!
10252 Common Permutation
10282 Babel fish
10286 Trouble with a pentagon
10300 Ecological Premium
10302 Summation of Polynomials
10323 Factorial! You Must be Kidding!!!
10324 Zeros and Ones
10327 Flip sort
10370 Above average
10409 Die game
10420 List of conquests
10424 Love calculator
10432 Polygon inside a circle
10473 Simple base conversion
10515 Powers et al.
10611 The playboy chimp
10696 f91
10700 Camel trading
Tags: , , ,
16 October 2010 Comments Off

ACM UVA OJ Problems Category by Difficulty Level

Difficulty- 0.5

272 TEX Quotes 0.5 Ad Hoc
http://acm.uva.es/p/v2/272.html
458 The Decoder 0.5 Ad Hoc
http://acm.uva.es/p/v4/458.html
10071 Back to High School Physics 0.5 Math (Physics)
http://acm.uva.es/p/v100/10071.html
10300 Ecological Premium 0.5 Ad Hoc
http://acm.uva.es/p/v103/10300.html
10302 Summation of Polynomials 0.5 Math
http://acm.uva.es/p/v103/10302.html

Difficulty-1.0

299 Train Swapping 1.0 Sorting
http://acm.uva.es/p/v2/299.html
10023 Square root 1.0 Ad Hoc
http://acm.uva.es/p/v100/10023.html
10696 f91 1.0 Ad Hoc
http://acm.uva.es/p/v106/10696.html
10783 Odd Sum 1.0 Math
http://acm.uva.es/p/v107/10783.html

Difficulty-1.5

146 ID Codes 1.5 Ad Hoc
http://acm.uva.es/p/v1/146.html
541 Error Correction 1.5 Ad Hoc
http://acm.uva.es/p/v5/541.html
591 Box of Bricks 1.5 Ad Hoc
http://acm.uva.es/p/v5/591.html
10286 Trouble with a Pentagon 1.5 Math (Trigonometry)
http://acm.uva.es/p/v102/10286.html
10327 Flip Sort 1.5 Sorting (Bubble Sort)
http://acm.uva.es/p/v103/10327.html
10370 Above Average 1.5 Math
http://acm.uva.es/p/v103/10370.html
10656 Maximum Sum (II) 1.5 Ad Hoc
http://acm.uva.es/p/v106/10656.html
[...]