1021 Emacs-like Editor
解法
テキストエディタって結構設計が大変なのですね。
簡単な問題とみて甘く見てました。
改行だけしかない空行、先頭行、末尾行などの取り扱いが意外と大変な問題でした。
一晩色々なパタンを考えてから提出、ポカミスを2度修正して合格となりました。
入力データの文章の最終行は\nがないようです。
後答えの最終行に\nをつけないと不正解になります。
#include<stdio.h>
#include<string>
#include<iostream>
#define ss std::string
//グローバル変数まとめ
unsigned int nowP;//カーソルの現在位置、nowP文字目
ss text;//テキスト 効率悪いが実装が楽な方を選ぶ
ss buffer;//カットコピーした文字を覚えておく
//グローバル変数終わり
void a(){
//先頭文字に移動
if(nowP==0)return;
while(0<nowP){
nowP--;
if(text[nowP]=='\n') break;
}
if(text[nowP]=='\n')nowP++;
}
void e(){
//行末へ移動する操作
while(nowP<text.size()){
if(text[nowP]=='\n')break;
nowP++;
}
}
void p(){
//上の行の先頭文字へ移動
a();
if(nowP==0) return ;
nowP--;
if(nowP==0)return;
a();
}
void n(){
//下に行があればカーソルを下の行の先頭文字に
e();
if(nowP<text.size()){
nowP++;
}else{
a();//次の行がないので先頭文字へ移動する
}
}
void f(){
//カーソルを一つ右に移動する
if(nowP<text.size()){
nowP++;
}
}
void b(){
//カーソルを一つ左に移動する
if(nowP>0){
nowP--;
}
}
void d(){
//一文字削除する
if(nowP<text.size()){
text.erase(nowP,1);
}
}
void k(){
//バッファに記録する、カーソルが行末を指してない場合末尾の改行はどうなるのだろうか,Bufferに保存する?
if(nowP==text.size())return;
if(text[nowP]=='\n'){
d();
buffer="\n";
}else{
int oldP=nowP;
e();
buffer=text.substr(oldP,nowP-oldP);
text.erase(oldP,nowP-oldP);
nowP=oldP;
}
}
void y(){
if(buffer.size()==0)return;
text.insert(nowP,buffer);
nowP+=buffer.size();
}
int main(){
text="";
nowP=0;
ss line;
while(1){
std::getline(std::cin, line);
if(line=="END_OF_TEXT")break;
text+=line+"\n";
}
text.erase(text.size()-1,1);
char com;
while(1){
std::cin>>com;
switch(com){
case 'a':
a();
break;
case 'e':
e();
break;
case 'p':
p();
break;
case 'n':
n();
break;
case 'f':
f();
break;
case 'b':
b();
break;
case 'd':
d();
break;
case 'k':
k();
break;
case 'y':
y();
break;
}
if(com=='-')break;
}
std::cout<<text<<"\n";
}
1023 Amazing Graze
#include<stdio.h>
#include<vector>
struct point{
int x,y;
};
std::vector<point> bPoints[202][202];
point aPoints[100002];
bool setData(){
point p,bp,ap;
int an,bn,r,size=50;
scanf("%d %d %d",&an,&bn,&r);
if(an==0 && bn==0) return false;
for(int x=0;x<202;x++){
for(int y=0;y<202;y++){
bPoints[x][y].clear();
}
}
r=16*r*r;
for(int i=0;i<an;i++){
scanf("%d %d",&aPoints[i].x,&aPoints[i].y);
}
for(int i=0;i<bn;i++){
scanf("%d %d",&p.x,&p.y);
bPoints[p.x/size][p.y/size].push_back(p);
}
int lx,rx,uy,dy,len,ans=0;
for(int i=0;i<an;i++){
ap=aPoints[i];
lx=ap.x/size-1;
lx=lx<0?0:lx;
rx=ap.x/size+1;
dy=ap.y/size-1;
dy=dy<0?0:dy;
uy=ap.y/size+1;
for(int y=dy;y<=uy;y++){
for(int x=lx;x<=rx;x++){
for(int no=0;no<bPoints[x][y].size();no++){
bp=bPoints[x][y][no];
len=(ap.x-bp.x)*(ap.x-bp.x)+(ap.y-bp.y)*(ap.y-bp.y);
if(len<=r){
ans++;
}
}
}
}
}
printf("%d\n",ans);
return true;
}
int main(){
while(setData()){
}
}
1027 A Piece of Cake
#include<stdio.h>
bool setData(){
int n,sum=0,c;
scanf("%d",&n);
if(n==0)return false;
for(int i=0;i<((n-1)*n)/2;i++){
scanf("%d",&c);
sum+=c;
}
printf("%d\n",sum/(n-1));
return true;
}
int main(){
while(setData()){
}
}
1028 ICPC: Ideal Coin Payment and Change
解法
大きな金額のコインから使いできるだけPに近いP近辺の値段を深さ優先探索で求めて解きます。
WAが怖かったのでコインの使用枚数を表すupやdownを広めに取っていますが多分もう少し狭い範囲で計算しても大丈夫でしょう。
コインの枚数制限を忘れないように注意さえすれば簡単な問題です。
#include<stdio.h>
const int coins[]={500,100,50,10,5,1};
const int type=6;
int ans;
int coinCounts[type];
int turisen(int r){
int re=0;
for(int i=0;i<type;i++){
re+=r/coins[i];
r%=coins[i];
}
return re;
}
void saiki(int deep,int r,int cc){
//rが金額残余。ccがコインカウント
if(deep==type&&r<=0){
int t=cc+turisen(-r);
ans=(ans>t)?t:ans;
return;
}else if(deep==type){
return;
}
if(cc>ans) return;
int t=r/coins[deep];
int up =t+5;//大きなコインでできるだけPに近い金額を作ろうとする処理
int down=t-4;
up= up<5?5:up;
up= up>coinCounts[deep]?coinCounts[deep]:up;
down=down>coinCounts[deep]?coinCounts[deep]:down;
down=down<0?0:down;
for(int i=down;i<=up;i++){
saiki(deep+1,r-i*coins[deep],cc+i);//downからupの枚数のコインを試しに使ってみる
}
}
void setData(int p){
ans=1000000000;
for(int i=type-1;i>=0;i--){
scanf("%d",&coinCounts[i]);
}
saiki(0,p,0);
printf("%d\n",ans);
}
int main(){
int p;
while(1){
scanf("%d",&p);
if(p==0) break;
setData(p);
}
}
1029 Traffic Analysis
#include<stdio.h>
#include <algorithm>
#include <vector>
bool setData(){
int n,m,t;
std::vector<int> times;
scanf("%d %d",&n,&m);
if(n+m==0) return false;
for(int i=0;i<n+m;i++){
scanf("%d",&t);
times.push_back(t);
}
std::sort(times.begin(),times.end());
int old=0,ans=0,temp;
for(int i=0;i<times.size();i++){
temp=times[i]-old;
ans=ans>temp?ans:temp;
old=times[i];
}
printf("%d\n",ans);
return true;
}
int main(){
while(setData()){
}
}
1030 Cubes Without Holes
#include<stdio.h>
#include<set>
struct hole{
int xyz[3];
bool operator<(const hole& h)const{
if(xyz[0]!=h.xyz[0]) return xyz[0]<h.xyz[0];
if(xyz[1]!=h.xyz[1]) return xyz[1]<h.xyz[1];
if(xyz[2]!=h.xyz[2]) return xyz[2]<h.xyz[2];
return false;
}
};
bool setData(){
int n,m;
scanf("%d %d",&n,&m);
if(n+m==0)return false;
std::set<hole> holes;
hole h;
char xyz[3];
int p1,p2,p3;
for(int i=0;i<m;i++){
scanf("%s %d %d",xyz,&p1,&p2);
if(xyz[0]=='x'&&xyz[1]=='y'){
h.xyz[0]=p1;
h.xyz[1]=p2;
p3=2;
}else if(xyz[0]=='x'&&xyz[1]=='z'){
h.xyz[0]=p1;
h.xyz[2]=p2;
p3=1;
}else{
h.xyz[1]=p1;
h.xyz[2]=p2;
p3=0;
}
for(int i=1;i<=n;i++){
h.xyz[p3]=i;
holes.insert(h);
}
}
printf("%d\n",n*n*n-holes.size());
return true;
}
int main(){
while(setData()){
}
}
最終更新:2011年12月21日 18:26