C言語とPC – ページ 3 – プログラミング言語Cやその他で書いたもの。関連するハードウェアやコンテスト等の情報も。

2211月 2019

MacBook Air 11インチ (Late 2010) のOS再インストール

ちょっとしたことで、MacBook Air（以下MBAということにする）のOSを再インストールすることになった。自分にとって、初めての経験だったので、自己メモしておく。２度とやることはないかもしれないが。

ますは機種の確認。購入時期は平成23年1月、CPU Intel Core 2 Duo 1.6GHz、メモリ4GB 1067MHz DDR3（基板への直付けとのことのようで、交換できないらしい）、ストレージ120GB SSD SATA、英語キーボード。ACアダプターは電圧14.5V/3.1A(45W)。機種は MacBook air 11インチ Late 2010 と呼ばれるようだ。

プロキシ接続なしのネット環境下で、MBAを起動し、速やかにキー Shift+Option+Command+Rを、回転する地球儀が表示されるまで押し続ける。

数十分のダウンロードタイムを経て、やっとインストール画面が表示される。内蔵のSSDディスクの内容を消去して、OSをインストールする。OSのバージョンはMAC OSX 10.7 Lion。Apple ID、パスワードを入力したら、他のMACデバイス（自分の場合はiPhone）に6桁の認証コードが表示される。この６桁のコードをもう一度MBAにて、パスワードの後に入力して、Apple IDとパスワードの入力を完了させる（ということで、２回の入力になる。１回目はふつうのパスワード、２回目はパスワード＋６桁認証コード。）

OS Lionのインストールが完了したら、MBAが使えるようになる。そこで、ソフトAppストアを起動し、購入履歴から、OSX Yosemiteにアップデートしていく。失敗談として書いておきたいのは、LionのつぎにいきなりOSX 10.11 El Capitanをアップデートしてみたところ、見事にインストール不可を食らった。数十分のダウンロード＋数十分のインストールの最後にそういう表示が出てしまい、アップル社の技術なさを恨んでしまった。結局、もう一度最初から、Lionの再インストールからやり直した。

そういうことで、Lion → Yosemite → El CapitanとひとつひとつOSをアップデートしていく。所要時間は数時間以上。急ぐ場合にやれることではない。

217月 2018

Python3 最大フローアルゴリズム Dinic’s Max Flow Algorithm

by admin ⋅ Leave a Comment

細かい説明を省略する。Classとメイン関数をみれば、なんとなく使い方についてわかるだろうから。

# *******************************************
# Dinic's Max Flow Algorithm
# *******************************************
class MaxFlow:
    def __init__(self, V):
        self.V = V
        self.level = [0] * V
        self.iter = [0] * V
        self.edge = [[] for i in range(V)]

    def add_edge(self, fr, to, cap):
        f, t = len(self.edge[fr]), len(self.edge[to])
        self.edge[fr].append([to, cap, t])
        self.edge[to].append([fr, cap, f])

    def bfs(self, s):
        self.level = [-1] * self.V
        self.level[s] = 0
        Q = []
        Q.append(s)
        while Q:
            v = Q.pop()
            for to, cap, rev in self.edge[v]:
                if cap > 0 and self.level[to] < 0:
                    self.level[to] = self.level[v] + 1
                    Q.append(to)

    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iter[v], len(self.edge[v])):
            to, cap, rev = self.edge[v][i]
            if cap > 0 and self.level[v] < self.level[to]:
                d = self.dfs(to, t, min(f, cap))
                if d > 0:
                    self.edge[v][i][1] -= d
                    self.edge[to][rev][1] += d
                    return d
            self.iter[v] = i
        return 0

    def maxFlow(self, s, t, INF=10**8):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0: break
            self.iter = [0] * self.V
            while True:
                f = self.dfs(s, t, INF)
                if f <= 0: break
                flow += f
        return flow

N, M = map(int, input().split())
d = MaxFlow(N)
for i in range(M):
	x, y = map(int, input().split())
	d.add_edge(x, y, 1)
source, sink = map(int, input().split())
print(d.maxFlow(source, sink))

# *******************************************

# Dinic's Max Flow Algorithm

# *******************************************

class MaxFlow:

def __init__(self, V):

self.V = V

self.level = [0] * V

self.iter = [0] * V

self.edge = [[] for i in range(V)]

def add_edge(self, fr, to, cap):

f, t = len(self.edge[fr]), len(self.edge[to])

self.edge[fr].append([to, cap, t])

self.edge[to].append([fr, cap, f])

def bfs(self, s):

self.level = [-1] * self.V

self.level[s] = 0

Q = []

Q.append(s)

while Q:

v = Q.pop()

for to, cap, rev in self.edge[v]:

if cap > 0 and self.level[to] < 0:

self.level[to] = self.level[v] + 1

Q.append(to)

def dfs(self, v, t, f):

if v == t: return f

for i in range(self.iter[v], len(self.edge[v])):

to, cap, rev = self.edge[v][i]

if cap > 0 and self.level[v] < self.level[to]:

d = self.dfs(to, t, min(f, cap))

if d > 0:

self.edge[v][i][1] -= d

self.edge[to][rev][1] += d

return d

self.iter[v] = i

return 0

def maxFlow(self, s, t, INF=10**8):

flow = 0

while True:

self.bfs(s)

if self.level[t] < 0: break

self.iter = [0] * self.V

while True:

f = self.dfs(s, t, INF)

if f <= 0: break

flow += f

return flow

N, M = map(int, input().split())

d = MaxFlow(N)

for i in range(M):

x, y = map(int, input().split())

d.add_edge(x, y, 1)

source, sink = map(int, input().split())

print(d.maxFlow(source, sink))

236月 2018

Python3 Union Setの実装

by admin ⋅ Leave a Comment

Python3で書いたはじめてのクラスなので、もっと簡潔な表現ができるかもしれないが、自己メモとして置いておく。

Union Setは２つの要素が同一集合に属するかどうか、効率的に判定できるアルゴリズム。構造が簡単で、競プロではよく見かける。

使い方は簡単。
u = UnionSet(nmax)　　# クラスの生成。nmaxは集合の最大値
u.unite(a, b)　　# 整数 a, b を同一集合にする
u.connected(a, b)　　# 整数 a, b は同一集合に属するかどうかを聞く
u.root(a)　　# 整数 a が属する集合の代表値（ルート値）

以下はコード。AOJ-ALDS1_11_Dに対する解答でもある。

# AOJ ALDS1_11_D Connected Components
# Python3 2018.6.23 bal4u

# UNION-FIND library
class UnionSet:
	def __init__(self, nmax):
		self.size = [1]*nmax
		self.id = [i for i in range(nmax+1)]
	def root(self, i):
		while i != self.id[i]:
			self.id[i] = self.id[self.id[i]]
			i = self.id[i]
		return i
	def connected(self, p, q): return self.root(p) == self.root(q)
	def unite(self, p, q):
		i, j = self.root(p), self.root(q)
		if i == j: return
		if self.size[i] < self.size[j]:
			self.id[i] = j
			self.size[j] += self.size[i]
		else:
			self.id[j] = i
			self.size[i] += self.size[j]
# UNION-FIND library

n, m = map(int, input().split())
u = UnionSet(n)
for i in range(m):
	s, t = map(int, input().split())
	u.unite(s, t)
q = int(input())
for i in range(q):
	s, t = map(int, input().split())
	print("yes" if u.connected(s, t) else "no")

# AOJ ALDS1_11_D Connected Components

# Python3 2018.6.23 bal4u

# UNION-FIND library

class UnionSet:

def __init__(self, nmax):

self.size = [1]*nmax

self.id = [i for i in range(nmax+1)]

def root(self, i):

while i != self.id[i]:

self.id[i] = self.id[self.id[i]]

i = self.id[i]

return i

def connected(self, p, q): return self.root(p) == self.root(q)

def unite(self, p, q):

i, j = self.root(p), self.root(q)

if i == j: return

if self.size[i] < self.size[j]:

self.id[i] = j

self.size[j] += self.size[i]

else:

self.id[j] = i

self.size[i] += self.size[j]

# UNION-FIND library

n, m = map(int, input().split())

u = UnionSet(n)

for i in range(m):

s, t = map(int, input().split())

u.unite(s, t)

q = int(input())

for i in range(q):

s, t = map(int, input().split())

print("yes" if u.connected(s, t) else "no")

226月 2018

Python3 凸包を求める関数を実装する

by admin ⋅ Leave a Comment

凸包を求めるPython3用関数を示す。

座標(x,y) は complex型データのリストで与えられるものとする。Python3では、複素数を扱うためのcomplex型がサポートされていて、以下ではreal部分をx座標、imag部分をy座標としている。

例えば、４点(0,0), (1,0), (1,1), (0,1)の座標に対応して、Python3は以下のようなリスとで表現する

a = [0, 1, 1+1j, 1j]

1	a = [0, 1, 1+1j, 1j]

凸包関数のリターン値として、凸包を構成する座標のリストを反時計回りで得られる。リストの長さは座標数に対応する。

# AOJ 0068 Enclose Pins with a Rubber Band
# Python3 2018.6.22 bal4u

def cross(a, b):
	return a.real*b.imag - a.imag*b.real
	
# 凸包　入力: 座標リスト　リターン:凸包を構成する座標リスト
def convex_hull(p):
	pp = sorted(p, key=lambda x:(x.imag,x.real))  # y座標を優先して昇順、同じならx座標で昇順
	n = len(pp)
	ans, j = [0]*(n+1), 0
	for i in range(n):
		while j > 1 and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) < 0: j -= 1
		ans[j] = pp[i]
		j += 1
	k = j
	for i in range(n-2, -1, -1):
		while j > k and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) < 0: j -= 1
		ans[j] = pp[i]
		j += 1
	return ans[0:j-1]
	
while 1:
	n = int(input())
	if n == 0: break
	p = []
	for i in range(n):
		x, y = list(map(float, input().split(',')))
		p.append(complex(x, y))
	print(n - len(convex_hull(p)))

# AOJ 0068 Enclose Pins with a Rubber Band

# Python3 2018.6.22 bal4u

def cross(a, b):

return a.real*b.imag - a.imag*b.real

# 凸包　入力: 座標リスト　リターン:凸包を構成する座標リスト

def convex_hull(p):

pp = sorted(p, key=lambda x:(x.imag,x.real)) # y座標を優先して昇順、同じならx座標で昇順

n = len(pp)

ans, j = [0]*(n+1), 0

for i in range(n):

while j > 1 and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) < 0: j -= 1

ans[j] = pp[i]

j += 1

k = j

for i in range(n-2, -1, -1):

while j > k and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) < 0: j -= 1

ans[j] = pp[i]

j += 1

return ans[0:j-1]

while 1:

n = int(input())

if n == 0: break

p = []

for i in range(n):

x, y = list(map(float, input().split(',')))

p.append(complex(x, y))

print(n - len(convex_hull(p)))

問題文 AOJ-068 を解くためにC言語プログラムから移植したもの。

216月 2018

Python3 ダイクストラアルゴリズムによる最短距離

by admin ⋅ Leave a Comment

以下の例題では、ノード間に高々１本の有向道路があり、移動コストが道路に与えられている。ノードを a, b とし、有向道路のコストが a から b は c で、b から a は d としている。つまり、隣接リストとしては、to[a] = (b, c)、to[b] = (a, d) になる。

全体のノード数は V で与えられる。スタートノードは start、ゴールとなるノードは goal。

INF = 0x7fffffff
import heapq
def dijkstra(V, to, start, goal):
	dist = [INF]*V
	Q = []
	dist[start] = 0
	heapq.heappush(Q, (0, start))
	while Q:
		t, s = heapq.heappop(Q)
		if s == goal: break
		if dist[s] < t: continue
		for e, cost in to[s]:
			nt = t + cost
			if dist[e] > nt:
				dist[e] = nt
				heapq.heappush(Q, (nt, e))
	return dist[goal]

INF = 0x7fffffff

import heapq

def dijkstra(V, to, start, goal):

dist = [INF]*V

Q = []

dist[start] = 0

heapq.heappush(Q, (0, start))

while Q:

t, s = heapq.heappop(Q)

if s == goal: break

if dist[s] < t: continue

for e, cost in to[s]:

nt = t + cost

if dist[e] > nt:

dist[e] = nt

heapq.heappush(Q, (nt, e))

return dist[goal]

Python3では、プライオリティキュー（minキュー）の使い方は以下のとおり。

#heapq
import heapq                        # heapq のインポート
Q = []                                  # キューの作成
heapq.heappush(Q, (cost, node))     # 要素の追加
cost, node = heapq.heappop(Q)       # 要素の取り出す

#heapq

import heapq # heapq のインポート

Q = [] # キューの作成

heapq.heappush(Q, (cost, node)) # 要素の追加

cost, node = heapq.heappop(Q) # 要素の取り出す

Qでの要素はタプルとして定義する。タプルの最初はキーとなるもの、２番め以降は自由に追加して良さそう。

上記のダイクストラ関数を利用した例は以下に示す。AOJ-117という問題。

n = int(input())+1
to = [[] for i in range(n)]
for i in range(int(input())):
	a, b, c, d = list(map(int, input().split(',')))
	to[a].append((b, c))
	to[b].append((a, d))
s, g, V, P = list(map(int, input().split(',')))
if s == g: print(V-P)
else: print(V-P - dijkstra(n, to, s, g) - dijkstra(n, to, g, s))

n = int(input())+1

to = [[] for i in range(n)]

for i in range(int(input())):

a, b, c, d = list(map(int, input().split(',')))

to[a].append((b, c))

to[b].append((a, d))

s, g, V, P = list(map(int, input().split(',')))

if s == g: print(V-P)

else: print(V-P - dijkstra(n, to, s, g) - dijkstra(n, to, g, s))

ノード番号は1-indexとして入力時に与えられるので、全体のノード数を最初の行で１つ増やしておいた。

206月 2018

Python3 トポロジカルソート

by admin ⋅ Leave a Comment

隣接リストを使って、トポロジカル・ソート（Topological Sort）をPython 3で実装する。

# AOJ 0119: Taro's Obsession
# Python3 2018.6.20

# トポロジーソート V:総ノード数, to[][]:隣接リスト
def topological_sort(V, to):
	cnt = [0]*V
	for i in range(V):
		for j in to[i]: cnt[j] += 1
	Q = []
	for i in range(V):
	   if cnt[i] == 0: Q.append(i)
	while len(Q) > 0:
		i = Q[0]
		del Q[0]
		print(i+1)  # ノードの表示
		for k in to[i]:
			cnt[k] -= 1
			if cnt[k] == 0:	Q.append(k)

m = int(input())
to = [[] for i in range(m)]
n = int(input())
for i in range(n):
	x, y = list(map(int, input().split()))
	to[x-1].append(y-1)
topological_sort(m, to)

# AOJ 0119: Taro's Obsession

# Python3 2018.6.20

# トポロジーソート V:総ノード数, to[][]:隣接リスト

def topological_sort(V, to):

cnt = [0]*V

for i in range(V):

for j in to[i]: cnt[j] += 1

Q = []

for i in range(V):

if cnt[i] == 0: Q.append(i)

while len(Q) > 0:

i = Q[0]

del Q[0]

print(i+1) # ノードの表示

for k in to[i]:

cnt[k] -= 1

if cnt[k] == 0: Q.append(k)

m = int(input())

to = [[] for i in range(m)]

n = int(input())

for i in range(n):

x, y = list(map(int, input().split()))

to[x-1].append(y-1)

topological_sort(m, to)

AOJ問題119に対する解答プログラムでもある。

196月 2018

Python3 で使う正規表現

by admin ⋅ Leave a Comment

C言語では全く使えない正規表現がPython3では大活躍している。

使い方のメモ：

import re
pa = ">'(=+)#(=+)~$"	# A >'======#======~
pb = ">\^(Q=)+~~$"	# B >^Q=Q=Q=Q=Q=Q=Q=Q=Q=~~

for i in range(int(input())):
	s = input()
	r = re.match(pa, s)
	if r and r.group(1) == r.group(2): print('A')
	elif re.match(pb, s): print('B')
	else: print('NA')

import re

pa = ">'(=+)#(=+)~$" # A >'======#======~

pb = ">\^(Q=)+~~$" # B >^Q=Q=Q=Q=Q=Q=Q=Q=Q=~~

for i in range(int(input())):

s = input()

r = re.match(pa, s)

if r and r.group(1) == r.group(2): print('A')

elif re.match(pb, s): print('B')

else: print('NA')

基本的に、まずモジュール re を import することから始まる。

re.match(pattern, text) という使い方で、テキストの先頭からパターンマッチングをしていく。

テキストの途中とマッチングするならば、re.search()を使う。
re.search(pattern, text)

正規表現でマッチングした部分は r.group() で得ることができる。group(0) はマッチングした文字列全体、group(1)は最初の正規表現でマッチングした部分、group(2) は２番めの部分。

上の例題では、「#」の前後にある「=」の数が等しいことが求められるので、group(1) == group(2) という判定条件を利用した。

166月 2018

C言語からPython3への移行

by admin ⋅ Leave a Comment

C言語ならよく分かるが、Python Version 3 をはじめて勉強するひとのために、まとめておく。

自分はまさにそのひとりだからだ。

＜演算子＞
余り切り捨て除算：　//　
　　C言語でいう整数同士の除算「/」。
　　実数同士の除算にも使える。　3.5//2.1 → 1.0　-3.5//2.1 → -2.0
　　しかし、負数の除算ではC言語と違う計算結果によるので、要注意!!! 以下は一例。
　　　（Python3） -5//2 → -3
　　　（C言語）　-5/2 → -2

べき乗：　**
　　C言語ではサポートされず。
　　多倍長整数はPython 3ではサポートされているので、3**1000 とか平気で書ける。
　　平方根なら 2**0.5。C言語のpow()関数は基本的に不要。

インクリメント演算子、デクリメント演算子はない：
　　C言語の ++, -- 演算子はPythonにない。i+=1, i-=1 で代用。

＜データ型＞
文字列 (str)： a, b, c = '', "", str()
リスト (list)：　a, b = [], list()
タプル (tuple)：　a, b = (), tuple()
辞書 (dict)：　a, b = {}, dict()
複素数（complex）： a, b = 2+1j, complex(2,1)
　　上の5例では、変数 a, b, c はどちらも同じデータ型になる。
　　文字列はシングルクォーテーション「'」で囲んでも、ダブルクォーテーション「"」で囲んでも全く同じ。

C言語でいう２次元配列のようなもの：
　　arr = [[0 for c in range(200)] for r in range(100)]
　　arr[99][199] = 1
　　Python 3 では以上のようにリストのリストで代用する。
　　グラフの連結関係を表現するのに必要な空の2次元配列は to = [[] for i in range(MAX)] で宣言する。

リストに対するソート：
　　競プロではユニークな解答出力を得るために、ソート操作が欠かせない。Python3では、以下のようなコートが使える。ただし、相手が数値か文字列かによって、ソート結果が変わるので、データ型に気をつけること。たとえば、文字列"9"と"10"では、昇順が"10", "9"になるが、数値9と10では、昇順が当然9,10になる。

tbl = [[Japan,0,5],[Egypt,1,3],[Canada,2,1],[Spain,3,7]]
for i in sorted(tbl, key=lambda x:(-x[2],x[1])): print(i[0], ',', i[2], sep='')

1 2	tbl = [[Japan,0,5],[Egypt,1,3],[Canada,2,1],[Spain,3,7]] for i in sorted(tbl, key=lambda x:(-x[2],x[1])): print(i[0], ',', i[2], sep='')

表示結果：

Spain,7
Japan,5
Egypt,3
Canada,1

Spain,7

Japan,5

Egypt,3

Canada,1

ソートの基準：チーム名と成績を入力し、成績の良い順(勝ち点の多い順)に並べ替える。勝ち点が同点の場合は入力順に出力すること。

＜リストの内包表現＞
リストを簡潔に、しかも高速に生成する手法のひとつに、内包表現を利用するというものがある。Pythonに慣れないひとにはわかりにくいが。

1. for 文による内包

 a = [i for i in range(1,10)]

1	a = [i for i in range(1,10)]

1から9までの連続した数値のリストが生成される。

2. for と if との組み合わせによる内包
for 繰り返しのなか、特定の要素をピックアップする。

 a = [i for i in range(10) if i & 1]

1	a = [i for i in range(10) if i & 1]

0から9までの連続した数値のうち、奇数だけを抽出してリストをつくる。

3. for と if-else との組み合わせ

 a = [i**2 if i & 1 else i**3 for i in range(10)]

1	a = [i2 if i & 1 else i3 for i in range(10)]

0から9までの連続した数値のうち、奇数は自乗、偶数は３乗のリストをつくる（つまり、[0, 1, 8, 9, 64, 25, 216, 49, 512, 81] がつくられる）。
☆ if-else は for のまえに書かないといけないことに留意

4. 上記の if-else と for との間にネスト的に if-else を入れることができる。自己誇示、自己満足に使えそう！

print(*["fizzbuzz" if i%15==0 else "fizz" if i%3==0 else "buzz" \
if i%5==0 else i for i in range(1,2**100)], sep='\n')

1 2	print(["fizzbuzz" if i%15==0 else "fizz" if i%3==0 else "buzz" \ if i%5==0 else i for i in range(1,2*100)], sep='\n')

C/C++プログラマは驚くしかない。

＜その他＞
複数変数の同時代入（初期化）：　a,b,c,d = 1,2,3,4
　　行数節約のために、変数の初期化は上記の形で書ける。

変数同士のswap操作：　a,b = b,a
　　わかりやすくて便利。

＜小数点の四捨五入＞
以下の例は、実数 ans を小数点2桁に正確に四捨五入する。

from decimal import Decimal, ROUND_HALF_UP
ans = 9876543210.123456
print(Decimal(str(ans).quantize(Decimal('0.01'), rounding=ROUND_HALF_UP))

from decimal import Decimal, ROUND_HALF_UP

ans = 9876543210.123456

print(Decimal(str(ans).quantize(Decimal('0.01'), rounding=ROUND_HALF_UP))

126月 2018

Python3 リストに対する操作

by admin ⋅ Leave a Comment

max()、min()、sorted()等の関数に、keyに違う関数を指定すると、keyで指定した関数で処理される。

a = list(input().split())

# リストの中の一番長いメンバ
print(max(a, key=len))

# リストの中の一番短いメンバ
print(min(a, key=len))

# リストの中の一番頻度の多いメンバ
print(max(a, key=a.count())

# リストを長さの降順で並べる
print(*sorted(a, key=len, reverse=True))

a = list(input().split())

# リストの中の一番長いメンバ

print(max(a, key=len))

# リストの中の一番短いメンバ

print(min(a, key=len))

# リストの中の一番頻度の多いメンバ

print(max(a, key=a.count())

# リストを長さの降順で並べる

print(*sorted(a, key=len, reverse=True))

C言語にはなかったスライス表現、慣れるととても使いやすく、簡潔な書き方が可能になる。つまり、for文を使わなくても、同等な表示が可能だ。

リストのスライス表現 a_list[start:end:step]
a_list = [1,2,3,4,5,6,7,8,9]
print(*a_list[2,-1,2]
#3, 5, 7  # 表示結果

リストのスライス表現 a_list[start:end:step]

a_list = [1,2,3,4,5,6,7,8,9]

print(*a_list[2,-1,2]

#3, 5, 7 # 表示結果

リストaの末尾への追加　a.append(x)　xがaの末尾に追加される

リストaの先頭への挿入　a.insert(0, x)　xがaの先頭に挿入される。ただし、内部ではリストが移動されるので、計算時間はo(N)になるかも。

リストaからの削除　del a[offset]　offsetは位置指定

リストaから取りだし、削除する　a.pop(offset)　offsetは位置指定、省略可（省略した場合はoffset=-1）

096月 2018

Python3 スタックの実装

by admin ⋅ Leave a Comment

Python3 （Python Version 3）用のスタック実装

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

s = Stack()
while True:
    try:
        a = int(input())
        if a > 0:
            s.push(a)
        else:	
            print(s.pop())
    except EOFError:
        break

class Stack:

def __init__(self):

self.items = []

def isEmpty(self):

return self.items == []

def push(self, item):

self.items.append(item)

def pop(self):

return self.items.pop()

def peek(self):

return self.items[len(self.items)-1]

def size(self):

return len(self.items)

s = Stack()

while True:

try:

a = int(input())

if a > 0:

s.push(a)

else:

print(s.pop())

except EOFError:

break

1行に整数1つの入力データはEOFになるまで与えられる。入力データが0以外のときに、データをスタックにpushする。入力データが0のときに、スタックからpopした値を標準出力する。

« 前へ 1 2 3 4 5 … 24 次へ »

Post Navigation