LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@anonymously115

paizaラーニングレベルアップ問題集の「二重ループメニュー」をやってみた。(5)

Posted at

paizaラーニングレベルアップ問題集の「二重ループメニュー」をやってみました。

問題
スーパー鳩時計

格子点

お金の支払い

三角形の探索

方針
スーパー鳩時計
  • $X=0,1,\dots,23$について
    • $Y=0,1,\dots,59$について
      • $X+Y$が$3$の倍数ならばFIZZを出力します
      • $X+Y$が$5$の倍数ならばBUZZを出力します
      • 改行を出力します
格子点
  • $X=1,2,\dots,98$について
    • $Y=1,2,\dots,99-X$について
      • $X^3+Y^3<100000$ならば
        • $XY$が最大値を超えていれば更新します

(別解)$X\le Y$として一般性を失いません。

  • $X=1,2,\dots,49$について
    • $Y=X,X+1,\dots,99-X$について
      • $X^3+Y^3\ge100000$ならば
        • $Y$のループを抜けます
      • $XY$が最大値を超えていれば
        • 最大値を更新します

この方法では、$X\ge 37$になると$Y$のループをいきなり脱出します。

お金の支払い
  • 最小値を$Z$で初期化します
  • $i=0,1,\dots,\lfloor\frac{Z}{X}\rfloor$について
    • $j=0,1,\dots,\lfloor\frac{Z-iX}{Y}\rfloor$について
      • $k=Z-(iX+jY)$が一円玉の枚数です
      • $i+j+k$が最小値未満ならば、最小値を更新します

二重ループでやらなくとも、各$i$に対して$j=\lfloor\frac{Z-iX}{Y}\rfloor$の時に枚数が最小になります。

三角形の探索

$c\le b\le a$に限定して考えます。この時、長さ$a$の辺が斜辺になります。

  • $c=1,2,\dots,\lfloor\frac{N}{3}\rfloor$について
    • $b=c,c+1,\dots,\lfloor\frac{N-c}{2}\rfloor$について
      • $a=N-(c+b)$です
      • $a^2=b^2+c^2$ならば
        • フラグを立て、ループを抜けます
      • $a^2<b^2+c^2$ならば、ループを抜けても構いません
    • フラグが立っていれば
      • ループを抜けます
C
スーパー鳩時計
#include <stdio.h>

int main() {
	for (int x = 0; x < 24; x++) {
		for (int y = 0; y < 60; y++) {
			int z = x + y;
			printf("%s%s\n", z % 3 ? "" : "FIZZ", z % 5 ? "" : "BUZZ");
		}
	}
	return 0;
}
格子点
#include <stdio.h>

int main() {
	int max = 0;
	int n = 100;
	for (int x = 1; x < 100; x++) {
		int k = n - x;
		for (int y = 1; y < k; y++) {
			if (x * x * x + y * y * y < 100000) {
				int z = x * y;
				if (z > max) max = z;
			}
		}
	}
	printf("%d\n", max);
	return 0;
}
お金の支払い
#include <stdio.h>

int main() {
	int x, y, z;
	scanf("%d %d %d", &x, &y, &z);
	int min = z;
	for (int i = 0; x * i <= z; i++) {
		for (int j = 0; x * i + y * j <= z; j++) {
			int k = z - (x * i + y * j);
			int m = i + j + k;
			if (m < min) min = m;
		}
	}
	printf("%d\n", min);
	return 0;
}
三角形の探索
#include <stdio.h>

int main() {
	int n;
	scanf("%d", &n);
	int f = 0;
	int m = n / 3;
	for (int c = 1; c <= m; c++) {
		int k = (n - c) / 2;
		for (int b = c; b <= k; b++) {
			int a = n - (b + c);
			if (a * a == b * b + c * c) {
				f = 1;
				break;
			}
		}
		if (f) break;
	}
	puts(f ? "YES" : "NO");
	return 0;
}
C++
スーパー鳩時計
#include <iostream>
using namespace std;

int main() {
	for (int x = 0; x < 24; x++) {
		for (int y = 0; y < 60; y++) {
			int z = x + y;
			if (z % 3 == 0) cout << "FIZZ";
			if (z % 5 == 0) cout << "BUZZ";
			cout << endl;
		}
	}
	return 0;
}
格子点
#include <iostream>
using namespace std;

int main() {
	int m = 0;
	int n = 100;
	for (int x = 1; x < n; x++) {
		int k = n - x;
		for (int y = 1; y < k; y++) {
			if (x * x * x + y * y * y <= 100000)
				m = max(m, x * y);
		}
	}
	cout << m << endl;
	return 0;
}
お金の支払い
#include <iostream>
using namespace std;

int main() {
	int x, y, z;
	cin >> x >> y >> z;
	int m = z;
	for (int i = 0; x * i <= z; i++) {
		for (int j = 0; x * i + y * j <= z; j++) {
			int k = z - (x * i + y * j);
			m = min(m, i + j + k);
		}
	}
	cout << m << endl;
	return 0;
}
三角形の探索
#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	bool f = false;
	int m = n / 3;
	for (int c = 1; c <= m; c++) {
		int k = (n - c) / 2;
		for (int b = c; b <= k; b++) {
			int a = n - (c + b);
			if (a * a == b * b + c * c) {
				f = true;
				break;
			}
		}
	}
	cout << (f ? "YES" : "NO") << endl;
	return 0;
}
C#
スーパー鳩時計
using System;

class Program
{
	public static void Main()
	{
		for (int x = 0; x < 24; x++) {
			for (int y = 0; y < 60; y++) {
				int z = x + y;
				if (z % 3 == 0) Console.Write("FIZZ");
				if (z % 5 == 0) Console.Write("BUZZ");
				Console.WriteLine();
			}
		}
	}
}
格子点
using System;

class Program
{
	public static void Main()
	{
		int max = 0;
		int n = 100;
		for (int x = 1; x < n; x++) {
			int k = n - x;
			for (int y = 1; y < k; y++) {
				if (x * x * x + y * y * y < 100000) {
					int z = x * y;
					if (z > max) max = z;
				}
			}
		}
		Console.WriteLine(max);
	}
}
お金の支払い
using System;

class Program
{
	public static void Main()
	{
		int[] xyz = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
		int x = xyz[0], y = xyz[1], z = xyz[2];
		int min = z;
		for (int i = 0; x * i <= z; i++) {
			for (int j = 0; x * i + y * j <= z; j++) {
				int k = z - (x * i + y * j);
				int m = i + j + k;
				if (m < min) min = m;
			}
		}
		Console.WriteLine(min);
	}
}
三角形の探索
using System;

class Program
{
	public static void Main()
	{
		int n = int.Parse(Console.ReadLine());
		bool f = false;
		int m = n / 3;
		for (int c = 1; c <= m; c++) {
			int k = (n - c) / 2;
			for (int b = c; b <= k; b++) {
				int a = n - (c + b);
				if (a * a == b * b + c * c) {
					f = true;
					break;
				}
			}
			if (f) break;
		}
		Console.WriteLine(f ? "YES" : "NO");
	}
}
Go
スーパー鳩時計
package main
import "fmt"

func main() {
	for x := 0; x < 24; x++ {
		for y := 0; y < 60; y++ {
			z := x + y
			if (z % 3 == 0) {
				fmt.Print("FIZZ")
			}
			if (z % 5 == 0) {
				fmt.Print("BUZZ")
			}
			fmt.Println()
		}
	}
}
格子点
package main
import "fmt"

func main() {
	max := 0
	n := 100
	for x := 1; x < n; x++ {
		k := n - x
		for y := 1; y < k; y++ {
			if x * x * x + y * y * y < 100000 {
				z := x * y
				if z > max {
					max = z
				}
			}
		}
	}
	fmt.Println(max)
}
お金の支払い
package main
import "fmt"

func main() {
	var x, y, z int
	fmt.Scan(&x, &y, &z)
	min := z
	for i := 0; x * i <= z; i++ {
		for j := 0; x * i + y * j <= z; j++ {
			k := z - (x * i + y * j)
			m := i + j + k
			if m < min {
				min = m
			}
		}
	}
	fmt.Println(min)
}
三角形の探索
package main
import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	f := false
	m := n / 3
	for c := 1; c <= m; c++ {
		k := (n - c) / 2
		for b := 1; b <= k; b++ {
			a := n - (c + b)
			if a * a == b * b + c * c {
				f = true
				break
			}
		}
		if f {
			break
		}
	}
	if f {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}
Java
スーパー鳩時計
public class Main {
	public static void main(String[] args) {
		for (int x = 0; x < 24; x++) {
			for (int y = 0; y < 60; y++) {
				int z = x + y;
				if (z % 3 == 0) System.out.print("FIZZ");
				if (z % 5 == 0) System.out.print("BUZZ");
				System.out.println();
			}
		}
	}
}
格子点
public class Main {
	public static void main(String[] args) {
		int max = 0;
		int n = 100;
		for (int x = 1; x < n; x++) {
			int k = n - x;
			for (int y = 1; y < k; y++) {
				if (x * x * x + y * y * y < 100000) {
					int z = x * y;
					if (z > max) max = z;
				}
			}
		}
		System.out.println(max);
	}
}
お金の支払い
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		int z = sc.nextInt();
		sc.close();
		int min = z;
		for (int i = 0; x * i <= z; i++) {
			for (int j = 0; x * i + y * j <= z; j++) {
				int k = z - (x * i + y * j);
				int m = i + j + k;
				if (m < min) min = m;
			}
		}
		System.out.println(min);
	}
}
三角形の探索
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		boolean f = false;
		int m = n / 3;
		for (int c = 1; c <= m; c++) {
			int k = (n - c) / 2;
			for (int b = c; b <= k; b++) {
				int a = n - (c + b);
				if (a * a == b * b + c * c) {
					f = true;
					break;
				}
			}
			if (f) break;
		}
		System.out.println(f ? "YES" : "NO");
	}
}
JavaScript
スーパー鳩時計
for (var x = 0; x < 24; x++) {
	for (var y = 0; y < 60; y++) {
		let z = x + y;
		console.log((z % 3 ? "" : "FIZZ") + (z % 5 ? "" : "BUZZ"));
	}
}
格子点
let max = 0;
const n = 100;
for (var x = 1; x < n; x++) {
	let k = n - x;
	for (var y = 1; y < k; y++) {
		if (x ** 3 + y ** 3 < 100000) {
			let z = x * y;
			if (z > max) max = z;
		}
	}
}
console.log(max);
お金の支払い
const [x, y, z] = require("fs").readFileSync("/dev/stdin", "utf8").split(' ').map(Number);
let min = z;
for (var i = 0; x * i <= z; i++) {
	for (var j = 0; x * i + y * j <= z; j++) {
		let k = z - (x * i + y * j);
		let m = i + j + k;
		if (m < min) min = m;
	}
}
console.log(min);
三角形の探索
const n = Number(require("fs").readFileSync("/dev/stdin", "utf8"));
let f = false;
const m = n / 3;
for (var c = 1; c <= m; c++) {
	let k = (n - c) / 2;
	for (var b = 1; b <= k; b++) {
		let a = n - (c + b);
		if (a * a == b * b + c * c) {
			f = true;
			break;
		}
	}
	if (f) break;
}
console.log(f ? "YES" : "NO");
Kotlin
スーパー鳩時計
fun main() {
	for (x in 0 until 24) {
		for (y in 0 until 60) {
			val z = x + y
			if (z % 3 == 0) print("FIZZ")
			if (z % 5 == 0) print("BUZZ")
			println()
		}
	}
}
格子点
fun main() {
	var max = 0
	val n = 100
	for (x in 1 until n) {
		val m = n - x
		for (y in 1 until m) {
			if (x * x * x + y * y * y < 100000) {
				val z = x * y
				if (z > max) max = z
			}
		}
	}
	println(max)
}
お金の支払い
fun main() {
	val (x, y, z) = readLine()!!.split(' ').map { it.toInt() }
	var min = z
	for (i in 0..(z/x)) {
		for (j in 0..((z-x*i)/y)) {
			val k = z - (x * i + y * j)
			val m = i + j + k
			if (m < min) min = m
		}
	}
	println(min)
}
三角形の探索
fun main() {
	val n = readLine()!!.toInt()
	var f = false
	for (c in 1..(n/3)) {
		for (b in 1..((n-c)/2)) {
			val a = n - (c + b)
			if (a * a == b * b + c * c) {
				f = true
				break
			}
		}
		if (f) break
	}
	println(if (f) "YES" else "NO")
}
PHP
スーパー鳩時計
<?php
	for ($x = 0; $x < 24; $x++) {
		for ($y = 0; $y < 60; $y++) {
			$z = $x + $y;
			if ($z % 3 == 0) echo "FIZZ";
			if ($z % 5 == 0) echo "BUZZ";
			echo PHP_EOL;
		}
	}
?>
格子点
<?php
	$max = 0;
	$n = 100;
	for ($x = 1; $x < $n; $x++) {
		$k = $n - $x;
		for ($y = 1; $y < $k; $y++) {
			if ($x ** 3 + $y ** 3 < 100000) {
				$z = $x * $y;
				if ($z > $max) $max = $z;
			}
		}
	}
	echo $max, PHP_EOL;
?>
お金の支払い
<?php
	[$x, $y, $z] = array_map("intval", explode(' ', fgets(STDIN)));
	$min = $z;
	for ($i = 0; $x * $i <= $z; $i++) {
		for ($j = 0; $x * $i + $y * $j <= $z; $j++) {
			$k = $z - ($x * $i + $y * $j);
			$m = $i + $j + $k;
			if ($m < $min) $min = $m;
		}
	}
	echo $min, PHP_EOL;
?>
三角形の探索
<?php
	$n = intval(fgets(STDIN));
	$f = 0;
	$m = $n / 3;
	for ($c = 1; $c <= $m; $c++) {
		$k = ($n - $c) / 2;
		for ($b = $c; $b <= $k; $b++) {
			$a = $n - ($b + $c);
			if ($a * $a == $b * $b + $c * $c) {
				$f = 1;
				break;
			}
		}
		if ($f) break;
	}
	echo $f ? "YES" : "NO", PHP_EOL;
?>
Perl
スーパー鳩時計
for (my $x = 0; $x < 24; $x++) {
	for (my $y = 0; $y < 60; $y++) {
		my $z = $x + $y;
		if ($z % 3 == 0) {
			print "FIZZ";
		}
		if ($z % 5 == 0) {
			print "BUZZ";
		}
		print $/;
	}
}
格子点
my $max = 0;
my $n = 100;
for (my $x = 1; $x < $n; $x++) {
	$k = $n - $x;
	for (my $y = 1; $y < $k; $y++) {
		if ($x ** 3 + $y ** 3 < 100000) {
			my $z = $x * $y;
			if ($z > $max) {
				$max = $z;
			}
		}
	}
}
print "$max$/";
お金の支払い
my ($x, $y, $z) = map { int($_) } split ' ', <STDIN>;
my $min = $z;
for (my $i = 0; $x * $i <= $z; $i++) {
	for (my $j = 0; $x * $i + $y * $j <= $z; $j++) {
		my $k = $z - ($x * $i + $y * $j);
		my $m = $i + $j + $k;
		if ($m < $min) {
			$min = $m;
		}
	}
}
print "$min$/";
三角形の探索
my $n = int(<STDIN>);
my $f = 0;
my $m = $n / 3;
for (my $c = 1; $c <= $m; $c++) {
	my $k = ($n - $c) / 2;
	for (my $b = $c; $b <= $k; $b++) {
		my $a = $n - ($b + $c);
		if ($a * $a == $b * $b + $c * $c) {
			$f = 1;
			last;
		}
	}
}
print $f ? "YES" : "NO", $/;
Python3
スーパー鳩時計
for x in range(24):
	for y in range(60):
		z = x + y
		print(("" if z % 3 else "FIZZ") + ("" if z % 5 else "BUZZ"))
格子点
m = 0
n = 100
for x in range(1, n):
	for y in range(1, n - x):
		if x ** 3 + y ** 3 < 100000:
			m = max(m, x * y)
print(m)
お金の支払い
x, y, z = map(int, input().split())
m = z
for i in range(z // x + 1):
	for j in range((z - x * i) // y + 1):
		k = z - (x * i + y * j)
		m = min(m, i + j + k)
print(m)
三角形の探索
n = int(input())
f = False
for c in range(1, n // 3 + 1):
	for b in range(1, (n - c) // 2 + 1):
		a = n - (c + b)
		if a * a == b * b + c * c:
			f = True
			break
	if f:
		break
print("YES" if f else "NO")
Ruby
スーパー鳩時計
24.times do |x|
	60.times do |y|
		z = x + y
		if z % 3 == 0
			print "FIZZ"
		end
		if z % 5 == 0
			print "BUZZ"
		end
		puts
	end
end
格子点
max = 0
N = 100
(1...N).each do |x|
	(1...(N-x)).each do |y|
		if x ** 3 + y ** 3 < 100000
			z = x * y
			if z > max
				max = z
			end
		end
	end
end
p max
お金の支払い
x, y, z = gets.split.map(&:to_i)
min = z
0.upto(z / x).each do |i|
	0.upto((z - x * i) / y).each do |j|
		k = z - (x * i + y * j)
		m = i + j + k
		if m < min
			min = m
		end
	end
end
p min
三角形の探索
N = gets.to_i
f = false
1.upto(N / 3).each do |c|
	1.upto((N - c) / 2).each do |b|
		a = N - (c + b)
		if a * a == b * b + c * c
			f = true
			break
		end
	end
	if f
		break
	end
end
puts f ? "YES" : "NO"
Scala
スーパー鳩時計
import scala.io.StdIn._

object Main extends App{
	for (x <- 0 until 24) {
		for (y <- 0 until 60) {
			val z = x + y
			if (z % 3 == 0) print("FIZZ")
			if (z % 5 == 0) print("BUZZ")
			println()
		}
	}
}
格子点
import scala.io.StdIn._

object Main extends App{
	var max = 0
	val n = 100
	for (x <- 1 until n) {
		for (y <- 1 until n - x) {
			if (x * x * x + y * y * y < 100000) {
				val z = x * y
				if (z > max) max = z
			}
		}
	}
	println(max)
}
お金の支払い
import scala.io.StdIn._

object Main extends App{
	val Array(x, y, z) = readLine().split(' ').map { _.toInt }
	var min = z
	for (i <- 0 to z / x) {
		for (j <- 0 to (z - x * i) / y) {
			val k = z - (x * i + y * j)
			val m = i + j + k
			if (m < min) min = m
		}
	}
	println(min)
}
三角形の探索
import scala.io.StdIn._

object Main extends App{
	def triangle(n: Int): Boolean = {
		for (c <- 1 to n / 3) {
			for (b <- 1 to (n - c) / 2) {
				val a = n - (b + c)
				if (a * a == b * b + c * c) return true
			}
		}
		false
	}
	println(if (triangle(readInt())) "YES" else "NO")
}
Swift
スーパー鳩時計
for x in 0..<24 {
	for y in 0..<60 {
		let z = x + y
		print((z % 3 == 0 ? "FIZZ" : "") + (z % 5 == 0 ? "BUZZ" : ""))
	}
}
格子点
var m = 0
let N = 100
for x in 1..<N {
	for y in 1..<(N-x) {
		if x * x * x + y * y * y < 100000 {
			m = max(m, x * y)
		}
	}
}
print(m)
お金の支払い
let xyz = readLine()!.split(separator: " ").compactMap { Int($0) }
let (x, y, z) = (xyz[0], xyz[1], xyz[2])
var m = z
for i in 0...(z / x) {
	for j in 0...((z - x * i) / y) {
		let k = z - (x * i + y * j)
		m = min(m, i + j + k)
	}
}
print(m)
三角形の探索
let n = Int(readLine()!)!
var f = false
for c in 1...(n / 3) {
	for b in 1...((n - c) / 2) {
		let a = n - (c + b)
		if a * a == b * b + c * c {
			f = true
			break
		}
	}
	if f {
		break
	}
}
print(f ? "YES" : "NO")

「格子点」の解答

1332

$(X,Y)=(37,36)$の時、$XY$の最大値$1332$となります。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?