| 04.07.2008 09:38:01 |
Автор:  Arman Suleimenov |
Сегодня, наконец, взялся (а точнее продолжил после трехмесячного перерыва) за решение задач из USACO, кстати говоря, кузницу таких "красных" кодеров из США, как neal_wu,
msg555, Minilek и многих других. Только что сдал с 3-ей попытки достаточно простую (скорее на внимательный implementation) задачу Castle из раздела 2.1. Алгоритм стандартный - раскраска графа.
Цитата
The castle floorplan is divided into M (wide) by N (1 <=M,N<=50) square modules. Each such module can have between zero and four walls. Castles always have walls on their "outer edges" to keep out the wind and rain.
Consider this annotated floorplan of a castle:
# = Wall -,| = No wall
-> = Points to the wall to remove to
make the largest possible new room
By way of example, this castle sits on a 7 x 4 base. A "room" includes any set of connected "squares" in the floor plan. This floorplan contains five rooms (whose sizes are 9, 7, 3, 1, and 8 in no particular order).
Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall.
The castle always has at least two rooms and always has a wall that can be removed.
PROGRAM NAME: castle
INPUT FORMAT
The map is stored in the form of numbers, one number for each module, M numbers on each of N lines to describe the floorplan. The input order corresponds to the numbering in the example diagram above.
Each module number tells how many of the four walls exist and is the sum of up to four integers:
1: wall to the west
2: wall to the north
4: wall to the east
8: wall to the south
Inner walls are defined twice; a wall to the south in module 1,1 is also indicated as a wall to the north in module 2,1.
Line 1: Two space-separated integers: M and N
Line 2..: M x N integers, several per line.
SAMPLE INPUT (file castle.in)
7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
OUTPUT FORMAT
The output contains several lines:
Line 1: The number of rooms the castle has.
Line 2: The size of the largest room
Line 3: The size of the largest room creatable by removing one wall
Line 4: The single wall to remove to make the largest room possible
Choose the optimal wall to remove from the set of optimal walls by choosing the wall farthest to the west (and then, if still tied, farthest to the south). Name that wall by naming the module that borders it on either the west or south, along with a direction of N or E giving the location of the wall with respect to the module.
SAMPLE OUTPUT (file castle.out)
5
9
16
4 1 E
|
Вот мое решение (c постфактум-модификациями  ).
Код
/*
ID: arman_s1
PROG: castle
LANG: C++
*/
#include <algorithm>
#include <fstream>
#include <iostream>
#define For(i,b) for(int i = 0; i < (int)b; ++i)
#define db(x) cout << #x << " = " << x << endl
using namespace std;
const int M=55;
int a[M][M];
bool v[M][M];
int n,m;
int cnt;
int cur;
int maxi;
bool inline valid(int i, int j)
{
return i>=0 && i<n && j>=0 && j<m && (!v[i][j]);
}
void dfs(int i, int j)
{
v[i][j]=1;
cur++;
if(!(a[i][j]&1<<0)) if(valid(i,j-1)) dfs(i,j-1);
if(!(a[i][j]&1<<1)) if(valid(i-1,j)) dfs(i-1,j);
if(!(a[i][j]&1<<2)) if(valid(i,j+1)) dfs(i,j+1);
if(!(a[i][j]&1<<3)) if(valid(i+1,j)) dfs(i+1,j);
}
int main ()
{
ofstream fout ("castle.out");
ifstream fin ("castle.in");
fin>>m>>n;
For(i,n) For(j,m) fin>>a[i][j];
cnt=0;
cur=0;
maxi=INT_MIN;
memset(v,0,sizeof(v));
For(i,n) For(j,m)
if(!v[i][j])
{
cur=0;
++cnt;
dfs(i,j);
maxi=max(maxi,cur);
}
fout<<cnt<<endl; // the # of rooms
fout<<maxi<<endl; // the size of the largest room
cur=0;
maxi=INT_MIN;
int row=INT_MIN,col=INT_MAX;
char dir;
For(i,n) For(j,m)
{
memset(v,0,sizeof(v));
v[i][j]=1;
cur=0;
if(a[i][j]&1<<2) if(valid(i,j+1)) dfs(i,j+1);
dfs(i,j);
if(maxi<cur){maxi=cur;row=i;col=j;dir='E';}
else if(maxi==cur)
{
if(j<col)
{
row=i;
col=j;
dir='E';
}
else if(j==col)
{
if(i>row)
{
row=i;
col=j;
dir='E';
}
}
}
memset(v,0,sizeof(v));
v[i][j]=1;
cur=0;
if(a[i][j]&1<<1) if(valid(i-1,j)) dfs(i-1,j);
dfs(i,j);
if(maxi<cur){maxi=cur;row=i;col=j;dir='N';}
else if(maxi==cur)
{
if(j<col)
{
row=i;
col=j;
dir='N';
}
else if(j==col)
{
if(i>=row)
{
row=i;
col=j;
dir='N';
}
}
}
} // of For
fout<<maxi<<endl; // max room after deleting the wall
fout<<(row+1)<<" "<<(col+1)<<" "<<dir<<endl; // the room to remove
fout.close();
return 0;
}
|
|
|
| 03.11.2007 00:42:16 |
Автор: Arman Suleimenov |
Отличная новость пришла из Орландо, где последние 3 дня проходил TopCoder Collegiate Challenge 2007, фактически студенческое первенство мира по программированию. В финале алгоритмического турнира победу, как и год назад, одержал выпусник нынешнего года механико-математического факультета МГУ Петр Митричев. Таким образом, Петр вернул себе первое место в рейтинге TopCoder, которое несколько недель принадлежало китайскому кодеру TianCheng Lou (handle - ACRush). Я следил за ходом финала онлайн и, безусловно, болел за Петра. И он победил! Мои ему искренние поздравления!
Итоги финала:
1. Petr (Петр Митричев, Россия, МГУ)
2. krijgertje (Erik-Jan Krijgsman, Нидерланды, University of Twente)
3. gawry (Pawel Gawrychowski, Польша, University of Wroclaw)
4. Vitaliy (Виталий Вальтман, Россия, СПбГУ)
5. ACRush (TianCheng Lou, Китай, TsingHua University)
6. xhl_kogitsune (Hiroshige Hayashizaki, Япония, University of Tokyo)
7. cyfra (Marcin Michalski, Польша, Warsaw University)
8. domino (Mircea Bogdan Pasoi, Румыния, University of Bucharest)
|
|
| 24.10.2007 07:51:42 |
Автор: Arman Suleimenov |
Today we had a TopCoder College Tour Single Round Match at the university. I was extremely nervous constantly keeping it in mind for more than a month. Of course, I was looking forward to win, but at the same time I prepared to accept defeat. And here it comes. The 23rd of October... TopCoder College Tour... In 5 minutes I smoothly went through the first problem (it was extremely easy, I should have solved it in one minute ), then got stuck with the Medium problem, after 10 minutes of struggle I decided to go straight to the 1000-point problem and spent all the time left (about an hour) working on it. Unfortunately I didn't succeed, because under the psychological pressure and the time constraint could not write the sub-program that determines whether the line segment intersects the rectangle . It's quite shameful to say...
During the challenge phase I successfully cracked one student's code for the first problem. This added 50 more points to my score. The round is over and regardless of the fact that I'm very dissatisfied with my today's performance I ended up winning the event.
|
|
| 10.10.2007 02:05:09 |
Автор: Arman Suleimenov |
|
|
|
| 28.09.2007 05:12:14 |
Автор: Arman Suleimenov |
Yesterday from 8:00 to 9:30 pm the qualifying contest to select members of OU ACM team was held in Stocker Engineering building. The problem set consisted of 5 problems, 10 points for each. I ended up solving up all five in 1 hour 28 minutes and got the first place. The problems were not difficult, neither of them required sophisticated algorithm, for me it was just the question of setting up the input & output (usual routine at ACMs) and coding up the processing part. The following problems were offered:
Train Swapping
Perfection
Error Correction
Back to High School Physics
3n+1
In the morning the same day I had another Single Round Match in Topcoder and didn't do well, seemingly to save my luck for the evening event
|
|
| 20.05.2007 18:09:39 |
Автор: Arman Suleimenov |
Here is the problem:
Цитата
Among the large Wisconsin cattle ranchers, it is customary to brand cows with serial numbers to please the Accounting Department. The cow hands don't appreciate the advantage of this filing system, though, and wish to call the members of their herd by a pleasing name rather than saying, "C'mon, #4734, get along."
Help the poor cowhands out by writing a program that will translate the brand serial number of a cow into possible names uniquely associated with that serial number. Since the cow hands all have cellular saddle phones these days, use the standard Touch-Tone® telephone keypad mapping to get from numbers to letters (except for "Q" and "Z"):
2: A,B,C 5: J,K,L 8: T,U,V
3: D,E,F 6: M,N,O 9: W,X,Y
4: G,H,I 7: P,R,S
Acceptable names for cattle are provided to you in a file named "dict.txt", which contains a list of fewer than 5,000 acceptable cattle names (all letters capitalized). Take a cow's brand number and report which of all the possible words to which that number maps are in the given dictionary which is supplied as dict.txt in the grading environment (and is sorted into ascending order).
For instance, the brand number 4734 produces all the following names:
GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI
As it happens, the only one of these 81 names that is in the list of valid names is "GREG".
Write a program that is given the brand number of a cow and prints all the valid names that can be generated from that brand number or ``NONE'' if there are no valid names. Serial numbers can be as many as a dozen digits long.
PROGRAM NAME: namenum
INPUT FORMAT
A single line with a number from 1 through 12 digits in length.
SAMPLE INPUT (file namenum.in)
4734
OUTPUT FORMAT
A list of valid names that can be generated from the input, one per line, in ascending alphabetical order.
SAMPLE OUTPUT (file namenum.out)
GREG
|
Solution
The key to make this problem easy was to use the map container from STL library. I declared one instance of map< string, vector<string> >, where the key of the "associative array" is the serial number and the value is the vector of all the names from dictionary corresponding to that serial. Here is the code itself:
Код
/*
ID: arman_s1
PROG: namenum
LANG: C++
*/
#include <fstream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#define For(i,n) for(int i = 0; i < (int)n; ++i)
#define All(t) t.begin(),t.end()
#define Sort(a) sort(All(a))
#define VS vector<string>
using namespace std;
string gen(const string& myword);
int main ()
{
ofstream fout ("namenum.out");
ifstream fin ("namenum.in");
ifstream tin("dict.txt");
string num;
fin >> num;
string myword;
map< string,vector<string> > cnt;
string g;
tin >> myword;
while(!tin.eof())
{
g = gen(myword);
cnt[g].push_back(myword);
tin >> myword;
}
if(cnt[num].empty())
fout << "NONE" << endl;
else
{
Sort(cnt[num]);
For(i,cnt[num].size())
fout << cnt[num][i] << endl;
}
return 0;
}
string gen(const string& myword)
{
string t = myword;
ostringstream os;
For(i,t.size())
{
switch(t[i])
{
case 'A': case 'B': case 'C': os << 2; break;
case 'D': case 'E': case 'F': os << 3; break;
case 'G': case 'H': case 'I': os << 4; break;
case 'J': case 'K': case 'L': os << 5; break;
case 'M': case 'N': case 'O': os << 6; break;
case 'P': case 'R': case 'S': os << 7; break;
case 'T': case 'U': case 'V': os << 8; break;
case 'W': case 'X': case 'Y': os << 9; break;
}
}
string res = os.str();
return res;
}
|
|
|
| 19.05.2007 04:44:48 |
Автор: Arman Suleimenov |
The problem
Цитата
A square pattern of size N x N (1 <= N <= 10) black and white square tiles is transformed into another square pattern. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations:
* #1: 90 Degree Rotation: The pattern was rotated clockwise 90 degrees.
* #2: 180 Degree Rotation: The pattern was rotated clockwise 180 degrees.
* #3: 270 Degree Rotation: The pattern was rotated clockwise 270 degrees.
* #4: Reflection: The pattern was reflected horizontally (turned into a mirror image of itself by reflecting around a vertical line in the middle of the image).
* #5: Combination: The pattern was reflected horizontally and then subjected to one of the rotations (#1-#3).
* #6: No Change: The original pattern was not changed.
* #7: Invalid Transformation: The new pattern was not obtained by any of the above methods.
In the case that more than one transform could have been used, choose the one with the minimum number above.
PROGRAM NAME: transform
INPUT FORMAT
Line 1: A single integer, N
Line 2..N+1: N lines of N characters (each either `@' or `-'); this is the square before transformation
Line N+2..2*N+1: N lines of N characters (each either `@' or `-'); this is the square after transformation
SAMPLE INPUT (file transform.in)
3
@-@
---
@@-
@-@
@--
--@
OUTPUT FORMAT
A single line containing the the number from 1 through 7 (described above) that categorizes the transformation required to change from the `before' representation to the `after' representation.
SAMPLE OUTPUT (file transform.out)
1
|
Arman's solution
Код
/*
ID: arman_s1
PROG: transform
LANG: C++
*/
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>
#define For(i,n) for(int i = 0; i < (int)n; ++i)
#define VS vector<string>
using namespace std;
VS rot90 (vector<string> v);
VS ref(VS v);
VS rot180(vector<string> v);
VS rot270(vector<string> v);
int main ()
{
ofstream fout("transform.out");
ifstream fin("transform.in");
int n;
char c;
fin >> n;
vector<string> v(n), t(n);
For(i,n)
For(j,n)
{
fin >> c;
v[i] += c;
}
For(i,n)
For(j,n)
{
fin >> c;
t[i] += c;
}
VS trans1 = rot90(v), trans2 = rot90(trans1), trans3 = rot90(trans2);
VS trans4 = ref(v);
VS trans51 = rot90(ref(v)), trans52 = rot180(ref(v)), trans53 = rot270(ref(v));
if (t==trans1) fout << "1";
else if (t == trans2) fout << "2";
else if (t == trans3) fout << "3";
else if (t == trans4) fout << "4";
else if (t == trans51 || t == trans52 || t == trans53) fout << "5";
else if (t == v) fout << "6";
else fout << "7";
fout << endl;
return 0;
}
VS rot90(vector<string> v)
{
VS tr(v.size());
int k = 0;
For(i,v.size())
{
for(int j = (int)(v.size() - 1); j >= 0; --j)
{
tr[k] += v[j][i];
}
k++;
}
return tr;
}
VS rot180(vector<string> v)
{
return rot90(rot90(v));
}
VS rot270(vector<string> v)
{
return rot90(rot90(rot90(v)));
}
VS ref(VS v)
{
VS tr(v.size());
int k = 0;
for(int i = (int)(v.size() - 1); i >= 0; --i)
{
For(j,v.size())
{
tr[k] += v[j][i];
k++;
}
k = 0;
}
return tr;
}
|
|
|
| 19.05.2007 04:38:08 |
Автор: Arman Suleimenov |
Continue publishing the problems from USA Computing Olympiad online judge.
Problem statement
ЦитатаYou have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random.
The beads considered first and second in the text that follows have been marked in the picture.
The configuration in Figure A may be represented as a string of b's and r's, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .
Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).
Determine the point where the necklace should be broken so that the most number of beads can be collected.
Example
For example, for the necklace in Figure A, 8 beads can be collected, with the breaking point either between bead 9 and bead 10 or else between bead 24 and bead 25.
In some necklaces, white beads had been included as shown in Figure B above. When collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color. The string that represents this configuration will include the three symbols r, b and w.
Write a program to determine the largest number of beads that can be collected from a supplied necklace.
PROGRAM NAME: beads
INPUT FORMAT
Line 1: N, the number of beads
Line 2: a string of N characters, each of which is r, b, or w
SAMPLE INPUT (file beads.in)
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
OUTPUT FORMAT
A single line containing the maximum of number of beads that can be collected from the supplied necklace.
SAMPLE OUTPUT (file beads.out)
11
OUTPUT EXPLANATION
Consider two copies of the beads (kind of like being able to runaround the ends). The string of 11 is marked.
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
******
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
***** |
My straight-forward solution
Код
/*
ID: arman_s1
PROG: beads
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#define For(i,n) for(int i = 0; i < n; ++i)
using namespace std;
void inc(int& i, int n);
void dec(int& i, int n);
void funl(int l, int i, int& curl, string s, bool& flag, bool& b, bool& r);
void funr(int ri, int i, int& curr, string s, bool& flag, bool& b, bool& r);
int main() {
ofstream fout ("beads.out");
ifstream fin ("beads.in");
string s;
int n, curr = 0, curl = 0, max = 0;
bool r = false, b = false;
bool flag;
fin >> n;
fin >> s;
bool allthesame = false;
char c = s[0];
for(int i = 1; i < n; ++i)
{
if (s[i] == c)
allthesame = true;
else
{
allthesame = false;
break;
}
}
if (allthesame)
{
max = n;
fout << max << endl;
}
else {
For(i,n)
{
int tmp;
for(int l = i - 1; l >= 0 && l != i; dec(l,n))
{
funl(l,i,curl,s,flag,b,r);
if (flag)
continue;
else
break;
}
b = r = false;
if (i == 0)
{
for(int ri = 0; ri < n; ++ri)
{
funr(ri,i,curr,s,flag,b,r);
if (flag)
continue;
else
break;
}
}
else
{
for(int ri = i; ri != (i - 1); inc(ri, n))
{
funr(ri,i,curr,s,flag,b,r);
if (flag)
continue;
else
break;
}
}
if (max < (curl + curr))
max = curl + curr;
b = r = false;
curl = 0;
curr = 0;
} // For(i,n)
fout << max << endl;
}// !allthesame
return 0;
}
void inc(int& i, int n)
{
if ((i + 1) >= n)
i = 0;
else
i++;
}
void dec(int& i, int n)
{
if ((i - 1) < 0)
i = n - 1;
else
--i;
}
void funl(int l, int i, int& curl, string s, bool& flag, bool& b, bool& r)
{
//cout << "funl " << s[l] << " " << curl << endl;
if (l == (i-1))
{
b = r = true;
}
if (s[l] == 'w'){
curl++;
if (l != (i-1)){
if (b)
r = false;
else if®
b = false;
}
flag = true;
return;
}
if(s[l] == 'r' && r){
curl++;
r = true;
b = false;
flag = true;
return;
}
else if(s[l] != 'b')
{
flag = false;
return;
}
if(s[l] == 'b' && b){
curl++;
b = true;
r = false;
flag = true;
return;
}
else if(s[l] != 'r')
{
flag = false;
return;
}
flag = true;
}
void funr(int ri, int i, int& curr, string s, bool& flag, bool& b, bool& r)
{
//cout << "funr " << s[ri] << " " << curr << endl;
if (ri==i)
{
b = true;
r = true;
}
if (s[ri] == 'w'){
curr++;
if (ri != i){
if (b)
r = false;
else if®
b = false;
}
flag = true;
return;
}
if(s[ri] == 'r' && r){
curr++;
r = true;
b = false;
flag = true;
return;
}
else if(s[ri] != 'b')
{
flag = false;
return;
}
if(s[ri] == 'b' && b){
curr++;
b = true;
r = false;
flag = true;
return;
}
else if(s[ri] != 'r')
{
flag = false;
return;
}
flag = true;
}
|
|
|
| 19.05.2007 04:33:40 |
Автор: Arman Suleimenov |
The problem from USA Computing Olympiad.
The problem statement
ЦитатаMilking Cows
Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. The second farmer begins at time 700 and ends at time 1200. The third farmer begins at time 1500 and ends at time 2100. The longest continuous time during which at least one farmer was milking a cow was 900 seconds (from 300 to 1200). The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 minus 1200).
Your job is to write a program that will examine a list of beginning and ending times for N (1 <= N <= 5000) farmers milking N cows and compute (in seconds):
* The longest time interval at least one cow was milked.
* The longest time interval (after milking starts) during which no cows were being milked.
PROGRAM NAME: milk2
INPUT FORMAT
Line 1: The single integer
Lines 2..N+1: Two non-negative integers less than 1000000, the starting and ending time in seconds after 0500
SAMPLE INPUT (file milk2.in)
3
300 1000
700 1200
1500 2100
OUTPUT FORMAT
A single line with two integers that represent the longest continuous time of milking and the longest idle time.
SAMPLE OUTPUT (file milk2.out)
900 300 |
My solution
Код
/*
ID: arman_s1
PROG: milk2
LANG: C++
*/
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#define For(i,n) for(int i = 0; i < (int)n; ++i)
using namespace std;
class Interval
{
public:
Interval(){}
Interval(int a, int b):start(a),end(b){}
int get_s(){return start;}
int get_e(){return end;}
bool operator < (const Interval& rhs) const
{
return (start < rhs.start);
}
void set_s(int s){start = s;}
void set_e(int e){end = e;}
void set(int a, int b) {start = a; end = b;}
friend ostream& operator << (ostream& os, const Interval& rhs)
{
os << rhs.start << " " << rhs.end;
return os;
}
const Interval& operator = (const Interval& rhs)
{
start = rhs.start;
end = rhs.end;
return *this;
}
bool over(const Interval& rhs)
{
return (rhs.start <= end);
}
int dif()
{
return end-start;
}
private:
int start;
int end;
};
int main ()
{
ofstream fout ("milk2.out");
ifstream fin ("milk2.in");
vector<Interval> v;
int n, a, b;
fin >> n;
Interval tmp;
for(u_int i = 1; i <= n; ++i)
{
fin >> a;
fin >> b;
tmp.set(a,b);
v.push_back(tmp);
}
sort(v.begin(), v.end());
int best = 0;
int idle = 0;
Interval cur = v[0];
if(n==1)
{
best = cur.dif();
idle = 0;
}
else {
for(int i = 1; i < (int)v.size(); ++i)
{
if (cur.over(v[i]))
{
if (cur.get_e() < v[i].get_e())
cur.set_e(v[i].get_e());
}
else
{
if (best < cur.dif()) best = cur.dif();
cur = v[i];
}
}
if (best < cur.dif()) best = cur.dif();
cur = v[0];
for(int i = 1; i < (int)v.size(); ++i)
{
if (cur.over(v[i]))
{
if (cur.get_e() < v[i].get_e())
cur.set_e(v[i].get_e());
}
else
{
if (idle < (v[i].get_s()-cur.get_e()))
idle = v[i].get_s()-cur.get_e();
cur = v[i];
}
//cout << "idle: " << idle << " cur: " << cur<< endl;
}
}
fout << best << " " << idle << endl;
return 0;
}
|
|
|
| 14.04.2007 08:08:59 |
Автор: Arman Suleimenov |
Вот новая задача.
Условие задачи: из списка неповторяющихся городов в файле input.txt составить список максимальной длины, в котором последняя буква города 1 - первая буква города 2, последняя буква города 2 - первая буква города 3, ..., последняя буква города (N - 1) - первая буква города N, где N - кол-во городов в списке максимальной длины.
Вот мое решение (C++):
Код
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cctype>
using namespace std;
void rec(string tmp, u_int index);
vector<string> cities, maxchain, curchain;
vector<bool> flags;
int main ()
{
ifstream fin;
string s;
fin.open("input.txt");
fin >> s;
while(!fin.eof())
{
cities.push_back(s);
fin >> s;
}
for (u_int i = 0; i < cities.size(); ++i)
flags.push_back(false);
for (u_int i = 0; i < cities.size(); ++i)
{
rec(cities[i], i);
curchain.clear();
}
for (u_int i = 0; i < maxchain.size(); ++i)
cout << maxchain[i] << endl;
fin.close();
return EXIT_SUCCESS;
}
void rec(string tmp, u_int index)
{
for (u_int i = 0; i < curchain.size(); ++i)
{
if (tmp == curchain[i])
return;
}
if (curchain.empty())
curchain.push_back(tmp);
else if ( tolower(tmp[0]) == curchain.back()[curchain.back().length() - 1] )
curchain.push_back(tmp);
flags[index] = true;
for (u_int i = 0; i < cities.size(); ++i)
{
if ( (flags[i] == false) && (tmp[tmp.length() - 1] == tolower(cities[i][0])) )
rec(cities[i], i);
}
if (curchain.size() > maxchain.size())
{
maxchain = curchain;
curchain.pop_back();
}
flags[index] = false;
}
|
Вот содержание тестового файла input.txt с данным набором городов:
Цитата
Mumbai
Karachi
Delhi
SaoPaulo
Moscow
Seoul
Istanbul
Shanghai
Lagos
Mexico
Jakarta
Tokyo
NewYork
Cairo
London
Beijing
Bogota
Tehran
Lima
HongKong
Dhaka
Bangkok
Lahore
RiodeJaneiro
Kinshasa
Baghdad
Bangalore
Tianjin
Yangon
Santiago
Kolkata
Wuhan
Chennai
Singapore
Riyadh
Guangzhou
SaintPetersburg
Chongqing
Shenyang
Chittagong
Alexandria
LosAngeles
Ahmedabad
Hyderabad
Busan
Yokohama
Ankara
Abidjan
HoChiMinh
Berlin
|
Вот ответ, выдаваемый программой:
Цитата
Mumbai
Istanbul
Lagos
Seoul
London
NewYork
Kinshasa
Alexandria
Ahmedabad
Dhaka
Ankara
Abidjan
|
P/S: Решение достаточно корявое, хотя на работу над кодом я трудился в свободное от учебы время со вторника. Хотел опубликовать решение вчера, но решил проверить на одном специально созданном тесте и оказалось, что решение неправильное. Сегодня поработал еще немного, теперь вроде версия рабочая. Хотя все же есть сомнения, наверняка, найдется тест, который может завалить программу. Буду рад услышать конструктивные замечания и корректировки.
|
|
| 20.03.2007 07:56:04 |
Автор: Arman Suleimenov |
Только что для развлечения нашел количество счастливых трамвайных билетов. Пара строк на C++:
Код
#include <iostream>
using namespace std;
int main()
{
int a[28]={}, cnt = 0;
for (int i = 0; i <= 999; ++i)
{
int tmp = i;
for (int j = 1; j <= 3; ++j) {
cnt += tmp % 10;
tmp /= 10;
}
a[cnt]++;
cnt = 0;
}
int newcnt = 0;
for (int i = 0; i < 28; ++i)
newcnt += a[i] * a[i];
cout << newcnt;
return 0;
}
|
А вот само условие задачи:
Цитата| Определите количество шестизначных "счастливых" трамвайных билетов. Счастливым называется такой билет, у которого сумма первых трех цифр совпадает с суммой трех последних. |
|
|
| 17.03.2007 06:57:08 |
Автор: Arman Suleimenov |
Today I have registered in Timus Online Judge - the online judging system with the largest archive of programming problems in Russia. I chose C++ as the language of preference, I don't know Java and due to lack of practice almost forgot Pascal.
I have already started having solved 2 fairly easy problems: 1000, 1001. The first one was just designed to learn how to submit problems to the server, the second is more about the memory economizing rather than the algorithm.
|
|
| 26.01.2007 21:01:54 |
Автор: Arman Suleimenov |
I don't want to say that you can not solve any existent problem in terms of one particular language, but there are programming languages whose intrinsic nature allows you to solve some types of problems simply and elegantly. If you are a carpenter, and the only tool you have is a hammer, then every problem you encounter becomes a nail. If you know only one way, you are bound to be limited in your creative freedom. The more methods you know, the more methods you discard as inappropriate in some cases, the more methods you apply as extremely efficient in your particular situation, the more masterful, the more experienced you are. Here is the list of major programming languages with a short description and the sphere of their potential application.
I have (some*) experience in 4 languages only: Pascal, Microsoft Assembler 4.0, C++ and Scheme. What languages do you prefer and "speak"?
*The only thing I have real experience in is inexperience. The only thing I know is my ignorance.
|
|
| 05.01.2007 07:02:47 |
Автор: Arman Suleimenov |
Сегодня приступил к изучению языка Scheme, функционального минималистического языка программирования, разработанного в MIT.
Как и в других диалектах Lisp, синтаксис Scheme очень прост и компактен.
Вот простые примеры некоторых выражений на этом новом для меня языке (как видно из них, синтаксические элементы языка группируются с помощью скобок):
(+ n m) ; возвращает сумму n и m
(define double (lambda (n) (+ n n))) ; декларирует функцию, которой передается один аргумент и которая возвращает его в "удвоенном" виде
(define absolute
(lambda (n)
(if (< n 0)
(- n)
n))) ; если n<0, то возвращаем -n, в противном случае возвращаем n
Что ж, путь длиной в 10000 ли начинается с одного шага. Который, думаю, еще сделать только предстоит...
|
|
|
|
