PCK17-1
1-5問目はプログラミングの基礎の
- for文などの繰り返し
- if文などの条件分岐
- 不等式を使った条件式
- 剰余算（割ったあまり）
とか押さえてればおkだよ
ほかに、
- 三項演算子
- 関数
- 配列
とかも理解しておこうね
1:お年玉
平均。奇数は考えなくてOK。かならず確認するように！
C++
#include <iostream>
using namespace std;
int main(){
int a,b;
cin >> a >> b;
cout << (a+b)/2 << endl;
}2:買い物
分岐。ifが使えればとける。
algorithmのmaxはご自由に。
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int a,b,c;
cin >> a >> b >> c;
// 買えない
// a+b = 二人の小遣い合計
if(c>a+b) cout << "NA" << endl;
// 買える
else cout << max(c-a, 0) << endl;
}3:９月Ｘ日
曜日を求める。7日周期だから7でMODをとればいい。このとき0日目(≡7日目)が何曜日か考えると早い(？)
switch文でもいいけど、以下のような配列をつかってもかけるよ。
逆に日付30通り書いてもいいよ。
#include <iostream>
#include <algorithm>
using namespace std;
string days[] = {"thu", "fri", "sat", "sun", "mon", "tue", "wed"};
int main(){
int x;
cin >> x;
cout << days[x%7] << endl;
}4:予約システム
a-bが一つ、s-fがn個あるとするよ。
一個でも被ったら”1”なんだよね？
んで、被る条件。
a≦s and f≦bかな。残念。
(a≦s and f≦b) or (s≦a and b≦f)かな。残念。
慣れてればかけるけど、慣れてないと思い浮かばないよね。
そういう時は、逆を考えてみて。
被らない条件は、a-bがs-fの左か、右か、だよね。
左なら、b≦s
右なら、f≦a
どちらか（or）だから、
f≦a or b≦s
これの逆だから、
not (f≦a or b≦s)
ド・モルガンの法則より
a<f and s<b
これは、あえてイメージするなら、
a-bとs-fが、必ず端っこで引っかかるイメージをするといいかな。二つのホッチキスの芯が。ガチャンて。（わかって）
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n, a, b;
cin >> a >> b >> n;
bool ok = false;
for(int i=0;i<n;i++){
int s,f;
cin >> s >> f;
if(a<f && s<b){
ok = true;
}
}
cout << (ok ? 1 : 0) << endl;
}ok |= trueでもいいよ。
答えが”1”だとわかった瞬間に終了してもいいよ
こんな感じ
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n, a, b;
cin >> a >> b >> n;
for(int i=0;i<n;i++){
int s,f;
cin >> s >> f;
if(a<f && s<b){
cout << 1 << endl;
return 0; // ここで終了
}
}
cout << 0 << endl;
}javaのpublic static void main(String[] args)
とかなら、return;って書けばいいよ。
5:電線
縦の線に乗っかってるのを見ると、x+1個、
横の線に乗っかってるのを見ると、y+1個
左上を二回数えてるから-1
最大公約数(GCD)の数だけ格子点で、二回数えてるから-GCD(x, y)
答えは、x+y+1+GCD(x,y)だね
最適化とかあるし無理にまとめなくてもいいかな。
x,yは小さい（最大で1000）から、
GCDはmin(x,y)からカウントダウンして、
xとyを割り切れたやつを使えば間に合うよ。
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b){
for(int i=max(a,b);i>=2;i--){
if(a%i==0 && b%i==0)
return i;
}
return 1;
}
int main(){
int x,y;
cin >> x >> y;
cout << (x+1) + (y+1) - 1 - gcd(x,y) << endl;
}もっと効率のいいアルゴリズムに、ユークリッドの互除法を用いたものがあるよ。
int gcd(int a, int b){
return b==0 ? a : gcd(b, a%b);
}gcdの中でgcdを呼び出してるね。
これは再帰関数っていうんだけど、
頻出だから、これもありなんだなっての覚えておいてね。
じゃあね。おやすみ。
同校の後輩チームが4問目で苦戦していたようだ
判定式を思い浮かべて、ソースに起こせるように練習しとけ
頑張ってね。
