街の数が20以下なのでワーシャル-フロイド法で
/************************************
* 2012/07/05 *
* AOJ Volume1 0117 *
* A reward for a Carpenter *
* crane *
*************************************/
#include <iostream>
#include <cstdio>
using namespace std;
#define MAX_N 1000
#define MAX_M 21
int field[MAX_M][MAX_M];
int n,m;
void warshall_floyd();
int main(){
int a,b,c,d;
cin >> n >> m;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
field[i][j]=MAX_N;
for(int i=0; i<m; i++){
scanf("%d,%d,%d,%d",&a,&b,&c,&d);
field[a][b] = c;
field[b][a] = d;
}
warshall_floyd();
int x1,x2,y1,y2;
scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2);
cout << y1-field[x1][x2]-field[x2][x1]-y2 << endl;
}
void warshall_floyd(){
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
field[i][j]=min(field[i][j],field[i][k]+field[k][j]);
}
2012年7月5日木曜日
2012年7月4日水曜日
AOJ Volume1 0112: A Milk Shop
昇順にソートした状態が最も待ち時間が少なくなる。
「お客さんは 10,000 人以下で 1 人あたりに要する時間は 60 分以下とします。」
とあるのでlong long int で対応。
/******************************
* 2012/07/04 *
* AOJ_Volume1_0112 *
* A_Milk_Shop *
* crane *
*******************************/
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 100001
int a[MAX_N];
int main(){
int n;
while(cin >> n,n){
for(int i=0; i<n; i++)
cin >> a[i];
sort(a, a+n);//昇順にソート
long long int sum=0, tmp=0;
for(int i=0; i<n; i++){
sum += tmp;
tmp += a[i];
}
cout << sum << endl;
}
return 0;
}
「お客さんは 10,000 人以下で 1 人あたりに要する時間は 60 分以下とします。」
とあるのでlong long int で対応。
/******************************
* 2012/07/04 *
* AOJ_Volume1_0112 *
* A_Milk_Shop *
* crane *
*******************************/
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 100001
int a[MAX_N];
int main(){
int n;
while(cin >> n,n){
for(int i=0; i<n; i++)
cin >> a[i];
sort(a, a+n);//昇順にソート
long long int sum=0, tmp=0;
for(int i=0; i<n; i++){
sum += tmp;
tmp += a[i];
}
cout << sum << endl;
}
return 0;
}
AOJ Volume1 0104:Magical Tiles
/*********************
* 2012/07/04 *
* AOJ_Volume1_0104 *
* Magical_Tiles *
* crane *
**********************/
#include<iostream>
using namespace std;
#define MAX_N 101
char field[MAX_N][MAX_N];
bool f[MAX_N][MAX_N];
int main(){
int h,w; //縦,横
while(cin >> h >> w, (h||w)){
//field make
for(int i=0; i<h; i++)
for(int j=0; j<w; j++){
cin >> field[i][j];
f[i][j] = false;
}
int x = 0, y = 0;
while(1){
if(field[y][x] == '.' || f[y][x] == true) break;
f[y][x] = true;
switch(field[y][x]){
case '>':
x++;
break;
case '<':
x--;
break;
case '^':
y--;
break;
case 'v':
y++;
break;
}
}
if(f[y][x]) cout << "LOOP" << endl;
else cout << x << " " << y << endl;
}
return 0;
}
* 2012/07/04 *
* AOJ_Volume1_0104 *
* Magical_Tiles *
* crane *
**********************/
#include<iostream>
using namespace std;
#define MAX_N 101
char field[MAX_N][MAX_N];
bool f[MAX_N][MAX_N];
int main(){
int h,w; //縦,横
while(cin >> h >> w, (h||w)){
//field make
for(int i=0; i<h; i++)
for(int j=0; j<w; j++){
cin >> field[i][j];
f[i][j] = false;
}
int x = 0, y = 0;
while(1){
if(field[y][x] == '.' || f[y][x] == true) break;
f[y][x] = true;
switch(field[y][x]){
case '>':
x++;
break;
case '<':
x--;
break;
case '^':
y--;
break;
case 'v':
y++;
break;
}
}
if(f[y][x]) cout << "LOOP" << endl;
else cout << x << " " << y << endl;
}
return 0;
}
AOJ Volume1 0101:Aizu PR
サンプルを実行すると、データセット数が入力された後に入力が勝手に一つ入る現象が発生。対策としてcin.get()を入れた。
/****************************************************************************************
* 2012/04/29
* AIZU ONLINE JUDGE volume1_0101 *
* AIZU PR *
* HoshinoをHoshinaに置き換えて出力する *
* 英文は1000文字以下 *
* *
* Input *
* 最初にデータセット数nが与えられる。続いてn行の英文が与えられる。 *
* 各データセットは１行に英文が与えられる。英文は半角英数字・記号を含む。 *
* Output *
* 各データセットについて”Hoshino”を”Hoshina”に変換した英文(半角)を１行に出力する。*
*****************************************************************************************/
/***********************************************
****************Time limit:1sec*****************
****************Memory limit:32768KB************
************************************************/
#include<iostream>
#include<string>
int main(){
//入力1 データセット数nを受け取る
int n; //データセット数受け取り用変数
std::cin >> n; std::cin.get();
for(int i=0; i<n; i++){
std::string input; //データセット
std::getline(std::cin, input); //データ入力
int input_size = input.length();//データ長
for(int i=0; i<input_size; i++){
if(input.substr(i,7) == "Hoshino"){
input.replace(i,7,"Hoshina");
}
}
std::cout << input << std::endl;
}
return 0;
}
/****************************************************************************************
* 2012/04/29
* AIZU ONLINE JUDGE volume1_0101 *
* AIZU PR *
* HoshinoをHoshinaに置き換えて出力する *
* 英文は1000文字以下 *
* *
* Input *
* 最初にデータセット数nが与えられる。続いてn行の英文が与えられる。 *
* 各データセットは１行に英文が与えられる。英文は半角英数字・記号を含む。 *
* Output *
* 各データセットについて”Hoshino”を”Hoshina”に変換した英文(半角)を１行に出力する。*
*****************************************************************************************/
/***********************************************
****************Time limit:1sec*****************
****************Memory limit:32768KB************
************************************************/
#include<iostream>
#include<string>
int main(){
//入力1 データセット数nを受け取る
int n; //データセット数受け取り用変数
std::cin >> n; std::cin.get();
for(int i=0; i<n; i++){
std::string input; //データセット
std::getline(std::cin, input); //データ入力
int input_size = input.length();//データ長
for(int i=0; i<input_size; i++){
if(input.substr(i,7) == "Hoshino"){
input.replace(i,7,"Hoshina");
}
}
std::cout << input << std::endl;
}
return 0;
}
AOJ Volume1 0100 Sale Result
大きな値を扱うためlong long intで対応。
/**************************
* 2012/07/04 *
* AOJ Volume1 0100 *
* Sale Result *
* crane *
***************************/
#include<iostream>
#include<vector>
#include<map>
using namespace std;
vector<int> num;
map<int, long long int> data;
int main(){
int n;
while(cin >> n,n){
num.clear();
data.clear();
for(int i=0; i<n; i++){
long long int dn, dp, dc;
cin >> dn >> dp >> dc;
if(!data[dn]) num.push_back(dn);
data[dn] += dp * dc;
}
bool frag = true;
for(int i=0; i<num.size(); i++){
if(1000000 <= data[num[i]] ){
frag = false;
cout <<num[i] << endl;
}
}
if(frag) cout << "NA" << endl;
}
return 0;
}
/**************************
* 2012/07/04 *
* AOJ Volume1 0100 *
* Sale Result *
* crane *
***************************/
#include<iostream>
#include<vector>
#include<map>
using namespace std;
vector<int> num;
map<int, long long int> data;
int main(){
int n;
while(cin >> n,n){
num.clear();
data.clear();
for(int i=0; i<n; i++){
long long int dn, dp, dc;
cin >> dn >> dp >> dc;
if(!data[dn]) num.push_back(dn);
data[dn] += dp * dc;
}
bool frag = true;
for(int i=0; i<num.size(); i++){
if(1000000 <= data[num[i]] ){
frag = false;
cout <<num[i] << endl;
}
}
if(frag) cout << "NA" << endl;
}
return 0;
}
AOJ Volume11 1155: How can I satisfy thee? Let me count the ways...
問題文に
<formula> ::= 0 | 1 | 2 | P | Q | R |
-<formula> | (<formula>*<formula>) | (<formula>+<formula>)
とあったので一文字目にP Q Rはないと考えてcase文で一文字ずつ処理。
/****************************************************
* 2012/06/30 *
* AOJ Volume11 1155 *
* How can I satisfy thee? Let me count the ways... *
* crane *
*****************************************************/
/*------------------------------------------------------------------------*
<formula> ::= 0 | 1 | 2 | P | Q | R |
-<formula> | (<formula>*<formula>) | (<formula>+<formula>)
->一文字目にP Q Rはなし
*--------------------------------------------------------------------------*/
#include<iostream>
#include<string>
using namespace std;
#define MAX_L 80
string in;
int pos;
int Vp,Vq,Vr;
int formula();
int main(){
while(cin >> in){
if(in == ".") break;
int result = 0; //結果の初期化
for(int p=0; p<3; p++)
for(int q=0; q<3; q++)
for(int r=0; r<3; r++){
Vp=p; Vq=q; Vr=r;
pos = 0;
if(formula()==2) result++;
}
cout << result << endl;
}
return 0;
}
int formula(){
char c = in.at(pos); //一文字読む
pos++;
if(isdigit(c)) //数字なら数値を返す
return c-'0';
switch(c){
case 'P':
return Vp;
break;
case 'Q':
return Vq;
break;
case 'R':
return Vr;
break;
case '-':
return 2-formula();
break;
case '(':
int a = formula(); //（）中の演算子左側
int tmp=0; //演算子用フラグ
if(in.at(pos) == '*')
tmp = 1;
pos++;
int b = formula(); //() 中の演算子右側
pos++; //)を飛ばすためpos++
/* * だった場合*/
if(tmp == 1){
return min(a, b);
}else{
/* + だった場合*/
return max(a, b);
}
break;
}
}
<formula> ::= 0 | 1 | 2 | P | Q | R |
-<formula> | (<formula>*<formula>) | (<formula>+<formula>)
とあったので一文字目にP Q Rはないと考えてcase文で一文字ずつ処理。
/****************************************************
* 2012/06/30 *
* AOJ Volume11 1155 *
* How can I satisfy thee? Let me count the ways... *
* crane *
*****************************************************/
/*------------------------------------------------------------------------*
<formula> ::= 0 | 1 | 2 | P | Q | R |
-<formula> | (<formula>*<formula>) | (<formula>+<formula>)
->一文字目にP Q Rはなし
*--------------------------------------------------------------------------*/
#include<iostream>
#include<string>
using namespace std;
#define MAX_L 80
string in;
int pos;
int Vp,Vq,Vr;
int formula();
int main(){
while(cin >> in){
if(in == ".") break;
int result = 0; //結果の初期化
for(int p=0; p<3; p++)
for(int q=0; q<3; q++)
for(int r=0; r<3; r++){
Vp=p; Vq=q; Vr=r;
pos = 0;
if(formula()==2) result++;
}
cout << result << endl;
}
return 0;
}
int formula(){
char c = in.at(pos); //一文字読む
pos++;
if(isdigit(c)) //数字なら数値を返す
return c-'0';
switch(c){
case 'P':
return Vp;
break;
case 'Q':
return Vq;
break;
case 'R':
return Vr;
break;
case '-':
return 2-formula();
break;
case '(':
int a = formula(); //（）中の演算子左側
int tmp=0; //演算子用フラグ
if(in.at(pos) == '*')
tmp = 1;
pos++;
int b = formula(); //() 中の演算子右側
pos++; //)を飛ばすためpos++
/* * だった場合*/
if(tmp == 1){
return min(a, b);
}else{
/* + だった場合*/
return max(a, b);
}
break;
}
}
AOJ Volume11 1159: Next Mayor
/************************************
* 2012/06/18 *
* AOJ Volume11 1159 *
* Next Mayor *
* crane *
*************************************/
#include<iostream>
#define MAX_N 50
int n, p;
int candidate[MAX_N]; //それぞれの候補者の持つ石の数
int main(){
while(std::cin >> n >> p, (n||p)){ //n->候補者の数 p->小石の総数
int turn = 0; //候補者ターン
for(int i=0; i<n; i++) candidate[i] = 0; //候補者も持石個数初期化
int w = p;
while(1){
if(w==0){
w += candidate[turn];
candidate[turn] = 0;
}else{
w--;
candidate[turn]++;
if(candidate[turn] == p)
break;
}
turn = (turn+1) % n;//次の人へ
}
std::cout << turn << std::endl;
}
return 0;
}
* 2012/06/18 *
* AOJ Volume11 1159 *
* Next Mayor *
* crane *
*************************************/
#include<iostream>
#define MAX_N 50
int n, p;
int candidate[MAX_N]; //それぞれの候補者の持つ石の数
int main(){
while(std::cin >> n >> p, (n||p)){ //n->候補者の数 p->小石の総数
int turn = 0; //候補者ターン
for(int i=0; i<n; i++) candidate[i] = 0; //候補者も持石個数初期化
int w = p;
while(1){
if(w==0){
w += candidate[turn];
candidate[turn] = 0;
}else{
w--;
candidate[turn]++;
if(candidate[turn] == p)
break;
}
turn = (turn+1) % n;//次の人へ
}
std::cout << turn << std::endl;
}
return 0;
}
AOJ Volume11 1160: How Many Islands
dfsを使用
/********************************************
* 2012/06/18 *
* AOJ Volume11 1160 *
* How Many Islands? *
*********************************************/
//--------------------------------------------------//
// 海->0 陸->1 //
//--------------------------------------------------//
#include<iostream>
#define MAX_N 50
int field[MAX_N][MAX_N];
/* w:横 h:縦*/
int w, h;
void dfs(int x, int y); //dfs処理用
int main(){
while(std::cin >> w >> h, w, h){ //地図情報入力
int result = 0; //結果個数初期化
/*地図作成*/
for(int i=0; i<h; i++) //縦
for(int j=0; j<w; j++) //横
std::cin >> field[i][j];
/*島破壊*/
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
if(field[i][j] == 1){
/*島があったら*/
dfs(j,i);
result++;
}
}
}
std::cout << result << std::endl;//結果出力
}
return 0;
}
void dfs(int x, int y){
int a[8] = {-1, -1, -1, 0, 1, 1, 1, 0};//横
int b[8] = {-1, 0, 1, 1, 1, 0,-1,-1};//縦
//今いるところを0にする
field[y][x] = 0;
/* 移動する８近傍をループ*/
for(int i=0; i<8; i++){
//移動先 (nx, ny)
int nx = x + a[i], ny = y + b[i];
//移動先が地図上か判定 & 移動先が島かどうか判定
if( 0<=nx && nx<w && 0<=ny && ny<h && field[ny][nx]==1)
dfs(nx, ny);
}
}
/********************************************
* 2012/06/18 *
* AOJ Volume11 1160 *
* How Many Islands? *
*********************************************/
//--------------------------------------------------//
// 海->0 陸->1 //
//--------------------------------------------------//
#include<iostream>
#define MAX_N 50
int field[MAX_N][MAX_N];
/* w:横 h:縦*/
int w, h;
void dfs(int x, int y); //dfs処理用
int main(){
while(std::cin >> w >> h, w, h){ //地図情報入力
int result = 0; //結果個数初期化
/*地図作成*/
for(int i=0; i<h; i++) //縦
for(int j=0; j<w; j++) //横
std::cin >> field[i][j];
/*島破壊*/
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
if(field[i][j] == 1){
/*島があったら*/
dfs(j,i);
result++;
}
}
}
std::cout << result << std::endl;//結果出力
}
return 0;
}
void dfs(int x, int y){
int a[8] = {-1, -1, -1, 0, 1, 1, 1, 0};//横
int b[8] = {-1, 0, 1, 1, 1, 0,-1,-1};//縦
//今いるところを0にする
field[y][x] = 0;
/* 移動する８近傍をループ*/
for(int i=0; i<8; i++){
//移動先 (nx, ny)
int nx = x + a[i], ny = y + b[i];
//移動先が地図上か判定 & 移動先が島かどうか判定
if( 0<=nx && nx<w && 0<=ny && ny<h && field[ny][nx]==1)
dfs(nx, ny);
}
}
AOJ Volume11 1165: Pablo Squarson's Headache
/************************************
* 2012/06/26 *
* AOJ Volume11 1165 *
* Pablo Squarson's Headache *
* wrote crane *
*************************************/
#include<iostream>
using namespace std;
#define MAX_N 200
int field[MAX_N][2]; //[][0]->x [][1]->y
int dx[] = {-1, 0, 1, 0};
int dy[] = { 0, 1, 0, -1};
int main(){
int n;
while(cin >> n,n){
int x=0;int y=0;
int ni, di;
field[0][0] = 0;
field[0][1] = 0;
for(int i=1; i<n; i++){
cin >> ni >> di;
field[i][0] = field[ni][0] + dx[di];
field[i][1] = field[ni][1] + dy[di];
}
int xmin=10000, xmax=-10000;
int ymin=10000, ymax=-10000;
for(int i=0; i<n; i++){
if(field[i][0] < xmin) xmin =field[i][0];
if(field[i][0] > xmax) xmax =field[i][0];
if(field[i][1] < ymin) ymin =field[i][1];
if(field[i][1] > ymax) ymax =field[i][1];
}
x = xmax - xmin + 1;
y = ymax - ymin + 1;
cout << x << " "<< y << endl;;
}
return 0;
}
* 2012/06/26 *
* AOJ Volume11 1165 *
* Pablo Squarson's Headache *
* wrote crane *
*************************************/
#include<iostream>
using namespace std;
#define MAX_N 200
int field[MAX_N][2]; //[][0]->x [][1]->y
int dx[] = {-1, 0, 1, 0};
int dy[] = { 0, 1, 0, -1};
int main(){
int n;
while(cin >> n,n){
int x=0;int y=0;
int ni, di;
field[0][0] = 0;
field[0][1] = 0;
for(int i=1; i<n; i++){
cin >> ni >> di;
field[i][0] = field[ni][0] + dx[di];
field[i][1] = field[ni][1] + dy[di];
}
int xmin=10000, xmax=-10000;
int ymin=10000, ymax=-10000;
for(int i=0; i<n; i++){
if(field[i][0] < xmin) xmin =field[i][0];
if(field[i][0] > xmax) xmax =field[i][0];
if(field[i][1] < ymin) ymin =field[i][1];
if(field[i][1] > ymax) ymax =field[i][1];
}
x = xmax - xmin + 1;
y = ymax - ymin + 1;
cout << x << " "<< y << endl;;
}
return 0;
}
AOJ Volume11 1172: Chebyshev's Theorem
エラトステネスの篩で素数テーブルを作成しておく。
/************************
* 2012/06/30 *
* AOJ Volume11 1172 *
* Chebyshev's Theorem *
* crane *
*************************/
#include<iostream>
#include<cmath>
using namespace std;
#define MAX_N 246913
bool field[MAX_N];
int main(){
field[0] = false;
field[1] = false;
for(int i=2; i<MAX_N; i++) field[i] = true;
for(int i=2; i<sqrt((double)MAX_N)+1; i++)
if(field[i])
for(int j=i*2; j<MAX_N; j+=i)
field[j] = false;
int n = 0;
while(cin >> n, n){
int count = 0;
for(int i=n+1; i<=2*n; i++)
if(field[i])
count++;
cout << count << endl;
}
return 0;
}
/************************
* 2012/06/30 *
* AOJ Volume11 1172 *
* Chebyshev's Theorem *
* crane *
*************************/
#include<iostream>
#include<cmath>
using namespace std;
#define MAX_N 246913
bool field[MAX_N];
int main(){
field[0] = false;
field[1] = false;
for(int i=2; i<MAX_N; i++) field[i] = true;
for(int i=2; i<sqrt((double)MAX_N)+1; i++)
if(field[i])
for(int j=i*2; j<MAX_N; j+=i)
field[j] = false;
int n = 0;
while(cin >> n, n){
int count = 0;
for(int i=n+1; i<=2*n; i++)
if(field[i])
count++;
cout << count << endl;
}
return 0;
}
登録:
投稿 (Atom)